Logic

Question 1

commutativity

Answer 1

φ ∧ ψ ≡ ψ ∧ φ
φ ∨ ψ ≡ ψ ∨ φ

Question 2

idempotence

Answer 2

φ ∧ φ ≡ φ
φ ∨ φ ≡ φ

Question 3

associativity

Answer 3

(φ ∧ ψ) ∧ χ ≡ φ ∧ (ψ ∧ χ)
(φ ∨ ψ) ∨ χ ≡ φ ∨ (ψ ∨ χ)

Question 4

De Morgan

Answer 4

¬(φ ∧ ψ) ≡ ¬φ ∨ ¬ψ
¬(φ ∨ ψ) ≡ ¬φ ∧ ¬ψ

Question 5

involution

Answer 5

¬¬φ ≡ φ
φ → ψ ≡ ¬φ ∨ ψ

Question 6

distributivity

Answer 6

(φ ∧ ψ) ∨ χ ≡ (φ ∨ χ) ∧ (ψ ∨ χ)

Question 7

sheffer stroke

Answer 7

φ | ψ ≡ ¬(φ ∧ ψ)
φ | φ ≡ ¬φ
φ ∨ ψ ≡ (φ | φ) | (ψ | ψ)

Question 8

φ ∧ ψ

Answer 8

¬¬(φ ∧ ψ)

Question 9

CNF1:

Answer 9

IMPL-FREE: φ → ψ ≡ ¬φ ∨ ψ

Question 10

CNF2:

Answer 10

NNF: ¬(φ ∧ ψ) ≡ ¬φ ∨ ¬ψ
¬(φ ∨ ψ) ≡ ¬φ ∧ ¬ψ
¬¬φ ≡ φ

Question 11

CNF3:

Answer 11

DISTR: (φ ∧ ψ) ∨ χ ≡ (φ ∨ χ) ∧ (ψ ∨ χ)
χ ∨ (φ ∧ ψ) ≡ (χ ∨ φ) ∧ (χ ∨ ψ)

Question 12

CNF from truth table

Answer 12

look at false formulas and negate the literals (…v…) ^ (…v…)

Question 13

DNF from truth table

Answer 13

look at true formulas and write down literals (… ^ …) v (…^…)

Question 14

DPLL

Answer 14

assume a literal is true or false, look for pure literals and unit clauses first then repeat till satisfiable or not satisfiable