Propositional Logic PDF

Lec 1: Propositional Logic 2 1 / The Foundations: Logic and Proofs Propositions Our discussion begins with an introduction to the basic building blocks of logic—propositions. A proposition is a declarative sentence (that is,...

Lec 1: Propositional Logic 2 1 / The Foundations: Logic and Proofs Propositions Our discussion begins with an introduction to the basic building blocks of logic—propositions. A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. EXAMPLE 1 All the following declarative sentences are propositions. 1. Washington, D.C., is the capital of the United States of America. 2. Toronto is the capital of Canada. 3. 1 + 1 = 2. 4. 2 + 2 = 3. ▲ Propositions 1 and 3 are true, whereas 2 and 4 are false. Some sentences that are not propositions are given in Example 2. EXAMPLE 2 Consider the following sentences. 1. What time is it? 2. Read this carefully. 3. x + 1 = 2.  Some sentences that are not propositions are given in Example 2. EXAMPLE 2 Consider the following sentences. 1. What time is it? 2. Read this carefully. 3. x + 1 = 2. 4. x + y = z. Sentences 1 and 2 are not propositions because they are not declarative sentences. Sentences 3 and 4 are not propositions because they are neither true nor false. Note that each of sentences 3 and 4 can be turned into a proposition if we assign values to the variables. We will also discuss ▲ other ways to turn sentences such as these into propositions in Section 1.4. We use letters to denote propositional variables (or statement variables), that is, vari- 1.1 Propositional Logic 3 ables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are p, q, r, s,.... The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted (384 ARISTOTLE by F,b.c.e.–322 if it is ab.c.e.) false Aristotle proposition. was born in Stagirus (Stagira) in northern Greece. His father was the personal physician of the King of Macedonia. Because his father died when Aristotle was young, Aristotle The area could not of logicthethat follow deals custom of with propositions following his father’s is called the profession. propositional Aristotle calculus became an orphan or propo- at a young age sitional whenlogic. It was his mother alsofirst died.developed His guardian systematically by the who raised him taught Greekrhetoric, him poetry, philosopher Aristotle and Greek. At the agemore of 17, his guardian sent him to Athens to further his education. Aristotle joined Plato’s Academy, where for 20 than 2300 years ago. years he attended Plato’s lectures, later presenting his own lectures on rhetoric. When Plato died in 347 B.C.E., We now was Aristotle turnnotour attention chosen to succeedto him methods becausefor his producing views differednew propositions too much from those from those of Plato. that Instead, Aristotle joined the court of King Hermeas where he remained for three years, and married the niece of the we already have. These methods were discussed by the English mathematician George Boole King. When the Persians defeated Hermeas, Aristotle moved to Mytilene and, at the invitation of King Philip  combining one or more propositions. New propositions, called compound propositions, are formed from existing propositions using logical operators. DEFINITION 1 Let p be a proposition. The negation of p, denoted by ¬p (also denoted by p), is the statement “It is not the case that p.” The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p, is the opposite of the truth value of p. 4 1 / The Foundations: Logic and Proofs EXAMPLE 3 Find the negation of the proposition Table 1 displays the truth table for the negation of a proposition p. This table has a row TABLE 1 The “Michael’s PC runs Linux” Truth Table for for each of the two possible truth values of a proposition p. Each row shows the truth value of the Negation of a ¬pexpress and this in to corresponding simple English. the truth value of p for this row. Proposition. The The Solution: negation of a proposition negation is can also be considered the result of the operation of the negation operator “It is not on that the case a proposition. Michael’sThePCnegation operator constructs a new proposition from runs Linux.” p ¬p a single existing proposition. We will now introduce the logical operators that are used to form This negation can be more simply expressed as T F new propositions from two or more existing propositions. These logical operators are also called “Michael’s PC does not run Linux.” connectives. ▲ F T EXAMPLE 4 Find the negation of the proposition “Vandana’s smartphone has at least 32GB of memory” DEFINITION 2 Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition and express this in simple English. “p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise. EXAMPLE 3 Find the negation of the proposition EXAMPLE 3 Find the negation of the proposition “Michael’s PC runs Linux” “Michael’s PC runs Linux” and express this in simple English. and express this in simple English. Solution: Solution: TheThe negation negation is is “It “It is not the the is not casecase that Michael’s PC runs that Michael’s PCLinux.” runs Linux.” This negation can be more simply expressed as This negation can be more simply expressed as “Michael’s PC does not run Linux.” ▲ “Michael’s PC does not run Linux.” EXAMPLE 4 Find the negation of the proposition EXAMPLE 4 Find the negation “Vandana’s of the has smartphone proposition at least 32GB of memory” and express this in simple “Vandana’s English. smartphone has at least 32GB of memory” Solution: The negation and express is this in simple English. “It is not the case that Vandana’s smartphone has at least 32GB of memory.” Solution: The negation is This negation can also be expressed as “It is not the case that Vandana’s smartphone has at least 32GB of memory.” “Vandana’s smartphone does not have at least 32GB of memory” or This even negation canasalso be expressed as more simply “Vandana’s “Vandana’s smartphone smartphone does has less not32GB than haveof atmemory.” least 32GB of memory” ▲ or even more simply as Proposition. The negation of a proposition can also be considered the result of the operation of the negation operator on a proposition. The negation operator constructs a new proposition from p ¬p aDEFINITION single existing proposition. 3 LetWe will qnow p and introduce the logical be propositions. operators that The disjunction of are usedq,todenoted p and form by p ∨ q, is the pro T F new propositions from two“p or more or q.”existing propositions. The disjunction p These ∨ q islogical false operators when both arepalso andcalled q are false and is true othe F T connectives. DEFINITION 2 Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise. Table 3 displays the truth table for p ∨ q. DEFINITION 2 Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise. Table 2 displays the truthTABLE table of 2p ∧The This table q. Truth has a row for each Table for of the 3four TABLE possible The Truth Table for combinations Table 2 displays of the truthtruth values the of pof and p ∧q.q.The Conjunction table offour This Tworows correspond to the table has a row for each the of pairs theoffour truthpossible Disjunction values of Two Propositions. Propositions. TT, TF, FT, and combinations FF, where of truth valuestheoffirst p and truth q. value in the The four paircorrespond rows is the truthtovalue of p and the pairs the second of truth values TT, TF, FT, and FF, where thepfirst truth value q in theppair ∧ qis the truth value p of p and the q second p ∨ q truth value is the truth value truth value is the truth value of q. of q. T “but” sometimes T T instead of “and” in T a conjunction. T Notethat Note thatininlogic logicthe theword word “but” sometimes isis used used instead of “and” in a conjunction. For T For example, the statement “The sun T is shining, F but it is raining” F is another wayTof saying F “The sun T example, the statement “The sun is shining, is shining and it is raining.” (InFnatural language,T but it is there is raining” is another way of saying “The F a subtle difference Fin meaningTbetween sun T is shining “and” and it isweraining.” and “but”; will not(InF natural be language, concerned therenuance F with this Fis a subtle here.)differenceFin meaningFbetween F “and” and “but”; we will not be concerned with this nuance here.) EXAMPLE 5 Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s EXAMPLE 5 Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has PC runs faster than 1 GHz.” more thanThe Solution: 16 conjunction GB free hardofdisk space” these and q is pthe∧ proposition propositions, “The processor q, is the proposition in Rebecca’s “Rebecca’s PC has more thanfaster PC runs 16 GBthanfree hard disk space, and the processor in Rebecca’s PC runs faster than 1 1 GHz.” GHz.” This conjunction can be expressed more simply as “Rebecca’s PC has more than 16 GB free hard disk space, and its processor runs faster than 1 GHz.” For this conjunction to be true, Solution: The conjunction of these true. Itpropositions, p ∧oneq,oris both the proposition “Rebecca’s are PC has ▲ both conditions given must be is false, when of these conditions false. more than 16 GB free hard disk space, and the processor in Rebecca’s PC runs faster than 1 propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition isjunction p ∨ q is false when both p and q are false and is true otherwise. DEFINITION 3 Let 6 1 / The Foundations: p and Logic be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition and qProofs “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise. the truth table for p ∨ q. 6 1 / The Foundations: Logic and Proofs TABLE 4 The Truth Table for TABLE 5 The Truth Table for Tablethe Exclusivethe 3 displays Ortruth table for p ∨ q. of Two the Conditional Statement Truth Table for TABLE 3 The Truth Table for Propositions. TABLEp4→The q. Truth Table for TABLE 5 The Truth Ta n of Two the Disjunction of Two the Exclusive Or of Two the Conditional Statemen Propositions. Propositions. p → q. p q p⊕q p q p→q p∧q p TABLE q 2 The p ∨ Truth q Table for pTABLE 3qThe Truth p Table ⊕ q for p q p the Conjunction T Tof Two F the Disjunction T ofTTwo T T T T Propositions. T TPropositions. T F T T F T F T TF T T T F F T F T F F F T p F qT T p ∧ qT F p F T q T pT∨ q T F T F F F F F F F F F T F T F T F T F T F T T T F F T F T F T F F T T F DEFINITION F F 4 F q be propositions. Let p and F F The exclusive or of p and q, denoted by that is true when exactly one of p and q is true and is false otherwi DEFINITION 4 Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q, is the proposition that is true when exactly one of p and q is true and is false otherwise. The truth table for the exclusive or of two propositions is displayed i The truth table for the exclusive orConditional of two propositions isStatements displayed in Table 4.  1.1 Propositional Logic 5 Remark: 1.1 Propositional Logic 5 The use of the connective or in a disjunction corresponds to one of the two ways the word or is The useduse in English, namely, as of the connective oranininclusive or. A a disjunction disjunctiontoisone corresponds trueofwhen at least the two ways one theof the word two propositions or is is true. used in English, For instance, namely, the inclusive as an inclusive or. Aor is being used disjunction in the is true statement when at least one of the two propositions is true. For instance, the inclusive or is being used in the statement “Students who have taken calculus or computer science can take this class.” “Students who have taken calculus or computer science can take this class.” Here, we mean that students who have taken both calculus and computer science can take the Here,as class, we mean well thatstudents as the studentswho whohave havetaken taken only both one calculus of theand twocomputer subjects.science On the can take other the hand, class, we are as wellthe using asexclusive the students who have or when taken only one of the two subjects. On the other hand, we say we are using the exclusive or when we say “Students who have taken calculus or computer science, but not both, can enroll in this “Students who have taken calculus or computer science, but not both, can enroll in this class.” class.” Here, we mean that students who have taken both calculus and a computer science course cannot Here, we mean that students who have taken both calculus and a computer science course cannot take takethe theclass. class.Only Onlythose thosewho whohave havetaken takenexactly exactlyoneoneof ofthe thetwo two courses courses can can take take the the class. class. Similarly, Similarly, when a menu at a restaurant states, “Soup or salad comes with an entrée,” the when a menu at a restaurant states, “Soup or salad comes with an entrée,” the restaurant almost always means that customers can have either soup or salad, restaurant almost always means that customers can have either soup or salad, but not both.but not both. Hence, Hence,this thisisisan anexclusive, exclusive,rather ratherthan thanan aninclusive, inclusive,or. or. AMPLE AMPLE66 What Whatisisthe thedisjunction disjunctionof ofthe thepropositions propositionsppand andqq where wherepp and andqq are are the the same same propositions propositions as as ininExample Example5? 5? Solution:The Solution: Thedisjunction disjunctionof ofppand andq, ∨q, q,pp∨ isthe q,is theproposition proposition “Rebecca’sPC “Rebecca’s PChas hasat atleast least16 16GB GBfree freehard harddisk disk space, space, or or the the processor processor in in Rebecca’s Rebecca’s PC PC runsfaster runs fasterthan than11GHz.” GHz.”  The truth table for the exclusive or of two propositions is displayed in Table 4. The truth table for the exclusive or of two propositions is displayed in Table 4. Conditional Statements Conditional Statements We will discuss several other important ways in which propositions can be combined. We will discuss several other important ways in which propositions can be combined. DEFINITION 5 Let p and q be propositions. The conditional statement p → q is the proposition “if p, then DEFINITION 5 Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.” The conditional statement p → q is false when p is true and q is false, and true otherwise. q.” The conditional statement p → q is false when p is true and q is false, and true otherwise. In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence). and q is called the conclusion (or consequence). Thestatement The statementpp → → qq is iscalled called aa conditional conditional statement statement because because p p→→q q asserts asserts that that qq is istrue true on the condition that p holds. A conditional statement is also called an on the condition that p holds. A conditional statement is also called an implication. implication. Thetruth The truth table table for for the the conditional conditional statement statement p p→→q is shown q is shown in in Table Table 5. 5. Note Note that that the the statement p → q is true when both p and q are true and when p is false (no statement p → q is true when both p and q are true and when p is false (no matter what truthmatter what truth valueqqhas). value has). Becauseconditional Because conditional statements statements play play such such anan essential essential role role in in mathematical mathematical reasoning, reasoning, aa variety of terminology is used to express p → variety of terminology is used to express p → q. You will encounter most if not all q. You will encounter most if not all ofof the the followingways following waysto toexpress express this this conditional conditional statement: statement: “ifp, “if thenq” p,then q” “p implies “p implies q” “if p, “if p, q”q” “p only if q” “p only “pisissufficient “p sufficientfor forq” q” “a sufficient “a sufficient condition for q is is p” p” “q if “q if p”p” “q whenever “q whenever p” “qwhen “q whenp” p” “q is “q is necessary for p” “a “a necessarycondition necessary condition for p is for p is q” q” “q “q follows from p” follows “q unless¬p” “qunless ¬p” AAuseful useful way way to to understand understand the the truth truth value value of a conditional statement statement is is to to think think of of an an obligation or a contract. For example, the pledge obligation or a contract. For example, the pledge many politicians make when running for office when running for office isis “If “IfIIam amelected, elected,then thenII will will lower lower taxes.” taxes.”  “q unless ¬p” and p → q always have the same truth value. paragraph carefully. We illustrate 6the translation 1 / The Foundations: Logic and between conditional Proofsand English statements in Ex- statements ample 7. EXAMPLE 7 Let p be the statement “Maria learns discrete mathematics” and q the statement “Maria will find a good job.” Express the statement p → q asTABLE a statement4 inThe Truth Table for English. TABLE 5 The Truth Table for the Exclusive Or of Two the Conditional Statement Propositions. Solution: From the definition of conditional statements, we see that when p is the statement p → q. “Maria learns discrete mathematics” and q is the statement “Maria will find a good job,” p → q represents the statement p q p⊕q p q p→q “If Maria learns discrete mathematics, then she will T find a good T job.” F T T T T statementFin English. Among There are many other ways to express this conditional T the most T F F natural of these are: F T T F T T F mathematics.” “Maria will find a good job when she learns discrete F F F F T “For Maria to get a good job, it is sufficient for her to learn discrete mathematics.” and “Maria will find a good job unless she does not learn discrete mathematics.” ▲ DEFINITION 4 Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q, is the prop that is true when exactly one of p and q is true and is false otherwise. Note that the way we have defined conditional statements is more general than the meaning attached to such statements in the English language. For instance, the conditional statement in Example 7 and the statement The truth table for the exclusive or of two propositions is displayed in Table 4. “If it is sunny, then we will go to the beach.” are statements used in normal language where there is a relationship between the hypothesis  of a program encounters such a statement, S is executed if p is true, but S is not executed if p is false, as illustrated in Example 8. EXAMPLE 8 What is the value of the variable x after the statement if 2 + 2 = 4 then x := x + 1 if x = 0 before this statement is encountered? (The symbol := stands for assignment. The statement x := x + 1 means the assignment of the value of x + 1 to x.) Solution: Because 2 + 2 = 4 is true, the assignment statement x := x + 1 is executed. Hence, x has the value 0 + 1 = 1 after this statement is encountered. ▲ CONVERSE, CONTRAPOSITIVE, AND INVERSE We can form some new conditional statements starting with a conditional statement p → q. In particular, there are three related conditional statements that occur so often that they have special names. The proposition q → p is called the converse of p → q. The contrapositive of p → q is the proposition ¬q → ¬p. The proposition ¬p → ¬q is called the inverse of p → q. We will see that of these three conditional statements formed from p → q, only the contrapositive always has the same truth 41. Explain, without using a truth table, why (p ∨ q ∨ r) ∧ values to solve Exercises (¬p ∨ ¬q ∨ ¬r) is true when at least one of p, q, and r 45. The truth value of th is true and at least one is false, but is false when all three logic is 1 minus the Exercise: variables have the same truth value. are the truth values o 42. What is the value of x after each of these statements is and “John is not hap encountered in a computer program, if x = 1 before the 46. The truth value of th statement is reached? fuzzy logic is the mi a) if x + 2 = 3 then x := x + 1 propositions. What a b) if (x + 1 = 3) OR (2x + 2 = 3) then x := x + 1 “Fred and John are h c) if (2x + 3 = 5) AND (3x + 4 = 7) then x := x + 1 happy?” d) if (x + 1 = 2) XOR (x + 2 = 3) then x := x + 1 47. The truth value of th e) if x < 2 then x := x + 1 fuzzy logic is the ma 43. Find the bitwise OR, bitwise AND, and bitwise XOR of propositions. What a each of these pairs of bit strings. “Fred is happy, or Jo Soultion: a) 101 1110, 010 0001 or John is not happy b)a. 1111 x=2. 0000, 1010 1010 ∗ 48. Is the assertion “Thi c)b.00 x=1.0111 0001, 10 0100 1000 ∗ 49. The nth statement in d)c. 11 x=2.1111 1111, 00 0000 0000 n of the statements i d. x=1. each of these expressions. 44. Evaluate a) What conclusion e. x=2. a) 1 1000 ∧ (0 1011 ∨ 1 1011) ments? b) (0 1111 ∧ 1 0101) ∨ 0 1000 b) Answer part (a) i c) (0 1010 ⊕ 1 1011) ⊕ 0 1000 the statements in d) (1 1011 ∨ 0 1010) ∧ (1 0001 ∨ 1 1011) c) Answer part (b) Fuzzy logic is used in artificial intelligence. In fuzzy logic, a statements.  Solution: Because“If2the+home 2 =team 4 iswins, true,then theitassignment isoriginal statement x := x + 1 is executed. Hence, raining.”statement. ▲ Only the contrapositive is equivalent to the x has the value 0 + 1 = 1 after this statement is encountered. ▲ The inverse is CONVERSE, “If it is not raining, then theAND CONTRAPOSITIVE, home team does not win.” INVERSE We canpropositions form somethatnew conditional BICONDITIONALS We now introduce another way to combine expresses statements starting Only thewith that two propositions havea the conditional same truthstatement value. p →statement. q. In particular, there are three related ▲ contrapositive is equivalent to the original conditional statements that occur so often that they have special names. The proposition q → p is called the converse of p → q. The contrapositive of p → q is the proposition ¬q → ¬p. The proposition ¬p → ¬q is called the inverse of p → q. We will see that of these three DEFINITION 6 conditional qBICONDITIONALS Let p andstatements be propositions. formed The We now from p introduce → q, only biconditional another theway statement to pcombine contrapositive↔ q propositions is the that hasexpresses proposition always the “p sameif truth and as value only p→ that if q.” two propositions q.The biconditional havestatement the same truth p↔ value. q is true when p and q have the same truth values, andshow We first is falsethatotherwise. Biconditional the contrapositive, ¬qstatements → ¬p, ofare also called bi-implications. a conditional statement p → q always has the same truth value as p → q. To see this, note that the contrapositive is false only when ¬p is false6 andLet DEFINITION ¬qp and is true, q be that is, onlyThe propositions. when p is truestatement biconditional and q isp false.↔ q isWe now show“pthat the proposition if neither Theconverse, the truth tableqand → for pp, only↔ q isThe ifnor q.” shown the inverse, biconditional ¬p in Table 6.→ statement ¬q, Note pthat ↔hasqthe is thestatement true same p↔ when p truth and q isthe value q have true as when→ both p truth same q for all the conditional possible statements truth values values, of p and p and→otherwise. is false q.q Note →p and qthat are true when Biconditional isand true pstatementsis and false qotherwise. are also iscalled That is why conditional false,bi-implications. the original we use the wordsis statement “iffalse, and only but theif” to express and converse this the logical connective inverse are both and why it is symbolically written true. mber that the by combining When twothe symbols → compound and ←. There propositions alwaysare some have other the same common truthways value to we express p ↔ q: call them equiv- positive, but neither nverse or inverse, of alent,“psoisthat a conditional The necessary truthand for pstatement ↔ q for tablesufficient q”and is shown its contrapositive in Table are equivalent. 6. Note that the statement p ↔ q is trueThe converse when both and itional statement is the inverse ofthe “if p then aq,conditional conditional statement statements and conversely” p →are q andalso q →equivalent, p are true andas the reader is false otherwise.can verify, That is why but neither is we use lent to it. equivalent “p iff to thewords q.”the original “if andconditional statement. only if” to express (Weconnective this logical will study and equivalent propositions why it is symbolically written in Sec- tion 1.3.) Take bynote that the combining onesymbols of the→most and ←.common There arelogical some other errors commonis toways assume thatp the to express ↔ q:converse orThe thelast way of inverse of expressing a conditional the statement biconditional statement p is equivalent to↔ uses the abbreviation thisq conditional statement.“iff” for “if and We only “p if.” Note illustrate is necessary the usethat ofp↔ and sufficient q has exactly conditional for q” the same statements intruth Example value 9. as (p → q) ∧ (q → p). “if p then q, and conversely” “p iff q.” TABLE 6 The Truth The last wayTable for the the biconditional statement p ↔ q uses the abbreviation “iff” for of expressing Biconditional ↔only “ifpand q. if.” Note that p ↔ q has exactly the same truth value as (p → q) ∧ (q → p). p q p↔q  The lastpway Then ↔ q of statement the biconditional statement p ↔ q uses the abbreviation expressing is the “if and“You onlycan if.” Note take that p the flight if ↔ and q hasif exactly only the you buy a same truth value as (p → q ) ∧ (q → ticket.” 1 / The Foundations: Logic and Proofs This statement is true if p and q are either both true or both false, that is, if you buy a ticket and can take the flight or if you do not buy a ticket and you cannot take the flight. It is false when EXAMPLE 10 Let p be the statement “You canp take and the flight,”opposite q have and let q be the statement truth values, “You that buy a ticket.” is, when you do not buy a ticket, but you can take the Then p ↔ q is the statementTABLE 6 The Truth Table for the flight (such as when you get a free trip) and when you buy a ticket but you cannot take the flight Biconditional p ↔ q. bumps you). ▲ (such as when the airline “You can take the flight if and only if you buy a ticket.” This statement is true if p and IMPLICIT q arepeither both USEtrueq OF or both pis,↔ BICONDITIONALS false, that q buy a ticket if you You andshould be aware that biconditionals are not can take the flight or if you doalwaysnot buy aexplicit ticket andin you cannot take natural the flight.In language. It is false when the “if and only if” construction used in particular, p and q have opposite truth values, T that is, whenis biconditionals T you do notused rarely buy a in T but you language. ticket, common can take the Instead, biconditionals are often expressed flight (such as when you get a free usingtrip) T and an when “if, you then” F buy or ana ticket “only but you if” F cannot take construction. the flight The other part of the “if and only if” is implicit. ▲ (such as when the airline bumps you). That is, the converse is implied, but not stated. For example, consider the statement in English “If F you finish your T meal, then you F can have dessert.” What is really meant is “You can have IMPLICIT USE OF BICONDITIONALS dessert F if and You only F if be should you finish aware thatTyour meal.” are biconditionals This notlast statement is logically equivalent to the always explicit in natural language.two statements In particular, “If you the “if finish and onlyyour meal, then used if” construction you in can have dessert” and “You can have dessert 10 1 / Thebiconditionals Foundations: Logic and used is rarely Proofsinonly common if you finish language. your biconditionals Instead, meal.” Because are often ofexpressed this imprecision in natural language, we need to using an “if, then” or an “only make an assumption if” construction. The otherwhether part of thea“ifconditional and only if” is statement implicit. in natural language implicitly includes its That is, the converse is implied, converse. Because but not stated. precision For example, is essential consider the statementin mathematics in English and in logic, we will always distinguish “If you finish your meal, thenbetween you can have the dessert.” conditional What statement is really meant p → q and is “You havebiconditional statement p ↔ q. can the EXAMPLEdessert 10 if andLet onlypifbeyou thefinish statement “You can your meal.” Thistake the flight,”is and last statement let q equivalent logically be the statement to the “You buy a ticket.” two statements Truth Then p ↔ q is the statement “If you finish your meal, Tables then you can of have Compound dessert” and “You can Propositions have dessert only if you finish your meal.” Because of this imprecision in natural language, we need to make an assumption whether aWe have now conditional introduced statement in naturalfour important language implicitly logical includesconnectives—conjunctions, its disjunctions, con- converse. Because “You canistake precision the flight ditional essential in if and only statements, mathematics and andif in you buywea ticket.” biconditional logic, statements—as will always distinguish well as negations. We can use these con- between the conditional statement p → qtoand nectives build up complicated the biconditional p ↔ q. propositions involving any number of propositional compound statement This statement is true if p and q are either both true or both variables. We can use truth tables to false, thatthe determine is, truth if youvalues buy a ticket and compound propositions, of these Truth Tables of Compound as Example Propositions 11 illustrates. We use a separate column to find the truth value of each compound can take the flight or if you do expression that notoccurs buy a ticket in the and you cannotproposition compound take the flight. asItitisis false when built up. The truth values of the We have now p and q have opposite introduced four compound important is found truth values, that proposition logical is, when for each connectives—conjunctions, in the finalwell column you do of theWe not buy a ticket, but you can take the combination disjunctions, table. of truth con- values of the propositional variables in it ditional statements, and biconditional statements—as as negations. can use these con- flight nectives to build (such as when up complicated you getpropositions compound a free trip) involving and whenany you buy a of number ticket but you cannot take the flight propositional EXAMPLE 11 tables ▲ variables. We (such can useastruth when Construct the airline to determine thethe bumps truth truthtable you). valuesof the compound of these proposition compound propositions, as Example 11 illustrates. We use a separate column to find the truth value of each compound expression that occurs in the compound (p ∨proposition ¬q ) → (p as ∧ q ). it is built up. The truth values of the IMPLICIT USEtheOF BICONDITIONALS You should be aware that biconditionals are not compound proposition for each combination of truth values of the propositional variables in it is found in the final column ofSolution: table. Because this truth table involves two propositional variables p and q , there are four always explicitrows in natural in this language. truth table, In particular, one for the each “ifofand theonlypairs if”ofconstruction truth values used TT,in TF, FT, and FF. The first EXAMPLE 11 Construct the truth table of thetwo compound columns proposition are used for the truth values of p and q , respectively. In the third column we find biconditionals is rarely used in common language. Instead, biconditionals are often expressed the truth value of ¬q , needed to find the truth value of p ∨ ¬q , found in the fourth column. The (p ∨ ¬q)using → (pan ∧ “if, q). then”fifthorcolumn an “only givesif” construction. the truth The valueotherof part p ∧of q.the “if and the Finally, onlytruth if” is value implicit. of (p ∨ ¬q ) → (p ∧ q ) is ▲ found in the last column. The resulting truth table is shown in Table 7. That is, the converse is implied, but not stated. For example, consider the statement in English Solution: Because this truth table involves two propositional variables p and q, there are four  rows in this truth table, one for each of the pairs of truth values TT, TF, FT, and FF. The first two columns are used for the truth values of p and q, respectively. In the third column we find the truth value of ¬q, needed to find the truth value of p ∨ ¬q, found in the fourth column. The column gives the truth value of p ∧ q. Finally, the truth value of (p ∨ ¬q) → (p ∧ q) is Solution: fifth ▲ found in the last column. The resulting truth table is shown in Table 7. TABLE 7 The Truth Table of (p ∨ ¬ q) → (p ∧ q). p q ¬q p ∨ ¬q p∧q (p ∨ ¬q) → (p ∧ q) T T F T T T T F T T F F F T F F F T F F T T F F Exercise: Construct a truth table for the formula ¬P ∧ (P → Q). Solution: P Q ¬P P→Q ¬P ∧ (P → Q) T T F T F T F F F F F T T T T F F T T T  1.1 Propositional Logic 11 Precedence of Logical Operators We can construct compound propositions using the negation operator and the logical operators TABLE 8 defined so far. We will generally use parentheses to specify the order in which logical operators Precedence of Logical Operators. in a compound proposition are to be applied. For instance, (p ∨ q) ∧ (¬r) is the conjunction of p ∨ q and ¬r. However, to reduce the number of parentheses, we specify that the negation Operator Precedence operator is applied before all other logical operators. This means that ¬p ∧ q is the conjunction of ¬p and q, namely, (¬p) ∧ q, not the negation of the conjunction of p and q, namely ¬(p ∧ q). ¬ 1 Another general rule of precedence is that the conjunction operator takes precedence over ∧ 2 the disjunction operator, so that p ∧ q ∨ r means (p ∧ q) ∨ r rather than p ∧ (q ∨ r). Because ∨ 3 this rule may be difficult to remember, we will continue to use parentheses so that the order of → 4 the disjunction and conjunction operators is clear. ↔ 5 Finally, it is an accepted rule that the conditional and biconditional operators → and ↔ have lower precedence than the conjunction and disjunction operators, ∧ and ∨. Consequently, p ∨ q → r is the same as (p ∨ q) → r. We will use parentheses when the order of the con- ditional operator and biconditional operator is at issue, although the conditional operator has precedence over the biconditional operator. Table 8 displays the precedence levels of the logical operators, ¬, ∧, ∨, →, and ↔.. Discrte Structures 27 26 Example: Find the result of the code p := TRUE ; PROGRAM LOGIC ; q :=VAR FALSE p,q ; , r , s : BOOLEAN ; r :=BEGIN TRUE ; 25 s := p ANDp :=NOT FALSE q OR ; r; q := FALSE ; WRITELN (s) ; r := TRUE ; END. s := p AND q OR r ; WRITELN(s) END. TRUE OR AND NOT Solution: TRUE s:= p AND (NOT q) OR r ; s= = (p AND q) (FALSE ANDOR TRUE) r OR TRUE = (TRUE AND FALSE) OR (TRUE) = FALSE OR TRUE = FALSE OR TRUE == TRUE TRUE OR AND NOT NOT q  VAR p , q , r , s : BOOLEAN ; BEGIN Example: Find the result of the code p := FALSE ; q := FALSE ; PROGRAM LOGIC ;. r := TRUE VAR p , q , r , s : BOOLE AN ; 27 ; Structures Discrte BEGIN s := p AND q OR r ; WRITELN(s) p := TRUEEND;. 26 q := FALSE ; r := TRUE ; s := p AND NOT q OR r ; WRITELN (s) ; END. TRUE TRUE Solution OR AND NOT s = (p AND q) OR r = (TRUE s:= p AND AND (NOT q) OR rFALSE) ; O