Ch.2: The Logic of Compound Statements

Chapter 2 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 2.1. Logical Form and Logical Equivalence 2.2. Conditional Statements 2.3. Valid and Invalid Arguments 2.4. Application: Digital Logic Circuits 2.5. Application: Number Systems and Circuits for Addition

189 flashcards · Mathematics · by lakesare

Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses

1. [Logical Form and Logical Equivalence] What does logical analysis of an argument determine, and what does it not determine?

   Whether the conclusion follows necessarily from the premises (form), not whether the premises are true (content). That is why logic is sometimes defined as the science of necessary inference.

2. [Logical Form and Logical Equivalence] What is the common logical form of this argument, with letters p,q,rp, q, rp,q,r for the component sentences? "If Jane is a math major or Jane is a computer science major, then Jane will take Math 150. Jane is a computer science major. Therefore, Jane will take Math 150."

   If ppp or qqq , then rrr . q\;qq . Therefore, rrr . ppp = "Jane is a math major", qqq = "Jane is a computer science major", rrr = "Jane will take Math 150".Example: "If logic is easy or I study hard, then I will get an A. I will study hard. Therefore, I will get an A." has the same form.

3. [Logical Form and Logical Equivalence] Which terms are the undefined initial terms of logic?

   Sentence, true and false. Every mathematical theory starts from a few undefined terms; all other terms are defined from them.

4. [Logical Form and Logical Equivalence] What is a statement (or proposition)?

   A sentence that is true or false, but not both. Example: "Two plus two equals five" is a statement (a false one).

5. [Logical Form and Logical Equivalence] Why is " x+y>0x + y > 0x+y>0 " not a statement?

   Its truth value depends on the values of xxx and yyy , so on its own it is neither true nor false. Example: for x=1,y=2x = 1, y = 2x=1,y=2 it is true; for x=−1,y=0x = -1, y = 0x=−1,y=0 it is false.For the same reason "He is a college student" is not a statement: its truth depends on whom "he" refers to.

6. [Logical Form and Logical Equivalence] ppp and qqq are statements. What are ∼p\sim p∼p , p∧qp \wedge qp∧q and p∨qp \vee qp∨q called, and how are they read?

   Negation ∼p\sim p∼p , read "not ppp " or "it is not the case that ppp ". Conjunction p∧qp \wedge qp∧q , read " ppp and qqq ". Disjunction p∨qp \vee qp∨q , read " ppp or qqq ".

7. [Logical Form and Logical Equivalence] In which order are ∼\sim∼ , ∧\wedge∧ and ∨\vee∨ evaluated?

   ∼\sim∼ first; ∧\wedge∧ and ∨\vee∨ are coequal, so an expression with both needs parentheses. Example: ∼p∧q\sim p \wedge q∼p∧q means (∼p)∧q(\sim p) \wedge q(∼p)∧q , not ∼(p∧q)\sim(p \wedge q)∼(p∧q) .Example: p∧q∨rp \wedge q \vee rp∧q∨r is ambiguous; one must write (p∧q)∨r(p \wedge q) \vee r(p∧q)∨r or p∧(q∨r)p \wedge (q \vee r)p∧(q∨r) .

8. [Logical Form and Logical Equivalence] How do " ppp but qqq " and "neither ppp nor qqq " translate into logic?

   " ppp but qqq " means p∧qp \wedge qp∧q ; "neither ppp nor qqq " means ∼p∧∼q\sim p \wedge \sim q∼p∧∼q . "But" is used in place of "and" when the second part is in some way unexpected.

9. [Logical Form and Logical Equivalence] Let hhh = "It is hot" and sss = "It is sunny". Write symbolically: (a) It is not hot but it is sunny. (b) It is neither hot nor sunny.

   (a) ∼h∧s\sim h \wedge s∼h∧s \quad (b) ∼h∧∼s\sim h \wedge \sim s∼h∧∼s

10. [Logical Form and Logical Equivalence] x,a,bx, a, bx,a,b are particular real numbers. What do x≤ax \le ax≤a and a≤x≤ba \le x \le ba≤x≤b mean, written with "and" / "or"?

    x≤ax \le ax≤a means x<ax < ax<a or x=ax = ax=a ; a≤x≤b\;a \le x \le ba≤x≤b means a≤xa \le xa≤x and x≤bx \le bx≤b . Example: 2≤x≤12 \le x \le 12≤x≤1 means " 2≤x2 \le x2≤x and x≤1x \le 1x≤1 ", which is false for every real xxx .

11. [Logical Form and Logical Equivalence] xxx is a particular real number; ppp = " 0<x0 < x0<x ", qqq = " x<3x < 3x<3 ", rrr = " x=3x = 3x=3 ". Write symbolically: (a) x≤3x \le 3x≤3 \quad (b) 0<x<30 < x < 30<x<3 \quad (c) 0<x≤30 < x \le 30<x≤3

    (a) q∨rq \vee rq∨r \quad (b) p∧qp \wedge qp∧q \quad (c) p∧(q∨r)p \wedge (q \vee r)p∧(q∨r)

12. [Logical Form and Logical Equivalence] What is the truth table of the negation ∼p\sim p∼p ?

    ∼p\sim p∼p has the opposite truth value from ppp . p∼pTFFT\begin{array}{c|c}p & \sim p \\ \hline \mathrm{T} & \mathrm{F} \\ \mathrm{F} & \mathrm{T}\end{array}pTF​∼pFT​​

13. [Logical Form and Logical Equivalence] When is the conjunction p∧qp \wedge qp∧q true?

    When, and only when, both ppp and qqq are true. pqp∧qTTTTFFFTFFFF\begin{array}{c|c|c}p & q & p \wedge q \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} \\ \mathrm{T} & \mathrm{F} & \mathrm{F} \\ \mathrm{F} & \mathrm{T} & \mathrm{F} \\ \mathrm{F} & \mathrm{F} & \mathrm{F}\end{array}pTTFF​qTFTF​p∧qTFFF​​ The rows are listed in the customary order TT, TF, FT, FF.

14. [Logical Form and Logical Equivalence] When is the disjunction p∨qp \vee qp∨q false?

    Only when both ppp and qqq are false. pqp∨qTTTTFTFTTFFF\begin{array}{c|c|c}p & q & p \vee q \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} \\ \mathrm{T} & \mathrm{F} & \mathrm{T} \\ \mathrm{F} & \mathrm{T} & \mathrm{T} \\ \mathrm{F} & \mathrm{F} & \mathrm{F}\end{array}pTTFF​qTFTF​p∨qTTTF​​ Example: " 2≤22 \le 22≤2 " means " 2<22 < 22<2 or 2=22 = 22=2 ", which is true because 2=22 = 22=2 .

15. [Logical Form and Logical Equivalence] In logic, is "or" inclusive or exclusive?

    Inclusive: " ppp or qqq " means ppp or qqq or both. The symbol ∨\vee∨ comes from the Latin "vel", which means "or" in its inclusive sense. The exclusive sense is written " ppp or qqq but not both".Example: "coffee, tea, or milk" from a waiter is exclusive; "cream or sugar" is inclusive.

16. [Logical Form and Logical Equivalence] What is a statement form (or propositional form)?

    An expression made of statement variables and logical connectives that becomes a statement when actual statements are substituted for its variables. Example: (p∧q)∨∼r(p \wedge q) \vee \sim r(p∧q)∨∼r .Its truth table gives its truth value for every combination of truth values of its variables. To fill it in, evaluate the innermost parentheses first, then the next innermost, and so on.

17. [Logical Form and Logical Equivalence] How is exclusive or ( p⊕qp \oplus qp⊕q , ppp XOR qqq ) written with ∼,∧,∨\sim, \wedge, \vee∼,∧,∨ , and what is its truth table?

    (p∨q)∧∼(p∧q)\boldsymbol{(p \vee q) \wedge \sim(p \wedge q)}(p∨q)∧∼(p∧q) : true when exactly one of p,qp, qp,q is true. pqp∨qp∧q∼(p∧q)(p∨q)∧∼(p∧q)TTTTFFTFTFTTFTTFTTFFFFTF\begin{array}{c|c|c|c|c|c}p & q & p \vee q & p \wedge q & \sim(p \wedge q) & (p \vee q) \wedge \sim(p \wedge q) \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{F} \\ \mathrm{T} & \mathrm{F} & \mathrm{T} & \mathrm{F} & \mathrm{T} & \mathrm{T} \\ \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{F}…

18. [Logical Form and Logical Equivalence] In the truth table of (p∧q)∨∼r(p \wedge q) \vee \sim r(p∧q)∨∼r (rows TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF), which rows are F?

    Rows 3, 5 and 7 (TFT, FTT, FFT). An or statement is false only when both parts are false: p∧qp \wedge qp∧q false and ∼r\sim r∼r false, i.e. rrr true and not both p,qp, qp,q true. pqrp∧q∼r(p∧q)∨∼rTTTTFTTTFTTTTFTFFFTFFFTTFTTFFFFTFFTTFFTFFFFFFFTT\begin{array}{c|c|c|c|c|c}p & q & r & p \wedge q & \sim r & (p \wedge q) \vee \sim r \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{T} \\ \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{T} \\ \ma…

19. [Logical Form and Logical Equivalence] What does logic let you do with a compound statement's truth, and what does it not do?

    It determines the truth of a compound statement from the truth of its components; it does not determine the truth of the components themselves.

20. [Logical Form and Logical Equivalence] When are two statement forms PPP and QQQ logically equivalent ( P≡QP \equiv QP≡Q )?

    When they have identical truth values for each possible substitution of statements for their statement variables. Two statements are logically equivalent when their forms are logically equivalent (with the same variable for the same component statement).Example: "Dogs bark and cats meow" and "Cats meow and dogs bark" are logically equivalent, since p∧q≡q∧pp \wedge q \equiv q \wedge pp∧q≡q∧p .

21. [Logical Form and Logical Equivalence] "6 is greater than 2" and "2 is less than 6" say the same thing. Is this because of their logical form?

    No: because of the definitions of "greater than" and "less than". By contrast, "Dogs bark and cats meow" and "Cats meow and dogs bark" say the same thing because of their logical form, p∧qp \wedge qp∧q and q∧pq \wedge pq∧p .

22. [Logical Form and Logical Equivalence] How do you test with a truth table whether two statement forms PPP and QQQ are logically equivalent?

    Make a column for PPP and a column for QQQ ; they are equivalent if and only if every row has the same value in both columns. One row where PPP and QQQ differ shows that they are not logically equivalent.

23. [Logical Form and Logical Equivalence] What is the double negative property?

    ∼(∼p)≡p\boldsymbol{\sim(\sim p) \equiv p}∼(∼p)≡p p∼p∼(∼p)TFTFTF\begin{array}{c|c|c}p & \sim p & \sim(\sim p) \\ \hline \mathrm{T} & \mathrm{F} & \mathrm{T} \\ \mathrm{F} & \mathrm{T} & \mathrm{F}\end{array}pTF​∼pFT​∼(∼p)TF​​

24. [Logical Form and Logical Equivalence] What are the two ways to show that statement forms PPP and QQQ are not logically equivalent?

    Truth table Find a row of the truth table in which PPP and QQQ have different truth values. Concrete statements Find statements to substitute for the variables that make one form true and the other false. Example: ppp = " 0<10 < 10<1 ", qqq = " 1<01 < 01<0 " make ∼(p∧q)\sim(p \wedge q)∼(p∧q) true and ∼p∧∼q\sim p \wedge \sim q∼p∧∼q false.

25. [Logical Form and Logical Equivalence] Are ∼(p∧q)\sim(p \wedge q)∼(p∧q) and ∼p∧∼q\sim p \wedge \sim q∼p∧∼q logically equivalent?

    No: they differ in rows 2 and 3 (TF and FT), where ∼(p∧q)\sim(p \wedge q)∼(p∧q) is T and ∼p∧∼q\sim p \wedge \sim q∼p∧∼q is F. pq∼(p∧q)∼p∧∼qTTFFTFTFFTTFFFTT\begin{array}{c|c|c|c}p & q & \sim(p \wedge q) & \sim p \wedge \sim q \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{F} \\ \mathrm{T} & \mathrm{F} & \mathrm{T} & \mathrm{F} \\ \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{F} \\ \mathrm{F} & \mathrm{F} & \mathrm{T} & \mathrm{T}\end{array}pTTFF​qTFTF​∼(p∧q)FTTT​∼p∧∼qFFFT​​

26. [Logical Form and Logical Equivalence] What are De Morgan's laws of logic?

    ∼(p∧q)≡∼p∨∼q\boldsymbol{\sim(p \wedge q) \equiv \sim p \vee \sim q}∼(p∧q)≡∼p∨∼q and ∼(p∨q)≡∼p∧∼q\boldsymbol{\sim(p \vee q) \equiv \sim p \wedge \sim q}∼(p∨q)≡∼p∧∼q The negation of an and statement is the or statement in which each component is negated, and vice versa.Example: the negation of "John is tall and Jim is redheaded" is "John is not tall or Jim is not redheaded".

27. [Logical Form and Logical Equivalence] Who was Augustus De Morgan?

    An English mathematician (1806–1871), the first to state De Morgan's laws in formal mathematical terms. With George Boole he founded the modern subject of symbolic logic in the nineteenth century.

28. [Logical Form and Logical Equivalence] Write negations using De Morgan's laws: (a) John is 6 feet tall and he weighs at least 200 pounds. (b) The bus was late or Tom's watch was slow.

    (a) John is not 6 feet tall or he weighs less than 200 pounds. (b) The bus was not late and Tom's watch was not slow. (b) can also be written "Neither was the bus late nor was Tom's watch slow."

29. [Logical Form and Logical Equivalence] xxx is a real number. Without a negated symbol, what are x≮2x \nless 2x≮2 , x≯2\;x \ngtr 2x≯2 , x≰2\;x \nleq 2x≰2 , x≱2\;x \ngeq 2x≱2 ?

    x≥2x \ge 2x≥2 , x≤2\;x \le 2x≤2 , x>2\;x > 2x>2 , x<2\;x < 2x<2 x≮2x \nless 2x≮2 : xxx does not lie to the left of 2, so x=2x = 2x=2 or xxx lies to the right of 2.

30. [Logical Form and Logical Equivalence] xxx is a real number. What is the negation of −1<x≤4-1 < x \le 4−1<x≤4 ?

    −1≥x\boldsymbol{-1 \ge x}−1≥x or x>4\boldsymbol{x > 4}x>4 −1<x≤4-1 < x \le 4−1<x≤4 means " −1<x-1 < x−1<x and x≤4x \le 4x≤4 "; by De Morgan's laws the negation is " −1≮x-1 \nless x−1≮x or x≰4x \nleq 4x≰4 ". It is not " −1≥x>4-1 \ge x > 4−1≥x>4 ", which no real number satisfies.

31. [Logical Form and Logical Equivalence] A program must select all files modified outside the range from date1 to date2 inclusive. Which condition does it test?

    file_modification_date < date1 or date2 < file_modification_date By De Morgan's laws, this is equivalent to ∼\sim∼ (date1 ≤\le≤ file_modification_date ≤\le≤ date2).

32. [Logical Form and Logical Equivalence] ppp = "Jim is tall and thin". Its negation can be written "Jim is not tall and thin", which looks like an and statement. Why doesn't this contradict De Morgan's laws?

    In formal logic, "and" and "or" stand only between complete statements, not sentence fragments. Written with complete statements, ppp is "Jim is tall and Jim is thin", and De Morgan's laws give "Jim is not tall or Jim is not thin".

33. [Logical Form and Logical Equivalence] What is a tautology, and what is a contradiction?

    Tautology: a statement form that is always true, whatever statements are substituted for its variables. Contradiction: a statement form that is always false. Example: p∨∼pp \vee \sim pp∨∼p is a tautology, p∧∼pp \wedge \sim pp∧∼p is a contradiction.A statement whose form is a tautology is a tautological statement; one whose form is a contradiction is a contradictory statement. Their truth or falsity comes from their logical structure, not their meaning.

34. [Logical Form and Logical Equivalence] ttt is a tautology and ccc a contradiction. Simplify p∧tp \wedge tp∧t and p∧cp \wedge cp∧c .

    p∧t≡p\boldsymbol{p \wedge t \equiv p}p∧t≡p and p∧c≡c\boldsymbol{p \wedge c \equiv c}p∧c≡c ptp∧tcp∧cTTTFFFTFFF\begin{array}{c|c|c|c|c}p & t & p \wedge t & c & p \wedge c \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{F} \\ \mathrm{F} & \mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{F}\end{array}pTF​tTT​p∧tTF​cFF​p∧cFF​​

35. [Logical Form and Logical Equivalence] What are the commutative and associative laws of logic?

    Commutative laws p∧q≡q∧pp∨q≡q∨pp \wedge q \equiv q \wedge p \qquad p \vee q \equiv q \vee pp∧q≡q∧pp∨q≡q∨p Associative laws (p∧q)∧r≡p∧(q∧r)(p∨q)∨r≡p∨(q∨r)(p \wedge q) \wedge r \equiv p \wedge (q \wedge r) \qquad (p \vee q) \vee r \equiv p \vee (q \vee r)(p∧q)∧r≡p∧(q∧r)(p∨q)∨r≡p∨(q∨r)

36. [Logical Form and Logical Equivalence] What are the distributive laws of logic?

    p∧(q∨r)≡(p∧q)∨(p∧r)\boldsymbol{p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)}p∧(q∨r)≡(p∧q)∨(p∧r) and p∨(q∧r)≡(p∨q)∧(p∨r)\boldsymbol{p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)}p∨(q∧r)≡(p∨q)∧(p∨r)

37. [Logical Form and Logical Equivalence] ttt is a tautology, ccc a contradiction. What are the identity laws and the negation laws?

    Identity laws p∧t≡pp∨c≡pp \wedge t \equiv p \qquad p \vee c \equiv pp∧t≡pp∨c≡p Negation laws p∨∼p≡tp∧∼p≡cp \vee \sim p \equiv t \qquad p \wedge \sim p \equiv cp∨∼p≡tp∧∼p≡c

38. [Logical Form and Logical Equivalence] What are the idempotent laws of logic?

    p∧p≡p\boldsymbol{p \wedge p \equiv p}p∧p≡p and p∨p≡p\boldsymbol{p \vee p \equiv p}p∨p≡p

39. [Logical Form and Logical Equivalence] ttt is a tautology, ccc a contradiction. What are the universal bound laws?

    p∨t≡t\boldsymbol{p \vee t \equiv t}p∨t≡t and p∧c≡c\boldsymbol{p \wedge c \equiv c}p∧c≡c

40. [Logical Form and Logical Equivalence] What are the absorption laws of logic?

    p∨(p∧q)≡p\boldsymbol{p \vee (p \wedge q) \equiv p}p∨(p∧q)≡p and p∧(p∨q)≡p\boldsymbol{p \wedge (p \vee q) \equiv p}p∧(p∨q)≡p Example: "it rains, or it rains and it is cold" is true exactly when "it rains" is true.

41. [Logical Form and Logical Equivalence] ttt is a tautology and ccc a contradiction. What are ∼t\sim t∼t and ∼c\sim c∼c ?

    ∼t≡c\boldsymbol{\sim t \equiv c}∼t≡c and ∼c≡t\boldsymbol{\sim c \equiv t}∼c≡t

42. [Logical Form and Logical Equivalence] Which five laws of logical equivalence are the axioms of a Boolean algebra, from which the other laws can be derived?

    Commutative, associative, distributive, identity and negation laws.

43. [Logical Form and Logical Equivalence] Simplify ∼(∼p∧q)∧(p∨q)\sim(\sim p \wedge q) \wedge (p \vee q)∼(∼p∧q)∧(p∨q) using the laws of logical equivalence.

    ≡p\boldsymbol{\equiv p}≡p ≡(∼(∼p)∨∼q)∧(p∨q)\equiv (\sim(\sim p) \vee \sim q) \wedge (p \vee q)≡(∼(∼p)∨∼q)∧(p∨q) (De Morgan) ≡(p∨∼q)∧(p∨q)\equiv (p \vee \sim q) \wedge (p \vee q)≡(p∨∼q)∧(p∨q) (double negative) ≡p∨(∼q∧q)\equiv p \vee (\sim q \wedge q)≡p∨(∼q∧q) (distributive) ≡p∨(q∧∼q)\equiv p \vee (q \wedge \sim q)≡p∨(q∧∼q) (commutative) ≡p∨c\equiv p \vee c≡p∨c (negation law, ccc a contradiction) ≡p\equiv p≡p (identity law)

44. [Logical Form and Logical Equivalence] Laws of logical equivalence versus truth tables: what can each do, and what does each cost?

    Laws can prove equivalence but never non-equivalence; truth tables decide both but need 2n2^n2n rows for nnn variables. Example: p∧(∼q∧∼r)≡(p∧∼q)∧∼rp \wedge (\sim q \wedge \sim r) \equiv (p \wedge \sim q) \wedge \sim rp∧(∼q∧∼r)≡(p∧∼q)∧∼r follows at once from the associative law, but needs 8 rows by truth table.

45. [Conditional Statements] What is the conditional p→qp \to qp→q , and when is it false?

    "If ppp then qqq "; it is false only when ppp is true and qqq is false. ppp is the hypothesis (or antecedent), qqq the conclusion (or consequent).

46. [Conditional Statements] What is the truth table of p→qp \to qp→q ?

    Only the row ppp = T, qqq = F is F. pqp→qTTTTFFFTTFFT\begin{array}{c|c|c}p & q & p \to q \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} \\ \mathrm{T} & \mathrm{F} & \mathrm{F} \\ \mathrm{F} & \mathrm{T} & \mathrm{T} \\ \mathrm{F} & \mathrm{F} & \mathrm{T}\end{array}pTTFF​qTFTF​p→qTFTT​​

47. [Conditional Statements] A store owner promises: "If you show up for work Monday morning, then you will get the job." In which case did the owner speak falsely?

    Only if you show up Monday morning and do not get the job. The promise says nothing about the case that you don't show up, so it is not false then, whether or not you get the job. This is why p→qp \to qp→q is true whenever ppp is false.

48. [Conditional Statements] A conditional statement that is true because its hypothesis is false is called vacuously true (or true by default).

    Example: "If 0=10 = 10=1 then 1=21 = 21=2 " is true.

49. [Conditional Statements] Why did the philosopher W. V. O. Quine advise against reading p→qp \to qp→q as " ppp implies qqq "?

    "Implies" suggests that qqq can be logically deduced from ppp , which is often not the case for a true p→qp \to qp→q .

50. [Conditional Statements] What is the order of operations for ∼,∧,∨,→,↔\sim, \wedge, \vee, \to, \leftrightarrow∼,∧,∨,→,↔ ?

    ∼\sim∼ first; then ∧\wedge∧ and ∨\vee∨ ; then →\to→ and ↔\leftrightarrow↔ . Operators on the same level are coequal: when both appear, parentheses may be needed.Example: p∨∼q→∼pp \vee \sim q \to \sim pp∨∼q→∼p means (p∨(∼q))→(∼p)(p \vee (\sim q)) \to (\sim p)(p∨(∼q))→(∼p) .

51. [Conditional Statements] What is the truth table of p∨∼q→∼pp \vee \sim q \to \sim pp∨∼q→∼p ?

    F, F, T, T (rows TT, TF, FT, FF) It means (p∨∼q)→∼p(p \vee \sim q) \to \sim p(p∨∼q)→∼p ; it is F when the hypothesis p∨∼qp \vee \sim qp∨∼q is T and the conclusion ∼p\sim p∼p is F, i.e. when ppp is T. pq∼p∼qp∨∼qp∨∼q→∼pTTFFTFTFFTTFFTTFFTFFTTTT\begin{array}{c|c|c|c|c|c}p & q & \sim p & \sim q & p \vee \sim q & p \vee \sim q \to \sim p \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{T} & \mathrm{F} \\ \mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{F}…

52. [Conditional Statements] p∨q→r≡ ?p \vee q \to r \equiv \; ?p∨q→r≡? (using two conditionals)

    (p→r)∧(q→r)\boldsymbol{(p \to r) \wedge (q \to r)}(p→r)∧(q→r) If rrr follows from ppp and also from qqq , then rrr follows from " ppp or qqq ". This is the basis of the division-into-cases method.Example: "If x>2x > 2x>2 or x<−2x < -2x<−2 then x2>4x^2 > 4x2>4 " means "if x>2x > 2x>2 then x2>4x^2 > 4x2>4 , and if x<−2x < -2x<−2 then x2>4x^2 > 4x2>4 ".

53. [Conditional Statements] How is p→qp \to qp→q written with ∼\sim∼ and ∨\vee∨ ?

    p→q≡∼p∨q\boldsymbol{p \to q \equiv \sim p \vee q}p→q≡∼p∨q Both are false only when ppp is T and qqq is F.

54. [Conditional Statements] Rewrite in if-then form: "Either you get to work on time or you are fired."

    If you do not get to work on time, then you are fired. With ∼p\sim p∼p = "you get to work on time", qqq = "you are fired", the sentence is ∼p∨q≡p→q\sim p \vee q \equiv p \to q∼p∨q≡p→q .

55. [Conditional Statements] What is the negation of p→qp \to qp→q ?

    ∼(p→q)≡p∧∼q\boldsymbol{\sim(p \to q) \equiv p \wedge \sim q}∼(p→q)≡p∧∼q ∼(p→q)≡∼(∼p∨q)≡∼(∼p)∧∼q≡p∧∼q\sim(p \to q) \equiv \sim(\sim p \vee q) \equiv \sim(\sim p) \wedge \sim q \equiv p \wedge \sim q∼(p→q)≡∼(∼p∨q)≡∼(∼p)∧∼q≡p∧∼q (De Morgan, then double negative).The negation of an if-then statement does not start with "if".

56. [Conditional Statements] Write negations: (a) If my car is in the repair shop, then I cannot get to class. (b) If Sara lives in Athens, then she lives in Greece.

    (a) My car is in the repair shop and I can get to class. (b) Sara lives in Athens and she does not live in Greece. (b) can be true: Sara might live in Athens, Georgia.

57. [Conditional Statements] What is the contrapositive of p→qp \to qp→q , and how is it related to p→qp \to qp→q ?

    ∼q→∼p\boldsymbol{\sim q \to \sim p}∼q→∼p , and it is logically equivalent to p→qp \to qp→q . Example: the contrapositive of "If today is Easter, then tomorrow is Monday" is "If tomorrow is not Monday, then today is not Easter".This equivalence is the basis of modus tollens and of proof by contraposition.

58. [Conditional Statements] Write the contrapositive: "If Howard can swim across the lake, then Howard can swim to the island."

    If Howard cannot swim to the island, then Howard cannot swim across the lake.

59. [Conditional Statements] What are the converse and the inverse of p→qp \to qp→q ?

    Converse: q→p\boldsymbol{q \to p}q→p . Inverse: ∼p→∼q\boldsymbol{\sim p \to \sim q}∼p→∼q . Example: for "If today is Easter, then tomorrow is Monday": converse "If tomorrow is Monday, then today is Easter"; inverse "If today is not Easter, then tomorrow is not Monday".

60. [Conditional Statements] "If today is Easter, then tomorrow is Monday" is always true. Are its converse and inverse always true?

    No: both are false on every Sunday except Easter. Converse: "If tomorrow is Monday, then today is Easter". Inverse: "If today is not Easter, then tomorrow is not Monday".

61. [Conditional Statements] Which of these are logically equivalent: a conditional p→qp \to qp→q , its converse, its inverse, its contrapositive?

    p→qp \to qp→q ≡\equiv≡ contrapositive ∼q→∼p\sim q \to \sim p∼q→∼p , and converse q→pq \to pq→p ≡\equiv≡ inverse ∼p→∼q\sim p \to \sim q∼p→∼q . No other pair. The inverse is the contrapositive of the converse, which is why those two are equivalent.

62. [Conditional Statements] What does " ppp only if qqq " mean as an if-then statement?

    "If ppp then qqq ", equivalently "if not qqq then not ppp ". ppp can take place only if qqq takes place also.

63. [Conditional Statements] Rewrite in if-then form in two ways (one the contrapositive of the other): "John will break the world's record for the mile run only if he runs the mile in under four minutes."

    If John breaks the world's record, then he will have run the mile in under four minutes. Contrapositive version: if John does not run the mile in under four minutes, then he will not break the world's record.

64. [Conditional Statements] Does " ppp only if qqq " mean " ppp if qqq "?

    No: " ppp only if qqq " means p→qp \to qp→q , while " ppp if qqq " means q→pq \to pq→p . Example: "John breaks the record only if he runs under four minutes" can be true while "John breaks the record if he runs under four minutes" is false: his time may be under four minutes but still too slow.

65. [Conditional Statements] What is the biconditional p↔qp \leftrightarrow qp↔q , and when is it true?

    " ppp if, and only if, qqq " (iff); true exactly when ppp and qqq have the same truth value. pqp↔qTTTTFFFTFFFT\begin{array}{c|c|c}p & q & p \leftrightarrow q \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} \\ \mathrm{T} & \mathrm{F} & \mathrm{F} \\ \mathrm{F} & \mathrm{T} & \mathrm{F} \\ \mathrm{F} & \mathrm{F} & \mathrm{T}\end{array}pTTFF​qTFTF​p↔qTFFT​​

66. [Conditional Statements] p↔q≡ ?p \leftrightarrow q \equiv \; ?p↔q≡? (using two conditionals)

    (p→q)∧(q→p)\boldsymbol{(p \to q) \wedge (q \to p)}(p→q)∧(q→p) " ppp if, and only if, qqq " says both " ppp if qqq " ( q→pq \to pq→p ) and " ppp only if qqq " ( p→qp \to qp→q ).Example: "This program is correct if, and only if, it produces correct answers for all possible sets of input data" means "If this program is correct, then it produces correct answers for all possible sets of input data; and if it produces correct answers for all possible sets of input data, then it is correct".

67. [Conditional Statements] rrr and sss are statements. What do " rrr is a sufficient condition for sss " and " rrr is a necessary condition for sss " mean?

    Sufficient condition "If rrr then sss ": the occurrence of rrr guarantees the occurrence of sss . Example: "Pia's birth on U.S. soil is a sufficient condition for her to be a U.S. citizen" means "If Pia was born on U.S. soil, then she is a U.S. citizen". Necessary condition "If not rrr then not sss ", equivalently "if sss then rrr ": sss cannot occur without rrr . Example: "John is at least 18 years old" is a necessary condition for "John is eligible to vote".

68. [Conditional Statements] rrr and sss are statements. What does " rrr is a necessary and sufficient condition for sss " mean?

    " rrr if, and only if, sss ", i.e. r↔sr \leftrightarrow sr↔s . Sufficient gives r→sr \to sr→s ; necessary gives s→rs \to rs→r .

69. [Conditional Statements] Use the contrapositive to rewrite in two ways: "George's attaining age 35 is a necessary condition for his being president of the United States."

    If George has not attained the age of 35, then he cannot be president. Equivalently: if George can be president, then he has attained the age of 35.

70. [Conditional Statements] Is "If 2+2=52 + 2 = 52+2=5 , then Mickey Mouse is president of the United States" an allowed statement in logic, and is it true?

    Allowed, and true, because its hypothesis is false. In logic the hypothesis and the conclusion of a conditional need not have related subject matter; otherwise someone would have to decide which clauses are related.

71. [Conditional Statements] A parent says "If you eat your dinner, you will get dessert." What does the parent usually mean, and how must such a statement be read in mathematics?

    The parent usually means a biconditional ("dessert if, and only if, you eat your dinner"); in mathematics an if-then statement means only the conditional. Reading conditionals as biconditionals in everyday speech leads to the mistaken belief that a conditional is equivalent to its converse and its inverse.

72. [Valid and Invalid Arguments] What are an argument and an argument form, and what are its premises and its conclusion?

    Argument: a sequence of statements. Argument form: a sequence of statement forms. The final one is the conclusion, all others are premises. Premises are also called assumptions or hypotheses. The symbol ∴\therefore∴ ("therefore") is placed before the conclusion.Example: "If Socrates is a man, then Socrates is mortal. Socrates is a man. ∴\therefore∴ Socrates is mortal." has the form p→qp∴q\begin{array}{rl} & p \to q \\ & p \\ \therefore & q \end{array}∴​p→qpq​

73. [Valid and Invalid Arguments] When is an argument form valid? When is an argument valid?

    A form is valid if, whatever statements are substituted for its variables, true premises always give a true conclusion. An argument is valid if its form is. So validity depends only on the form of an argument, not on its content.

74. [Valid and Invalid Arguments] Can a valid argument have all premises true and a false conclusion?

    No. That is exactly what validity rules out: the truth of the conclusion follows from the truth of the premises by logical form alone. The conclusion is then said to be inferred or deduced.

75. [Valid and Invalid Arguments] A row of a truth table in which all the premises of an argument form are true is called a critical row.

76. [Valid and Invalid Arguments] How do you test an argument form for validity with a truth table?

    Valid if and only if the conclusion is true in every critical row (row of the truth table where all premises are true). Steps: identify the premises and the conclusion; build a truth table for all of them; check the conclusion in the critical rows.A critical row with a false conclusion shows that an argument of this form can have true premises and a false conclusion, so the form is invalid.In the other rows the conclusion's truth value is irrelevant, so it need not be filled in.

77. [Valid and Invalid Arguments] Is this argument form valid? p→q∨∼rq→p∧r∴p→r\begin{array}{rl} & p \to q \vee \sim r \\ & q \to p \wedge r \\ \therefore & p \to r \end{array}∴​p→q∨∼rq→p∧rp→r​

    Invalid: for p=p = p= T, q=r=q = r = q=r= F both premises are true but p→rp \to rp→r is false. pqrp→q∨∼rq→p∧rp→rTTTTTTTTFTFTFTFTTFFTTFFTTTFFTFTFFFTTTTFFFTTT\begin{array}{ccc|cc|c} p & q & r & p \to q \vee \sim r & q \to p \wedge r & p \to r \\ \hline T & T & T & T & T & T \\ T & T & F & T & F & \\ T & F & T & F & T & \\ T & F & F & T & T & \mathbf{F} \\ F & T & T & T & F & \\ F & T & F & T & F & \\ F & F & T & T & T & T \\ F & F & F & T & T & T \end{array}pTTTTFFFF​qTTFFTTFF​rTFTFTFTF​p→q∨∼rTTF…

78. [Valid and Invalid Arguments] What is a syllogism, and what are its major and minor premise?

    An argument form with two premises and a conclusion. The first premise is the major premise, the second the minor premise. Example: modus ponens p→qp∴q\begin{array}{rl} & p \to q \\ & p \\ \therefore & q \end{array}∴​p→qpq​ is a syllogism with major premise p→qp \to qp→q and minor premise ppp .

79. [Valid and Invalid Arguments] What is the form of modus ponens?

    p→qp∴q\begin{array}{rl} & p \to q \\ & p \\ \therefore & q \end{array}∴​p→qpq​ Latin for "method of affirming": the conclusion is an affirmation.Example: If the sum of the digits of 371,487 is divisible by 3, then 371,487 is divisible by 3. The sum of the digits of 371,487 is divisible by 3. ∴\therefore∴ 371,487 is divisible by 3.

80. [Valid and Invalid Arguments] Modus ponens: p→qp∴q\begin{array}{rl} & p \to q \\ & p \\ \therefore & q \end{array}∴​p→qpq​ Why is modus ponens valid, by a truth table?

    The only critical row is p=q=p = q = p=q= T, and there the conclusion qqq is true. pqp→qpqTTTTTTFFTFTTFFFTF\begin{array}{cc|cc|c} p & q & p \to q & p & q \\ \hline T & T & T & T & T \\ T & F & F & T & \\ F & T & T & F & \\ F & F & T & F & \end{array}pTTFF​qTFTF​p→qTFTT​pTTFF​qT​​

81. [Valid and Invalid Arguments] What is the form of modus tollens?

    p→q∼q∴∼p\begin{array}{rl} & p \to q \\ & \sim q \\ \therefore & \sim p \end{array}∴​p→q∼q∼p​ Latin for "method of denying": the conclusion is a denial.Example: If Zeus is human, then Zeus is mortal. Zeus is not mortal. ∴\therefore∴ Zeus is not human.

82. [Valid and Invalid Arguments] Modus tollens: p→q∼q∴∼p\begin{array}{rl} & p \to q \\ & \sim q \\ \therefore & \sim p \end{array}∴​p→q∼q∼p​ Why is modus tollens valid, without a truth table?

    p→qp \to qp→q is logically equivalent to its contrapositive ∼q→∼p\sim q \to \sim p∼q→∼p , and modus ponens applied to ∼q→∼p\sim q \to \sim p∼q→∼p and ∼q\sim q∼q gives ∼p\sim p∼p . Intuitively, by contradiction: if ppp were true, then qqq would be true by the first premise, but qqq is false.Studies show that nearly all college students apply modus ponens correctly, but fewer than 60% apply modus tollens correctly.

83. [Valid and Invalid Arguments] Use modus ponens or modus tollens to complete each argument: a. If there are more pigeons than pigeonholes, then at least two pigeons roost in the same hole. There are more pigeons than pigeonholes. ∴\therefore∴ ? b. If 870,232 is divisible by 6, then it is divisible by 3. 870,232 is not divisible by 3. ∴\therefore∴ ?

    a. At least two pigeons roost in the same hole (modus ponens). b. 870,232 is not divisible by 6 (modus tollens).

84. [Valid and Invalid Arguments] What is a rule of inference?

    A valid argument form. Example: modus ponens and modus tollens are rules of inference.

85. [Valid and Invalid Arguments] What does the rule of generalization say?

    p∴p∨q\begin{array}{rl} & p \\ \therefore & p \vee q \end{array}∴​pp∨q​ and q∴p∨q\begin{array}{rl} & q \\ \therefore & p \vee q \end{array}∴​qp∨q​ If ppp is true, then more generally " ppp or qqq " is true for any statement qqq .Example: Anton is a junior. ∴\therefore∴ Anton is a junior or Anton is a senior. (So Anton is an upperclassman.)

86. [Valid and Invalid Arguments] What does the rule of specialization say?

    p∧q∴p\begin{array}{rl} & p \wedge q \\ \therefore & p \end{array}∴​p∧qp​ and p∧q∴q\begin{array}{rl} & p \wedge q \\ \therefore & q \end{array}∴​p∧qq​ It discards information to focus on the property of interest.Example: Ana knows numerical analysis and Ana knows graph algorithms. ∴\therefore∴ Ana knows graph algorithms.

87. [Valid and Invalid Arguments] What does the rule of conjunction say?

    pq∴p∧q\begin{array}{rl} & p \\ & q \\ \therefore & p \wedge q \end{array}∴​pqp∧q​ Example: 2<32 < 32<3 . 3<53 < 53<5 . ∴\therefore∴ 2<32 < 32<3 and 3<53 < 53<5 .

88. [Valid and Invalid Arguments] What does the rule of elimination say?

    p∨q∼q∴p\begin{array}{rl} & p \vee q \\ & \sim q \\ \therefore & p \end{array}∴​p∨q∼qp​ and p∨q∼p∴q\begin{array}{rl} & p \vee q \\ & \sim p \\ \therefore & q \end{array}∴​p∨q∼pq​ With only two possibilities, ruling one out leaves the other.Example: x−3=0x - 3 = 0x−3=0 or x+2=0x + 2 = 0x+2=0 . xxx is not negative, so x+2≠0x + 2 \neq 0x+2=0 . ∴\therefore∴ x−3=0x - 3 = 0x−3=0 .

89. [Valid and Invalid Arguments] What does the rule of transitivity say?

    p→qq→r∴p→r\begin{array}{rl} & p \to q \\ & q \to r \\ \therefore & p \to r \end{array}∴​p→qq→rp→r​ Example: If 18,486 is divisible by 18, then 18,486 is divisible by 9. If 18,486 is divisible by 9, then the sum of its digits is divisible by 9. ∴\therefore∴ If 18,486 is divisible by 18, then the sum of its digits is divisible by 9.

90. [Valid and Invalid Arguments] What is the form of proof by division into cases?

    p∨qp→rq→r∴r\begin{array}{rl} & p \vee q \\ & p \to r \\ & q \to r \\ \therefore & r \end{array}∴​p∨qp→rq→rr​ If the conclusion follows in each of the possible cases, it is true.Example: xxx is a nonzero real number, so xxx is positive or xxx is negative. If xxx is positive, then x2>0x^2 > 0x2>0 . If xxx is negative, then x2>0x^2 > 0x2>0 . ∴\therefore∴ x2>0x^2 > 0x2>0 .

91. [Valid and Invalid Arguments] You know these are true. Where are your glasses? a. If I was reading the newspaper in the kitchen, then my glasses are on the kitchen table. b. If my glasses are on the kitchen table, then I saw them at breakfast. c. I did not see my glasses at breakfast. d. I was reading the newspaper in the living room or I was reading the newspaper in the kitchen. e. If I was reading the newspaper in the living room, then my glasses are on the coffee table.

    On the coffee table. 1. (a), (b), transitivity: if I read in the kitchen, then I saw my glasses at breakfast.2. That and (c), modus tollens: I was not reading in the kitchen.3. That and (d), elimination: I was reading in the living room.4. That and (e), modus ponens: the glasses are on the coffee table.

92. [Valid and Invalid Arguments] What is a fallacy?

    An error in reasoning that results in an invalid argument. Example: converse error and inverse error.

93. [Valid and Invalid Arguments] Besides the converse and inverse error, what are three common fallacies?

    Using ambiguous premises Treating ambiguous premises as if they were unambiguous. Circular reasoning Assuming what is to be proved, without having derived it from the premises. Jumping to a conclusion Drawing a conclusion without adequate grounds.

94. [Valid and Invalid Arguments] Complete: for an argument to be valid means that every argument of the same form whose premises … has a … conclusion.

    … are all true has a true conclusion.

95. [Valid and Invalid Arguments] What are two ways to show that an argument is invalid?

    Find a critical row with a false conclusion in its truth table, or find an argument of the same form with all premises true and a false conclusion. Invalid means: some argument of that form has all premises true and a false conclusion.

96. [Valid and Invalid Arguments] What is the converse error, and what is its other name?

    The invalid form p→qq∴p\begin{array}{rl} & p \to q \\ & q \\ \therefore & p \end{array}∴​p→qqp​ , also called the fallacy of affirming the consequent. The conclusion would follow if p→qp \to qp→q were replaced by its converse q→pq \to pq→p , but a conditional is not logically equivalent to its converse.

97. [Valid and Invalid Arguments] Why is this argument invalid? If Zeke is a cheater, then Zeke sits in the back row. Zeke sits in the back row. ∴\therefore∴ Zeke is a cheater.

    It commits the converse error: someone who is not a cheater but sits in the back row makes both premises true and the conclusion false. For such a person the first premise is true by default, since its hypothesis is false.

98. [Valid and Invalid Arguments] What is the inverse error, and what is its other name?

    The invalid form p→q∼p∴∼q\begin{array}{rl} & p \to q \\ & \sim p \\ \therefore & \sim q \end{array}∴​p→q∼p∼q​ , also called the fallacy of denying the antecedent. The conclusion would follow if p→qp \to qp→q were replaced by its inverse ∼p→∼q\sim p \to \sim q∼p→∼q , but a conditional is not logically equivalent to its inverse.Example: If interest rates are going up, stock market prices will go down. Interest rates are not going up. ∴\therefore∴ Stock market prices will not go down.

99. [Valid and Invalid Arguments] Can a valid argument have a false conclusion? Can an invalid argument have a true conclusion?

    Yes and yes. In logic, true and valid have different meanings. Example: If John Lennon was a rock star, then John Lennon had red hair. John Lennon was a rock star. ∴\therefore∴ John Lennon had red hair. (Valid by modus ponens; false major premise, false conclusion.)Example: If New York is a big city, then New York has tall buildings. New York has tall buildings. ∴\therefore∴ New York is a big city. (Invalid by the converse error; true conclusion.)

100. [Valid and Invalid Arguments] When is an argument sound?

     When it is valid and all its premises are true. Otherwise it is unsound. Only for a sound argument can we be sure that the conclusion is true.