Propositional Logic#

While application of logic appears to be intuitive, the study of logic itself can get quite philosophical at times, having been developed from the movement of analytic philosophy.

Statements and Statement Variables#

A statement is a sentence that is either true or false.

Note

You can then ask “how do we define a sentence?” or even “what is a definition?” and these would be valid questions, though we won’t bother answering them. For the purpose of mathematics, anything that you think is a sentence is a sentence, and it is reasonable to assume that this will not cause any ambiguity in a thousand years.

A variable is a symbol used to represent an object. For example, a statement variable is a symbol that represents a statement. We could define \(p\) to be the statement “I did not go to Universal Studios Singapore” and henceforth \(p\) would be a statement variable. Sometimes they are used as shorthands for actual statements, other times they are necessary to represent a general statement.

Note here that the truth of a statement need not be absolute in any sense. “I did not go to Universal Studios Singapore” can be true from the perspective of one person, but false from another.

Logical Connectives#

A logical connective is a symbol used in between statements to form new statements. Such statements are known as compound statements.

A propositional statement, or a proposition, is a statement formed using statement variables and logical connectives.

We will introduce three logical connectives: \(\wedge\), \(\vee\), and \(\sim\). Let \(p\) and \(q\) be statement variables.

\(p\wedge q\) is known as the conjunction of \(p\) and \(q\), read “\(p\) and \(q\)”.
\(p\vee q\) is known as the disjunction of \(p\) and \(q\), read “\(p\) or \(q\)”.
\(\sim p\) (also \(\neg~p\)) is known as the negation of \(p\), read “not \(p\)”.

Each logical connective is defined using a truth table, which exhaustively lists down the truth of the resulting proposition for every possible combination of truth values of \(p\) and \(q\) (or just \(p\) for negation). Below, \(T\) denotes true and \(F\) denotes false.

\(p\wedge q\) is always false unless both \(p\) and \(q\) are true.#
\(p\)	\(q\)	\(p\wedge q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(F\)

\(p\vee q\) is always true unless both \(p\) and \(q\) are false.#
\(p\)	\(q\)	\(p\vee q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(T\)
\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(F\)

\(p\)	\(\sim p\)
\(T\)	\(F\)
\(F\)	\(T\)

We are now ready to see an example of “translating an English sentence into the language of mathematics”. Remember that part of the course objectives is to learn how to write mathematics. Here, the idea to communicate is given (in English) and we are just communicating it mathematically.

Let \(p\) be the statement “I went to Universal Studios Singapore” and \(q\) be the statement “I rode the Battlestar Galactica”. To communicate “I went to Universal Studios Singapore and I rode the Battlestar Galactica”, we may write \(p\wedge q\). The choice of using \(\wedge\) here really stems from our interpretation of the sentence, in particular the English word “and”.

Note

There are many other ways to do this. In particular, note that there is nothing stopping us from letting \(p\) be the entire statement, and then writing down \(p\). Do you need the statement “I went to Universal Studios Singapore” elsewhere? If so, it might be a good idea to separate it out.

A compound statement is also a statement, so we can in fact use logical connectives to connect it with other statements, forming propositions like \(p\wedge q\wedge r\) or \(\sim p\vee q\).

Conditionals#

We will now introduce another logical connective: \(\rightarrow\). Let \(p\) and \(q\) be statement variables. \(p\rightarrow q\) is read “\(p\) implies \(q\)”, and have the following definition via a truth table.

\(p\)	\(q\)	\(p\rightarrow q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(T\)

\(\rightarrow\) is often used to write down ideas exhibiting conditional relationships. Let \(p\) be “it is raining” and \(q\) be “the ground is wet”. The sentence “if it is raining, then the ground is wet” is written as \(p\rightarrow q\).

The truth tables for \(\wedge\), \(\vee\) and \(\sim\) quite intuitively captures the idea of “and”, “or” and “not” in English. This is not quite the case for \(\rightarrow\).

The second row makes the most sense to us: hypothetically if we observe that it is raining, but then we observe that the ground is not wet, the conditional relationship “if it is raining, then the ground is wet” cannot be true, so \(p\rightarrow q\) being false captures this intuition.

Observe that \(p\rightarrow q\) is required to be true when both \(p\) and \(q\) are true, as otherwise we cannot differentiate it from the case where \(p\) is true and \(q\) is false. Unfortunately, this makes sentences like “if you are reading this, then Paris is in France” true, and this intuition mismatch is what we have to accept.

What does our intuition tell us about \(p\rightarrow q\) when \(p\) is false? Well, nothing. We said “if \(p\), then \(q\)”. We did not intend to draw conclusions when \(p\) is false. It is therefore our freedom to define \(p\rightarrow q\) to be whatever we find convenient when \(p\) is false. What we eventually settled on is to have it be true. One tutorial question later will give a justification on this decision.

Note

If you’re interested, check out paradoxes of material implication for more examples of intuition mismatch arising from the definition of \(p\rightarrow q\).

As a result, when \(p\rightarrow q\) is true, the overall information we gain is that it is impossible that \(p\) is true but \(q\) is false.

Biconditionals#

\(p\leftrightarrow q\) is read “\(p\) if and only if \(q\)” and is defined by the following truth table:

\(p\leftrightarrow q\) is true when \(p\) and \(q\) are both true or both false.#
\(p\)	\(q\)	\(p\leftrightarrow q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(T\)

Intuitively, \(p\leftrightarrow q\) is the conjunction of \(p\rightarrow q\) and \(q\rightarrow p\). Just like how \(\rightarrow\) is used to express conditional relationships, \(\leftrightarrow\) further asserts that the relationship also goes the opposite way. Not only do we have “if \(p\), then \(q\)”, but also “if \(q\), then \(p\)”. As a result, \(p\) and \(q\) can only be both true or both false simultaneously.

Ambiguity in Propositions#

At this point, it should be understood that propositions have a truth value under a truth assignment of its statement variables. For example, the proposition \(p\vee q\vee r\) is false if we assign \(p\), \(q\), \(r\) to all be false.

An issue arises if we consider the expression \(p\wedge q\vee r\). This statement could represent the conjunction of \(p\) and \(q\vee r\), or the disjunction of \(p\wedge q\) and \(r\). When \(p\) is false, \(q\) is true and \(r\) is true, the statement is false in the former interpretation, but true in the latter.

This issue is similar to that of evaluating the arithmetic expression \(3 + 4\times 5\). In both cases, ambiguity arises if we do not establish a conventional order of operations and/or introduce parentheses to the expression.

CS1231S establishes the convention that \(\sim\) should be performed first, followed by \(\wedge\) and \(\vee\), which are coequal. This means that parentheses must be used to distinguish between the two possible interpretations of \(p\wedge q\vee r\) as \((p\wedge q)\vee r\) or \(p\wedge(q\vee r)\). Note that there is no “left-to-right evaluation rule”. The expression \(p\wedge q\vee r\) is deemed ambiguous and thus meaningless.

Continuing the order of operations, \(\rightarrow\) and \(\leftrightarrow\) are coequally performed last. This means, for example, that the statement \(\sim p\wedge q\rightarrow r\) is unambiguous.

Hint

There is no need to remember the order of operations, as it could vary from courses to courses. In addition, it doesn’t hurt to use parentheses whenever we are unsure of the order of operations, or to avoid confusing readers who might not be using the same conventions.

Tautologies and Contradictions#

A tautology is a proposition that is true under all possible truth assignments of its statement variables.

A contradiction is a proposition that is false under all possible truth assignments of its statement variables.

For example, the proposition \(p\vee\sim p\) is a tautology, while the proposition \(p\wedge\sim p\) is a contradiction, as can be seen from the following truth table:

The column \(p\vee\sim p\) is always \(T\), while the column \(p\wedge\sim p\) is always \(F\).#
\(p\)	\(\sim p\)	\(p\vee\sim p\)	\(p\wedge\sim p\)
\(T\)	\(F\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)

The intuition here is that a statement is always either true or false, but never both.

Note

At this point, it is important to realise that the number of rows in a truth table is decided by the number of statement variables involved. The propositions above only involve the variable \(p\), which can either be true or false, resulting in two rows in the truth table.

Logical Equivalence#

Two propositions \(\phi\) and \(\psi\) are logically equivalent (denoted \(\phi\equiv\psi\)) whenever their truth values are equal under all possible truth assignments to their statement variables.

Note

We tend to use Greek letters \(\phi\) (“phi”) and \(\psi\) (“psi”) to denote propositions. By our definition of propositions, this means for example that \(\phi\) could consist of statement variables \(p\), \(q\) and \(r\) alongside logical connectives.

For example, let \(\phi\) be \(p\rightarrow q\) and \(\psi\) be \(\sim p\vee q\). From the truth table below, we see that they share the same truth values under all possible truth assignments to \(p\) and \(q\).

The column \(p\rightarrow q\) is always the same as the column \(\sim p\vee q\). Thus we have \(p\rightarrow q\equiv\sim p\vee q\).#
\(p\)	\(q\)	\(p\rightarrow q\)	\(\sim p\)	\(\sim p\vee q\)
\(T\)	\(T\)	\(T\)	\(F\)	\(T\)
\(T\)	\(F\)	\(F\)	\(F\)	\(F\)
\(F\)	\(T\)	\(T\)	\(T\)	\(T\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)

Note

What is the difference between \(p\leftrightarrow q\) and \(p\equiv q\)? This is a question that has confused many students for extended periods of time, myself included. Some claim that they are interchangeable, some claim that there are philosophical differences. I am presenting below the differences as I understand it.

\(\leftrightarrow\) is a logical connective. Hence, \(\phi\leftrightarrow\psi\) can be viewed as one propositional statement.
\(\equiv\) is an assertion on propositional statements. \(\phi\equiv\psi\) cannot be viewed as one propositional statement. Rather, it is a statement asserting the logical equivalence between two propositional statements.

Similar questions had been asked in the Mathematics Stack Exchange here and here, and in the Philosophy Stack Exchange here.

The equivalence between \(p\rightarrow q\) and \(\sim p\vee q\) is only one of a collection of laws establishing commonly used logical equivalences.

With these laws at hand, we now have two methods to go around establishing the logical equivalence of two given propositions \(\phi\) and \(\psi\).

Use a truth table and compare the columns of \(\phi\) and \(\psi\). In general, the number of rows in the truth table should grow exponentially with respect to the number of variables involved.
Use the laws above to simplify \(\phi\) and \(\psi\) to the same proposition. More often than not, that same proposition is either \(\phi\) or \(\psi\).

Question 3

Simplify the propositions below using the laws given in Theorem 2.1.1 (Epp) and the implication law (if necessary) with only negation (\(\sim\)), conjunction (\(\wedge\)) and disjunction (\(\vee\)) in your final answers. Supply a justification for every step.

\(\sim a\wedge (\sim a\rightarrow (b\wedge a))\)

\((p\vee\sim q)\rightarrow q\)

\(\sim (p\vee\sim q)\vee (\sim p\wedge\sim q)\)

\((p\rightarrow q)\rightarrow r\)

For now, we want students to cite justification for every step. This is to ensure that you do not arrive at the answer by coincidence. Only after you have gained sufficient experience then would we relax this and allow you to skip obvious steps, or combine multiple steps in a line.
The original question for part (a) involves correcting an answer that skipped a few steps so that it can be awarded full credit. This will be emphasized verbally, but on this page I don’t want to put too much focus on exam-wise reminders.
Hereafter, we use \(\text{true}\) and \(\text{false}\) to denote some tautology and contradiction respectively. We can rightfully treat them as shorthands for some “legit” propositions like \(p\vee\sim p\) and \(p\wedge\sim p\).
The various techniques used to simplify propositions will be covered verbally as needed.

We can similar establish logical nonequivalence between propositions. Two propositions are not logically equivalent whenever we can find a truth assignment to their statement variables such that the resulting truth values of the propositions are different.

When \(\phi\) and \(\psi\) are logically equivalent, we can use a truth table and see that the columns of \(\phi\) and \(\psi\) are exactly the same. When they’re not logically equivalent, we must be able to find a row in the truth table in which the columns of \(\phi\) and \(\psi\) mismatch.

Question 4

Prove, or disprove, that \((p\rightarrow q)\rightarrow r\) is logically equivalent to \(p\rightarrow (q\rightarrow r)\).

We have two options (corresponding to “Prove” and “disprove”):
- “Guess” that the propositions are logically equivalent, then try to establish this fact by either using a truth table or by simplification.
- “Guess” that the propositions are not logically equivalent, then try to look for a truth assignment for which there is a mismatch on the truth values of the two propositions.
Which option to pick relies mainly on intuitions, but remember that there is nothing stopping us from trying both! If one option didn’t work, we might at least obtain some inspirations on how to proceed with another.

We shall first guess that \((p\rightarrow q)\rightarrow r\equiv p\rightarrow (q\rightarrow r)\).

From Question 3(d), the left hand side simplifies to \((p\wedge\sim q)\vee r\).
- It is not necessary to remember Question 3(d). One could just redo the simplifications.
The right hand side simplifies, using the implication law twice, to \(\sim p\vee\sim q\vee r\).
At this point, we are stuck and can’t seem to simplify either side any further.
Maybe we should turn to using a truth table:

\(p\)	\(q\)	\(r\)	\(p\rightarrow q\)	\((p\rightarrow q)\rightarrow r\)	\(q\rightarrow r\)	\(p\rightarrow (q\rightarrow r)\)
\(T\)	\(T\)	\(T\)	\(T\)	\(T\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(T\)	\(F\)	\(F\)	\(F\)
\(T\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)
\(F\)	\(T\)	\(T\)	\(T\)	\(T\)	\(T\)	\(T\)
\(F\)	\(T\)	\(F\)	\(T\)	\(F\)	\(F\)	\(T\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(T\)	\(T\)
\(F\)	\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)

Now, we see that the columns of \((p\rightarrow q)\rightarrow r\) and \(p\rightarrow (q\rightarrow r)\) do not match!

At this point, it should be clear that we are working towards establishing logical nonequivalence instead, so we need to come up with a truth assignment that disproves the equivalence. The truth table told us exactly the truth assignments we are looking for.

More on Conditionals#

We will make the following definitions:

The converse of the proposition \(p\rightarrow q\) is \(q\rightarrow p\).
The inverse of the proposition \(p\rightarrow q\) is \(\sim p\rightarrow\sim q\).
The contrapositive of the proposition \(p\rightarrow q\) is \(\sim q\rightarrow\sim p\).

There are several observations to make here:

The converse of the converse is the original proposition. The same applies to inverse and contraposition.
\(p\rightarrow q\) is logically equivalent to its contrapositive, i.e. \(p\rightarrow q\equiv\sim q\rightarrow\sim p\).
- This means “if it is raining, then the ground is wet” can be rephrased as “if the ground is not wet, then it is not raining”.
- We can simplify \(p\rightarrow q\) to \(\sim q\rightarrow\sim p\) as follows:
\[\begin{split}\begin{align*} p\rightarrow q &\equiv\sim p\vee q &\text{by the implication law} \\ &\equiv q\vee\sim p &\text{by the commutative law} \\ &\equiv\sim(\sim q)\vee\sim p &\text{by the double negative law} \\ &\equiv\sim q\rightarrow\sim p &\text{by the implication law} \end{align*}\end{split}\]
The contrapositive of the inverse is the converse (and vice versa), so the converse and the inverse are logically equivalent.

To summarise, \(p\rightarrow q\) is logically equivalent to its contrapositive \(\sim q\rightarrow\sim p\). Its converse \(q\rightarrow p\) is logically equivalent to its inverse \(\sim p\rightarrow\sim q\), which is also the contrapositive of the converse.

It is a common logical fallacy to believe that “if \(p\), then \(q\)” can be rephrased as “if not \(p\), then not \(q\)” or “if \(q\), then \(p\)”. These two fallacies are known as inverse error and converse error respectively.

Also, by the implication law, De Morgan’s law and the double negative law, one has \(\sim (p\rightarrow q)\equiv p\wedge\sim q\). This intuitively means that “if \(p\) then \(q\)” being false is only possible when \(p\) is true and (but) \(q\) is false. We can also see this from the truth table for \(\rightarrow\), in which the only row where \(p\rightarrow q\) is false is when \(p\) is true and \(q\) is false.

As alluded to earlier, the propsition \(p\leftrightarrow q\) is in fact logically equivalent to the conjunction of \(p\rightarrow q\) with its converse / inverse, i.e. \(p\leftrightarrow q\equiv (p\rightarrow q)\wedge (q\rightarrow p)\). This can be verified using a truth table:

The columns \(p\leftrightarrow q\) and \((p\rightarrow q)\wedge (q\rightarrow p)\) are identical.#
\(p\)	\(q\)	\(p\leftrightarrow q\)	\(p\rightarrow q\)	\(q\rightarrow p\)	\((p\rightarrow q)\wedge (q\rightarrow p)\)
\(T\)	\(T\)	\(T\)	\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)	\(F\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)	\(T\)	\(F\)	\(F\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(T\)

So something “nice” happens when both \(p\rightarrow q\) and its converse / inverse are true, in the sense that \(p\) and \(q\) are either both true or both false.

If, Only If, Necessary and Sufficient Conditions#

In English, the following four sentences all have the same meaning as “if \(p\), then \(q\)”, and are therefore all written mathematically as \(p\rightarrow q\).

\(q\) if \(p\).
\(p\) only if \(q\).
\(q\) is a necessary condition of \(p\).
\(p\) is a sufficient condition of \(q\).

The only information that is communicated by the sentence “it is raining only if the ground is wet” is “if the ground is not wet, then it is not raining”. In particular, it is not claiming that “if the ground is wet, then it is raining” – there are other ways to make the ground wet. Hence generally, the sentence “\(p\) only if \(q\)” is translated as \(\sim q\rightarrow\sim p\), which is logically equivalent to \(p\rightarrow q\), and not \(q\rightarrow p\).

As a corollary, if it is both true that “\(p\) if \(q\)” and “\(p\) only if \(q\)”, then mathematically we have \(p\leftrightarrow q\). This justifies reading \(p\leftrightarrow q\) as “\(p\) if and only if \(q\)”.

A more elaborate way of saying “if \(p\), then \(q\)” is “given that \(p\) is true, it is necessary that \(q\) is true”. This is what we mean by “necessary condition”. We also say that \(p\) is a sufficient condition of \(q\), since the condition of \(p\) being true is sufficient for us to conclude that \(q\) is true. There might be other ways to make \(q\) true, but \(p\) being true is already sufficient.

Similarly, if \(p\) is a necessary and sufficient condition for \(q\) (or vice versa), we write \(p\leftrightarrow q\).

At this point, some students complain that this part of the course felt like an English lesson. Yes, I agree, we can’t translate a sentence without being able to interpret it in the first place.

Note

This is a good place to mention that English (and every other natural language) can be ambiguous, and interpretations of English sentences can be highly subjective. In a sense, I only forcefully declared that we will interpret the four sentences above as \(p\rightarrow q\). What I also hope is that you can gain some intuitions behind why we are interpreting them as such.

Argument Forms and Arguments#

We now want to build towards the notion of a mathematical proof. We start by thinking about what an argument really is.

An argument form is a sequence of propositions \(\phi_1, \phi_2, \cdots , \phi_k\) known as premises, followed by a proposition \(\psi\) known as the conclusion. They can be denoted like so:

\[\begin{split}\begin{array}{l} \phi_1 \\ \phi_2 \\ \vdots \\ \phi_k \\ \hline \therefore\psi \end{array}\end{split}\]

Moreover, if \(\phi_1\wedge\phi_2\wedge\cdots\wedge\phi_k\rightarrow\psi\) is a tautology, we say that the argument form is valid.

For example, here is an argument form with two premises \(p\rightarrow q\) and \(p\), followed by the conclusion \(q\):

\[\begin{split}\begin{array}{l} p \\ p\rightarrow q \\ \hline \therefore q \end{array}\end{split}\]

One can check that \((p\wedge (p\rightarrow q))\rightarrow q\) is a tautology, so this argument form is valid. This validity is also intuitive: if we know as premises that \(p\rightarrow q\), and on top of that \(p\) is true, then as conclusion, \(q\) would be implied to be true.

Rules of Inference#

We now make one observation: consider the following argument form with two premises:

\[\begin{split}\begin{array}{l} \phi_1 \\ \phi_2 \\ \hline \therefore\psi \end{array}\end{split}\]

We want to decide whether this argument form is valid. Suppose now that we know that the following argument form is valid:

\[\begin{split}\begin{array}{l} \phi_1 \\ \phi_2 \\ \hline \therefore\psi' \end{array}\end{split}\]

where \(\psi'\) is some proposition different from \(\psi\). Intuitively, we should be able to “advance” the original argument form into the following:

\[\begin{split}\begin{array}{l} \phi_1 \\ \phi_2 \\ \psi' \\ \hline \therefore\psi \end{array}\end{split}\]

in the sense that the original argument form is valid if and only if this new argument form is valid, so we can work with this new one instead. I leave it as an exercise for the readers to check that indeed \(\phi_1\wedge\phi_2\equiv\phi_1\wedge\phi_2\wedge\psi'\) and thus the argument form \(\phi_1\wedge\phi_2\rightarrow\psi\) is logically equivalent to the argument form \(\phi_1\wedge\phi_2\wedge\psi\rightarrow\psi'\). It should also be clear that this can be generalized to argument forms with more than two premises.

Just like how we have two methods to argue the logical equivalence of two propositions, we now have two methods to decide the validity of an argument form.

Argue that \(\phi_1\wedge\phi_2\wedge\cdots\wedge\psi_k\rightarrow\psi\) is a tautology using the laws of logical equivalences, or by analyzing the critical rows of a truth table (see below).
Use valid argument forms to make intermediary deductions until we eventually derive the conclusion.

A rule of inference is a commonly used argument form to perform the latter. There are only a handful of them, and they are supposed to be intuitive and fundamental in some sense. For this reason, each rule of inference is given a name, two of the names are actually Latin terms to sound cooler.

Similarly, to argue the invalidity of an argument form is to argue that \(\phi_1\wedge\phi_2\wedge\cdots\wedge\psi_k\rightarrow\psi\) is not a tautology, so we need to find a truth assignment where \(\phi_1\wedge\phi_2\wedge\cdots\wedge\psi_k\) is true but \(\psi\) is false (this is because \(\sim (p\rightarrow q)\equiv p\wedge\sim q\)). This means that the validity of an argument form depends critically on the rows of the truth table in which \(\phi_1\), \(\phi_2\), \(\cdots\), \(\phi_k\) are true. These rows are known as a critical rows. For an argument to be valid, \(\psi\) has to be true in every critical row. To argue invalidity, then, is to find a critical row in which \(\psi\) is false.

The converse error and inverse error, as mentioned before, can be thought of as invalid argument forms:

\[\begin{split}\begin{array}{l} \phi\rightarrow\psi \\ \psi \\ \hline \therefore\phi \end{array}\end{split}\]

and

\[\begin{split}\begin{array}{l} \phi\rightarrow\psi \\ \sim\phi \\ \hline \therefore\sim\psi \end{array}\end{split}\]

respectively. For example, to see that the argument form for converse error is invalid, we consider a truth assignment under which \(\phi\) is false and \(\psi\) is true. Note that the premises \(\phi\rightarrow\psi\) and \(\psi\) are both true, but the conclusion \(\phi\) is false. It follows that the corresponding critical row is problematic, and hence the argument form is invalid. I can come up with this counterexample by understanding what makes \(p\rightarrow q\) different from \(q\rightarrow p\): when \(q\) is true and \(p\) is false, \(p\rightarrow q\) is true but the converse is false.

Question 6

The conditional statement \(p\rightarrow q\) is an important logical statement. Oftentimes, students are perplexed by this definition. The first two rows look reasonable, but the last two rows seem strange. However, this way of defining \(p\rightarrow q\) actually gives us the nice intuitive property of the following statement:

\[((p\rightarrow q)\wedge (q\rightarrow r)\rightarrow (p\rightarrow r))\]

which is the transitive rule of inference we studied in lecture:

\[\begin{split}\begin{array}{l} p\rightarrow q \\ q\rightarrow r \\ \hline \therefore p\rightarrow r \end{array}\end{split}\]

For example, given premises “if \(x\) is a square then \(x\) is a rectangle” and “if \(x\) is a rectangle then \(x\) is a quadrilateral”, the conclusion is “if \(x\) is a square then \(x\) is a quadrilateral”. We use such intuitive reasoning very often in our life.

Show that if we define the conditional statement alternatively as follows, then the transitive rule of inference would no longer hold.

Alternative 1: \(\rightarrow_a\)#
\(p\)	\(q\)	\(p\rightarrow_a q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(F\)

Alternative 2: \(\rightarrow_b\)#
\(p\)	\(q\)	\(p\rightarrow_b q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(F\)

Alternative 3: \(\rightarrow_c\)#
\(p\)	\(q\)	\(p\rightarrow_c q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(T\)

Arguments#

An argument is an argument form whose statement variables are substituted for actual statements. For example, here is an argument having the argument form mentioned above:

\[\begin{split}\begin{array}{l} \text{Socrates is a man.} \\ \text{If Socrates is a man, then Socrates is mortal.} \\ \hline \therefore\text{Socrates is mortal.} \end{array}\end{split}\]

An argument is sound if its argument form is valid, and all its premises are true. If you believe that “Socrates is a man”, and the fact that “if Socrates is a man, then Socrates is mortal”, then coupled with the fact that the underlying argument form is valid, it follows that the argument above should appear sound to you.

Question 8

Given the following argument:

\[\begin{split}\begin{array}{l} p\vee (q\wedge r) \\ \sim p \\ \hline \therefore q\wedge r \end{array}\end{split}\]

Without actually drawing the truth table, determine the values of \(p\), \(q\) and \(r\) in the critical row(s) of the truth table. Is the argument valid?

Give a counterexample to show that the following argument is invalid.

\[\begin{split}\begin{array}{l} p\vee (q\wedge r) \\ \sim (p\wedge q) \\ \hline \therefore r \end{array}\end{split}\]

Determine whether the following argument is valid or invalid. Use variables to represent the statements (for example: let \(p\) be “I go to the beach”.)

\[\begin{split}\begin{array}{l} \text{If I go to the beach, I will take my shades or my sunscreen.} \\ \text{I am taking my shades but not my sunscreen.} \\ \hline \therefore\text{I will go to the beach.} \end{array}\end{split}\]

Determine whether the following argument is valid or invalid. Use variables to represent the statements.

\[\begin{split}\begin{array}{l} \text{I will buy a new goat or a used Yugo.} \\ \text{If I buy both a new goat and a used Yugo, I will need a loan.} \\ \text{I bought a used Yugo but I don't need a loan.} \\ \hline \therefore\text{I didn't buy a new goat.} \end{array}\end{split}\]

You can sort of see the parallel between propositions vs statements, and argument forms vs arguments. Propositions and argument forms are written in terms of statement variables, and they semantically represent the form of a statement and an argument, respectively. Statements and arguments are, in some sense, the “application” of the symbolic rules of logic in real life, where we substitute each statement variable with actual statements to help us determine their truths.

A mathematical proof, or simply a proof, can be thought of as a sound argument (even though we might not always present it in the same format). When we have a proof of a statement \(p\), we mean that we have a sound argument whose conclusion is \(p\). The premises consist of statements we already know are true in the context around the statement we are proving (e.g. to prove that Socrates is mortal, we need to agree that Socrates is a man, which any sane person will believe is true). Having a proof of a statement \(p\) allows us to conclude that \(p\) is true (under the assumptions we have just made), and the fun part is that we can now use \(p\) as a premise to prove further results.

And that is what modern mathematics is about! We make fundamental assumptions (different sets of assumptions in different theories), then prove meaningful statements based on these assumptions, then use these results to prove further results and so on.

Here is a good place to take a step back and admire the big picture. We said that a proposition consists of statement variables connected by logical connectives. Each proposition has a truth value under some truth assignments. We can substitute each statement variable with actual statements in order to study the real world. An argument form consists of a number of premises followed by a conclusion. An argument is an argument form with actual statements. An argument is sound if its form is valid, and everyone agrees that the premises are true. Having a sound argument (or a proof) that leads to a conclusion establishes the truth of that conclusion (for people who agree with the premises).

Types of Numbers#

We will take a detour here and explore the types of numbers that will be encountered in this course. The purpose of this section is to establish some fundamental assumptions (based on what you’ve seen in pre-university years) which we can take as premises, so that we can start forming arguments on concrete mathematical objects rather than working with toy statements.

Natural numbers, denoted \(\mathbb{N}\), consist of the numbers \(0\), \(1\), \(2\), \(\cdots\).
Integers, denoted \(\mathbb{Z}\), consist of the natural numbers along with the negatives: \(\cdots\), \(-1\), \(0\), \(1\), \(\cdots\).
Rational numbers, denoted \(\mathbb{Q}\), consist of all fractions, including integers whose denominator is 1.
Real numbers, denoted \(\mathbb{R}\), consist of any number that does not involve the imaginary number \(i\).
Irrational numbers, denoted \(\mathbb{R}\backslash\mathbb{Q}\), consist of real numbers that are not rational.

The definitions above are non-rigorous. Defining the numbers rigorously is not that trivial.

The superscripts \(+\) and \(-\) are used to denote the positive and negative versions of the numbers, respectively. For example, \(\mathbb{Q}^+\) consist of the positive rational numbers.

Subscripts are used to give more specific bounds. For example, \(\mathbb{Z}_{\geq 12}\) consist of \(12\), \(13\), \(14\), \(\cdots\).

We will now introduce the symbol \(\in\) as a shorthand for “is a member of”. This will be elaborated more in Chapter 3. It follows that \(0\in\mathbb{N}\), \(-1\in\mathbb{Z}\), \(\frac{1}{2}\in\mathbb{Q}^+\) and so on.

Basic Algebra#

We assume, without proof, the truth of a collection of laws to perform algebraic manipulations. For example, we take for granted that addition on the real numbers is commutative, i.e. \(a + b = b + a\) for any real number \(a\) and \(b\).

It is theoretically possible to prove them from scratch, but they are too intuitive and too numerous that we will not bother with it in this course. I am very reluctant to include the full list on this page, so please refer to Canvas > Files > Lecture Slides and look for the files AppendixA_1.jpg, AppendixA_2.jpg and AppendixA_3.jpg. These are the pages of Appendix A of Susanna S. Epp’s textbook “Discrete Mathematics with Applications”, the prescribed textbook for this course.

We will refer to applications of these laws as “basic algebra”.

Question 5

Given the conditional statement “If \(12x - 7 = 29\), then \(x = 3\)”, write the negation, contrapositive, converse and inverse of the statement.

Is the given conditional statement true? If it is true, prove it; otherwise, give a counterexample.

Is its converse true? If it is true, prove it; otherwise, give a counterexample.

In general, is it possible for the converse of a conditional statement to be true while the inverse of the same statement is false? Why?

Parity and Divisibility#

An integer \(n\) is said to be even if and only if \(n = 2k\) for some integer \(k\). For example, \(8\) is even because \(8 = 2 * 4\). \(0\) is even because \(0 = 2 * 0\). \(-4\) is even because \(-4 = 2 * (-2)\).

An integer \(n\) is said to be odd if and only if \(n = 2k + 1\) for some integer \(k\). For example, \(-3\) is odd because \(-3 = 2(-2) + 1\).

It can be shown that an integer is either even or odd, but not both. The property of an integer of whether it is even or odd is known as the parity of the number. For example, the \(3\) and \(5\) have the same parity because both are odd.

For integers \(a\) and \(b\), we say that \(a\) divides \(b\), or \(b\) is divisible by \(a\) (denoted \(a|b\)) if and only if \(a = bk\) for some integer \(k\). For example, \(2\) and \(-3\) both divide \(6\), as \(6 = 2(3) = (-3)(-2)\) (here \(k = 3\) and \(k = -2\) respectively).

It follows that even integers are exactly those divisible by \(2\), and odd integers are exactly those that don’t.

Note

Note the use of “if and only if” when defining things. To be pedantic, by saying “\(n\) is even if \(n = 2k\) for some integer \(k\)”, we are just specifying what integers are considered even. To complete the definition, we should also specify what integers are not considered even: “\(n\) is even only if \(n = 2k\) for some integer \(k\)”. Some authors tend to omit writing “only if” in definitions, in which case it should be assumed that there is an implicit “only if”.

We will also introduce two new symbols which will be heavily elaborated in Chapter 2: \(\exists\) and \(\forall\). For now, treat \(\exists\) as a shorthand for the English term “there exists”, and \(\forall\) as a shorthand for the English term “for all”. I hope everyone agrees that in English, “for some” has the same meaning as “there exists”, so the definitions of even and odd integers can be rewritten as:

An integer \(n\) is said to be odd if and only if \(\exists k\in\mathbb{Z}\) s.t. \(n = 2k + 1\).
An integer \(n\) is said to be even if and only if \(\exists k\in\mathbb{Z}\) s.t. \(n = 2k\).

where s.t. is the abbreviation for “such that”.

Note that it is also true that \(n\) is odd if and only if \(\exists m\in\mathbb{Z}\) s.t. \(n = 2m + 1\). We say that \(m\) is a dummy variable. It intuitively serves as a placeholder for “some integer”, and can be named whatever we want.

Proof Techniques#

You should have noticed by now that proofs play a very important role in the development of mathematics: it allows us to establish the truth of a mathematical statement in a rigorous way. Before we dive into strategies to come up with proofs, I want to emphasize again that problem-solving does not begin with proof writing. Intuition is built behind why a statement might be true, and only then we begin to prove it rigorously to verify and communicate our intuitions.

Direct Proof#

There is no rigorous definition of what a direct proof is. Generally speaking, a direct proof for \(p\) uses only pre-established facts to eventually derive the goal statement \(p\). It is not so meaningful to ask questions like “is proof by division into cases a type of direct proof?” because (a) it doesn’t really matter and (b) it really depends on the proof itself: each case can be handled differently, perhaps one directly and another one indirectly.

As an example, we argue that if \(n\) is an even integer, then \(n^2\) is an even integer. Roughly, the intuition here is that when squaring an integer, any factor of \(2\) should not “disappear”. Here is a direct proof that makes use of this intuition:

Let \(n\) be an even integer.
Then, by definition of even integers, \(n = 2k\) for some integer \(k\).
Then, \(n^2 = (2k)^2 = 4k^2 = 2(2k)\) by basic algebra.
Let \(m = 2k\). Since \(k\) is an integer, \(2k\) is also an integer by basic algebra.
Since \(n^2 = 2m\) (by substituting \(m = 2k\) in line 3) and \(m\) is an integer, \(n^2\) is even by definition of even integers.

Allow me to spend a few paragraphs explaining the intricacies of this seemingly simple proof:

The format of having each line of the proof numbered is only enforced in CS1231S, but not after you have passed the course. One of the benefits of numbering the lines is so that we can reference the lines easily (such as in line 5, and the reference to line 5 literally just now). Further mathematical proofs can be too complicated to write down in numbered lists, so it is more common to present them as paragraphs, possibly broken down into lemmas and theorems.
The general strategy to prove directly a statement of the form \(p\rightarrow q\) is to work under the case where \(p\) is true and try to deduce that \(q\) is true. The reason this works is that in the case where \(p\) is false, \(p\rightarrow q\) is vacuously true. So technically, we are dividing into two cases depending on the truth of \(p\), and our goal is for \(p\rightarrow q\) to be true in both cases. However, the case where \(p\) is false is, independent of what \(p\) and \(q\) stand for, always trivially handled, and hence omitted.
It is helpful to imagine how you would have written down the proof on your own.
- As discussed above, the strategy is to suppose \(p\), then try to deduce \(q\). This is exactly what line 1 and line 5 are doing, so it is reasonable to write these two lines first (although we wouldn’t know that the proof has 5 lines in advance).
- Line 2 uses the definition of an even integer, which is true (because we literally defined it ourselves), along with modus ponens, to conclude that \(n = 2k\) for some integer \(k\). Usually, the application of rules of inference is only explicitly written down when we are arguing validity of argument forms, so it is omitted here.
- Arguably, the “trickiest” of the proof lies in line 3 and 4. One has to have gained the intuition to try to square \(n\), then use basic algebra to discover that the resulting expression resembles an even number, thus filling in the gap between line 1 and 5.
- Notice our preliminary intuition in action in line 3: when \(n\) is squared, not only did its factor of \(2\) not disappear, it became \(2^2 = 4\) which is of course even.
Each variable (\(n\), \(m\), \(k\)) must be defined properly. For example, in line 2, it is insufficient to only write \(n = 2k\) and omit “for some integer \(k\)”, since that phrase is supposed to introduce what \(k\) is by specifying its range. Without the fact that \(k\) is an integer, line 4 wouldn’t work.
There is no hard rule on what is considered one line of proof. We can kind of just “vibe it out” as long as the proof is readable by whoever is reading it.

Proof by Contraposition#

Proof by contraposition can be used to indirectly prove statements of the form \(p\rightarrow q\). The idea is to use the fact that \(p\rightarrow q\) is logically equivalent to its contrapositive \(\sim q\rightarrow\sim p\) and thus (directly) prove the contrapositive instead.

For example, let \(n\) be an integer. One can prove by contraposition that if \(n^2\) is even, then \(n\) is even. Intuitively, it would be difficult to work under the hypothesis \(n^2\) is even. There is not much algebraic manipulations we can do after taking square roots. Instead, since an integer is either even or odd but not both, we will prove that if \(n\) is odd, then \(n^2\) is odd.

Suppose \(n\) is odd.
Then, by definition of odd integers, \(n = 2k + 1\) for some integer \(k\).
Then, \(n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\) by basic algebra.
Let \(m = 2k^2 + 2k\). Since \(k\) is an integer, \(m\) is also an integer.
Since \(n^2 = 2m + 1\) (by substituting \(m = 2k^2 + 2k\) in line 3) and \(m\) is an integer, \(n^2\) is odd by definition of odd integers.
By contraposition, if \(n^2\) is even, then \(n\) is even.

This result along with the previous one tell us that \(n\) is even if and only if \(n^2\) is even, and furthermore, \(n\) is odd if and only if \(n^2\) is odd, so now we know that an integer always has the same parity as its square.

There is in fact a direct proof for the statement above:

A meme on a proof by contraposition — Source: https://mathstodon.xyz/@VinceVatter/113873301556475236#

Proof by Contradiction#

In a proof by contradiction (also known as reductio ad impossible if you want to sound fancy), the idea is to use the fact that the following argument form is valid:

\[\begin{split}\begin{array}{l} \sim\phi\rightarrow F \\ \hline \therefore\phi \end{array}\end{split}\]

where recall that \(F\) is some contradiction. Thus, the strategy to prove a statement \(p\) is to prove \(\sim p\rightarrow F\) instead, since once the truth of \(\sim p\rightarrow F\) is established, we can apply the valid argument form above to conclude \(p\).

The most classic example of a proof by contradiction is the proof of the irrationality of \(\sqrt{2}\):

Suppose \(\sqrt{2}\) is not irrational, then it is rational.
Then, by definition of rational numbers, \(\sqrt{2} = \frac{p}{q}\) for some integers \(p, q\) such that the fraction \(\frac{p}{q}\) cannot be reduced further.
Then, \(2 = \frac{p^2}{q^2}\), so \(2q^2 = p^2\) by basic algebra.
Since \(q\) is an integer, \(q^2\) is an integer, so \(p^2\) is even, so \(p\) is even by what we proved above.
Since \(p\) is even, \(p = 2k\) for some integer \(k\), so \(2q^2 = (2k)^2 = 4k^2\), so \(q^2 = 2k^2\).
Since \(k\) is an integer, \(k^2\) is an integer, so \(q^2\) is even, so \(q\) is even by what we proved above.
Since \(p\) is even and \(q\) is even, the fraction \(\frac{p}{q}\) can be reduced further, contradicting line 2, so \(\sqrt{2}\) has to be irrational.

We will not focus too much on the intuition behind this proof. After all, the discovery of this proof by Hippasus was a shock to the Pythagorean school of mathematics insisting that all numbers are rational, so much so that Pythagoras allegedly drowned him at a sea afterwards. This goes to show the elusiveness of this result.

More importantly, note the structure of the proof: recall that our goal is to prove \(\sim p\rightarrow F\). To do so, we work under the case where the hypothesis \(\sim p\) is true (and hence write down line 1) and try to arrive at some contradiction. The contradiction in this case is \(q\wedge\sim q\), where \(q\) is “\(\frac{p}{q}\) cannot be reduced further”.

If we were to prove \(p\rightarrow q\) by contradiction, we should first suppose that \(p\wedge\sim q\), since that is the negation of our goal. A common mistake is to suppose \(\sim q\), then arrive at \(\sim p\), then incorrectly claim that this is a contradiction. This is incorrect because \(p\) was never part of the supposition. Instead, such students have produced a proof by contraposition. Note that a proof by contradiction for \(p\rightarrow q\) need not contradict \(p\) in the proof, and could instead contradict something else, so not every proof by contradiction can be translated into a proof by contraposition.

Question 9

The island of Wantuutrewan is inhabited by exactly two types of people: knights who always tell the truth and knaves who always lie. Every native is a knight or a knave, but not both. You visit the island and have the following encounters with the natives.

Two natives A and B speak to you:

A says: Both of us are knights.

B says: A is a knave.

What are A and B?

The intuitive thing to do is to first assume an identity for A (or B) and make further deductions based on what they said:

Suppose that A is a knight, so A always tells the truth.
Since A says “Both of us are knights” and A always tells the truth, B must be a knight (in particular), so B always tells the truth.
Since B says “A is a knave” and B always tells the truth, A is a knave.
Since A is a knave, and every native is a knight or a knave but not both, A is not a knight, contradicting line 1, so A is a knave.

We can now wrap the argument above and call it a proof by a contradiction for A being a knave. With this information at hand, since B says “A is a knave”, B is telling the truth, so B is a knight (note that the setup of the question implies every native either always tells the truth or always lies).

The conclusion is that A is a knave and B is a knight. Now, to write it down “properly”,

Two natives C and D speak to you:

C says: D is a knave.

D says: C is a knave.

How many knights and knaves are there?

As usual, we first assume an identity for C, say C is a knight:

Since C says “D is a knave” and C always tells the truth, D has to be a knave, so D always lies.
Since D says “C is a knave” and D always lies, C is not a knave, so C is a knight. This is consistent with our initial assumption.

So in the case that C is a knight, no contradiction arises. The other case is that C is a knave. One can check that this leads to D being a knight without contradictions.