Discrete Math › Section B · Logic and proofs › Topic B.1

Statements, connectives, and quantifiers

Mathematics is written in statements, and their logical shape decides when they are true. This topic builds compound statements from five connectives, then adds quantifiers, the phrases "for all" and "there exists", which let one statement speak about every element of a set or only some of them.

Why logic comes first

Mathematics establishes general facts by proof, and a proof is a special kind of argument: premises that lead, step by step, to a conclusion. An argument is valid when its conclusion must be true whenever all its premises are true, and sound when it is valid and its premises really are true. These are the definitions used in the philosophy topic Arguments, validity, and soundness. To judge an argument you must first read its statements exactly: how each is built and what makes it true.

Statements

A statement is a declarative sentence with a definite truth value, true or false. "91 is prime" is a statement, and a false one, since \(91 = 7 \times 13\). "There are infinitely many pairs of primes that differ by 2" is one too: nobody yet knows its truth value, but it has one. These are not statements: "Is 91 prime?" (a question), "Factor 91" (a command), "the largest prime below 100" (a noun phrase) and \(2x - 1 = 9\), which is true or false only once x is known. A statement is atomic if it cannot be split into smaller statements, and molecular if it is built from smaller ones.

Five connectives

Molecular statements are built with logical connectives. Writing P, Q and R for statements, as in the philosophy topic Logical statements, the five connectives are: conjunction \(P \wedge Q\), "P and Q"; disjunction \(P \vee Q\), "P or Q"; the conditional or implication \(P \to Q\), "if P, then Q"; the biconditional \(P \leftrightarrow Q\), "P if and only if Q"; and negation \(\neg P\), "not P". The first four are binary, joining two statements; negation is unary. Crucially, a molecular statement's truth value depends only on the truth values of its parts, not on what they say.

Truth conditions

A truth table lists the value of a statement for every combination of values of its parts:

\begin{array}{cc|c|c|c|c} P & Q & P \wedge Q & P \vee Q & P \to Q & P \leftrightarrow Q \\ \hline T & T & T & T & T & T \\ T & F & F & T & F & F \\ F & T & F & T & T & F \\ F & F & F & F & T & T \end{array}

Negation simply flips the value. Mathematical "or" is inclusive: \(P \vee Q\) is true when both parts are true. The conditional is false only when P is true and Q is false, and the biconditional is true when the two parts match. The next topic, Implications and related statements, explains why the conditional's table must look like this.

Worked example: evaluating compound statements

Let P be "91 is prime", Q be "91 is odd" and R be "64 is a perfect square". Find the truth value of each compound. 1. Settle the parts: P is false, Q is true, R is true, since \(64 = 8^2\). 2. \(P \vee Q\) is true, because one true part is enough. 3. \(P \wedge Q\) is false, because P is false. 4. \(\neg P \wedge R\) is true: both \(\neg P\) and R are true. 5. \(Q \to P\) is false: a true hypothesis with a false conclusion. 6. \(P \to R\) is true, since its hypothesis P is false. 7. \(Q \leftrightarrow R\) is true, as both parts are true.

Translating ordinary language

English hides logical structure, so translate with care. "But" means and: with P "7 is prime" and Q "9 is prime", "7 is prime but 9 is not" is \(P \wedge \neg Q\). "Neither P nor Q" is \(\neg P \wedge \neg Q\). "Exactly one of P and Q" is exclusive or, which needs two connectives: \((P \vee Q) \wedge \neg(P \wedge Q)\). With P "6 is prime" and Q "7 is prime", that statement is true. Each part must itself be a statement: "6 and 9 are multiples of 3" splits into "6 is a multiple of 3" and "9 is a multiple of 3".

Predicates

Many mathematical sentences contain variables. A predicate is a sentence with one or more free variables, written like a function with a capital letter: let \(P(x)\) mean "x is a perfect square". A predicate is neither true nor false until its variable is dealt with. Substituting a value gives a statement: \(P(9)\) is true and \(P(10)\) is false. A predicate can have several variables, as \(x < y\) does, and then every variable must be given a value or quantified before the sentence has a truth value.

Quantifiers and the domain

The universal quantifier \(\forall\) reads "for all", and the existential quantifier \(\exists\) reads "there exists" or "for some". The statement \(\forall x\, P(x)\) is true when \(P(a)\) is true for every value a in the domain of discourse, the set the variable ranges over. The statement \(\exists x\, P(x)\) is true when \(P(a)\) is true for at least one a. The domain can change the answer: \(\exists x\,(x + 3 = 1)\) is false over the natural numbers but true over the integers, where \(x = -2\). So always state the domain, or make sure the context fixes it.

Every and some

"Every A is a B" becomes \(\forall x\,(A(x) \to B(x))\): for anything at all, if it is an A, then it is a B. Using \(\wedge\) instead would wrongly claim that everything is an A. "Some A is a B" becomes \(\exists x\,(A(x) \wedge B(x))\): something is both. Using \(\to\) here would make the statement true merely because something is not an A. "No A is a B" becomes \(\forall x\,(A(x) \to \neg B(x))\). By convention, an open sentence stated as a fact, such as "if x is a multiple of 4, then x is even", means its universal generalisation, with \(\forall x\) in front.

Worked example: the order of quantifiers

Over the natural numbers, decide each statement. 1. \(\forall x\, \exists y\,(y > x)\): for any x, choose \(y = x + 1\), which is larger, so it is true. 2. \(\exists y\, \forall x\,(y > x)\): this claims one number larger than every number, itself included, but \(y > y\) is false, so it is false. 3. Compare: in step 1, y may depend on x; in step 2, a single y must work for every x. Swapping the quantifiers changed the meaning. 4. \(\forall x\, \exists y\,(x + y = 0)\): for \(x = 1\) we would need \(y = -1\), not a natural number, so it is false; over the integers it is true.

Common mistakes to avoid

First, treating a sentence with a free variable, such as \(2x - 1 = 9\), as a statement. Second, reading "or" as exclusive; in logic it is inclusive unless "but not both" is stated. Third, translating "every A is a B" with \(\wedge\), or "some A is a B" with \(\to\). Fourth, swapping the order of different quantifiers as if nothing changed. Fifth, confusing "every number is even or odd", which is true, with "every number is even, or every number is odd", which is false. Sixth, ignoring the domain of discourse.

Key takeaways

A statement is a declarative sentence that is true or false; molecular statements are built from atomic ones with \(\wedge\), \(\vee\), \(\to\), \(\leftrightarrow\) and \(\neg\), and their truth values follow from the truth table. "Or" is inclusive. A predicate becomes a statement when its variables are given values or quantified, with \(\forall\) (for all) or \(\exists\) (there exists) over a stated domain. "Every A is a B" uses \(\to\), "some A is a B" uses \(\wedge\), and the order of quantifiers matters.

Flashcards

Flashcard

Statement

A declarative sentence with a definite truth value

Questions, commands and open sentences are not statements.

Test your understanding

Question 1 of 5

Which of these is a statement?

Question 2 of 5

Let P be "10 is prime" and Q be "10 is even". Which compound statement is true?

Question 3 of 5

With P(x) meaning "x is prime" and E(x) meaning "x is even", which formula says "Some primes are even"?

Question 4 of 5

The domain is the natural numbers {0, 1, 2, ...}. Which statement is true?

Question 5 of 5

Let P be "4 is prime" and Q be "9 is prime". Which formula says "Neither 4 nor 9 is prime"?

← Previous topicNext topic →