Propositional Formulas in CNF - semantics Flashcards
What is the semantic definition of a propositional formula?
A propositional formula is either satisfiable or unsatisfiable based on whether there exists an assignment of variables that makes it true
What is an assignment in propositional logic?
A mapping that gives every variable either the value true (1) or false (0)
How can an assignment be written as a set of literals?
As a set of literals where x is included if ν(x)=1 and ¬x is included if ν(x)=0
For n variables how many possible assignments exist?
2^n possible assignments
What is the value of Top (⊤) under any assignment?
Always true (1) regardless of assignment
What is the value of Bottom (⊥) under any assignment?
Always false (0) regardless of assignment
How is the value of a negation (¬v) calculated?
1 minus the value of v: if v is 1 then ¬v is 0 and vice versa
When is a clause true under an assignment?
A clause is true if at least one of its literals is true under the assignment
What does an empty clause (⊥) evaluate to?
Always false since it contains no literals that could be true
What are the three key properties of disjunction?
Commutative (order doesn’t matter), idempotent (repetition doesn’t matter), and associative (grouping doesn’t matter)
When is a CNF formula true under an assignment?
When all of its clauses are true under that assignment
What does an empty formula (⊤) evaluate to?
Always true since it contains no clauses that could be false
What are the three key properties of conjunction?
Commutative (order doesn’t matter), idempotent (repetition doesn’t matter), and associative (grouping doesn’t matter)
What is a CNF formula’s set representation?
A set of sets of literals where each inner set represents a clause
How do you add a clause C to CNF φ?
Write φ ∪ {C}
How do you remove a clause C from CNF φ?
Write φ∖{C}
What is the SAT problem?
The task of finding a satisfying assignment for a propositional formula (or proving none exists)
When is a formula considered satisfiable?
When there exists at least one assignment under which the formula evaluates to true
When is a formula considered unsatisfiable?
When the formula is false under all possible assignments
What’s the relationship between a clause and its literals?
A clause is true if ANY of its literals are true (disjunction)
What’s the relationship between a CNF formula and its clauses?
A CNF formula is true if ALL of its clauses are true (conjunction)
Why is the empty clause (⊥) always false?
Because it has no literals that could make it true
Why is the empty formula (⊤) always true?
Because it has no clauses that could make it false
How do you calculate the value of a CNF formula given an assignment?
Evaluate each clause (true if any literal is true) then check if all clauses are true
What determines which variables need assignments?
The variables that appear in the formula need assignments
How is a literal evaluated under an assignment?
If it’s a positive literal x its value is ν(x), if it’s a negative literal ¬x its value is 1-ν(x)
