Logic Lecture 3 Flashcards
What is Disjunctive Normal Form (DNF)?
A disjunction of conjunctions of literals.
What is a literal in propositional logic?
A propositional variable or its negation.
How is a truth table used to extract a DNF formula?
Identify rows where the formula is true and construct a disjunction of conjunctions from those rows.
Give an example of a DNF formula.
(p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ ¬r).
Is the formula ‘p’ in DNF?
Yes, because it consists of a single literal.
What is an example of a DNF extracted from a truth table?
p ∨ q ≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q).
What is an adequate system of connectives?
A set of logical operators that can express all possible truth tables.
Which connectives form an adequate system?
{¬, ∧, ∨}.
Why is {¬, ∧} an adequate system?
Because disjunction (∨) can be expressed as ¬(¬p ∧ ¬q).
Why is {¬, ∨} an adequate system?
Because conjunction (∧) can be expressed as ¬(¬p ∨ ¬q).
What is the Sheffer stroke (|)?
A single connective (NAND) that forms an adequate system.
What is the meaning of the Sheffer stroke?
φ | ψ ≡ ¬(φ ∧ ψ), meaning ‘not both φ and ψ’.
How can negation (¬) be expressed using only the Sheffer stroke?
¬φ ≡ φ | φ.
How can disjunction (∨) be expressed using only the Sheffer stroke?
φ ∨ ψ ≡ (φ | φ) | (ψ | ψ).
How can conjunction (∧) be expressed using only the Sheffer stroke?
φ ∧ ψ ≡ (φ | ψ) | (φ | ψ).
What is Conjunctive Normal Form (CNF)?
A conjunction of disjunctions of literals.
What is a clause in CNF?
A disjunction of literals.
How can a truth table be used to extract a CNF formula?
Identify rows where the formula is false and construct a conjunction of disjunctions that exclude those cases.
What are the three steps for transforming a formula into CNF?
- Remove implications, 2. Move negations inward, 3. Distribute ∨ over ∧.
How is the tautology test applied to CNFs?
A CNF is a tautology if every clause contains both a literal and its negation.
What is satisfiability?
The problem of determining if there exists an assignment of truth values that makes a formula true.
Why is the satisfiability problem significant?
It is NP-complete and used in AI, cryptography, and theorem proving.
What is a SAT solver?
A tool designed to solve the satisfiability problem efficiently.
How is Sudoku encoded as a satisfiability problem?
Each number placement is represented as a propositional variable with constraints forming a CNF formula.
What are the five Sudoku rules expressed in propositional logic?
- 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.
What is the Davis-Putnam-Logemann-Loveland (DPLL) procedure?
An algorithm used to determine the satisfiability of CNF formulas.
What are the simplification rules in the DPLL procedure?
Eliminate unit clauses, eliminate pure literals, and apply backtracking.
What does the DPLL procedure do if a formula simplifies to ‘true’?
It determines that the formula is satisfiable.
What does the DPLL procedure do if a formula simplifies to ‘false’?
It determines that the formula is unsatisfiable.
