2.7 Propositional Satisfiability
Computational Thinking & Algorithms
Propositional satisfiability is a concept in logic that checks whether a statement can be true. It helps us know if a logical expression has at least one situation where it is true. This concept is widely used in computer science, especially in problem solving and programming. Satisfiability helps us test logical statements and make decisions. It is important for designing algorithms and verifying programs. Understanding satisfiability improves reasoning skills. It also helps in solving complex problems efficiently.
Example
“Bring pizza OR (burger AND do NOT bring soda).”
Result: Bring pizza, no soda = satisfiable expression. Solution exists.
“You must bring pizza AND you must NOT bring pizza.”
Result: No solution exists = unsatisfiable expression.
Conditions for a Proposition to be Satisfiable
A proposition is satisfiable if there is at least one combination of truth values that makes it true. If all possible combinations make it false, it is unsatisfiable. Satisfiability depends on the structure of the expression and the logical connectives used. Logical connectives like AND, OR, and NOT determine whether a statement can be true. Checking all possible cases using a truth table is one way to test satisfiability. A proposition with at least one “true” outcome is satisfiable. This condition helps in reasoning and decision-making.