Logic and Proofs

Introduction to logic

A proposition is a statement which is either true or false. For example:

1. “The sun is a star."
2. "The moon is made of cheese."
3. " $2+2=4$ ."
4. " $2+3=7$ ."
5. "Every even integer greater than 4 is the sum of two prime numbers."
6. " $2>3$ or $2<3$ ."
7. "If the world is flat then $2+2=4$ .”

We only insist that the statement is true or false, we do not need to know which it is. Notice that the last two examples are formed by combining simpler propositions, namely "$2>3$ ", "$2<3$ ", “The world is flat”, and "$2+2=4$ ". A proposition which has been built up in this way is called a compound proposition, as opposed to a simple proposition which cannot be split into simpler propositions.

1. ” $2x=100$ "
2. " $2x=100$ for some integer $x$ "
3. "Shake well before opening"
4. "CompSci 225 is the largest course at the University of Auckland”

We typically use letters like $p$ , $q$ and $r$ to stand for simple propositions: we call these propositional variables. We usually use capital letters like $A$ , $B$ and $C$ to denote compound propositions, or propositions which might be simple or might be compound.

When we want to build more complicated propositions out of simpler ones, we use connectives. If $A$ and $B$ are propositions, then so are the following:

We read these as “not $A$ ”, ”$A$ and $B$ ”, ”$A$ or $B$ ”, ”$A$ implies $B$ ” (or “if $A$ then $B$ ”) and ”$A$ is equivalent to $B$ ” (or ”$A$ if and only if $B$ ”) respectively. We can combine compound propositions into more and more complicated propositions. For example, if $p$ denotes the proposition “It is raining”, $q$ denotes the proposition “The sun is shining” and $r$ denotes the proposition “There is a rainbow”, then $(p\land q)\to r$ represents the proposition “If it is raining and the sun is shining, then there is a rainbow”, while $(p\land \lnot r)\to\lnot q$ represents the proposition “If it is raining and there is no rainbow, then the sun is not shining”.

Solution. Let $p$ denote the proposition “You drink”.\ Let $q$ denote the proposition “You drive”.\ Let $r$ denote the proposition “You’re a bloody idiot”\ Then the slogan can be expressed as\

Truth values

We refer to the truth or falsity of a proposition as its truth value. The truth value of a compound proposition depends only on the truth or falsity of the propositions from which it was built, according to rules which we can give for each connective. We will consider these in detail later, but we can summarize them in the following table, which we call a “truth table”. In this table, 0 represents “false” and 1 represents “true”.

The truth value of a compound proposition depends on the truth values of the propositions it was built from, according to the following rules:

• $\lnot A$ is false if $A$ is true, and it is true if $A$ is false.
• $A\land B$ is true if both $A$ and $B$ are true: otherwise it is false.
• $A\lor B$ is true if either $A$ or $B$ is true, or if both are true (so $\lor$ represents “inclusive or”).
• $A\to B$ is true unless $A$ is true and $B$ is false. [This rule may seem odd---why is $(0=1)\to(2+2=5)$ true? This rule is a standard convention in logic. To help make sense of it, consider the statement “For any real number $x$ , if $x>2$ then $x^2>4$ “. Try substituting the values $x=1$ and $x=-3$ into “if $x>2$ then $x^2>4$ ”.]
• $A\leftrightarrow B$ is true if $A$ and $B$ have the same truth value, and false otherwise.

Suppose that the proposition “if it snows today, then we will go skiing” is true. Suppose also that the hypothesis “it is snowing today” is true. Then from these two propositions we can deduce the conclusion “we will go skiing”.

The rule of deduction is called modus ponens _and can be written as $( p \land (p \rightarrow q) )\rightarrow q$ .

Using these rules, we can build up the truth table for any compound proposition.

The second style becomes more useful as the propositions get more complicated. The column between the vertical lines gives the truth value of the whole proposition.

p : Blaise Pascal invented several calculating machines,

q : The first all-electronic digital computer was constructed in the twentieth century,

r : $\pi$ was calculated to 1,000,000 decimal digits in 1954.

Represent the following proposition symbolically and construct a truth table.

We can define some other useful binary connectives besides the ones we have already mentioned. The most useful ones are $\oplus$ , NAND and NOR, which denote “exclusive or”, “not-and” and “not-or”. Thus $A\oplus B$ is true if and only if either $A$ is true or $B$ is true, but not both. Also $A$ NAND $B$ is true if and only if $A\land B$ is false, and $A$ NOR $B$ is true if and only if $A\lor B$ is false.

Tautologies, contradictions and contingent propositions

A tautology is a proposition that is always true no matter what truth values we assign to the propositional variables it contains. For example, we showed in an earlier example that $(p\to q)\lor(q\to r)$ is a tautology. A contradiction is a proposition that is always false no matter what truth values we assign to the propositional variables it contains. A proposition that is neither a tautology nor a contradiction is said to be contingent. Here are some examples.

1. $p\lor\lnot p$ is a tautology.
2. $p\to p$ is a tautology.
3. $p\land\lnot p$ is a contradiction.
4. $\lnot(p\to q)\land\lnot p$ is a contradiction.
5. $p\to(q\to r)$ is contingent.
6. $p\land(q\to p)$ is contingent.

Logical equivalence and logical implication

Two propositions $A$ and $B$ are logically equivalent, written $A\Leftrightarrow B$ , if, whenever we assign truth values to the propositional variables they contain, $A$ and $B$ have the same truth value. Thus $A\Leftrightarrow B$ holds if and only if $A\leftrightarrow B$ is a tautology. To decide whether or not two propositions are logically equivalent, we can use truth tables. For example, to show that $p\to q \Leftrightarrow \lnot q \to \lnot p$ , we build up the following truth table:

Notice that columns 3 and 5 are identical.

Alternatively, we can try to convert one to the other using the following standard logical equivalences:

For example, we can show that $p\to(q\lor r)\Leftrightarrow(p\to q)\lor(p\to r)$ as follows:

1. $p \land \lnot q$
2. $(p \to q)$
3. $(p \lor \lnot q) \land (\lnot p \lor r)$
4. $(p \land \lnot q \land \lnot r) \lor \lnot (q \lor \lnot r)$ .

Let $A$ and $B$ be propositions. We say that $A$ logically implies $B$ , written $A\Rightarrow B$ , if, whenever we assign truth values to the propositional variables they contain, if $A$ is true then $B$ is also true. Thus $A\Rightarrow B$ if and only if $A\to B$ is a tautology, and $A\Leftrightarrow B$ if and only if $A\Rightarrow B$ and $B\Rightarrow A$ . That is, $A\Leftrightarrow B$ if and only if $A\leftrightarrow B$ is a tautology.

To clarify, the symbol $\to$ is a logical operation (defined using a truth table) while the symbol $\Rightarrow$ usually denotes some process of deduction.

Introduction to proofs

Mathematics is different from many other facets of life, as it is based on logic and proof. One of the most important reasons to study mathematics is to improve your ability to think logically, precisely, carefully and critically.

An important principle in mathematics is the need for precise definitions. Every technical word or symbol in mathematics has a precise definition. It must be un-ambiguous whether an object satisfies a definition or not.

1. An integer is even if it is something like 2 or 4.
2. An integer $n$ is even if there exists an integer $k$ such that $n = 2k$ .
3. An integer $n$ is even if there exists an integer $k$ such that $n = 2k+1$ .
4. An integer $n$ is even if $n \in A$ .
5. An integer $n$ is even if $\sin(n) = \cos(n) = 0$ .

Theorems are essentially conditional statements, although the wording of a theorem may obscure this fact. Since theorems are conditional then we have to start doing mathematics with some initial facts that are assumed to be true: these are given by definitions and axioms.

There are several basic types of theorem:

• ’$a$ is a $B$ ’ (i.e., the object $a$ satisfies the definition $B$ ).
• ‘if $A$ then $B$ ’ (i.e., if $a$ is an object that satisfies definition $A$ then it also satisfies definition $B$ ).
• ‘there is an $a$ that satisfies $B$ ’ (i.e., a definition is not vacuous).

When the theorem is expressed as a conditional statement $A \Rightarrow B$ then $A$ is called the hypothesis and $B$ is called the conclusion of the theorem.

Mathematics is about facts (theorems).

The interesting question is how do facts become “accepted” or “agreed” as part of mathematics. The discoverer of a mathematical fact is required to communicate their ideas to the wider community of mathematicians. But mathematicians are a hard audience to please: they are sceptical and don’t want to be fooled. So they do not simply believe everything that they are told is true. Mathematicians first insist on precise definitions before even agreeing that a claim is meaningful. Then, mathematicians are not convinced that a statement is true until a precise, rigorous, logical argument has been provided and checked: a mathematical proof. The ability to think logically and to read proofs not only increases mathematical understanding, but also hones skills that can be used in other situations. In this section we will discuss some basic methods of proof.

By a proof of a theorem we mean a logical argument that establishes the theorem to be true.

The most natural form of proof is a direct proof.

Suppose that we wish to prove the theorem $P \Rightarrow Q$ . Since $P \rightarrow Q$ is true whenever $P$ is false, we need only show that whenever $P$ is true, so is $Q$ .

Therefore:

in a direct proof we assume that the hypothesis of the theorem, $P$ , is true and demonstrate that the conclusion, $Q$ is true.

It then follows that $P \rightarrow Q$ is always true.

We will illustrate some types of proofs by proving certain elementary facts about the integers. (Later on we will prove results about Sets and Graphs using the same types of proofs). We will use the following two definitions.

1. An integer $n$ is called even if it can be written in the form $n = 2k$ for some integer $k$ .
2. An integer $n$ is called odd if it can be written in the form $n= 2k + 1$ for some integer $k$ .

Proof: Let $n = 2k+1$ for some integer $k$ . Then $n+1 = 2k+1+1 = 2(k+1)$ is of the form $2l$ for some integer $l$ , and so $n+1$ is even.

We will also use the fact that every integer is either even or odd but not both. The following theorem is proved using a direct proof.

Many proofs use the law of syllogism, which states

Write out the logical expression established in the previous example. Hence, by two applications of the law of syllogism we conclude that $p \Rightarrow q$ , that is, the theorem is proved.

Proofs by contraposition and contradiction

The contrapositive law states that the propositions $p\rightarrow q$ and $\neg q \rightarrow\neg p$ are logically equivalent.

To prove a theorem $p \rightarrow q$ by this method, we give a direct proof of the proposition $\neg q \rightarrow \neg p$ by assuming $\neg q$ and proving $\neg p$ . The contrapositive law allows us to conclude that $p \rightarrow q$ .

Solution. If I find the exam difficult, then I didn’t study hard enough.

A very different style of proof is proof by contradiction.

To prove the theorem $p \rightarrow q$ : Assume $p$ and $\neg q$ are true and deduce a false statement $r$ . Since $(p \wedge \neg q) \rightarrow r$ is true but $r$ is false, we can conclude that the premise $p \wedge \neg q$ of this conditional statement is false. But then its negation $\neg (p \wedge \neg q)$ is true, which is logically equivalent to the desired statement $p \rightarrow q$ .

Solution. Assume, for a contradiction, that $a$ is odd, $a+b$ is even and $b$ is even. So $a = 2k+1$ and $b = 2l$ for some integers $k, l$ . But then $a+b = 2k+1 + 2l = 2(k+l) + 1$ . Since $k+l \in \Z$ it follows that $a+b$ is odd, but this contradicts the fact that $a+b$ is even. Hence $b$ cannot have been even and so $b$ must be odd.

Proving this theorem by contradiction seems natural because the theorem expresses a negative idea (that $a^2 - 4b$ is not equal to $2$ ). Thus, when we negate the conclusion, we obtain the positive statement that $a^2 - 4b = 2$ .

Recall that a rational number is one that can be written as the quotient of two integers. Note also that the theorem to be proved can be written as the conditional statement: If $r$ is a rational number, then $r^2 \not = 2$ . Again proving this theorem by contradiction seems natural because the theorem expresses a negative idea (that $r^2$ is not equal to 2). Thus, when we negate the conclusion, we obtain the positive statement that there is a rational number $r$ such that $r^2 = 2$ .

Solution. (This proof is due to the great Euclid, who lived around 300 BC in ancient Greece.)

Assume, for a contradiction, that there are finitely many primes. Write them as $\{p_{1}, p_{2},...p_{n}\}$ for some natural number $n$ . Consider the number $q=p_{1} p_{2}...p_{n}+1$ . By its construction, $q$ is not divisible by any of the primes $p_{1}, p_{2},...p_{n}$ . Hence, $q$ must itself be prime or it must be divisible by another prime that is not in the set $\{p_{1}, p_{2},...p_{n}\}$ . In either case, we find a prime that is not in our original set. Hence we achieve our contradiction.

To prove: $A$ if and only if $B$ then we need to prove $A \rightarrow B$ and $B \rightarrow A$ . Sometimes “if and only if” is abbreviated as “iff”.

Counterexamples and proof by cases

There are other types of proofs as well. One method of proof that is quite important in discrete mathematics is proof by mathematical induction, which is discussed later in the course. Another type of proof is a proof by cases, in which the theorem to be proved is subdivided into parts, each of which is proved separately. The next example demonstrates this technique.

To close this section, we will briefly consider the problem of disproving a proposition $p \rightarrow q$ , that is, of showing that it is false. A conditional statement is false only when its premise is true and its conclusion is false, we must find an instance in which $p$ is true and $q$ is false. Such an instance is called a counter-example to the statement.

Proof by construction

This method is a much more ‘positive’ method than proof by contradiction. It is a method for proving the existence of certain objects, by actually finding one.

We can prove it by constructing such a positive integer $n$ . Simply take $n = 5k+1$ . This is greater than $k$ , and when we divide $n$ by $5$ we get remainder $1$ .

Language in proofs

Human understanding and communication rely on language. The purpose of a proof is to communicate the truth of a statement through language. Remember that a proof is supposed to convince a sceptical reader that a statement is true. The right way to read a proof is to not believe it, but to challenge the proof and argue with it, and to try to break it. The right way to write a proof is to make the argument so clear and natural that no-one can doubt that the statement is true. To write a beautiful and convincing proof you should give the reader clues to what is going on both locally and in the proof as a whole. In the previous sections we looked at the proof structure as a whole; now we look at the usage of ordinary English, which mostly gives the local information about the proof.

1. Tell the reader from the start what the general approach of the proof will be.

2. Introduce names for objects before you use them. Ensure that every technical word has a precise meaning that has been defined earlier (or is standard terminology in the subject).

3. Use words like “hence”, “therefore”, “thus”, “so”, “then”, “note,” “recall” etc as signposts.

A proof that is well laid-out and signposted is much easier to read.

We now outline some starting statements and end cues that you might use in some common proof formats.

To Prove: Implication $p\rightarrow q$ . If $p$ true then $q$ true.

Method: Assume $p$ true and deduce $q$ true.

Start Cues: “We prove directly … ”, “Let $p$ be as in the statement”.

End Cues: ”$q$ , as required.” “Q.E.D.”, $\Box$ , ”… as was to be shown”/ Restatement of the result.

The logical structure of direct proof is the most simpleminded and most common: assume the hypothesis or hypotheses and deduce the conclusion. Direct proof is frequently cued in the first sentence.

The “Q.E.D.” abbreviating the Latin “Quod Erat Demonstrandum” that you may have seen or written ought to be a reliable cue to the end of a direct proof.

To Prove: Implication $p\rightarrow q$ . If $p$ (true) then $q$ (true).

Method: Prove "$\neg q \rightarrow \neg p$ ". Assume not $q$ , deduce not $p$ .

Start Cues: “We prove the contrapositive”, “We show not $q$ implies not $p$ ”, “We procede indirectly”, “Assume not $q$ …”

End Cues: “So, by contraposition”, Restatement of the original '$p \rightarrow q$ '

The thing to remember is that once you start down this path assuming $\neg q$ and deducing $\neg p$ , the proof is really a direct one, although something different than what you started with.

To Prove: Implication $p\rightarrow q$ . If $p$ then $q$ .

Method: Assume $p$ AND not $q$ , deduce a contradiction

Start Cues: “We prove by contradiction”, “Assume, for a contradiction”, “Suppose (not $q$ )“

End Cues: “Which is a contradiction. Hence $q$ must be true, which completes the proof.”

To Prove: $(p\lor q) \rightarrow r$

Method: Prove $p\rightarrow r$ , then prove $q\rightarrow r$

Start Cues: “We prove by cases …”

Case start: “Case 1 (2,…)”, “In the first case”

Case end: ”… finishes Case 1”, “So we are done in the first case”

End Cues: “So in either case …”

Predicates and quantifiers

A predicate is a function on some domain $D$ such that $P(x)$ is a proposition/statement for each value $x \in D$ .

For example, for $D = \N$ , $P(n)$ could be any of

1. $n$ is even.
2. $n$ is prime
3. $n = 3$
4. $n > 512$
5. $1 + 2 + \cdots + n = n(n+1)/2$

These are not predicates $P(n)$ :

1. $n = x$
2. $1 + 2 + \cdots + n = n(n+1)/2$ \ for all \ $n$

A statement like $p(n)$ that includes the variable $n$ is not a proposition, since it cannot be said to be true or false until we know what $n$ is. There are two ways we can turn it into a proposition. The first is to substitute in some particular value of $n$ , to get propositions like $p(4)$ and $p(17)$ . The other way is to quantify the predicate. To do this we use one of the two quantifiers $\forall$ and $\exists$ . The first of these, $\forall$ , is called the universal quantifier. It means “For all _”, or “For every _“. So, for example, the statement $\forall n\,p(n)$ means “For every $n$ , $n$ is even”. The second quantifier, $\exists$ , is called the existential quantifier. It means “For some _”, or “There exists _ such that”. For example, $\exists n\,p(n)$ means “There is some $n$ such that $n$ is even”. So in this case $\forall n\,p(n)$ is false, whereas $\exists n\,p(n)$ is true. Sometimes we make the domain of definition more explicit: for example, we could have written these examples as $\forall n\in\N\,(p(n))$ and ” $/>\exists n\in\N\,(p(n))$ .

If we quantify a predicate $p$ to get a proposition, the truth value of a resulting proposition depends on the truth values of the various propositions $p(d)$ for the elements $d$ of the domain of definition. To be precise, $\forall x\,p(x)$ is true if $p(d)$ is true for every element $d$ of the domain of definition of $p$ . On the other hand, $\exists x\,p(x)$ is true if $p(d)$ is true for at least one element $d$ of the domain of definition.

Then $\forall n \in \N, P(n)$ is false and $\exists n \in \N, P(n)$ is true.

What are $P(1)$ and $P(2)$ ?

Is $\forall n \in \Z, P(n)$ true or false?

Is $\exists n \in \Z, P(n)$ true or false?

What happens if we change $P(n)$ to be the predicate $n^2 > n$ ?

Let $P(x)$ , $Q(x)$ , and $R(x)$ be the statements ”$x$ is a lion,” ”$x$ is fierce,” and ”$x$ drinks coffee,” respectively. Assuming that the universe of discourse is the set of all creatures, express the statements in the argument using quantifiers and $P(x)$ , $Q(x)$ , and $R(x)$ .

Express this argument using quantifiers.

Solution. Let $p(x)$ be the statement “x is human”.

Let $q(x)$ be the statement “x makes mistakes”.

The statement “All humans make mistakes” is $\forall x, p(x) \rightarrow q(x)$ .

Let the constant symbol $a$ stand for the individual “I”.

Then the argument becomes:$\left( \forall x(p(x)\to q(x))\right) \land \lnot q(a) \rightarrow \lnot p(a)$

We refer to the variable $n$ in a predicate $p(n)$ as a free variable. This is because we are free to substitute any particular value of $n$ to get a proposition. In contrast, the variables $n$ in $\forall n\,p(n)$ or in $\exists n\,p(n)$ are called bound variables. They are bound by the quantifiers, so we cannot substitute particular values in.

We allow predicates to have two or more variables. For example, we may use $p(x,y)$ to denote the predicate ”$x$ is greater than $y$ ”, ("$x>y$ ") with domain of definition the set $\mathbb R\times\mathbb R<L$ . Then $x$ and $/>y$ are both free variables in $p(x,y)$ . We can quantify either one of the variables, or we can quantify both of them. For example, $\forall y\,p(x,y)$ is a predicate that has only one free variable, namely $x$ . In this case, it means ”$x$ is greater than every real number”. Of course, this is false for every real number $x$ (since $p(x,x+1)$ is false), so $\exists x\forall y\,p(x,y)$ is a false proposition. On the other hand, consider the predicate $\exists x\,p(x,y)$ , which has $y$ as its only free variable. This means “Some real number is greater than $y$ “. This is true for every $y$ , since for example $p(y+1,y)$ holds. So the proposition $\forall y\exists x\,p(x,y)$ is true. This example shows that we have to be careful about the order of the quantifiers: $\exists x\forall y\,p(x,y)$ and $\forall y\exists x\,p(x,y)$ do not have the same truth value.

If the predicate has more than one variable, it is not necessary for the domains of definition for the different variables to be the same. For example, if $P$ denotes the set of all people, then we can use $p(x,y)$ to denote the relation “person $x$ is more than $y$ years old”, with domain of definition $P\times\mathbb N<L$ . Of course, if we intend to use both ” $p(x,y)$ and $p(y,x)$ then the domains should be the same.

• Everybody knows Andrew: $\forall x\,p(x,a)$ .
• Everybody who knows Andrew likes him: $\forall x\,(p(x,a)\to q(x,a))$ .
• Nobody likes a person who is famous but not rich: $\forall x\forall y\,((s(x)\land\lnot r(x))\to\lnot q(y,x))$ .
• Some famous people are not rich: $\exists x\,(s(x)\land\lnot r(x))$ .
• Not every rich person is famous: either $\lnot\forall x(r(x)\to s(x))$ or $\exists x(r(x)\land\lnot s(x))$ .
• Everybody likes anybody who is rich: $\forall x\forall y\,(r(y)\to q(x,y))$ or $\forall y\,(r(y)\to\forall x\,q(x,y))$ .
• Andrew likes everybody who is not rich: $\forall x(\lnot r(x)\to q(a,x))$ .
• Everybody likes somebody: $\forall x\exists y\,q(x,y)$ .

Notice that we actually translate “Some famous people are not rich” as “At least one famous person is not rich”.

Tautologies and implications in predicate logic

A proposition in predicate logic that is always true, no matter what the domains of definition and meaning of the predicates it contains (so long as the domains of definition are non-empty) is said to be a tautology.

1. $\forall x\forall y\,(p(x,y)\to p(y,x))$ is not a tautology
2. $\exists x\exists y\,(p(x,y)\to p(y,x))$ is a tautology.
3. $\exists x\forall y\,p(x,y)\to\forall y\exists x\,p(x,y)$ is a tautology.
4. $\forall y\exists x\,p(x,y)\to\exists x\forall y\,p(x,y)$ is not a tautology.

Proof

1. To show that a proposition is not a tautology, we need to find some domain of definition and some meaning for the predicate in which the proposition is false. In this case we can take the domain to be $\mathbb R$ and $p(x,y)$ to be "$x>y$ ". Then $p(1,0)$ is true and $p(0,1)$ is false, so $p(1,0)\to p(0,1)$ is false. Thus there is some $y$ such that $p(1,y)\to p(y,1)$ is false, so $\forall y\,(p(1,y)\to p(y,1))$ is false. Therefore there is some $x$ for which $\forall y\,(p(x,y)\to p(y,x))$ is false, so $\forall x\forall y\,(p(x,y)\to p(y,x))$ is false. Thus $\forall x\forall y\,(p(x,y)\to p(y,x))$ is not a tautology.

2. To show that a proposition is a tautology, we need to show it is true in any non-empty domain of definition and any meaning of the predicate. So let $D$ be a non-empty set, and let $p(x,y)$ be a predicate with domain of definition $D\times D$ . Then, since $D$ is non-empty, we can find some $d\in D$ . Now $p(d,d)$ is either true or it is false: either way, $p(d,d)\to p(d,d)$ is true. Therefore there is some $y\in D$ such that $p(d,y)\to p(y,d)$ is true, so $\exists y\,(p(d,y)\to p(y,d))$ is true. Thus there is some $x\in D$ such that $\exists y\,(p(x,y)\to p(y,x))$ is true, so $\exists x\exists y\,(p(x,y)\to p(y,x))$ is true. Since this is true for any domain $D$ and any predicate $p$ , $\exists x\exists y\,(p(x,y)\to p(y,x))$ is a tautology.

3. Exercise

4. Exercise