Onetone Blog

1.3 Propositional Equivalences

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.

1.2 Applications of Propositional Logic

Translating English Sentences • Steps to convert an English sentence to a statement in propositional logic ○ Identify atomic propositions and represent using propositional variables. ○ Determine appropriate logical connectives • Example: “If I go to Harry’s or to the country, I will not go shopping.” ○ p: "I go to Harry’s." ○ q: "I go to the country." ○ r: "I will go shopping." ○ p∨q→¬r • Example: “You can get an extra piece of pie if you have completed your homework or if you are extremely hungry” ○ p: You have completed your homework ○ q: You are extremely hungry ○ r: You can get an extra piece of pie ○ p∨q→r System Specifications • System and Software engineers take requirements in English and express them in a precise specification language based on logic. • Example: “The automated reply cannot be sent when the file system is full” ○ p: “The automated reply can be sent” ○ q: “The file system is full.” ○ q→¬ p Logic Puzzles • An island has two kinds of inhabitants, knights, who always tell the truth, and knaves, who always lie. • You go to the island and meet A and B. ○ A says “B is a knight.” ○ B says “The two of us are of opposite types.” • What are the types of A and B? ○ Let p and q be the statements that A is a knight and B is a knight, respectively. ○ So, then Øp represents the proposition that A is a knave and Øq that B is a knave. ○ If A is a knight, then p is true. Since knights tell the truth, q must also be true. Then (p ∧Øq)∨(Øp∧q) would have to be true, but it is not. So, A is not a knight and therefore Øp must be true. ○ If A is a knave, then B must not be a knight since knaves always lie. So, then both Øp and Øq hold since both are knaves. Logic Circuits • Electronic circuits; each input/output signal can be viewed as a 0 or 1. ○ 0 represents False ○ 1 represents True • Complicated circuits are constructed from three basic circuits called gates. ○ The inverter (NOT gate) takes an input bit and produces the negation of that bit. ○ The OR gate takes two input bits and produces the value equivalent to the disjunction of the two bits. ○ The AND gate takes two input bits and produces the value equivalent to the conjunction of the two bits. • More complicated digital circuits can be constructed by combining these basic circuits to produce the desired output given the input signals by building a circuit for each piece of the output expression and then combining them.

$Proposition 2: The Division Algorithm • Statement ○ Let a,b∈Z, where b 0 ○ Then ∃!q,r∈Z s.t. a=qb+r, and 0≤r b • Proof (Existence) ○ Let S≔{a−bq│q∈Za−bq≥0}⊆Z(≥0) ○ S is not empty § Let q∈Z s.t. q≤a/b § Then bq≤a § ⇒0≤a−bq § i.e. a−bq∈S ○ Thus S contains a unique minumum elemtent: call it r ○ Choose q∈Z s.t. § a−bq=r § ⇒a=bq+r ○ We still need to show 0≤r b § We know 0≤r, since r∈S, so we just need to show r b § If r≥b, then a−b(q+1)=a−bq−b=r−b≥0 § But a−b(q+1)∈S, and it is less than r § This is impossible, since r is minimum element of S § Thus, r b ○ Therefore we ve proven the existence of q and r • Proof (Uniqueness) ○ Suppose ∃q,q^′,r,r^′∈Z s.t. § a=bq+r, where 0≤r b § a=bq^′+r^′, where 0≤r^′ b ○ We must show q=q′ and r=r^′ ○ Suppose r≠r^′ § Without loss of generality, assume r^′ r § Then 0 r^′−r=(a−bq^′ )−(a−bq)=b(q−q^′ ) § Thus, ├ b┤|├ (r^′−r)┤, but 0 r^′−r≤r^′ b. § This is impossible, thus r=r^′ ○ We have bq+r=bq^′+r⇒q=q^′ ○ Therefore we ve proven the uniqueness of q and r • Note we can prove the following stronger statement ○ If a,b∈Z, and b≠0, then ∃!q,r∈Z ○ s.t. a=bq+r, and 0≤r |b| • Proof (Existence) ○ Assume b 0 ○ Choose q,r∈Z s.t. a=(−b)q+r, and 0≤r −b ○ Then a=b(−q)+r, and 0≤r |b| ○ This proves existence • Proof (Uniqueness) ○ Assume b 0 ○ Suppose ∃q,q^′,r,r^′∈Z s.t. § a=bq+r, where 0≤r b § a=bq^′+r^′, where 0≤r^′ b ○ Then § a=(−b)(−q)+r, where 0≤r |b|=−b § a=(−b)(−q′)+r^′, where 0≤r^′ |b|=−b ○ Since −b 0, our previous result implies −q=−q^′ ○ ⇒q=q′ and r=r^′ Greatest Common Divisor • If a,b∈Z, where either a≠0 or b≠0 • A greatest common divisor of a and b is a positive integer d s.t. ○ d|a and d|b ○ If e∈Z s.t. e|a and e|b then e|d • We write the g.c.d. of a and b, if it exists, as (a,b) • As a convention (0,0)≔0 Proposition 3: Uniqueness of Greatest Common Divisor • Statement ○ Let a,b∈Z, where either a≠0 or b≠0 ○ Suppose ∃d,d^′∈Z( 0) s.t. (1) d and d′ both divide a and b (2) If e∈Z s.t. e|a and e|b, then e|d and e|d^′ ○ Then d=d^′ • Proof ○ Combining properties (1) and (2), we have d|d′ and d^′ |d ○ Choose q,q^′∈Z s.t. dq=d′ and d^′ q^′=d ○ By substitution, we get dqq^′=d ○ Then qq^′=1⇒q=q^′=±1 ○ If q=q^′=−1, then d=−d^′ 0. ○ This is impossible since d and d′ are both positive ○ Therefore q=q^′=1 and d=d^′ Proposition 4 • Statement ○ Suppose a,b∈Z, where b≠0 ○ Choose q,r∈Z s.t. a=qb+r, and 0≤r |b| ○ If (b,r) exists, then (a,b) exists and (a,b)=(b,r) • Proof ○ Set d≔(b,r) ○ d|a and d|b § Choose q_1,q_2∈Z s.t. dq_1=b and dq_2=r § Then a=qb+r=qq_1 d+q_2 d=d(qq_1+q_2 ), so d|a § And we already know d|b ○ If e∈Z s.t. e|a and e|b, then e|d § Let e∈Z s.t. e|a and e|b § Choose q_3,q_4∈Z s.t. eq_3=a and eq_4=b § a=qb+r § ⇒a−qb=r § ⇒eq_3−qeq_4=r § ⇒e(q_3−qq_4 )=r § Thus e|r § Since e|b and d=(b,r) § We can conclude that e|d ○ By Proposition 3, (a,b)=(b,r) Proposition 5 • Statement ○ (a,0)=|a|,∀a∈Z • Proof ○ If a=0 § This is true by our convention ○ If a≠0 § Certainly ├ |a|┤|├ a┤, and ├ |a|┤|├ 0┤ § If e∈Z s.t. e|a and ├ e┤|├ 0┤, then ├ e┤|├ |a|┤ § Therefore (a,0)=|a|$

Shawn Zhong

Shawn Zhong

1.3 Propositional Equivalences

1.2 Applications of Propositional Logic

1.1 Propositional Logic

0. Introductory Lecture

Math 541 – 1/29

Search

WeChat Account