Logical Proofs

This page is a learning resource for those people who want to learn how to do logical proofs. Disclaimer: The information provided here is solely from my own experiences in university logic classes. The goal of this page is to be an easy to understand and to-the-point guide for complete beginners to mathematical proofs.

Proofs can be thought of as 'mathematical writing' with the purpose of showing that an idea is true or false. However, before actually looking at proofs, it's necessary to develop some mathematical language. The next section on propositions will serve as the foundation for a number of key ideas moving forward.

Propositional Translation

For the first part, we are going to learn how to translate natural language into logical expressions. For this we'll use operators shown in the following table:

Symbol	Meaning	Translations
$\lnot A$ $\sim A\,$	Negation	Not A
$(A\vee B)$	Or	A or B
$(A\land B)$ $(A\cdot B)$	And	A and B
$(A\rightarrow B)$ $(A\Rightarrow B)$ $(A\supset B)$	Implication	If A then B A implies B
$(A\leftrightarrow B)$ $(A\Leftrightarrow B)$ $(A\equiv B)$	Equivalence	A if and only if B

In the table above, A and B are arbitrary letters that each represent a proposition, which is a statement that is strictly either true or false. For example, we could have A represent the statement "The capital of New York is Albany," and B represent the statement "2 + 2 = 1029384.234." In this case, the truth value (status of being either true or false) of A would be True and would be False for B. Here are some examples of statements that are not propositions:

"It's a nice day today." - This statement is rather subjective. There isn't a universal metric to label the 'niceness' of a given day as a binary true or false.

"x + 1 = 2" - We don't know whether this statement is true or not because we don't know what x is. While one might look at this and think, x must obviously be 1, therefore the statement can be true, recall that propositions can also be false. Rather than thinking of this as an equation to be solved, look at it like more like a question, "is x plus 1 equal to 2?" which we cannot answer without knowing the value of x. However, if the statement separately told us that x is equal to 1, then we could say that x + 1 = 2 is true.

Mathematical Or

Let us begin by looking at the Or operator, denoted by the symbol $\vee$.

Suppose that A and B are propositions. The expression "A or B", denoted, $(A\vee B)$, is true when either A or B is true.

As a quick note on 'or' in the English language, there is an 'inclusive or' and an 'exclusive or', which people usually determine through context clues. For example, the 'or' used in "The meal comes with soup or salad" is an 'exclusive or' because it's implied that you can only choose one, not both. On the other hand, "Please bring a drivers license or student ID" would have an 'inclusive or', because while you can bring one or the other, there won't be any problem if you bring both. Since there can be quite a bit of ambiguity in spoken language, moving forward we'll need to make some assumptions as to what certain words really mean. One such assumption will be that in a statement, 'or' will refer to the inclusive or, and that the exclusive or (sometimes shortened to XOR) will be explicitly stated when used.

A truth table is a table that shows the outcomes of all possible truth value combinations of the components of the proposition.

A	B	$(A\vee B)$
True	True	True
True	False	True
False	True	True
False	False	False

Since $(A\vee B)$ depends on only A and B, we list the truth values of A and B, followed by a column for the truth value of A or B. Notice that $(A\vee B)$ is only false when both A and B are false.

Lastly, notice that both A and $(A\vee B)$ are propositions. As shown by the truth table, the $(A\vee B)$ column only has results that are True or False, depending on the components A and B; recall that the definition of a proposition is a statement that is either true or false. That is to say that propositions can be as short as one letter, or can be a convoluted expression of many components. However, in the end, a proposition will always boil down to being true or false.

Example, evaluate the truth value of this statement: "Either Chicago is in Georgia or Canada is south of Detroit."

Step 1: Convert the statement from English into mathematical notation.

Select letters to represent the smallest propositions involved in the statement and identify any operators used. Recall that choice of letters is arbitrary, so instead of A and B, we could declare that G represents the statement "Chicago is in Georgia", and D represents "Canada is south of Detroit." Then, in mathematical notation, the entire statement is $(G\vee D)$

Step 2: Evaluate truth values

The proposition G is false, because Chicago is in Illinois. The proposition D is true, surprisingly (look at a map). With this in mind, we can substitute in the truth values and evaluate the expression: False $\vee$ True. Referencing the truth table for the Or operator (which shows that for $(A\vee B)$, as long as at least one of the propositions A and B is true, $(A\vee B)$ is true), we conclude that $(G\vee D)$ is true, and therefore the original statement is true.

Mathematical And

The And operator is denoted by $\land$. Suppose that A and B are two propositions. Then the proposition "A and B", denoted $(A\land B)$, is true whenever both A and B are true, and false if either A or B is false. See the truth table below:

A	B	$(A\land B)$
True	True	True
True	False	False
False	True	False
False	False	False

Similar to the Or operator, the truth value after applying the And operator in $(A\land B)$ depends on the truth values of the propositions A and B. For example, consider the statement "I did my homework and I cleaned my room." Suppose H and C are propositions where H represents "I did my homework" and C represents "I cleaned my room". Then the statement can be written as $(H\land C)$. The entire statement is only true when both H and C are true, as in, I've actually finished my homework and cleaned my room. However, if I lied about cleaning my room, then the proposition "I cleaned my room" would be false, and in turn, the statement "I did my homework and I cleaned my room" would also be false. With the And operator, having one component being false is enough to make the entire statement false. And then if it turns out I lied about cleaning my room and doing homework, then both H and C are false, and $(H\land C)$ is unquestionably false.

Negation

Next is the negation operator, denoted by $\lnot$. The negation operator acts on one proposition, such as $\lnot A$, which is read as "not A".

A	$\lnot A$
True	False
False	True

As shown in the above truth table, negation reverses the truth value of the proposition. Suppose we have the statement "I don't have a cat," and want to express this statement using mathematical notation. One option would be to declare: let D be the proposition "I don't have a cat." Then the statement would just be D. Another option would be to declare: let C be the proposition "I do have a cat". In this case, the statement would be $\lnot C$, as in, the negation of C. Note that propositions D and $\lnot C$ mean the same thing and are interchangeable (some may prefer to keep their propositions in positive language and use negations).

Specifically, two propositions are equivalent if they have the same truth values (in the future, $\equiv$ will be used to specifically denote equivalence).

Let's show that D is equivalent to $\lnot C$:

Case 1: Suppose that the speaker actually has a cat. Then the truth value of D, "I don't have a cat," would be false, and the truth value of C, "I have a cat," would be true. However, since $\lnot C$ means that we must negate C, and since the negation of true is false, $\lnot C$ is also false.

Case 2: Suppose that the speaker does not have a cat. Then the truth value of D would be true, and the truth value of C would be false. It follows that $\lnot C$ is true.

In both cases, D and $\lnot C$ have the same truth value. Since we have looked at all possible cases, we conclude that D and $\lnot C$ are equivalent. (Although it would also be valid- and perhaps easier- to show this point by comparing truth table columns, a method used in the section below)

Conditional Statements

Suppose that A and B are propositions. Then $(A\rightarrow B)$ is read "If A, then B." This is known as a conditional statement. (Note: things will start getting a little more complicated now)

A	B	$(A\rightarrow B)$
True	True	True
True	False	False
False	True	True
False	False	True

Notice that $(A\rightarrow B)$ is only false when A is true and B is false, and is true otherwise. Consider the statement "If you come shopping with me, then I'll buy you some takoyaki." Let S and T be propositions, where S is "You came shopping with me" and T is "I bought you takoyaki." Now, let's analyze the proposition $(S\rightarrow T)$. As in, suppose one morning I declared that original statement: "If you come shopping with me, then I'll buy you some takoyaki." When S and T are both true, it means that at the end of the day, you came shopping with me and I bought you takoyaki. Then, the original statement $(S\rightarrow T)$ is true, or I honored my word. Now suppose that you don't come shopping with me; then, S is false. In that case, whether I choose to buy takoyaki for you anyway or not, the original statement still holds true. In $(S\rightarrow T)$, the event where you get takoyaki was dependent on whether you shopping with me: T is dependent on S. When S is false, all bets are off on T. The only situation where I'd be a liar is if you come shopping with me and I don't buy you takoyaki, which corresponds to when S is true and T is false; this is also the only case when $(S\rightarrow T)$ is false.

One common area of confusion with conditionals is correctly identifying the conditional relationship when reading a statement. That is to say, while the "If A, then B" format is common and perhaps the most clear way to state a conditional relationship $(A\rightarrow B)$, conditionals can be implied from many different phrasings, such as: "A is sufficient for B", "A only B", "B, if A", "B whenever A", and "B is necessary for A."

Conditional statements are important because there are a number of proof methods specifically for proving statements in the $(A\rightarrow B)$ format, which will be discussed later down the page.

Lastly, suppose we have a conditional statement, $(A\rightarrow B)$.

1. The converse of $(A\rightarrow B)$ is $(B\rightarrow A)$. One can think of it as, converse is the reverse of the conditional. To compare the truth values of the original conditional and the converse, consider the following truth table:

A	B	$(A\rightarrow B)$	$(B\rightarrow A)$
True	True	True	True
True	False	False	True
False	True	True	False
False	False	True	True

Notice that the columns for $(A\rightarrow B)$ and $(B\rightarrow A)$ are not the same. A conditional statement is not equivalent to its converse (more about equivalence later as well).

2. The inverse of $(A\rightarrow B)$ is $(\lnot A\rightarrow \lnot B)$. As in, the inverse inverts the truth value of each side of the conditional.

A	B	$(A\rightarrow B)$	$\lnot A$	$\lnot B$	$(\lnot A\rightarrow \lnot B)$
True	True	True	False	False	True
True	False	False	False	True	True
False	True	True	True	False	False
False	False	True	True	True	True

As shown above, the columns for the original conditional statement, $(A\rightarrow B)$, and its inverse, $(\lnot A\rightarrow \lnot B)$, do not have the same truth values for each row. Therefore they are not the equivalent.

3. The contrapositive of $(A\rightarrow B)$ is $(\lnot B\rightarrow \lnot A)$. (So, while the converse flips A and B, and the inverse negates both sides, the contrapositive does both.) Unlike the converse and inverse, the contrapositive actually is equivalent to the original conditional statement; the truth table columns match for each row.

A	B	$(A\rightarrow B)$	$\lnot A$	$\lnot B$	$(\lnot B\rightarrow \lnot A)$
True	True	True	False	False	True
True	False	False	False	True	False
False	True	True	True	False	True
False	False	True	True	True	True

Also, notice that the converse and inverse of a conditional statement have matching truth values for matching truth value combinations of A and B. This is because, suppose we take the contrapositive of the converse of $(A\rightarrow B)$, the contrapositive of $(B\rightarrow A)$ is (flip the positions of the two propositions that the conditional is acting on and then negate both sides...) $(\lnot A\rightarrow \lnot B)$, which is the same as the inverse of $(A\rightarrow B)$. This property that a conditional statement is equivalent to its contrapositive will be important moving forward, and will be a key idea behind a certain proof technique.

Lastly, note that the contrapositive of the contrapositive is just the original conditional statement. As in, the contrapositive of $(A\rightarrow B)$ is $(\lnot B\rightarrow \lnot A)$, and then the contrapositive of $(\lnot B\rightarrow \lnot A)$ is $(A\rightarrow B)$.

Biconditional Statement

Suppose we have propositions A and B. Then $A\leftrightarrow B$ is a biconditional statement, read as "A if and only if B." The keywords for a biconditional are "if and only if," which is sometimes abbreviated to "iff". Other ways of implying a biconditional statement are: "A is necessary and sufficient for B", "A is equivalent to B", and "A implies B, and conversely."

A	B	$(A\leftrightarrow B)$
True	True	True
True	False	False
False	True	False
False	False	True

As shown by the truth table, the biconditional is only true when A and B have the same truth value, and is false otherwise. Before doing any examples, some definitions:

A tautology is a proposition that is true for every assignment of truth values to its components. That is, a tautology is always true. A simple example is $A\leftrightarrow A$. Since A can only be true or false, the proposition can only be evaluated as True $\leftrightarrow$ True, or False $\leftrightarrow$ False. In either case, the biconditional would be true.

A contradiction is a proposition that is false for every assignment of truth values to its components. As in, a contradiction is always false. Consider the example $A\land \lnot A$. Once again, A can only be true or false. If A is True then the proposition is True $\land$ False, and if A is False then the proposition is False $\land$ True. In either case, since the And operator is acting on a True and a False, the proposition will always be false.

Notice that since $A\leftrightarrow B$ is true precisely when A and B are the same, the propositions A and B are equivalent when $A\leftrightarrow B$ is a tautology.

Also, the biconditional statement $A\leftrightarrow B$ is equivalent to the expression $(A\rightarrow B)\land (B\rightarrow A)$, as shown by how these two propositions have matching truth values in the truth table below.

A	B	$(A\leftrightarrow B)$	$(A\rightarrow B)$	$(B\rightarrow A)$	$(A\rightarrow B)\land (B\rightarrow A)$
True	True	True	True	True	True
True	False	False	False	True	False
False	True	False	True	False	False
False	False	True	True	True	True

What this means is that a biconditional statement $A\leftrightarrow B$ is the same as saying that A implies B and B implies A. This may help when determining whether a biconditional statement is true or not. For instance, let R and C be propositions, where R is "It's raining" and C is "It's cloudy." Is $R\leftrightarrow C$ always true? Let's first consider $R\rightarrow C$. Recall that a conditional statement has only one situation where it evaluates to be false: when we have True $\rightarrow$ False. If R is true, then it's raining, and if it's raining, does that mean it must be cloudy? For simplicity let's ignore sunshowers. Then, $R\rightarrow C$ must be a tautology because there are no situations where it's raining and there are no clouds (because the rain needs to come from somewhere). Next, let us consider $C\rightarrow R$. Is there a situation where $C\rightarrow R$ is false? As in, where it's cloudy and it's not raining? Yes. That's actually what I'm seeing outside my window right now. Continuing, since it is possible for $C\rightarrow R$ to be false, there exists a case where $(R\rightarrow C)\land (C\rightarrow R)$ is also false. And since $R\leftrightarrow C$ is equivalent to $(R\rightarrow C)\land (C\rightarrow R)$, it follows that it is possible for $R\leftrightarrow C$ to be false. Therefore, $R\leftrightarrow C$ is not a tautology, and R is not equivalent to C.

Theorems Section 1

These theorems are some of the truths that logically follow from the material we've covered so far. As in, it's possible to derive them using the ideas previously discussed. In the examples section below, it will be shown precisely how to derive some of them.

These first couple of theorems will be for showing that certain propositions are equivalent. It's possible to verify all these by drawing a truth table and comparing columns. Although, I do recommend taking some time to look at each of these and logically reason to yourself why they must be true.

A quick note on how to decide what operators to apply first in a more complicated proposition:

Symbols with Highest Priority (decreasing priority as you go down the list)
$\lnot$
$\land$
$\lor$
$\rightarrow$
$\leftrightarrow$

If a symbol appears more than once, then apply them from left to right. For example, A $\land$ B $\lor$ C $\land$ D would be evaluated in this order: first A $\land$ B, then C $\land$ D, and lastly use the truth values of the previous two propositions to evaluate the Or operator. Of course, parenthesis will also help show you grouping/priority (the prior proposition could've been written (A $\land$ B) $\lor$ (C $\land$ D)), but sometimes propositions won't be written with any parenthesis and the order will be completely implied based on the application priority shown above. I usually like to use parenthesis as much as possible for the sake of clarity though.

Theorem 1.1: For propositions A, B, and C, the following are equivalent:

1. $A\equiv \lnot (\lnot A)$
2. $(A\lor B)\equiv (B\lor A)$
3. $(A\land B)\equiv (B\land A)$
4. $A\lor (B\lor C)\equiv (A\lor B)\lor C$
5. $A\land (B\land C)\equiv (A\land B)\land C$
6. $A\land (B\lor C)\equiv (A\land B)\lor (A\land C)$
7. $A\lor (B\land C)\equiv (A\lor B)\land (A\lor C)$

If you look at Theorem 1.1.2 through 1.1.5 all together, it basically just says that if you have a proposition that exclusively has Or operators (or exclusively has And operators), then it doesn't really matter what order you evaluate all the individual Or operators (or And operators). For instance, suppose you have: True $\land$ True $\land$ False $\land$ True. Then, you can evaluate the proposition:

(True $\land$ True) $\land$ False $\land$ True $\equiv$ True $\land$ False $\land$ True $\equiv$ True $\land$ True $\land$ False $\equiv$ (True $\land$ True) $\land$ False $\equiv$ True $\land$ False $\equiv$ False

Or you can just go from left to right: True $\land$ True $\land$ False $\land$ True $\equiv$ True $\land$ False $\land$ True $\equiv$ False $\land$ True $\equiv$ False

Note: this is only when you have a bunch of And operators (or Or operators) together! On the other hand, for example, if you have some And operators spread out over a proposition but not all together, like $(A\land B)\rightarrow (C\land D)$, then evaluate them from left to right as previously mentioned for default application order, unless implied otherwise by parenthesis.

As for Theorems 1.1.6 and 1.1.7, these are the Distributive Laws. The idea is somewhat similar to when you want to distribute in an expression like x * (y + z), which would be equal to xy + xz.

Theorem 1.2: DeMorgan's Laws. For propositions A and B, the following are equivalent:

1. $\lnot (A\land B)\equiv \lnot A\lor \lnot B$
2. $\lnot (A\lor B)\equiv \lnot A\land \lnot B$

DeMorgan's Laws are helpful for when you have a negation acting on some expression enclosed by parentheses, and want to get rid of those parenthesis. A quick dialogue about these:

• MathPerson: So, what's the negation of A and B? For example, if "A and B" was "I showered and I brushed my teeth"?
• ThisOtherGirl: Hmm. Is it "I didn't shower and I didn't brush my teeth"?
• MathPerson: Whoa! Wait just a moment there...
• ThisOtherGirl: Ohh no I got it, since with 'AND' statements, only one of them need to be false to make the entire statement false.. It would be "I didn't shower OR I didn't brush my teeth".
• MathPerson: That's right! When we negate an AND statement, we're saying that the statement is false. In this case, that means that one of the propositional components (being "I showered" and "I brushed my teeth") must be false. The way that there's an AND operator on one side of the equivalence side and an OR operator on the other is important! Now, what if we wanted to negate the statement "I showered or I brushed my teeth"?
• ThisOtherGirl: An OR statement is false when both components are false... so "I didn't shower and I didn't brush my teeth".
• MathPerson: Excellent! I'm so proud of you!

Theorem 1.3: For propositions P, Q, and R, the following are equivalent:

1. $P\rightarrow Q\equiv \lnot P\lor Q$
2. $\lnot (P\land Q)\equiv Q\rightarrow \lnot P$
3. $P\leftrightarrow Q\equiv (P\rightarrow Q)\land (Q\rightarrow P)$
4. $P\rightarrow (Q\rightarrow R)\equiv (P\land Q)\rightarrow R$
5. $\lnot (P\rightarrow Q)\equiv P\land \lnot Q$
6. $P\rightarrow (Q\land R)\equiv (P\rightarrow Q)\land (P\rightarrow R)$
7. $\lnot (P\land Q)\equiv P\rightarrow \lnot Q$
8. $(P\lor Q)\rightarrow R\equiv (P\rightarrow R)\land (Q\rightarrow R)$

Ok, I know that the statements above look way more complicated, but the only really important parts of Theorem 1.3 are 1.3.1 and 1.3.3. Although, we already went over 1.3.3 in the biconditional section above. Theorem 1.3.1 will just be really useful when you're manipulating an expression using equivalence. The rest of the equivalences can be derived using 1.3.1 and Theorems 1.1 and 1.2 (which is exactly what you can do in the Exercises section below!). As a quick example though, let's show that Theorem 1.3.5, $\lnot (P\rightarrow Q)\equiv P\land \lnot Q$, is true. To do this, you can start using either side of the equivalence sign, and use other equivalences in order to get an expression that matches the other side of the equivalence. As in:

$\lnot (P\rightarrow Q)\equiv \lnot (\lnot P\lor Q)\equiv \lnot (\lnot P)\land \lnot Q\equiv P\land \lnot Q$

We get from $\lnot (P\rightarrow Q)$ to $\lnot (\lnot P\lor Q)$ by using Theorem 1.3.1, which allows us to replace the $P\rightarrow Q$ in the parenthesis with $\lnot P\lor Q$. Next, to get from $\lnot (\lnot P\lor Q)$ to $\lnot (\lnot P)\land \lnot Q$, we use Theorem 1.2.2, which helps us apply the negation to the expression within the parenthesis. Since there's already a negation acting on P, the negation you get after using DeMorgan's Law just stacks onto $(\lnot P)$, making the double negated $\lnot (\lnot P)$. Of course, $\lnot (\lnot P)$ can be reduced to just $P$ by using Theorem 1.1.1. Which is how we get from $\lnot (\lnot P)\land \lnot Q$ to $P\land \lnot Q$. Since $P\land \lnot Q$ is the other side of the equivalence in Theorem 1.3.5, we've shown that $\lnot (P\rightarrow Q)\equiv P\land \lnot Q$.

Note that since equivalences are a two way street, if $\lnot (P\rightarrow Q)\equiv P\land \lnot Q$ is true then so is $P\land \lnot Q\equiv \lnot (P\rightarrow Q)$.

Exercises Section 1

Ready to get started on some exercises? Then go ahead and try some of these problems out! (There are answers and full explanations for each problem below the questions.) Oh, but I do recommend reading the answer to Exercise 1 before taking a stab at the harder proving-equivalence problems. (More information about these types of biconditional proofs later!)

Exercise 1: Above, we proved Theorem 1.3.5 by showing there's a chain of equivalences that let you get from $\lnot (P\rightarrow Q)$ to $P\land \lnot Q$. However, another valid approach would be to show that there's a way to get from $P\land \lnot Q$ to $\lnot (P\rightarrow Q)$ instead. Why not try to do precisely that?

Solving math problems can be stressful. So here's a cat picture to .. maybe help? You can do it! Although it's also perfectly fine to mess up exercises. The experience of trying and failing and learning will ultimately result in a better understanding.

Exercise 2: Prove that Theorem 1.1.4, $A\lor (B\lor C)\equiv (A\lor B)\lor C$, is true using a truth table.

Exercise 3: Prove Theorem 1.3.4, $P\rightarrow (Q\rightarrow R)\equiv (P\land Q)\rightarrow R$, is true using equivalences.

Exercise 4: Prove that Theorem 1.3.2, $\lnot (P\land Q)\equiv Q\rightarrow \lnot P$, is true using a truth table.

Exercise 5: Convert "Grapes grow on vines and pistachios grow on trees" into a propositional form. (Optional: evaluate the truth value of the proposition)

Exercise 6: Explain using words why Theorem 1.3.1, $P\rightarrow Q\equiv \lnot P\lor Q$, must be true. (Hint, look at the truth table for $P\rightarrow Q$)

Exercise 7: Prove that Theorem 1.3.8, $(P\lor Q)\rightarrow R\equiv (P\rightarrow R)\land (Q\rightarrow R)$, is true using equivalences.

Exercise 8: Cindy is a senior in high school. One morning she walked into her first period accounting class fashionably late while holding a cup of brand coffee. Unfortunately the accounting teacher is in a bad mood and says, "I will not write you up if and only if you have a note from the office and you have been late less than three times this year, or if you completed today's homework and your parents called the office ahead of time." Cindy does have a note from the office, this is the tenth time she's late this year, she did complete today's homework, and her parents did not call. Assuming that the accounting teacher keeps their word, what is the outcome of this situation?

******************************************************************* Answers are below! Scroll down when ready! ********************************************************************

*********************************************************************************************************************************************************************************************

*********************************************************************************************************************************************************************************************

Answers Section 1

Exercise 1:

One approach is to just do what we did earlier except in reverse. That is:

$P\land \lnot Q\equiv \lnot (\lnot P)\land \lnot Q\equiv \lnot (\lnot P\lor Q)\equiv \lnot (P\rightarrow Q)$

The reasons for manipulating the proposition in each step would still correspond to the respective theorems used earlier, although the process is less intuitive compared to the process starting with $\lnot (P\rightarrow Q)$. We can also look at the problem starting from scratch. In general, when I'm not sure how to proceed with a proof problem, the first thing I do is reread all of the theorems, and look for anything that might be useful. At a glance, Theorem 1.1.1 could be useful, since the expression we're working with has a negation in it, but the rest of Theorem 1.1 doesn't seem super relevant because we're starting with only one Or operator and $P\land \lnot Q\equiv \lnot Q\land P$ won't really move anything forward. Theorem 1.2.2 might be helpful for putting in parenthesis, but it won't get us to the desired end result. It could possibly serve as an intermediary step though, so let's remember it for now. Lastly, looking at Theorem 1.3, the equivalences that stand out are the ones where one side of the equivalence looks like $P\land \lnot Q$, or looks like something we can get to from $P\land \lnot Q$ (but not including Theorem 1.3.5, because using the theorem you're trying to prove in the proof for that theorem will make a circular proof!! it's invalid to assume something is true before you've proved it's true!!). Anyway, Theorem 1.3 has a couple theorems where one side of the equivalence is of the form $\lnot (P\land Q)$, but we can't use these because recall from DeMorgan's laws, putting in parenthesis means we'll have to switch the And operator in $P\land \lnot Q$to an Or operator. As in, using Theorem 1.2.2 ($\lnot A\land \lnot B\equiv \lnot (A\lor B)$),

$P\land \lnot Q\equiv \lnot (\lnot P\lor \lnot (\lnot Q))\equiv \lnot (\lnot P\lor Q)$.

Fortunately, the expression inside the parenthesis, $\lnot P\lor Q$ , appears as the right hand side of Theorem 1.3.1 ($P\rightarrow Q\equiv \lnot P\lor Q$). Therefore, we can do some substitution and get $\lnot (\lnot P\lor Q)\equiv \lnot (P\rightarrow Q)$. Since $\lnot (P\rightarrow Q)$ is exactly the proposition we want, we're done!

Exercise 2:

A	B	C	$(A\lor B)$	$(B\lor C)$	$A\lor (B\lor C)$	$(A\lor B)\lor C$
True	True	True	True	True	True	True
True	True	False	True	True	True	True
True	False	True	True	True	True	True
True	False	False	True	False	True	True
False	False	False	False	False	False	False
False	False	True	False	True	True	True
False	True	False	True	True	True	True
False	True	True	True	True	True	True

Ok actually, this problem might've been trickier than it looked because it actually has three components (A, B, and C), whereas previous examples had at most two. In the truth table, it's necessary to have a row for each possible assignment of True/False for each of the three components. The shortcut for finding how many rows you need is calculating two to the power of the number of components. Here, it would be 2^3, which is equal to 8, hence the 8 rows. Although honestly, you shouldn't have to draw a truth table for more than three components, so you don't really need to memorize the calculation shortcut. (If you're interested in the reasoning behind why it's two to the power of the number of components, it's based on the idea of combinations from probability.)

Also, you can also organize the columns however you think makes the most sense. In this case, the components are all at the left, the columns we want to compare are at the right, and the columns in the middle are parts that we need to evaluate to get to the columns we want to compare. This is just to make it so that it's less likely for mistakes to happen (when filling in a new column, you only need to apply one operation and you can reference the previous columns). You can also omit some columns if you're lazy, as long as you have a column for each of the smallest components (in this case A, B, and C), as well as for the two expressions you're trying to prove are equivalent.

Exercise 3:

So we want to prove $P\rightarrow (Q\rightarrow R)\equiv (P\land Q)\rightarrow R$. I'll start with the left hand side of the equivalence, but if you started from the right or used a different approach, no problem! In proofs there's often multiple ways to go about things. Anyway, my first thoughts looking at the left hand side there is to try doing out both of those conditionals (using Theorem 1.3.1) and see where that gets us. Reasoning being that our options are super limited with $P\rightarrow (Q\rightarrow R)$, and getting rid of those conditionals might open some new possibilities (and also because the expression on the right of the equivalence has an And operator, hmm).

$P\rightarrow (Q\rightarrow R)\equiv P\rightarrow (\lnot Q\lor R)\equiv \lnot P\lor (\lnot Q\lor R)$

From here, the path forward is a lot clearer. Let's use Theorem 1.1.4 to move those parenthesis: $\lnot P\lor (\lnot Q\lor R)\equiv (\lnot P\lor \lnot Q)\lor R$

This is relevant because now we can use DeMorgan's Laws, specifically Theorem 1.2.1, in order to pull out the negations get the And operator we want between P and Q: $(\lnot P\lor \lnot Q)\lor R\equiv \lnot (P\land Q)\lor R$

We're really close now. For the last step, we'll use Theorem 1.3.1 one more time, and then we're done: $\lnot (P\land Q)\lor R\equiv (P\land Q)\rightarrow R$

As a quick note about that last step, note that even though in the theorems we use singular letters to represent propositions, those letters could actually be standing in for longer propositions. Recall that $A,(A\lor B),(A\land B\land C\rightarrow D)$, could all be considered propositions; a proposition is anything that is ultimately true or false. So even though Theorem 1.3.1 is $P\rightarrow Q\equiv \lnot P\lor Q$, we could just as well say that A and B are propositions where A is $(P\land Q)$ and B is $R$. Then say:

$\lnot (P\land Q)\lor R\equiv \lnot A\lor B\equiv A\rightarrow B\equiv (P\land Q)\rightarrow R$

(by substituting in and out the propositions for A and B). It's not necessary of course, this is just to show that the P, Q, R, or whatever letters that appear in theorems, can represent longer expressions.

Lastly, this is how you could write the full answer:

$P\rightarrow (Q\rightarrow R)\equiv P\rightarrow (\lnot Q\lor R)\equiv \lnot P\lor (\lnot Q\lor R)\equiv (\lnot P\lor \lnot Q)\lor R\equiv \lnot (P\land Q)\lor R\equiv (P\land Q)\rightarrow R$

Therefore, it follows that $P\rightarrow (Q\rightarrow R)\equiv (P\land Q)\rightarrow R$.

Exercise 4:

No catch this time, just a 4 row truth table:

P	Q	$\lnot P$	$(P\land Q)$	$\lnot (P\land Q)$	$Q\rightarrow \lnot P$
True	True	False	True	False	False
True	False	False	False	True	True
False	True	True	False	True	True
False	False	True	False	True	True

Exercise 5:

Let G and P be propositions, where G is "Grapes grow on vines" and P is "Pistachios grow on trees". Then the statement can be expressed as $G\land P$. Both G and P are true, so by the definition of the And operator, $G\land P$ is also true.

Exercise 6:

I'll just put a copy of the truth table for $P\rightarrow Q$ here:

P	Q	$(P\rightarrow Q)$
True	True	True
True	False	False
False	True	True
False	False	True

So, let's say we wanted to create an expression that also accepts two components, P and Q, and is true when $P\rightarrow Q$ is also true. Recall that when P is false, $P\rightarrow Q$ will always be true, regardless of Q (as shown by the last two rows of the truth table). However, if we had our expression just be $\lnot P$, then we wouldn't be accounting for the situation when $P\rightarrow Q$ is true because both P and Q are true. You might've also noticed that $P\rightarrow Q$ is always true whenever Q is true. Hence, $\lnot P\lor Q$. The only situation when $P\rightarrow Q$ is false is when P is true and Q is false, which would also correspond to $(\lnot True)\lor False$, or just $False\lor False$, which is also false.

Exercise 7:

Ok now we're proving $(P\lor Q)\rightarrow R\equiv (P\rightarrow R)\land (Q\rightarrow R)$. This time I think I'd opt to start with the right hand side (but again, no problem if you went about this in a different way!). Let's try getting rid of those conditionals again.

$(P\rightarrow R)\land (Q\rightarrow R)\equiv (\lnot P\lor R)\land (Q\rightarrow R)\equiv (\lnot P\lor R)\land (\lnot Q\lor R)$

Hmm. Now we've got to an expression that reminds me of the distributive laws in Theorem 1.1. Specifically Theorem 1.1.7, $A\lor (B\land C)\equiv (A\lor B)\land (A\lor C)$, although the formatting looks a little different. Fortunately we can just move around the order a little bit using Theorem 1.1.2.

$(\lnot P\lor R)\land (\lnot Q\lor R)\equiv (R\lor \lnot P)\land (R\lor \lnot Q)\equiv R\lor (\lnot P\land \lnot Q)\equiv (\lnot P\land \lnot Q)\lor R$

Now we've got to a point that should look a little familiar. Similar to Exercise 3, let's use DeMorgan's Laws (although Theorem 1.2.2 this time) to pull out the negation, and then finish with Theorem 1.3.1.

$(\lnot P\land \lnot Q)\lor R\equiv \lnot (P\lor Q)\lor R\equiv (P\lor Q)\rightarrow R$

Therefore, $(P\lor Q)\rightarrow R\equiv (P\rightarrow R)\land (Q\rightarrow R)$.

Exercise 8:

First, let's convert the accounting teacher's words into propositional form (there are different ways of doing this, particularly with handling the negation).

Let W, N, T, H, and P be propositions, where W is "Accounting teacher writes Cindy up", N is "Cindy has a note", T is "Cindy has been late less than three times", H is "Cindy did today's homework", and P is "Cindy's parents called the office."

Then, the teachers statement is: $\lnot W\leftrightarrow N\land T\lor H\land P$

You can also include parenthesis to make it $\lnot W\leftrightarrow (N\land T)\lor (H\land P)$, which is the same as above, but maybe less confusing to look at.

Anyway, using what we know, we can assign truth values to all the propositional components on the right hand side of the biconditional: N - True, T - False, H - True, P - False. Then, evaluating the right hand side, $(N\land T)\lor (H\land P)$, we have:

$(True\land False)\lor (True\land False)\equiv (False)\lor (False)\equiv False$

Therefore, the biconditional is $\lnot W\leftrightarrow False$.

Since we're assuming that the accounting teacher keeps their word (which implies that the biconditional is a tautology) and the right side of the biconditional is false, the left hand side, $\lnot W$, must also be false. And, if $\lnot W$ is false, then $\lnot (\lnot W)$ must be true. Given that $\lnot (\lnot W)\equiv W$, it follows that W is true. Recall that W is "Accounting teacher writes Cindy up".

Sooooooo, in the end, it looks like Cindy ran into a spot of bad luck today.

Anyway, congratulations on making it to the end of the first exercises and answers section!

Direct Proofs

At this point we're finally ready to get started on writing proofs.