w4 - proposition logic

Question 1

Implication truth table

logically equiv to what?

Answer 1

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 2

DNF (Disjunctive Normal Form) meaning

Answer 2

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 3

Conjunctive Normal Form (CNF)

Answer 3

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

connected by ANDs

Question 4

“none or both of”

Answer 4

If and only if

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

Question 5

“no more than one of”

Answer 5

Same as “at most one of”

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

Question 6

At most k are true

Answer 6

• 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 7

At least k are true

Answer 7

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

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

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 8

Distributive law

A or (BC) =???

Answer 8

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

Question 9

Absorption law

A ∨ (A ∧ B) = ??

Answer 9

A∧(A∨B)=A

A∨(A∧B) = A

If A is true → A ∨ (anything) = true = A

If A is false → A ∧ B = false, so A ∨ false = false = A