Logic 3

Question 1

Literal (1)

Answer 1

1. Propositional variable or its negation

Question 2

DNF (2)

Answer 2

1. Formula of the type ψ1 ∨ ψ2

2. ψ is made by conjunctions ∧

Question 3

CNF (2)

Answer 3

1. Formula of the type ψ1 ∧ ψ2

2. ψ is made by disjunctions ∨

Question 4

Adequate system (1)

Answer 4

1. Can express al truth tables.

Question 5

Sheffer stroke equivalences (3)

Answer 5

1. ¬ψ = ψ | ψ
2. ψ ∨ φ = ¬ψ | ¬φ = (ψ|ψ) | (φ|φ)
3. ψ ∧ φ = (ψ|φ) | (φ|ψ)

Question 6

CNF Algorithm (3)

Answer 6

1. IMPL-FREE: Eliminate all implications
2. NNF: Move all negations to literals
3. DISTR: Apply distributivity to re-arrange in CNF form

Question 7

DPLL (1)

Answer 7

1. Used to check satisfiability of CNF

Question 8

DPLL Algorithm (3)

Answer 8

1. If there are unit clauses (only one element in brackets) assign value to variable (T if p or F if ¬p)
2. Assign values to pure propositional variables (T if only p appears or F if only ¬p appears)
3. Choose a value for a variable and test for both evaluations of T and F.

Question 9

Extracting DNF from truth table (3)

Answer 9

1. Select rows which evaluate to TRUE
2. For each row which is TRUE compose a formula of conjunctions which evaluates to true
3. Combine all conjunction formulas through disjunctions.

Question 10

Extracting CNF from truth table (3)

Answer 10

1. Select all rows which evaluate to FALSE
2. For each row compose a formula through disjunctions which makes the valuation of that row false.
3. Combine formulas through conjunctions.