Tautologies, Contradictions, and Contingencies • Tautology ○ A tautology is a proposition which is always true. ○ Example: p∨¬p • Contradiction ○ A contradiction is a proposition which is always false. ○ Example: p∧¬p • Contingency ○ A contingency is a proposition which is neither a tautology nor a contradiction ○ Example: p Logically Equivalent • Two compound propositions p and q are logically equivalent if p↔︎q is a tautology. • We write this as p⇔q or as p≡q where p and q are compound propositions. • Two compound propositions p and q are equivalent if and only if the columns in a truth table giving their truth values agree. • Example p q ¬p ¬p∨q p→q T T F T T T F F F F F T T T T F F T T T De Morgan’s Laws • ¬(p∧q)≡¬p∨¬q • ¬(p∨q)≡¬p∧¬q • Truth Table p q ¬p ¬q p∨q ¬(p∨q) ¬p∧¬q T T F F T F F T F F T T F F F T T F T F F F F T T F T T Key Logical Equivalences • Identity Laws ○ p∧T≡p ○ p∨F≡p • Domination Laws ○ p∨T≡T ○ p∧F≡F • Idempotent Laws ○ p∨p≡p ○ p∧p≡p • Double Negation Law ○ ¬(¬p)≡p • Negation Laws ○ p∨¬p≡T ○ p∧¬p≡F • Commutative Laws ○ p∧q≡q∧p ○ p∨q=q∨p • Associative Laws ○ (p∨q)∨r=p∨(q∨r) ○ (p∧q)∧r=p∧(q∧r) • Distributive Laws ○ p∨(q∧r)≡(p∨q)∧(p∨r) ○ p∧(q∨r)≡(p∧q)∨(p∧r) • Absorption Laws ○ p∨(p∧q)≡p ○ p∧(p∨q)≡p • Logical Equivalences Involving Conditional Statements ○ p→q≡¬p∨q ○ p→q≡¬q→¬p ○ p∨q≡¬p→q ○ p∧q≡¬(p→¬q) ○ ¬(p→q)≡p∧¬q ○ (p→q)∧(p→r)≡p→(q∧r) ○ (p→r)∧(q→r)≡(p∨q)→r ○ (p→q)∨(p→r)≡p→(q∨r) ○ (p→r)∨(q→r)≡(p∧q)→r • Logical Equivalences Involving Biconditional Statements ○ p⟷q≡(p→q)∧(q→p) ○ p⟷q≡¬p⟷¬q ○ p⟷q≡(p∧q)∨(¬p∧¬q) ○ ¬(p⟷q)≡p⟷¬q Constructing New Logical Equivalences • We can show that two expressions are logically equivalent by developing a series of logically equivalent statements. • To prove that A≡B we produce a series of equivalences beginning with A and ending with B. ○ A≡A_1≡A_2≡…≡A_n≡B • Keep in mind that whenever a proposition (represented by a propositional variable) occurs in the equivalences listed earlier, it may be replaced by an arbitrarily complex compound proposition. Propositional Satisfiability • A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true. • When no such assignments exist, the compound proposition is unsatisfiable. • A compound proposition is unsatisfiable if and only if its negation is a tautology. Questions on Propositional Satisfiability • (p∨¬q)∧(q∨¬r)∧(r∨¬p) ○ p∨¬q=T⇒set p=T ○ q∨¬r=T⇒set q=T ○ r∨¬p=T⇒set r=T ○ One solution: p=q=r=T • (p∨¬q)∧(q∨¬r)∧(r∨¬p)∧(p∨q∨r)∧(¬p∨¬q∨¬r) ○ Not satisfiable. ○ Check each possible assignment of truth values to the propositional variables and none will make the proposition true. Notation • ⋁24_(j=1)^n▒p_j ≡p_1∨p_2∨…∨p_n • ⋀24_(j=1)^n▒p_j ≡p_1∧p_2∧…∧p_n Sudoku • A Sudoku puzzle is represented by a 9×9 grid made up of nine 3×3 subgrids, known as blocks. • Some of the 81 cells of the puzzle are assigned one of the numbers 1,2, …, 9. • The puzzle is solved by assigning numbers to each blank cell so that every row, column and block contains each of the nine possible numbers. • Example • Encoding as a Satisfiability Problem ○ Let p(i,j,n) denote the proposition that is true when the number n is in the cell in the ith row and the jth column. ○ There are 9×9×9 = 729 such propositions. ○ In the sample puzzle p(5,1,6) is true, but p(5,j,6) is false for j = 2,3,…, 9 ○ For each cell with a given value, assert p(i,j,n), when the cell in row i and column j has the given value. ○ Assert that every row contains every number. § ⋀24_(i=1)9▒⋀24_(n=1)9▒⋁24_(j=1)^9▒p(i,j,n) ○ Assert that every column contains every number. § ⋀24_(j=1)9▒⋀24_(n=1)9▒⋁24_(i=1)^9▒p(i,j,n) ○ Assert that each of the 3×3 blocks contain every number. § ⋀24_(r=0)2▒⋀24_(s=0)2▒⋀24_(n=1)9▒⋀24_(i=1)3▒⋁24_(j=1)^3▒p(3r+i,3s+j,n) ○ Assert that no cell contains more than one number. Take the conjunction over all values of n, n’, i, and j, where each variable ranges from 1 to 9 and n≠n′ of § p(i,j,n)→¬p(i,j,n′) • Solving Satisfiability Problems ○ To solve a Sudoku puzzle, we need to find an assignment of truth values to the 729 variables of the form p(i,j,n) that makes the conjunction of the assertions true. ○ Those variables that are assigned to yield a solution to the puzzle. ○ A truth table can always be used to determine the satisfiability of a compound proposition. ○ But this is too complex even for modern computers for large problems. ○ There has been much work on developing efficient methods for solving satisfiability problems as many practical problems can be translated into satisfiability problems.
