Ch.3: The Logic of Quantified Statements
Chapter 3 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 3.1. Predicates and Quantified Statements I 3.2. Predicates and Quantified Statements II 3.3. Statements with Multiple Quantifiers 3.4. Arguments with Quantified Statements
113 flashcards · Mathematics · by lakesare
Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses
[Predicates and Quantified Statements I] What is the predicate calculus, and what is the statement calculus?
Predicate calculus: symbolic analysis of predicates and quantified statements. Statement calculus: of compound statements built with ∼,∧,∨,→,↔\sim, \wedge, \vee, \to, \leftrightarrow∼,∧,∨,→,↔ . The statement calculus is also called the propositional calculus.The validity of "All men are mortal. Socrates is a man. ∴\therefore∴ Socrates is mortal." can be shown only with the predicate calculus.
[Predicates and Quantified Statements I] What is a predicate, and what is the domain of a predicate variable?
Predicate: a sentence with finitely many variables that becomes a statement when values are substituted for them. Domain: the set of all allowed values. The domain of a predicate variable is the set of all values that may be substituted in place of the variable.Example: " xxx is a student at yyy " is a predicate Q(x,y)Q(x, y)Q(x,y) ; the predicate symbol is QQQ , the predicate variables are xxx and yyy .
[Predicates and Quantified Statements I] P(x)P(x)P(x) is the predicate " x2>xx^2 > xx2>x " with domain R\mathbf{R}R . Which of P(2)P(2)P(2) , P(12)P(\frac{1}{2})P(21) , P(−12)P(-\frac{1}{2})P(−21) are true?
P(2)P(2)P(2) and P(−12)P(-\frac{1}{2})P(−21) are true; P(12)P(\frac{1}{2})P(21) is false. P(2)P(2)P(2) : 4>24 > 24>2 . P(12)\ P(\frac{1}{2}) P(21) : 14>12\frac{1}{4} > \frac{1}{2}41>21 is false. P(−12)\ P(-\frac{1}{2}) P(−21) : 14>−12\frac{1}{4} > -\frac{1}{2}41>−21 .
[Predicates and Quantified Statements I] P(x)P(x)P(x) is a predicate and xxx has domain DDD . What is the truth set of P(x)P(x)P(x) , and how is it written?
The set of all elements of DDD that make P(x)P(x)P(x) true, written {x∈D∣P(x)}\{x \in D \mid P(x)\}{x∈D∣P(x)} . Read "the set of all xxx in DDD such that P(x)P(x)P(x) ".Example: the truth set of " x2=4x^2 = 4x2=4 " with domain R\mathbf{R}R is {−2,2}\{-2, 2\}{−2,2} .
[Predicates and Quantified Statements I] Q(n)Q(n)Q(n) is the predicate " nnn is a factor of 8". What is its truth set when the domain is Z+\mathbf{Z}^+Z+ (positive integers), and when it is Z\mathbf{Z}Z ?
Z+\mathbf{Z}^+Z+ : {1,2,4,8}\boldsymbol{\{1, 2, 4, 8\}}{1,2,4,8} . Z\ \mathbf{Z} Z : {1,2,4,8,−1,−2,−4,−8}\boldsymbol{\{1, 2, 4, 8, -1, -2, -4, -8\}}{1,2,4,8,−1,−2,−4,−8} . The negative integers −1,−2,−4,−8-1, -2, -4, -8−1,−2,−4,−8 also divide 8 without remainder.
[Predicates and Quantified Statements I] What is a quantifier, and what do the symbols ∀\forall∀ and ∃\exists∃ mean?
A word for a quantity, such as "some" or "all". ∀\forall∀ : "for all" (universal quantifier), ∃\exists∃ : "there exists" (existential quantifier). A quantifier tells for how many elements of the domain a predicate is true; adding quantifiers turns a predicate into a statement.
[Predicates and Quantified Statements I] Who introduced the concept of a quantifier into symbolic logic, and when?
Charles Sanders Peirce and, independently, Gottlob Frege, in the late nineteenth century. Peirce (1839 to 1914) was an American philosopher, logician and engineer; Frege (1848 to 1925) a German logician.
[Predicates and Quantified Statements I] Which English expressions can be used for the symbol ∀\forall∀ ?
for all, for every, for any, for each, for arbitrary, given any Example: " ∀\forall∀ real numbers xxx and yyy , x+y=y+xx + y = y + xx+y=y+x ": here ∀\forall∀ refers to both xxx and yyy .
[Predicates and Quantified Statements I] Why write " ∀\forall∀ human beings xxx , xxx is mortal" rather than " xxx are mortal"?
xxx is a single individual, but a generic one: xxx has all the properties shared by every human being and no other properties.
[Predicates and Quantified Statements I] Q(x)Q(x)Q(x) is a predicate with domain DDD . When is the universal statement " ∀x∈D,Q(x)\forall x \in D, Q(x)∀x∈D,Q(x) " true, when false, and what is a counterexample to it?
True iff Q(x)Q(x)Q(x) is true for every xxx in DDD ; false iff Q(x)Q(x)Q(x) is false for at least one xxx in DDD . A counterexample is a value of xxx for which Q(x)Q(x)Q(x) is false. Example: x=0x = 0x=0 is a counterexample to " ∀x∈Z,x2>0\forall x \in \mathbf{Z}, x^2 > 0∀x∈Z,x2>0 ".
[Predicates and Quantified Statements I] D={1,2,3,4,5}D = \{1, 2, 3, 4, 5\}D={1,2,3,4,5} . Is " ∀x∈D,x2≥x\forall x \in D, x^2 \ge x∀x∈D,x2≥x " true? Is " ∀x∈R,x2≥x\forall x \in \mathbf{R}, x^2 \ge x∀x∈R,x2≥x " true?
The first is true, the second is false. 1≥11 \ge 11≥1 , 4≥24 \ge 24≥2 , 9≥39 \ge 39≥3 , 16≥416 \ge 416≥4 , 25≥525 \ge 525≥5 .Counterexample for R\mathbf{R}R : x=12x = \frac{1}{2}x=21 , since (12)2=14≱12(\frac{1}{2})^2 = \frac{1}{4} \not\ge \frac{1}{2}(21)2=41≥21 .
[Predicates and Quantified Statements I] What is the method of exhaustion, and when can it be used?
Showing that a predicate is true separately for each element of the domain. It can be used only when the domain is finite. Most mathematical sets are infinite, so the method rarely proves general results.Example: " ∀x∈{1,2,3},x2≥x\forall x \in \{1, 2, 3\}, x^2 \ge x∀x∈{1,2,3},x2≥x " holds since 1≥11 \ge 11≥1 , 4≥24 \ge 24≥2 , 9≥39 \ge 39≥3 .
[Predicates and Quantified Statements I] Which English expressions can be used for the symbol ∃\exists∃ ?
there exists, there is a, we can find a, there is at least one, for some, for at least one The words "such that" go just before the predicate: " ∃p∈P\exists p \in P∃p∈P such that ppp is a student in Math 140".
[Predicates and Quantified Statements I] Q(x)Q(x)Q(x) is a predicate with domain DDD . When is the existential statement " ∃x∈D\exists x \in D∃x∈D such that Q(x)Q(x)Q(x) " true, and when false?
True iff Q(x)Q(x)Q(x) is true for at least one xxx in DDD ; false iff Q(x)Q(x)Q(x) is false for all xxx in DDD . Example: " ∃m∈Z+\exists m \in \mathbf{Z}^+∃m∈Z+ such that m2=mm^2 = mm2=m " is true, since 12=11^2 = 112=1 .
[Predicates and Quantified Statements I] E={5,6,7,8}E = \{5, 6, 7, 8\}E={5,6,7,8} . Is " ∃m∈E\exists m \in E∃m∈E such that m2=mm^2 = mm2=m " true?
No. 25≠525 \ne 525=5 , 36≠636 \ne 636=6 , 49≠749 \ne 749=7 , 64≠864 \ne 864=8 : no element of EEE makes m2=mm^2 = mm2=m true.
[Predicates and Quantified Statements I] Write " ∀x∈R,x2≠−1\forall x \in \mathbf{R}, x^2 \ne -1∀x∈R,x2=−1 " informally, without "all".
No real numbers have squares equal to −1-1−1 . "None are" and "no ... are" mean the same as "all are not".
[Predicates and Quantified Statements I] In mathematics, how many positive integers does "Some positive integers equal their own squares" claim exist?
At least one. In ordinary English the plural might suggest at least two; in mathematics "some" means "at least one" whatever the grammatical number.
[Predicates and Quantified Statements I] What does it mean that a quantifier trails the rest of the sentence?
The quantification is placed at the end of the sentence. Example: " 2n2n2n is even for any integer nnn " instead of "For any integer nnn , 2n2n2n is even".Example: " x2≤0x^2 \le 0x2≤0 for some real number xxx ".
[Predicates and Quantified Statements I] Write formally, with quantifiers and variables: "No dogs have wings" and "Some programs are structured".
∀\forall∀ dogs ddd , ddd does not have wings. ∃\ \exists ∃ a program ppp such that ppp is structured. With DDD the set of dogs and PPP the set of programs: ∀d∈D\forall d \in D∀d∈D , ddd does not have wings; ∃p∈P\exists p \in P∃p∈P such that ppp is structured.
[Predicates and Quantified Statements I] What is a universal conditional statement?
A statement of the form " ∀x\forall x∀x , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) ". Arguably the most important form of statement in mathematics.Example: ∀x∈R\forall x \in \mathbf{R}∀x∈R , if x>2x > 2x>2 then x2>4x^2 > 4x2>4 .
[Predicates and Quantified Statements I] Write " ∀x∈R\forall x \in \mathbf{R}∀x∈R , if x>2x > 2x>2 then x2>4x^2 > 4x2>4 " informally, without quantifiers or variables.
If a real number is greater than 2, then its square is greater than 4. Or: The squares of all real numbers greater than 2 are greater than 4.
[Predicates and Quantified Statements I] Write in the form " ∀x\forall x∀x , if ___ then ___": "No fire trucks are green".
∀x\forall x∀x , if xxx is a fire truck, then xxx is not green. The domain of xxx is often left implicit in universal conditional statements.
[Predicates and Quantified Statements I] " ∀\forall∀ real numbers xxx , if x>2x > 2x>2 then x2>4x^2 > 4x2>4 " is true.How does this show that an if-then statement with a false hypothesis must be true?
The if-then statement must hold for every real xxx , including those with x≤2x \le 2x≤2 , such as "If 1>21 > 21>2 then 12>41^2 > 412>4 " and "If −3>2-3 > 2−3>2 then (−3)2>4(-3)^2 > 4(−3)2>4 ". Both have a false hypothesis; the first has a false conclusion, the second a true one. So both kinds must count as true.
[Predicates and Quantified Statements I] How can " ∀x∈U\forall x \in U∀x∈U , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) " be rewritten without if-then?
∀x∈D,Q(x)\forall x \in D, Q(x)∀x∈D,Q(x) , where DDD is the set of all xxx in UUU that make P(x)P(x)P(x) true. Conversely, " ∀x∈D,Q(x)\forall x \in D, Q(x)∀x∈D,Q(x) " can be written " ∀x\forall x∀x , if xxx is in DDD then Q(x)Q(x)Q(x) ".Example: " ∀x\forall x∀x , if xxx is a square then xxx is a rectangle" ≡\equiv≡ " ∀\forall∀ squares xxx , xxx is a rectangle".
[Predicates and Quantified Statements I] How can " ∃x\exists x∃x such that P(x)∧Q(x)P(x) \wedge Q(x)P(x)∧Q(x) " be rewritten with a narrower domain?
∃x∈D\exists x \in D∃x∈D such that Q(x)Q(x)Q(x) , where DDD is the set of all xxx for which P(x)P(x)P(x) is true. Example: " ∃n\exists n∃n such that Prime(n)∧Even(n)\text{Prime}(n) \wedge \text{Even}(n)Prime(n)∧Even(n) " ≡\equiv≡ " ∃\exists∃ a prime number nnn such that Even(n)\text{Even}(n)Even(n) " ≡\equiv≡ " ∃\exists∃ an even number nnn such that Prime(n)\text{Prime}(n)Prime(n) ".
[Predicates and Quantified Statements I] "If a number is an integer, then it is a rational number" contains no word like all, every, any or each. What shows that it is universally quantified?
The indefinite article "a". This is implicit universal quantification. Existential quantification can be implicit too: "24 can be written as a sum of two even integers" means " ∃\exists∃ even integers mmm and nnn such that 24=m+n24 = m + n24=m+n ".
[Predicates and Quantified Statements I] P(x)P(x)P(x) and Q(x)Q(x)Q(x) are predicates with common domain DDD . What do P(x)⇒Q(x)P(x) \Rightarrow Q(x)P(x)⇒Q(x) and P(x)⇔Q(x)P(x) \Leftrightarrow Q(x)P(x)⇔Q(x) mean?
P(x)⇒Q(x)P(x) \Rightarrow Q(x)P(x)⇒Q(x) Every element of the truth set of P(x)P(x)P(x) is in the truth set of Q(x)Q(x)Q(x) ; equivalently ∀x,P(x)→Q(x)\forall x, P(x) \to Q(x)∀x,P(x)→Q(x) . Example: x>2⇒x2>4x > 2 \Rightarrow x^2 > 4x>2⇒x2>4 for x∈Rx \in \mathbf{R}x∈R . P(x)⇔Q(x)P(x) \Leftrightarrow Q(x)P(x)⇔Q(x) P(x)P(x)P(x) and Q(x)Q(x)Q(x) have identical truth sets; equivalently ∀x,P(x)↔Q(x)\forall x, P(x) \leftrightarrow Q(x)∀x,P(x)↔Q(x) . Example: x2=1⇔∣x∣=1x^2 = 1 \Leftrightarrow |x| = 1x2=…
[Predicates and Quantified Statements I] The domain of nnn is Z+\mathbf{Z}^+Z+ . Q(n)Q(n)Q(n) : " nnn is a factor of 8", R(n)R(n)R(n) : " nnn is a factor of 4", S(n)S(n)S(n) : " n<5n < 5n<5 and n≠3n \ne 3n=3 ". Which relationships with ⇒\Rightarrow⇒ and ⇔\Leftrightarrow⇔ hold?
R(n)⇒Q(n)\boldsymbol{R(n) \Rightarrow Q(n)}R(n)⇒Q(n) , R(n)⇔S(n)\ \boldsymbol{R(n) \Leftrightarrow S(n)} R(n)⇔S(n) , S(n)⇒Q(n)\ \boldsymbol{S(n) \Rightarrow Q(n)} S(n)⇒Q(n) Truth sets: QQQ : {1,2,4,8}\{1, 2, 4, 8\}{1,2,4,8} ; RRR and SSS : {1,2,4}\{1, 2, 4\}{1,2,4} .
[Predicates and Quantified Statements I] A math text contains " (x+1)2=x2+2x+1(x + 1)^2 = x^2 + 2x + 1(x+1)2=x2+2x+1 " and "Solve 3x−4=53x - 4 = 53x−4=5 ". How is xxx quantified in each?
Universally in the first, existentially in the second. ∀\forall∀ real numbers xxx , (x+1)2=x2+2x+1(x + 1)^2 = x^2 + 2x + 1(x+1)2=x2+2x+1 . Show (by finding a value) that ∃\exists∃ a real number xxx such that 3x−4=53x - 4 = 53x−4=5 .
[Predicates and Quantified Statements I] What is Tarski's World?
A computer program by Jon Barwise and John Etchemendy for teaching logic. It shows blocks of various sizes, shapes and colors on a grid; the learner decides which statements about the blocks are true.Named after the logician Alfred Tarski (1902 to 1983).
[Predicates and Quantified Statements I] In this Tarski world (domain: the 11 objects), are these true? (a) ∀t,Triangle(t)→Blue(t)\forall t, \text{Triangle}(t) \to \text{Blue}(t)∀t,Triangle(t)→Blue(t) (b) ∀x,Blue(x)→Triangle(x)\forall x, \text{Blue}(x) \to \text{Triangle}(x)∀x,Blue(x)→Triangle(x)
(a) true, (b) false. (a): all the triangles a,c,ga, c, ga,c,g are blue.(b): counterexample eee , which is blue and is a square.
[Predicates and Quantified Statements I] In this Tarski world (domain: the 11 objects; RightOf(x,y)\text{RightOf}(x, y)RightOf(x,y) : xxx is to the right of yyy , possibly in a different row), are these true? (c) ∃y\exists y∃y such that Square(y)∧RightOf(d,y)\text{Square}(y) \wedge \text{RightOf}(d, y)Square(y)∧RightOf(d,y) (d) ∃z\exists z∃z such that Square(z)∧Gray(z)\text{Square}(z) \wedge \text{Gray}(z)Square(z)∧Gray(z)
(c) true, (d) false. (c): eee and hhh are squares, and ddd is to their right.(d): every square is blue ( eee ) or black ( hhh , jjj ).
[Predicates and Quantified Statements II] What is the negation of "All mathematicians wear glasses"?
There is at least one mathematician who does not wear glasses. "No mathematicians wear glasses" is not the negation: one mathematician without glasses already makes the original statement false.
[Predicates and Quantified Statements II] Negation of a universal statement ∼(∀x∈D,Q(x))≡ ?\sim(\forall x \in D, Q(x)) \equiv \; ?∼(∀x∈D,Q(x))≡?
∃x∈D such that ∼Q(x)\boldsymbol{\exists x \in D \text{ such that } \sim Q(x)}∃x∈D such that ∼Q(x) "All are" is negated by "some are not".Example: ∼(∀\sim(\forall∼(∀ primes ppp , ppp is odd )≡∃) \equiv \exists)≡∃ a prime ppp such that ppp is not odd.
[Predicates and Quantified Statements II] Negation of an existential statement ∼(∃x∈D such that Q(x))≡ ?\sim(\exists x \in D \text{ such that } Q(x)) \equiv \; ?∼(∃x∈D such that Q(x))≡?
∀x∈D,∼Q(x)\boldsymbol{\forall x \in D, \sim Q(x)}∀x∈D,∼Q(x) "Some are" is negated by "none are" (or "all are not").Example: ∼(∃\sim(\exists∼(∃ a triangle TTT such that the sum of the angles of TTT is 200∘)200^\circ)200∘) ≡\equiv≡ ∀\forall∀ triangles TTT , the sum of the angles of TTT is not 200∘200^\circ200∘ .
[Predicates and Quantified Statements II] What does logical equivalence of quantified statements mean?
The statements have identical truth values no matter which predicates are substituted for the predicate symbols and which sets are used as domains. Example: ∼(∀x∈D,Q(x))≡∃x∈D\sim(\forall x \in D, Q(x)) \equiv \exists x \in D∼(∀x∈D,Q(x))≡∃x∈D such that ∼Q(x)\sim Q(x)∼Q(x) , for every predicate QQQ and every set DDD .
[Predicates and Quantified Statements II] Write "No politicians are honest" formally, then give a formal and an informal negation.
Formal: ∀\forall∀ politicians xxx , xxx is not honest. Negation: ∃\exists∃ a politician xxx such that xxx is honest; informally: Some politicians are honest.
[Predicates and Quantified Statements II] When negating an informal statement, which question helps to avoid mistakes?
"What exactly would it mean for the statement to be false?" Rewriting the statement formally and applying the formal negation rule also helps.Example: "Some computer hackers are over 40" is false exactly when no computer hackers are over 40, i.e. all computer hackers are 40 or under.
[Predicates and Quantified Statements II] Negate "The number 1,357 is divisible by some integer between 1 and 37". Which is true, the statement or its negation?
Negation: 1,357 is not divisible by any integer between 1 and 37. The statement is true. 1357=23⋅591357 = 23 \cdot 591357=23⋅59 , so 23 divides 1,357.Formally: ∃\exists∃ an integer nnn between 1 and 37 such that 1,357 is divisible by nnn ; negation: ∀\forall∀ integers nnn between 1 and 37, 1,357 is not divisible by nnn .
[Predicates and Quantified Statements II] Why is "All mathematicians do not wear glasses" a poor negation of "All mathematicians wear glasses"?
It is ambiguous: read flatly, it means no mathematician wears glasses, which is stronger than the negation. "No mathematician wears glasses" implies the negation but is not equivalent to it.Only with stress on "not" does it mean the negation "some mathematician does not wear glasses".
[Predicates and Quantified Statements II] Negation of a universal conditional statement ∼(∀x, if P(x) then Q(x))≡ ?\sim(\forall x, \text{ if } P(x) \text{ then } Q(x)) \equiv \; ?∼(∀x, if P(x) then Q(x))≡?
∃x such that P(x) and ∼Q(x)\boldsymbol{\exists x \text{ such that } P(x) \text{ and } \sim Q(x)}∃x such that P(x) and ∼Q(x) Combine ∼(∀x,R(x))≡∃x\sim(\forall x, R(x)) \equiv \exists x∼(∀x,R(x))≡∃x such that ∼R(x)\sim R(x)∼R(x) with ∼(P(x)→Q(x))≡P(x)∧∼Q(x)\sim(P(x) \to Q(x)) \equiv P(x) \wedge \sim Q(x)∼(P(x)→Q(x))≡P(x)∧∼Q(x) .Example: ∼(∀\sim(\forall∼(∀ people ppp , if ppp is blond then ppp has blue eyes )≡∃) \equiv \exists)≡∃ a person ppp such that ppp is blond and ppp does not have blue eyes.
[Predicates and Quantified Statements II] Negate informally: "If a computer program has more than 100,000 lines, then it contains a bug."
There is at least one computer program that has more than 100,000 lines and does not contain a bug.
[Predicates and Quantified Statements II] Q(x)Q(x)Q(x) is a predicate whose domain is the finite set D={x1,x2,…,xn}D = \{x_1, x_2, \dots, x_n\}D={x1,x2,…,xn} . What are " ∀x∈D,Q(x)\forall x \in D, Q(x)∀x∈D,Q(x) " and " ∃x∈D\exists x \in D∃x∈D such that Q(x)Q(x)Q(x) " logically equivalent to?
Q(x1)∧Q(x2)∧⋯∧Q(xn)\boldsymbol{Q(x_1) \wedge Q(x_2) \wedge \dots \wedge Q(x_n)}Q(x1)∧Q(x2)∧⋯∧Q(xn) and Q(x1)∨Q(x2)∨⋯∨Q(xn)\boldsymbol{Q(x_1) \vee Q(x_2) \vee \dots \vee Q(x_n)}Q(x1)∨Q(x2)∨⋯∨Q(xn) So the negation rules for ∀\forall∀ and ∃\exists∃ generalize De Morgan's laws.Example: with D={0,1}D = \{0, 1\}D={0,1} , " ∀x∈D,x⋅x=x\forall x \in D, x \cdot x = x∀x∈D,x⋅x=x " means 0⋅0=00 \cdot 0 = 00⋅0=0 and 1⋅1=11 \cdot 1 = 11⋅1=1 ; " ∃x∈D\exists x \in D∃x∈D such that x+x=xx + x = xx+x=x " mea…
[Predicates and Quantified Statements II] When is " ∀x\forall x∀x in DDD , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) " vacuously true (true by default)?
When P(x)P(x)P(x) is false for every xxx in DDD . Example: " ∀x∈R\forall x \in \mathbf{R}∀x∈R , if x2<0x^2 < 0x2<0 then x=5x = 5x=5 " is vacuously true.
[Predicates and Quantified Statements II] A bowl contains no balls. Is "All the balls in the bowl are blue" true or false, and why?
True (vacuously): its negation "There exists a ball in the bowl that is not blue" is false, since there is no ball in the bowl. Left: three blue balls and one gray ball in the bowl, so the statement is false. Right: the bowl is empty, so the statement is true.
[Predicates and Quantified Statements II] What do the words "in general" signal in mathematics?
What follows is a generalization of the example just discussed that always holds. In ordinary language "in general" means "usually, but not always".
[Predicates and Quantified Statements II] Give the contrapositive, converse and inverse of " ∀x∈D\forall x \in D∀x∈D , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) ".
Contrapositive ∀x∈D\forall x \in D∀x∈D , if ∼Q(x)\sim Q(x)∼Q(x) then ∼P(x)\sim P(x)∼P(x) Example: ∀x∈R\forall x \in \mathbf{R}∀x∈R , if x2≤4x^2 \le 4x2≤4 then x≤2x \le 2x≤2 . Converse ∀x∈D\forall x \in D∀x∈D , if Q(x)Q(x)Q(x) then P(x)P(x)P(x) Example: ∀x∈R\forall x \in \mathbf{R}∀x∈R , if x2>4x^2 > 4x2>4 then x>2x > 2x>2 . Inverse ∀x∈D\forall x \in D∀x∈D , if ∼P(x)\sim P(x)∼P(x) then ∼Q(x)\sim Q(x)∼Q(x) Example: ∀x∈R\forall x \in \mathbf{R}∀x∈R , if x≤2x \le 2x≤2 then x2≤4x^2 \le 4x2≤4 . The e…
[Predicates and Quantified Statements II] Which of the contrapositive, converse and inverse of " ∀x∈D\forall x \in D∀x∈D , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) " is logically equivalent to it?
Only the contrapositive. Each xxx that makes "if P(x)P(x)P(x) then Q(x)Q(x)Q(x) " true also makes "if ∼Q(x)\sim Q(x)∼Q(x) then ∼P(x)\sim P(x)∼P(x) " true, since p→q≡∼q→∼pp \to q \equiv \sim q \to \sim pp→q≡∼q→∼p .Example: " ∀x∈R\forall x \in \mathbf{R}∀x∈R , if x>2x > 2x>2 then x2>4x^2 > 4x2>4 " is true, but its converse "if x2>4x^2 > 4x2>4 then x>2x > 2x>2 " and its inverse "if x≤2x \le 2x≤2 then x2≤4x^2 \le 4x2≤4 " are false: take x=−3x = -3x=−3 .
[Predicates and Quantified Statements II] r(x)r(x)r(x) and s(x)s(x)s(x) are predicates. What do " r(x)r(x)r(x) is a sufficient condition for s(x)s(x)s(x) ", " r(x)r(x)r(x) is a necessary condition for s(x)s(x)s(x) " and " r(x)r(x)r(x) only if s(x)s(x)s(x) " mean (each for all xxx )?
Sufficient condition ∀x\forall x∀x , if r(x)r(x)r(x) then s(x)s(x)s(x) Example: squareness is sufficient for rectangularity: ∀x\forall x∀x , if xxx is a square, then xxx is a rectangle. Necessary condition ∀x\forall x∀x , if ∼r(x)\sim r(x)∼r(x) then ∼s(x)\sim s(x)∼s(x) ; equivalently, ∀x\forall x∀x , if s(x)s(x)s(x) then r(x)r(x)r(x) Example: being at least 35 is necessary for being President of the United States: ∀\forall∀ people xxx , if xxx is President of the United States, then xxx is at l…
[Predicates and Quantified Statements II] Write as a universal conditional statement, without "necessary": "Being at least 35 years old is a necessary condition for being President of the United States."
∀\forall∀ people xxx , if xxx is younger than 35, then xxx cannot be President of the United States. Or, by the contrapositive: ∀\forall∀ people xxx , if xxx is President of the United States, then xxx is at least 35 years old.
[Predicates and Quantified Statements II] Write as a universal conditional statement: "A product of two numbers is 0 only if one of the numbers is 0."
If neither of two numbers is 0, then the product of the numbers is not 0. Or, by the contrapositive: if a product of two numbers is 0, then one of the numbers is 0.
[Predicates and Quantified Statements II] Complete the negations: "All RRR have property SSS " →\to→ "There is ___ RRR that ___." "Some RRR have property SSS " →\to→ "___."
There is some RRR that does not have property SSS . / No RRR have property SSS . Example: "All cats are black" →\to→ "Some cat is not black"; "Some cats are black" →\to→ "No cats are black".
[Statements with Multiple Quantifiers] A factory guide says: "There is a person supervising every detail of the production process." Which two meanings can this sentence have?
One single person supervises all the details, or each detail has some supervisor, possibly a different one for different details. Informal language is ambiguous here; only the context can decide which meaning was intended.
[Statements with Multiple Quantifiers] A statement that contains more than one quantifier is called multiply-quantified.
Example: " ∀\forall∀ nonzero real numbers uuu , ∃\exists∃ a real number vvv such that uv=1uv = 1uv=1 " contains two quantifiers.
[Statements with Multiple Quantifiers] What is the convention for interpreting a statement with more than one quantifier?
The actions suggested by the quantifiers are performed in the order in which the quantifiers occur. So in " ∀x\forall x∀x , ∃y\exists y∃y ..." xxx is chosen first and yyy is chosen afterwards, knowing xxx .
[Statements with Multiple Quantifiers] How do you establish the truth of a statement of the form ∀x∈D, ∃y∈E\forall x \in D, \ \exists y \in E∀x∈D, ∃y∈E such that P(x,y)P(x, y)P(x,y) ?
Someone else picks any x∈Dx \in Dx∈D ; then you must find a y∈Ey \in Ey∈E such that P(x,y)P(x, y)P(x,y) holds for that xxx . Because yyy is chosen after xxx , a different yyy may be used for each different xxx .Example: " ∀\forall∀ positive real numbers xxx , ∃\exists∃ a positive real number yyy such that y<xy < xy<x " is true: for any given xxx , choose y=x/2y = x/2y=x/2 .
[Statements with Multiple Quantifiers] How do you establish the truth of a statement of the form ∃x∈D\exists x \in D∃x∈D such that ∀y∈E, P(x,y)\forall y \in E, \ P(x, y)∀y∈E, P(x,y) ?
Find one particular x∈Dx \in Dx∈D such that P(x,y)P(x, y)P(x,y) holds for every y∈Ey \in Ey∈E anyone might choose. You are not allowed to change xxx after you have chosen it.Example: " ∃\exists∃ a positive integer mmm such that ∀\forall∀ positive integers nnn , m≤nm \le nm≤n " is true with m=1m = 1m=1 .
[Statements with Multiple Quantifiers] Circles a,ca, ca,c blue, bbb gray. Triangles ddd black, f,if, if,i gray. Squares eee black, g,hg, hg,h gray, jjj blue. "To the right of" means in a column further right.Is "For all triangles xxx , there is a square yyy such that xxx and yyy have the same color" true in this world?
True. Given triangle ddd (black), choose square eee (black). Given fff or iii (gray), choose square ggg or hhh (gray).
[Statements with Multiple Quantifiers] Circles a,ca, ca,c blue, bbb gray. Triangles ddd black, f,if, if,i gray. Squares eee black, g,hg, hg,h gray, jjj blue. "To the right of" means in a column further right.Is "There is a triangle xxx such that for all circles yyy , xxx is to the right of yyy " true in this world?
True: choose x=dx = dx=d or x=ix = ix=i . Both ddd and iii are in the fourth column, to the right of the circles aaa , bbb and ccc (columns 3, 1, 2).
[Statements with Multiple Quantifiers] Uta, Tim and Yuen chose these cafeteria items. Stations: salads, main courses, desserts, beverages.Write informally and find the truth value: (a) ∃\exists∃ an item III such that ∀\forall∀ students SSS , SSS chose III . (b) ∃\exists∃ a student SSS such that ∀\forall∀ items III , SSS chose III .
(a) Some item was chosen by every student: true (pie). \; (b) Some student chose every item: false. (b) is false because no student chose all nine items.
[Statements with Multiple Quantifiers] Uta, Tim and Yuen chose these cafeteria items. Stations: salads, main courses, desserts, beverages.Write informally and find the truth value: (a) ∃\exists∃ a student SSS such that ∀\forall∀ stations ZZZ , ∃\exists∃ an item III in ZZZ such that SSS chose III . (b) ∀\forall∀ students SSS and ∀\forall∀ stations ZZZ , ∃\exists∃ an item III in ZZZ such that SSS chose III .
(a) Some student chose an item from every station: true. \; (b) Every student chose an item from every station: false. (a) Uta and Tim both did. (b) Yuen chose no salad.
[Statements with Multiple Quantifiers] The reciprocal of a real number aaa is a real number bbb with ab=1ab = 1ab=1 . Write formally with quantifiers: (a) Every nonzero real number has a reciprocal. (b) There is a real number with no reciprocal.
(a) ∀\forall∀ nonzero real numbers uuu , ∃\exists∃ a real number vvv such that uv=1uv = 1uv=1 . (b) ∃\exists∃ a real number ccc such that ∀\forall∀ real numbers ddd , cd≠1cd \ne 1cd=1 . Both are true; in (b), c=0c = 0c=0 .
[Statements with Multiple Quantifiers] Write "There is a smallest positive integer" formally, using both ∃\exists∃ and ∀\forall∀ . Is it true?
∃\exists∃ a positive integer mmm such that ∀\forall∀ positive integers nnn , m≤nm \le nm≤n . True. m=1m = 1m=1 is less than or equal to every positive integer.
[Statements with Multiple Quantifiers] Write "There is no smallest positive real number" formally, using both ∀\forall∀ and ∃\exists∃ . Why is it true?
∀\forall∀ positive real numbers xxx , ∃\exists∃ a positive real number yyy such that y<xy < xy<x . For any positive xxx , the number y=x/2y = x/2y=x/2 satisfies 0<x/2<x0 < x/2 < x0<x/2<x .Example: for x=0.001x = 0.001x=0.001 , y=0.0005y = 0.0005y=0.0005 .
[Statements with Multiple Quantifiers] Write formally: the limit of the sequence ana_nan as nnn goes to infinity equals LLL ( limn→∞an=L\lim_{n \to \infty} a_n = Llimn→∞an=L ).
∀ε>0\forall \varepsilon > 0∀ε>0 , ∃\exists∃ an integer NNN such that ∀\forall∀ integers nnn , if n>Nn > Nn>N then L−ε<an<L+εL - \varepsilon < a_n < L + \varepsilonL−ε<an<L+ε . Informally: ana_nan gets arbitrarily close to LLL as nnn grows without bound.Example: for an=1/na_n = 1/nan=1/n and L=0L = 0L=0 , given ε\varepsilonε choose any integer N≥1/εN \ge 1/\varepsilonN≥1/ε .
[Statements with Multiple Quantifiers] What is the negation of ∀x∈D, ∃y∈E\forall x \in D, \ \exists y \in E∀x∈D, ∃y∈E such that P(x,y)P(x, y)P(x,y) ?
∃x∈D\exists x \in D∃x∈D such that ∀y∈E, ∼P(x,y)\forall y \in E, \ \sim P(x, y)∀y∈E, ∼P(x,y) . Apply the negation rules for single quantifiers from left to right: first ∃x∈D\exists x \in D∃x∈D such that ∼(∃y∈E\sim(\exists y \in E∼(∃y∈E such that P(x,y))P(x, y))P(x,y)) .Example: the negation of "every person loves somebody" is "some person loves nobody".
[Statements with Multiple Quantifiers] What is the negation of ∃x∈D\exists x \in D∃x∈D such that ∀y∈E, P(x,y)\forall y \in E, \ P(x, y)∀y∈E, P(x,y) ?
∀x∈D, ∃y∈E\forall x \in D, \ \exists y \in E∀x∈D, ∃y∈E such that ∼P(x,y)\sim P(x, y)∼P(x,y) . Apply the negation rules for single quantifiers from left to right: first ∀x∈D, ∼(∀y∈E, P(x,y))\forall x \in D, \ \sim(\forall y \in E, \ P(x, y))∀x∈D, ∼(∀y∈E, P(x,y)) .Example: the negation of "there is a smallest positive integer" ( ∃m ∀n, m≤n\exists m \ \forall n, \ m \le n∃m ∀n, m≤n ) is " ∀\forall∀ positive integers mmm , ∃\exists∃ a positive integer nnn such that m>nm > nm>n ".
[Statements with Multiple Quantifiers] Circles a,ca, ca,c blue, bbb gray. Triangles ddd black, f,if, if,i gray. Squares eee black, g,hg, hg,h gray, jjj blue. "To the right of" means in a column further right.Negate "For all squares xxx , there is a circle yyy such that xxx and yyy have the same color". Which is true, the statement or its negation?
∃\exists∃ a square xxx such that ∀\forall∀ circles yyy , xxx and yyy do not have the same color. The negation is true. Square eee is black and no circle is black.
[Statements with Multiple Quantifiers] Circles a,ca, ca,c blue, bbb gray. Triangles ddd black, f,if, if,i gray. Squares eee black, g,hg, hg,h gray, jjj blue. "To the right of" means in a column further right.Negate "There is a triangle xxx such that for all squares yyy , xxx is to the right of yyy ". Which is true, the statement or its negation?
∀\forall∀ triangles xxx , ∃\exists∃ a square yyy such that xxx is not to the right of yyy . The negation is true. No triangle is to the right of square ggg (or jjj ), which are in the rightmost column.
[Statements with Multiple Quantifiers] How do these two statements differ in meaning? (1) ∀\forall∀ people xxx , ∃\exists∃ a person yyy such that xxx loves yyy . (2) ∃\exists∃ a person yyy such that ∀\forall∀ people xxx , xxx loves yyy .
(1) Everybody loves somebody (possibly different people). (2) There is one person whom everybody loves. The statements differ only in the order of the quantifiers.
[Statements with Multiple Quantifiers] Does changing the order of the quantifiers change the meaning of a statement?
For ∀\forall∀ and ∃\exists∃ : usually yes. For two quantifiers of the same type: no. Reversing ∀\forall∀ and ∃\exists∃ can change the truth value to its opposite.Example: " ∀\forall∀ real numbers xxx and ∀\forall∀ real numbers yyy , x+y=y+xx + y = y + xx+y=y+x " means the same as " ∀\forall∀ real numbers yyy and ∀\forall∀ real numbers xxx , x+y=y+xx + y = y + xx+y=y+x ".
[Statements with Multiple Quantifiers] Circles a,ca, ca,c blue, bbb gray. Triangles ddd black, f,if, if,i gray. Squares eee black, g,hg, hg,h gray, jjj blue. "To the right of" means in a column further right.Do these two statements have the same truth value? (a) For every square xxx there is a triangle yyy such that xxx and yyy have different colors. (b) There exists a triangle yyy such that for every square xxx , xxx and yyy have different colors.
No: (a) is true, (b) is false. (a) For ggg or hhh (gray) choose ddd (black); for eee (black) choose fff or iii (gray); for jjj (blue) choose any triangle.(b) The gray triangles f,if, if,i fail for the gray squares, and the black triangle ddd fails for the black square eee .
[Statements with Multiple Quantifiers] P(x,y)P(x, y)P(x,y) is a property involving xxx and yyy , and " ∀x∈D, ∃y∈E\forall x \in D, \ \exists y \in E∀x∈D, ∃y∈E such that P(x,y)P(x, y)P(x,y) " is true. Is " ∃x∈D\exists x \in D∃x∈D such that ∀y∈E, P(x,y)\forall y \in E, \ P(x, y)∀y∈E, P(x,y) " true?
It may be true or false, depending on the property P(x,y)P(x, y)P(x,y) . Example: " ∀x∈R,∃y∈R\forall x \in \mathbb{R}, \exists y \in \mathbb{R}∀x∈R,∃y∈R such that x+y=0x + y = 0x+y=0 " is true, but " ∃x∈R\exists x \in \mathbb{R}∃x∈R such that ∀y∈R, x+y=0\forall y \in \mathbb{R}, \ x + y = 0∀y∈R, x+y=0 " is false.Example: " ∀x∈R,∃y∈R\forall x \in \mathbb{R}, \exists y \in \mathbb{R}∀x∈R,∃y∈R such that x⋅y=0x \cdot y = 0x⋅y=0 " and " ∃x∈R\exists x \in \mathbb{R}∃x∈R such that ∀y∈R, x⋅y=0\forall y…
[Statements with Multiple Quantifiers] In formal logical notation (no words "in" and "such that"), how are " ∀x\forall x∀x in DDD , P(x)P(x)P(x) " and " ∃x\exists x∃x in DDD such that P(x)P(x)P(x) " written?
∀x (x∈D→P(x))\forall x \, (x \in D \to P(x))∀x(x∈D→P(x)) and ∃x (x∈D∧P(x))\exists x \, (x \in D \wedge P(x))∃x(x∈D∧P(x)) All properties of variables, including membership in DDD , are described by predicates.
[Statements with Multiple Quantifiers] Domain: the objects of a Tarski world. Predicates Circle(x)\text{Circle}(x)Circle(x) , Above(x,y)\text{Above}(x, y)Above(x,y) (" xxx is above yyy "), and fff is a particular object.Write "For all circles xxx , xxx is above fff " and its negation in formal logical notation.
∀x (Circle(x)→Above(x,f))\forall x \, (\text{Circle}(x) \to \text{Above}(x, f))∀x(Circle(x)→Above(x,f)) ; negation ∃x (Circle(x)∧∼Above(x,f))\exists x \, (\text{Circle}(x) \wedge \sim\text{Above}(x, f))∃x(Circle(x)∧∼Above(x,f)) First ∃x∼(Circle(x)→Above(x,f))\exists x \sim(\text{Circle}(x) \to \text{Above}(x, f))∃x∼(Circle(x)→Above(x,f)) by negating ∀\forall∀ , then the negation of an if-then statement: ∼(p→q)≡p∧∼q\sim(p \to q) \equiv p \wedge \sim q∼(p→q)≡p∧∼q .
[Statements with Multiple Quantifiers] Domain: the objects of a Tarski world. Predicates Square(x)\text{Square}(x)Square(x) , Black(x)\text{Black}(x)Black(x) .Write "There is a square xxx such that xxx is black" and its negation in formal logical notation.
∃x (Square(x)∧Black(x))\exists x \, (\text{Square}(x) \wedge \text{Black}(x))∃x(Square(x)∧Black(x)) ; negation ∀x (∼Square(x)∨∼Black(x))\forall x \, (\sim\text{Square}(x) \vee \sim\text{Black}(x))∀x(∼Square(x)∨∼Black(x)) First ∀x∼(Square(x)∧Black(x))\forall x \sim(\text{Square}(x) \wedge \text{Black}(x))∀x∼(Square(x)∧Black(x)) by negating ∃\exists∃ , then De Morgan's law.
[Statements with Multiple Quantifiers] Domain: the objects of a Tarski world. Predicates Circle(x)\text{Circle}(x)Circle(x) , Square(x)\text{Square}(x)Square(x) , SameColor(x,y)\text{SameColor}(x, y)SameColor(x,y) .Write "For all circles xxx , there is a square yyy such that xxx and yyy have the same color" in formal logical notation.
∀x (Circle(x)→∃y (Square(y)∧SameColor(x,y)))\forall x \, (\text{Circle}(x) \to \exists y \, (\text{Square}(y) \wedge \text{SameColor}(x, y)))∀x(Circle(x)→∃y(Square(y)∧SameColor(x,y))) Negation: ∃x (Circle(x)∧∀y (∼Square(y)∨∼SameColor(x,y)))\exists x \, (\text{Circle}(x) \wedge \forall y \, (\sim\text{Square}(y) \vee \sim\text{SameColor}(x, y)))∃x(Circle(x)∧∀y(∼Square(y)∨∼SameColor(x,y))) .
[Statements with Multiple Quantifiers] Domain: the objects of a Tarski world. Predicates Square(x)\text{Square}(x)Square(x) , Triangle(x)\text{Triangle}(x)Triangle(x) , RightOf(x,y)\text{RightOf}(x, y)RightOf(x,y) .Write "There is a square xxx such that for all triangles yyy , xxx is to the right of yyy " in formal logical notation.
∃x (Square(x)∧∀y (Triangle(y)→RightOf(x,y)))\exists x \, (\text{Square}(x) \wedge \forall y \, (\text{Triangle}(y) \to \text{RightOf}(x, y)))∃x(Square(x)∧∀y(Triangle(y)→RightOf(x,y))) Negation: ∀x (∼Square(x)∨∃y (Triangle(y)∧∼RightOf(x,y)))\forall x \, (\sim\text{Square}(x) \vee \exists y \, (\text{Triangle}(y) \wedge \sim\text{RightOf}(x, y)))∀x(∼Square(x)∨∃y(Triangle(y)∧∼RightOf(x,y))) .Steps of the negation: negate ∃\exists∃ , De Morgan's law, negate ∀\forall∀ , negate the if-then statement.
[Statements with Multiple Quantifiers] What is the disadvantage and what is the advantage of fully formal logical notation?
Disadvantage: errors can go unrecognized. Advantage: operations such as negation become mechanical. The notation is far from intuitive understanding, but its operations can be programmed on a computer. Formal notation is used in artificial intelligence, program verification, and automata theory and formal languages.
[Statements with Multiple Quantifiers] The symbols for quantifiers, variables, predicates and logical connectives together make up the language of first-order logic.
[Statements with Multiple Quantifiers] What is Prolog, and what does a simple Prolog program consist of?
A programming language ("programming in logic") whose programs are statements describing a situation plus questions about it. Search and inference are built into the language, so Prolog derives the answers from the statements. Developed in France in the 1970s by A. Colmerauer and P. Roussel for artificial intelligence.
[Statements with Multiple Quantifiers] Prolog statements: isabove (g,b1)(g, b_1)(g,b1) , isabove (b1,w1)(b_1, w_1)(b1,w1) , isabove (w2,b2)(w_2, b_2)(w2,b2) , isabove (b2,b3)(b_2, b_3)(b2,b3) , and isabove (X,Z)(X, Z)(X,Z) if isabove (X,Y)(X, Y)(X,Y) and isabove (Y,Z)(Y, Z)(Y,Z) .What does Prolog answer to ?isabove (X,w1)(X, w_1)(X,w1) , and how does it find each answer?
X=b1X = b_1X=b1 , X=gX = gX=g X=b1X = b_1X=b1 is a given fact. X=gX = gX=g must be inferred: ggg is above b1b_1b1 , b1b_1b1 is above w1w_1w1 , and the rule "if XXX is above YYY and YYY is above ZZZ , then XXX is above ZZZ ". The blocks described by the statements.
[Statements with Multiple Quantifiers] Prolog statements: isabove (g,b1)(g, b_1)(g,b1) , isabove (b1,w1)(b_1, w_1)(b1,w1) , isabove (w2,b2)(w_2, b_2)(w2,b2) , isabove (b2,b3)(b_2, b_3)(b2,b3) , isabove (X,Z)(X, Z)(X,Z) if isabove (X,Y)(X, Y)(X,Y) and isabove (Y,Z)(Y, Z)(Y,Z) ; color (g(g(g , gray ))) , color (b1(b_1(b1 , blue ))) , color (b2(b_2(b2 , blue ))) , color (b3(b_3(b3 , blue ))) , color (w1(w_1(w1 , white ))) , color (w2(w_2(w2 , white ))) .What does Prolog answer to (a) ?…
(a) No \; (b) XXX = white \; (c) X=b1X = b_1X=b1 , X=b2X = b_2X=b2 , X=b3X = b_3X=b3 (a) asks "Is b2b_2b2 above w1w_1w1 ?"; b2b_2b2 is in the other stack.
[Arguments with Quantified Statements] What does the rule of universal instantiation say?
If some property is true of everything in a set, then it is true of any particular thing in the set. Example: All men are mortal. Socrates is a man. ∴\therefore∴ Socrates is mortal.
[Arguments with Quantified Statements] Why is universal instantiation called the fundamental tool of deductive reasoning?
Formulas, definitions and theorems state general truths, and every use of one on a particular object is an instance of universal instantiation. Example: from " ∀\forall∀ real numbers xxx , x1=xx^1 = xx1=x " and " rrr is a particular real number", conclude r1=rr^1 = rr1=r .
[Arguments with Quantified Statements] rrr is a particular real number and kkk a particular integer. Which universal truths are instantiated to simplify rk+1⋅rr^{k+1} \cdot rrk+1⋅r , and what is the result?
x1=xx^1 = xx1=x for all real xxx , and xm⋅xn=xm+nx^m \cdot x^n = x^{m+n}xm⋅xn=xm+n for all real xxx and integers m,nm, nm,n . Result: rk+2r^{k+2}rk+2 . rk+1⋅r=rk+1⋅r1=r(k+1)+1=rk+2r^{k+1} \cdot r = r^{k+1} \cdot r^1 = r^{(k+1)+1} = r^{k+2}rk+1⋅r=rk+1⋅r1=r(k+1)+1=rk+2 .
[Arguments with Quantified Statements] State universal modus ponens (formal version).
∀x\forall x∀x , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) . P(a)\;P(a)P(a) for a particular aaa . ∴Q(a)\;\therefore Q(a)∴Q(a) . Informally: if xxx makes P(x)P(x)P(x) true, then xxx makes Q(x)Q(x)Q(x) true; aaa makes P(x)P(x)P(x) true; therefore aaa makes Q(x)Q(x)Q(x) true.It combines universal instantiation with modus ponens. The first premise is called the major premise, the second the minor premise.
[Arguments with Quantified Statements] Rewrite with quantifiers, variables and predicate symbols. Is the argument valid? "If an integer is even, then its square is even. kkk is a particular integer that is even. ∴k2\therefore k^2∴k2 is even."
∀x\forall x∀x , if E(x)E(x)E(x) then S(x)S(x)S(x) . E(k)\;E(k)E(k) . ∴S(k)\;\therefore S(k)∴S(k) . Valid, by universal modus ponens. E(x)E(x)E(x) : " xxx is an even integer"; S(x)S(x)S(x) : " x2x^2x2 is even".
[Arguments with Quantified Statements] What conclusion follows by universal modus ponens? "If TTT is any right triangle with hypotenuse ccc and legs aaa and bbb , then c2=a2+b2c^2 = a^2 + b^2c2=a2+b2 . The triangle TTT is a right triangle with both legs equal to 1 and hypotenuse ccc ."
c2=12+12=2\boldsymbol{c^2 = 1^2 + 1^2 = 2}c2=12+12=2 So c=2c = \sqrt{2}c=2 : there is a line segment whose length is 2\sqrt{2}2 .
[Arguments with Quantified Statements] Prove that the sum of any two even integers is even. (An integer is even if and only if it equals twice some integer.)
Let m,nm, nm,n be particular but arbitrarily chosen even integers; m=2rm = 2rm=2r , n=2sn = 2sn=2s for some integers r,sr, sr,s , so m+n=2(r+s)m + n = 2(r + s)m+n=2(r+s) , which is even since r+sr + sr+s is an integer. Each step of this proof is an argument by universal modus ponens.
[Arguments with Quantified Statements] Proof that the sum of two even integers m,nm, nm,n is even: m=2rm = 2rm=2r , n=2sn = 2sn=2s for some integers r,sr, sr,s ; m+n=2r+2s=2(r+s)m + n = 2r + 2s = 2(r + s)m+n=2r+2s=2(r+s) ; r+sr + sr+s is an integer, so 2(r+s)2(r + s)2(r+s) is even.Which universal statements does universal modus ponens apply to in the steps of this proof?
m=2rm = 2rm=2r , n=2sn = 2sn=2s If an integer is even, then it equals twice some integer. 2r+2s=2(r+s)2r + 2s = 2(r + s)2r+2s=2(r+s) If a quantity is an integer, then it is a real number; and for all real numbers a,b,ca, b, ca,b,c : ab+ac=a(b+c)ab + ac = a(b + c)ab+ac=a(b+c) . r+sr + sr+s is an integer For all integers uuu and vvv , u+vu + vu+v is an integer. 2(r+s)2(r + s)2(r+s) is even If a number equals twice some integer, then that number is even.
[Arguments with Quantified Statements] What does the principle of existential instantiation say?
If we know that something exists, we may give it a name. Example: mmm is even, so some integer rrr satisfies m=2rm = 2rm=2r ; the proof then calls that integer rrr .
[Arguments with Quantified Statements] State universal modus tollens (formal version).
∀x\forall x∀x , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) . ∼Q(a)\;\sim Q(a)∼Q(a) , for a particular aaa . ∴∼P(a)\;\therefore \sim P(a)∴∼P(a) . It combines universal instantiation with modus tollens, and it is the heart of proof by contradiction.Example: All human beings are mortal. Zeus is not mortal. ∴\therefore∴ Zeus is not human.
[Arguments with Quantified Statements] Rewrite with quantifiers, variables and predicate symbols, with the major premise in conditional form. Is the argument valid? "All human beings are mortal. Zeus is not mortal. ∴\therefore∴ Zeus is not human."
∀x\forall x∀x , if H(x)H(x)H(x) then M(x)M(x)M(x) . ∼M(Z)\;\sim M(Z)∼M(Z) . ∴∼H(Z)\;\therefore \sim H(Z)∴∼H(Z) . Valid, by universal modus tollens. H(x)H(x)H(x) : " xxx is human"; M(x)M(x)M(x) : " xxx is mortal"; ZZZ : Zeus.
[Arguments with Quantified Statements] What conclusion follows by universal modus tollens? "All professors are absent-minded. Tom Hutchins is not absent-minded."
Tom Hutchins is not a professor.
[Arguments with Quantified Statements] When is an argument form with predicates valid?
When for every choice of predicates substituted for its predicate symbols, true premises give a true conclusion. An argument is valid if and only if its form is valid.
[Arguments with Quantified Statements] Universal modus ponens: ∀x\forall x∀x , if P(x)P(x)P(x) then Q(x)Q(x)Q(x) . P(a)\;P(a)P(a) for a particular aaa . ∴Q(a)\;\therefore Q(a)∴Q(a) .How does the proof that universal modus ponens is valid go?
Assume both premises are true. By universal instantiation, "if P(a)P(a)P(a) then Q(a)Q(a)Q(a) " is true; with P(a)P(a)P(a) true, modus ponens gives Q(a)Q(a)Q(a) . So the laws of logic are used to prove that the laws of logic are valid.
[Arguments with Quantified Statements] How is the statement " ∀x∈D, Q(x)\forall x \in D, \ Q(x)∀x∈D, Q(x) " represented by a diagram?
The disk for DDD is drawn entirely inside the disk for the elements that make Q(x)Q(x)Q(x) true. Example: "All integers are rational numbers": " ∀x∈D, Q(x)\forall x \in D, \ Q(x)∀x∈D, Q(x) " and " ∀x\forall x∀x , if xxx is in DDD then Q(x)Q(x)Q(x) " are logically equivalent, so both have this kind of diagram.
[Arguments with Quantified Statements] How do you test the validity of an argument with diagrams?
Represent the truth of both premises with diagrams, then check whether the diagrams necessarily represent the truth of the conclusion as well. If some way of combining the premise diagrams makes the conclusion false, the argument is invalid.
[Arguments with Quantified Statements] Who was perhaps the first to analyze arguments with diagrams of sets as disks?
Gottfried Wilhelm Leibniz (1646 to 1716). He also developed the main ideas of calculus at about the same time as, and independently of, Isaac Newton.