1.1 Propositional Logic 5 The use of th or in a disiunction ands to ane of the tu or is used in English,namely,as an inclusive or.A disjunction is true 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." Here we mean that students who have taken both calculus and co we are using the exclusive or when we say "Students who have taken calculus or computer science.but not both,can enroll in this class" Here we m take the class.Only those who have taken exactly one of the two courses can take the class. Similarly.when a menu at a restaurant states,"Soup or salad comes with an entree,"the restaurant almost always means that customers can have either soup or salad,but not both. Hence.this is an exclusive.rather than an inclusive.or. EXAMPLE 6 What is the disjunction of the ions and where pand are the same propositions as in Example 5? a Solution:The disjunction of p and q.pvq.is the proposition "Rebecca's PC free hard disk space.or the proces Rebeca'sPC runs faster than 1 gHz This p e when Rah 's DC h east 16 GB free hard disk s than th ssor rns faste than 1 GHz.and w are true It is false when both of these conditions are false,that is,when Rebecca's PC has less than 16 GB free hard disk space and the processor in her PC runs at 1 GHz or slower. ked.the or in a disj disiunction is true when at least one of the two pr ositions in it is true.Sometimes,we useor in an exclusive sense.When the exclusive or is used to connect the propositions p and g.the abebo e the and This proposition is true when p is true and is are true upportinghis family.Nevertheless.he becam ant math ns of the 180 ol of his aio for teaching mather unsati of is day nge oR空asoa装a收 Boole made dis ooehed The MathematicnaysisofLothe first of hisconributionsto symboliclogic Cork. Laws of Though and on tions that w he contracted as a result of keeping a lecture engagement even though he was soaking wet from a rainstorm
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 used in English, namely, as an inclusive or. A disjunction is true 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.” Here, we mean that students who have taken both calculus and computer science can take the class, as well as the students who have taken only one of the two subjects. On the other hand, we are using the exclusive or when we say “Students who have taken calculus or computer science, but not both, can enroll in this class.” Here, we mean that students who have taken both calculus and a computer science course cannot take the class. Only those who have taken exactly one of the two courses can take the class. Similarly, 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, but not both. Hence, this is an exclusive, rather than an inclusive, or. EXAMPLE 6 What is the disjunction of the propositions p and q where p and q are the same propositions as in Example 5? Solution: The disjunction of p and q, p ∨ q, is the proposition “Rebecca’s PC has at least 16 GB free hard disk space, or the processor in Rebecca’s PC runs faster than 1 GHz.” This proposition is true when Rebecca’s PC has at least 16 GB free hard disk space, when the PC’s processor runs faster than 1 GHz, and when both conditions are true. It is false when both of these conditions are false, that is, when Rebecca’s PC has less than 16 GB free hard disk space and the processor in her PC runs at 1 GHz or slower. ▲ As was previously remarked, the use of the connective or in a disjunction corresponds to one of the two ways the word or is used in English, namely, in an inclusive way. Thus, a disjunction is true when at least one of the two propositions in it is true. Sometimes, we use or in an exclusive sense. When the exclusive or is used to connect the propositions p and q, the proposition “p or q (but not both)” is obtained. This proposition is true when p is true and q is false, and when p is false and q is true. It is false when both p and q are false and when both are true. GEORGE BOOLE (1815–1864) George Boole, the son of a cobbler, was born in Lincoln, England, in November 1815. Because of his family’s difficult financial situation, Boole struggled to educate himself while supporting his family. Nevertheless, he became one of the most important mathematicians of the 1800s.Although he considered a career as a clergyman, he decided instead to go into teaching, and soon afterward opened a school of his own. In his preparation for teaching mathematics, Boole—unsatisfied with textbooks of his day— decided to read the works of the great mathematicians. While reading papers of the great French mathematician Lagrange, Boole made discoveries in the calculus of variations, the branch of analysis dealing with finding curves and surfaces by optimizing certain parameters. In 1848 Boole publishedThe Mathematical Analysis of Logic, the first of his contributions to symbolic logic. In 1849 he was appointed professor of mathematics at Queen’s College in Cork, Ireland. In 1854 he published The Laws of Thought, his most famous work. In this book, Boole introduced what is now called Boolean algebra in his honor. Boole wrote textbooks on differential equations and on difference equations that were used in Great Britain until the end of the nineteenth century. Boole married in 1855; his wife was the niece of the professor of Greek at Queen’s College. In 1864 Boole died from pneumonia, which he contracted as a result of keeping a lecture engagement even though he was soaking wet from a rainstorm
61/The Foundations:Logic and Proofs 246km TABLE5 The Truth Table for l Statemen p→9 p→q T T F F F T Let pand be propositions.The exclusiveorofp and q.denoted by pq.is the proposition that is true when exactly one of p and g is true and is false otherwise. The truth table for the exclusive or of two propositions is displayed in Table 4. Conditional Statements We will discuss several other important ways in which propositions can be combined. DEFINITION5 Let p and be propositions.The conditional statement p is the proposition"if p.then In the le co dhcse e.and tue omery antecedent or pre uence) The statement a is called a conditional state Assessment asserts that is true on the condition that p holds.A conditional statement is also called an in licat The truth table for the conditional statement pg is shown in Table 5.Note that the statement pis true when both p and are true and when p is false(no matter what truth value g has). use conditional statements play such an essential att of term wing ways to express t if not p.then g "a sufficient condition for is p" “aifn "g whenever p" g when p" 'g is necessary for p "a necessary condition for p is q" "g follows from p g unlessp A useful way to understand the truth value of a conditional when running for ofnce "If I am elected,then I will lower taxes
6 1 / The Foundations: Logic and Proofs TABLE 4 The Truth Table for the Exclusive Or of Two Propositions. p q p ⊕ q T T F T F T F T T F F F TABLE 5 The Truth Table for the Conditional Statement p → q. p q p → q T T T T F F F T T F F T 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 in Table 4. Conditional Statements 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 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) and q is called the conclusion (or consequence). The statement p → q is called a conditional statement because p → q asserts that q is true on the condition that p holds. A conditional statement is also called an implication. The truth table for the conditional statement p → q is shown in Table 5. Note that the statement p → q is true when both p and q are true and when p is false (no matter what truth value q has). Because conditional statements play such an essential role in mathematical reasoning, a variety of terminology is used to express p → q. You will encounter most if not all of the following ways to express this conditional statement: “if p, then q” “p implies q” “if p, q” “p only if q” “p is sufficient for q” “a sufficient condition for q is p” “q if p” “q whenever p” “q when p” “q is necessary for p” “a necessary condition for p is q” “q follows from p” “q unless ¬p” A useful way to understand the truth value of a conditional statement is to think of an obligation or a contract. For example, the pledge many politicians make when running for office is “If I am elected, then I will lower taxes
1.1 Propositional Logic 7 taxes,although the person may have sufficient influence to cause those in power to lower taxes It is only when the politician is elected but does not lower taxes that voters can say that the politician has broken the campaign pledge.This last scenario corresponds to the case when p is tru "If you get 100%on the final,then you will get anA." If you manage to get a 100%on the final,then you would expect to receive an A.If you do not get 100%you may or may not receive an A depending on other factors.However,if you do get 100% ous ways to e o th he rc n this o rem ember tha nresses the same thing as "if n then a" e that "nonl if "says that p cannot be true when is not true.That is,the statement is false if p is true but q is false.When p is false,q may be either true or false,because the statement says nothing about the truth value of q.Be ca erul not t o use ause this is inco 1o se You might h ember that es the same conditional statement as "if p the ”moans th2tif th st he tru That is the statom ed in e that"g unle 7 unlessp"is false when p is true but g is false,but it is true otherwise.Consequently. “unless一p"andp→g always have the same truth value. We illustrate the translation between conditional statements and English statements in Ex- ample 7. be th ment a learns discrete a statement"Maria will the statement g as a stateme sh Solution:From the definition of conditional sta e that when p is the statement "Maria learns discrete mathematics"and g is the statement"Maria will find a good job."p represents the statement "If Maria learns discrete mathematics,then she will find a good job. "Maria will find a good job when she learns discrete mathematics." "For Maria to get a good job.it is sufficient for her to leam discrete mathematics." and "Maria will find a good job unless she does not learn discrete mathematics." 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 "If it is sunny.then we will go to the beach. are statements used in no mal lang oen the hy mathematics,but she does not get a good job,and the second is true unless it is indeed sunny. but we do not go to the beach.On the other hand,the statement
1.1 Propositional Logic 7 If the politician is elected, voters would expect this politician to lower taxes. Furthermore, if the politician is not elected, then voters will not have any expectation that this person will lower taxes, although the person may have sufficient influence to cause those in power to lower taxes. It is only when the politician is elected but does not lower taxes that voters can say that the politician has broken the campaign pledge. This last scenario corresponds to the case when p is true but q is false in p → q. Similarly, consider a statement that a professor might make: “If you get 100% on the final, then you will get an A.” If you manage to get a 100% on the final, then you would expect to receive an A. If you do not get 100% you may or may not receive an A depending on other factors. However, if you do get 100%, but the professor does not give you an A, you will feel cheated. Of the various ways to express the conditional statement p → q, the two that seem to cause the most confusion are “p only if q” and “q unless ¬p.” Consequently, we will provide some guidance for clearing up this confusion. To remember that “p only if q” expresses the same thing as “if p, then q,” note that “p only if q” says that p cannot be true when q is not true. That is, the statement is false if p is true, but q is false. When p is false, q may be either true or false, because the statement says nothing about the truth value of q. Be careful not to use “q only if p” to express p → q because this is incorrect. To see this, note that the true values of “q only if p” and p → q are different when p and q have different truth values. You might have trouble understanding how “unless” is used in conditional statements unless you read this paragraph carefully. To remember that “q unless ¬p” expresses the same conditional statement as “if p, then q,” note that “q unless ¬p” means that if ¬p is false, then q must be true. That is, the statement “q unless ¬p” is false when p is true but q is false, but it is true otherwise. Consequently, “q unless ¬p” and p → q always have the same truth value. We illustrate the translation between conditional statements and English statements in Example 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 as a statement in English. Solution: From the definition of conditional statements, we see that when p is the statement “Maria learns discrete mathematics” and q is the statement “Maria will find a good job,” p → q represents the statement “If Maria learns discrete mathematics, then she will find a good job.” There are many other ways to express this conditional statement in English. Among the most natural of these are: “Maria will find a good job when she learns discrete mathematics.” “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.” ▲ 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 “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 and the conclusion. Further, the first of these statements is true unless Maria learns discrete mathematics, but she does not get a good job, and the second is true unless it is indeed sunny, but we do not go to the beach. On the other hand, the statement
8 1/The Foundations:Logic and Proofs "If Juan has a smartphone,then 2+3=5" thes )Thent.bec ent "If Juan has a smartphone,then 2+3=6" is true if luan does not hay a smartphone,even though 2+3=6 is false.We would not use thene e he yothethe n m e these last two conditional statements in natural langu (ex ematical reasoning,we consider conditional statements of a more general sort than we use in The mathematical concept of a conditional statement i independent of a cause-and 6 wee nypo on.Our de on E arallel F e to makeit The if-then construction used in many mming lang es is different from that used in logic.Most programming languages contain statements such as if p then S.where p is a proposition and S is a program segment (one or more statements to be executed).When execution such a st tatement,S is executed if p is true,but S is not executed if p e.as u Example 8 EXAMPLE 8 What is the value of the variablex after the statement if 2+2=4then x :=x+ e this emer Solution:Because 2+2=4 is true.the assig ment statement r:=r+1 is executed.Henc 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 pg.In particular,there are three related conditional statements that occur so often that they have special names.The propositionp trapositive of p→y g is th the inve I p q.we wI dements formed from pg only the contrapositive always has the same truth We first show that the contrapositive, p of a conditional state a alwav has the same truth value as p- To see this,note that the contrapositive is false only when p is false and is true.that is,only when p is true and g is false.We now show that neither →p,nor the in D ,q,has the same truth value as p,→q for al p and g.Note th when p is true and is false,the original conditiona but the converse and e call then alent.so that a conditional statement and its co tement is the inve rse of a conditional statement are also equivalent.as the reader can verify.but neither is equivalent to the original conditional statement.(We will study equivalent propositions in Sec- tion 1.3.)Take note that one of the most common logical errors is to assume that the converse or thee s equivalen strate the use of conditio
8 1 / The Foundations: Logic and Proofs “If Juan has a smartphone, then 2 + 3 = 5” is true from the definition of a conditional statement, because its conclusion is true. (The truth value of the hypothesis does not matter then.) The conditional statement “If Juan has a smartphone, then 2 + 3 = 6” is true if Juan does not have a smartphone, even though 2 + 3 = 6 is false. We would not use these last two conditional statements in natural language (except perhaps in sarcasm), because there is no relationship between the hypothesis and the conclusion in either statement. In mathematical reasoning, we consider conditional statements of a more general sort than we use in English. The mathematical concept of a conditional statement is independent of a cause-andeffect relationship between hypothesis and conclusion. Our definition of a conditional statement specifies its truth values; it is not based on English usage. Propositional language is an artificial language; we only parallel English usage to make it easy to use and remember. The if-then construction used in many programming languages is different from that used in logic. Most programming languages contain statements such as if p then S, where p is a proposition and S is a program segment (one or more statements to be executed). When execution 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 value as p → q. We first show that the contrapositive, ¬q → ¬p, of 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 false and ¬q is true, that is, only when p is true and q is false. We now show that neither the converse, q → p, nor the inverse, ¬p → ¬q, has the same truth value as p → q for all possible truth values of p and q. Note that when p is true and q is false, the original conditional statement is false, but the converse and the inverse are both true. Remember that the contrapositive, but neither the converse or inverse, of a conditional statement is equivalent to it. When two compound propositions always have the same truth value we call them equivalent, so that a conditional statement and its contrapositive are equivalent. The converse and the inverse of a conditional statement are also equivalent, as the reader can verify, but neither is equivalent to the original conditional statement. (We will study equivalent propositions in Section 1.3.) Take note that one of the most common logical errors is to assume that the converse or the inverse of a conditional statement is equivalent to this conditional statement. We illustrate the use of conditional statements in Example 9
1.1 Propositional Logic9 EXAMPLE9 What are the contrapositive.the converse.and the inverse of the conditional statement "The home team wins whenever it is raining? e of the ways to express the conditional statemen "If it is raining.then the home team wins." Consequently.the contrapositive of this conditional statement i "If the home team does not win,then it is not raining. The converse is "If the home team wins,then it is raining." The inverse is "If it is not raining.then the home team does not win." Only the contrapositive is equivalent to the original statement. DEFINITION 6 ns.The biconditional statement pq is the and is false otherwise.Bi ents are in Table 6.Note that the when both ctive and why it is symbolically written by combining the symbolsand There are some other common ways to express pg 五5ndrg “pifq. The last way of expressing the biconditional statement pg uses the abbreviation"iff"for “"if and only if."Note that p分has exactly the same truth value as(p→q)A(g→p). TABLE 6 The Truth Table for the p+q
1.1 Propositional Logic 9 EXAMPLE 9 What are the contrapositive, the converse, and the inverse of the conditional statement “The home team wins whenever it is raining?” Solution: Because “q whenever p” is one of the ways to express the conditional statement p → q, the original statement can be rewritten as “If it is raining, then the home team wins.” Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.” The converse is “If the home team wins, then it is raining.” The inverse is “If it is not raining, then the home team does not win.” Only the contrapositive is equivalent to the original statement. ▲ BICONDITIONALS We now introduce another way to combine propositions that expresses that two propositions have the same truth value. DEFINITION 6 Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications. The truth table for p ↔ q is shown in Table 6. Note that the statement p ↔ q is true when both the conditional statements p → q and q → p are true and is false otherwise. That is why we use the words “if and only if” to express this logical connective and why it is symbolically written by combining the symbols → and ←. There are some other common ways to express p ↔ q: “p is necessary and sufficient for q” “if p then q, and conversely” “p iff q.” The last way of expressing the biconditional statement p ↔ q uses the abbreviation “iff” for “if and only if.” Note that p ↔ q has exactly the same truth value as (p → q) ∧ (q → p). TABLE 6 The Truth Table for the Biconditional p ↔ q. p q p ↔ q T T T T F F F T F F F T