Question

(a) Show that the following formula in CNF is unsatisfiable: $$ (p \vee q) \wedge(p \vee \neg q) \wedge(\neg p \vee q) \wedge(\neg p \vee \neg q) $$ (b) Show that the following formula in CNF is unsatisfiable: $$ \begin{array}{c} (p \vee q \vee r) \wedge(p \vee \neg q \vee r) \wedge(\neg p \vee q \vee r) \wedge(\neg p \vee \neg q \vee r) \\ \wedge(p \vee q \vee \neg r) \wedge(p \vee \neg q \vee \neg r) \wedge(\neg p \vee q \vee \neg r) \wedge(\neg p \vee \neg q \vee \neg r) \end{array} $$ Can you find an easier argument than just writing the entire truth table? (c) Generalize the above to some class of CNF formulas on an arbitrary number \(n \geq 1\) of proposition letters, and prove it by induction on \(n\).

Short answer

Both CNF formulas are unsatisfiable; no assignment satisfies all clauses. For generalization, similar CNFs are unsatisfiable for any number of variables by inductive reasoning.

Step-by-step solution

Understanding CNF Formulas

A CNF (Conjunctive Normal Form) formula consists of clauses linked by 'and', where each clause is a disjunction of literals (e.g., variables and their negations). The task is to determine if there's any satisfying assignment (i.e., a way to assign truth values to variables that makes the entire expression true). An unsatisfiable formula has no such assignment.

Simplify Part (a)

For the formula \( (p \vee q) \wedge (p \vee eg q) \wedge (eg p \vee q) \wedge (eg p \vee eg q) \), let's investigate if there’s any assignment that satisfies all clauses simultaneously. Notice each pair of clauses covers all possibilities for \( q \) given \( p \), and vice versa:- \( p \vee q \) and \( p \vee eg q \) both need \( p \) to be true,- \( eg p \vee q \) and \( eg p \vee eg q \) both need \( p \) to be false.Since each set independently demands contradictory values for \( p \), no assignment can satisfy the formula, proving it is unsatisfiable.

Simplify Part (b)

For the formula involving three variables:\[ (p \vee q \vee r) \wedge (p \vee eg q \vee r) \wedge (eg p \vee q \vee r) \wedge (eg p \vee eg q \vee r) \wedge (p \vee q \vee eg r) \wedge (p \vee eg q \vee eg r) \wedge (eg p \vee q \vee eg r) \wedge (eg p \vee eg q \vee eg r) \]Every binary possibility for \( p \) and \( q \) is covered in pairs for both \( r \) and \( eg r \), thus:- Assigning \( r \) true satisfies some clauses while the others require \( eg r \).- Assigning \( r \) false satisfies some clauses while the others require \( r \).There is a symmetry causing each variable to require contradictory values, rendering the formula unsatisfiable.

Generalization by Induction

Consider the CNF formula involving \( n \) variables, each in a clause and its negation also in a clause. Let's use induction:- Base Case (\( n = 1 \)): Two clauses \( (p) \wedge (eg p) \) are unsatisfiable as described above.- Inductive Step: Assume for \( n = k \) variables, a similar CNF is unsatisfiable. Show that adding one more variable, say \( r \), with clauses including both \( r \) and \( eg r \), maintains unsatisfiability by ensuring each additional clause continues to introduce the same contradiction seen in base and inductive scenarios.Conclusively, for any \( n \), a CNF containing both the variable and its negation is unsatisfiable.

Key concepts

Conjunctive Normal Form

In propositional logic, Conjunctive Normal Form (CNF) is a way of structuring logical formulas. It consists of a series of clauses connected by 'and' operations. Each clause itself contains a series of literals (these could be particular variables or their negations) connected by 'or' operators.

CNF is significant because it simplifies the problem of determining the satisfiability of complex logical expressions. To see if a CNF formula is satisfiable means finding if there is an assignment of truth values to its variables that makes the entire logic expression true.

• Clauses: Individual groupings of literals connected by 'or'.
• Conjunction: Clauses combined by 'and', forming the entire CNF expression.
• Literals: Variables or their negations.

The exercise provided examples where determining the unsatisfiability shows there cannot be a truth assignment that satisfies all clauses. Understanding these structures allows breaking down large logical problems into smaller, manageable parts.

Propositional Logic

Propositional logic forms the basis for Conjunctive Normal Form and other logical expressions. It deals with propositions, which are statements that are either true or false, and uses logical connectives like 'and', 'or', and 'not'.

The realm of propositional logic focuses on evaluating the truth of compound statements formed by simpler statements. This is particularly important for constructing logical arguments, automating reasoning, and performing digital circuit design.

• Propositions: Basic statements with a truth value (true or false).
• Logical Connectives: Includes 'and' (\( \wedge \)), 'or' (\( \vee \)), and 'not' (\( eg \)).
• Truth Tables: Tools used to determine the truth value of complex expressions based on the truth of their components.

Understanding propositional logic is fundamental for approaching CNF unsatisfiability problems, as it allows recognition of how individual logical parts fit into larger expressions.

Inductive Proof

Inductive proof is a powerful mathematical method used to demonstrate the truth of an infinite number of cases. It involves two key steps: establishing the base case and proving the inductive step. This technique is applied to problems like generalizing CNF unsatisfiability.

For a general class of CNF formulas with increasing numbers of variables, an inductive proof can show that unsatisfiability holds.

• Base Case: Prove the property for an initial case (e.g., for one variable, where it is easy to demonstrate unsatisfiability).
• Inductive Step: Assume the property holds for \( n = k \). Then prove it for \( n = k + 1 \).
• Generalization: Since both steps are satisfied, the property holds for all examples in the sequence.

By using induction in the generalized CNF context, it becomes clear why no truth assignment can satisfy a CNF formula that includes each variable and its negation as separate clauses.