Logic Lecture 3

Question 1

What is Disjunctive Normal Form (DNF)?

Answer 1

A disjunction of conjunctions of literals.

Question 2

What is a literal in propositional logic?

Answer 2

A propositional variable or its negation.

Question 3

How is a truth table used to extract a DNF formula?

Answer 3

Identify rows where the formula is true and construct a disjunction of conjunctions from those rows.

Question 4

Give an example of a DNF formula.

Answer 4

(p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ ¬r).

Question 5

Is the formula ‘p’ in DNF?

Answer 5

Yes, because it consists of a single literal.

Question 6

What is an example of a DNF extracted from a truth table?

Answer 6

p ∨ q ≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q).

Question 7

What is an adequate system of connectives?

Answer 7

A set of logical operators that can express all possible truth tables.

Question 8

Which connectives form an adequate system?

Answer 8

{¬, ∧, ∨}.

Question 9

Why is {¬, ∧} an adequate system?

Answer 9

Because disjunction (∨) can be expressed as ¬(¬p ∧ ¬q).

Question 10

Why is {¬, ∨} an adequate system?

Answer 10

Because conjunction (∧) can be expressed as ¬(¬p ∨ ¬q).

Question 11

What is the Sheffer stroke (|)?

Answer 11

A single connective (NAND) that forms an adequate system.

Question 12

What is the meaning of the Sheffer stroke?

Answer 12

φ | ψ ≡ ¬(φ ∧ ψ), meaning ‘not both φ and ψ’.

Question 13

How can negation (¬) be expressed using only the Sheffer stroke?

Answer 13

¬φ ≡ φ | φ.

Question 14

How can disjunction (∨) be expressed using only the Sheffer stroke?

Answer 14

φ ∨ ψ ≡ (φ | φ) | (ψ | ψ).

Question 15

How can conjunction (∧) be expressed using only the Sheffer stroke?

Answer 15

φ ∧ ψ ≡ (φ | ψ) | (φ | ψ).

Question 16

What is Conjunctive Normal Form (CNF)?

Answer 16

A conjunction of disjunctions of literals.

Question 17

What is a clause in CNF?

Answer 17

A disjunction of literals.

Question 18

How can a truth table be used to extract a CNF formula?

Answer 18

Identify rows where the formula is false and construct a conjunction of disjunctions that exclude those cases.

Question 19

What are the three steps for transforming a formula into CNF?

Answer 19

1. Remove implications, 2. Move negations inward, 3. Distribute ∨ over ∧.

Question 20

How is the tautology test applied to CNFs?

Answer 20

A CNF is a tautology if every clause contains both a literal and its negation.

Question 21

What is satisfiability?

Answer 21

The problem of determining if there exists an assignment of truth values that makes a formula true.

Question 22

Why is the satisfiability problem significant?

Answer 22

It is NP-complete and used in AI, cryptography, and theorem proving.

Question 23

What is a SAT solver?

Answer 23

A tool designed to solve the satisfiability problem efficiently.

Question 24

How is Sudoku encoded as a satisfiability problem?

Answer 24

Each number placement is represented as a propositional variable with constraints forming a CNF formula.

Question 25

What are the five Sudoku rules expressed in propositional logic?

Answer 25

1. Each cell contains one number, 2. Each row contains each number exactly once, 3. Each column contains each number exactly once, 4. Each 3x3 box contains each number exactly once, 5. The given numbers are fixed.

Question 26

What is the Davis-Putnam-Logemann-Loveland (DPLL) procedure?

Answer 26

An algorithm used to determine the satisfiability of CNF formulas.

Question 27

What are the simplification rules in the DPLL procedure?

Answer 27

Eliminate unit clauses, eliminate pure literals, and apply backtracking.

Question 28

What does the DPLL procedure do if a formula simplifies to 'true'?

Answer 28

It determines that the formula is satisfiable.

Question 29

What does the DPLL procedure do if a formula simplifies to 'false'?

Answer 29

It determines that the formula is unsatisfiable.