w4 - proposition logic

Question 1

proposition meaning

Answer 1

A proposition is a statement which is either true or false.

1+1=2 - a proposition that is true

It will rain tommorow - a proposition

This statement is false - not a proposition

Question 2

Implication truth table

logically equiv to what?

Answer 2

P Q | P => Q
F F | T
F T | T
T F | F
T T | T

¬(P)∨Q

Think of a domino with p —- q.
If p falls, then q must fall (so if p=1, q must =1)
If q falls, p does not need to fall for this to be true

Question 3

none or both of (equivalance)

Answer 3

“if and only if”

P Q | P <=> Q
F F | T
F T | F
T F | F
T T | T

P⇔Q = (P⇒Q)∧(Q⇒P)

Question 4

tautology meaning

Answer 4

If a statement is a tautology, the right-hand column of its truth table has every entry True.

Question 5

DNF (Disjunctive Normal Form) meaning

Answer 5

A Boolean expression is in Disjunctive Normal Form (DNF) if
* it is written as a disjunction of some number of parts, where
* each part is a conjunction of some number of literals

‘sum to product’ - each ‘and’ (conjunction) is connected by an or ‘disju

DNF is computational expensive (with k variables, there is 2^k rows in the truth table)

Question 6

Conjunctive Normal Form (CNF)

Answer 6

A Boolean expression is in Conjunctive Normal Form (CNF) if
* it is written as a conjunction of some number of parts (sometimes called clauses), where
* each part is a disjunction of some number of literals.
* Called Clause

product to sum

Question 7

convert DNF to CNF

Answer 7

Apply demorgan’s law twice

once to the overall not(P) and once to the individual clauses

Question 8

“At least one of… must be true”

Answer 8

Combine them with OR

At least one of A, B, C, D
A∨B∨C∨D

Question 9

” only if”

Answer 9

Implication

A only if B
A⇒B
¬A ∨B

Question 10

“none or both of”

Answer 10

If and only if

None, or both, of A and B
A⇔B
(A⇒B)∧( B⇒A)
(¬A ∨B)∧(A ∨¬B)

Question 11

“no more than one of”

Answer 11

• Think of, can’t have any pairs in the set
• Disallowing all possible pairs

no more than one of A, B, C
¬(A∧B)∧¬(A∧C)∧¬(D∧C)
(¬A∨¬B)∧(¬A∨¬C)∧¬(¬D∨¬C)

Question 12

At most k are true

Answer 12

• For every set of k+1 variables, at least one is false
• Forbid any conjunction of k+1 variables to be true
• Requires n choose k+1 clauses

Given J, M, K

At most one of:
(¬J ∨¬M)∧ (¬J∨¬K)∧(¬M∨¬K)

At most two of:
¬J∨¬M∨¬K

At most three of
Always 

write out n choose (k+1) clauses (which is conected by an and).
Then negate each literal

Question 13

At least k are true

Answer 13

For eery set of n−k+1 at least one is true

Given J, M, K

At least one of:
J∨M∨K

At least two of:
(J ∨M)∧ (J∨K) ∧(M∨K)

At least three of:
J∧M∧K

write out n choose (n-k+1) clauses, which is connected by an ‘and’

Question 14

Distributive law

A or (BC) =???

Answer 14

A or (BC)
(A or B) and (A and C)

Question 15

Absorption law

Answer 15

A(A+B)=A

A+AB = A