4.1 Propositional Logic

A proposition is simply a statement. Propositional logic studies the ways statements can interact with each other. It is important to remember that propositional logic does not really care about the content of the statements. For example, in terms of propositional logic, the claims, “if the moon is made of cheese then basketballs are round,” and “if spiders have eight legs then Sam walks with a limp” are exactly the same. They are both implications: statements of the form, $P \to Q$ .

Truth Tables

Here's a question about playing Monopoly:

If you get more doubles than any other player then you will lose, or if you lose then you must have bought the most properties.

True or false? We will answer this question, and won't need to know anything about Monopoly. Instead we will look at the logical form of the statement.

We need to decide when the statement $open parenthesis P → Q close parenthesis ∨ open parenthesis Q → R close parenthesis$ is true. Using the definitions of the connectives in Mathematical Statements, we see that for this to be true, either $P \to Q$ must be true or $Q \to R$ must be true (or both). Those are true if either $P$ is false or $Q$ is true (in the first case) and $Q$ is false or $R$ is true (in the second case). So—yeah, it gets kind of messy. Luckily, we can make a chart to keep track of all the possibilities. Enter truth tables. The idea is this: on each row, we list a possible combination of T's and F's (for true and false) for each of the sentential variables, and then mark down whether the statement in question is true or false in that case. We do this for every possible combination of T's and F's. Then we can clearly see in which cases the statement is true or false. For complicated statements, we will first fill in values for each part of the statement, as a way of breaking up our task into smaller, more manageable pieces.

Since the truth value of a statement is completely determined by the truth values of its parts and how they are connected, all you really need to know is the truth tables for each of the logical connectives. Here they are:

$P$	$Q$	$P ∧ Q$
T	T	T
T	F	F
F	T	F
F	F	F

$P$	$Q$	$P ∨ Q$
T	T	T
T	F	T
F	T	T
F	F	F

$P$	$Q$	$P \to Q$
T	T	T
T	F	F
F	T	T
F	F	T

$P$	$Q$	$P \leftrightarrow Q$
T	T	T
T	F	F
F	T	F
F	F	T

The truth table for negation looks like this:

P

\neg P

None of these truth tables should come as a surprise; they are all just restating the definitions of the connectives. Let's try another one.

Example 1

Make a truth table for the statement $¬ P ∨ Q$ .

Note that this statement is not $¬ open parenthesis P ∨ Q close parenthesis$ , the negation belongs to $P$ alone. Here is the truth table:

$P$	$Q$	$\neg P$	$¬ P ∨ Q$
T	T	F	T
T	F	F	F
F	T	T	T
F	F	T	T

We added a column for $\neg P$ to make filling out the last column easier. The entries in the $\neg P$ column were determined by the entries in the $P$ column. Then to fill in the final column, look only at the column for $Q$ and the column for $\neg P$ and use the rule for $∨$ .

Now let's answer our question about monopoly:

Example 2

Analyze the statement, “if you get more doubles than any other player you will lose, or that if you lose you must have bought the most properties,” using truth tables.

Represent the statement in symbols as $open parenthesis P → Q close parenthesis ∨ open parenthesis Q → R close parenthesis$ , where $P$ is the statement “you get more doubles than any other player,” $Q$ is the statement “you will lose,” and $R$ is the statement “you must have bought the most properties.” Now make a truth table.

The truth table needs to contain 8 rows in order to account for every possible combination of truth and falsity among the three statements. Here is the full truth table:

$P$	$Q$	$R$	$P \to Q$	$Q \to R$	$open parenthesis P → Q close parenthesis ∨ open parenthesis Q → R close parenthesis$
T	T	T	T	T	T
T	T	F	T	F	T
T	F	T	F	T	T
T	F	F	F	T	T
F	T	T	T	T	T
F	T	F	T	F	T
F	F	T	T	T	T
F	F	F	T	T	T

The first three columns are simply a systematic listing of all possible combinations of T and F for the three statements (do you see how you would list the 16 possible combinations for four statements?). The next two columns are determined by the values of $P$ , $Q$ , and $R$ and the definition of implication. Then, the last column is determined by the values in the previous two columns and the definition of $∨$ . It is this final column we care about.

Notice that in each of the eight possible cases, the statement in question is true. So our statement about monopoly is true (regardless of how many properties you own, how many doubles you roll, or whether you win or lose).

The statement about monopoly is an example of a tautology, a statement which is true on the basis of its logical form alone. Tautologies are always true but they don't tell us much about the world. No knowledge about monopoly was required to determine that the statement was true. In fact, it is equally true that “If the moon is made of cheese, then Elvis is still alive, or if Elvis is still alive, then unicorns have 5 legs.”

Logical Equivalence

You might have noticed in Example that the final column in the truth table for $¬ P ∨ Q$ is identical to the final column in the truth table for $P \to Q$ :

$P$	$Q$	$P \to Q$	$¬ P ∨ Q$
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

This says that no matter what $P$ and $Q$ are, the statements $¬ P ∨ Q$ and $P \to Q$ either both true or both false. We therefore say these statements are logically equivalent.

Recognizing two statements as logically equivalent can be very helpful. Rephrasing a mathematical statement can often lend insight into what it is saying, or how to prove or refute it. By using truth tables we can systematically verify that two statements are indeed logically equivalent.

Example 3

Are the statements, “it will not rain or snow” and “it will not rain and it will not snow” logically equivalent?

We want to know whether $¬ open parenthesis P ∨ Q close parenthesis$ is logically equivalent to $¬ P ∧ ¬ Q$ . Make a truth table which includes both statements:

$P$	$Q$	$¬ open parenthesis P ∨ Q close parenthesis$	$¬ P ∧ ¬ Q$
T	T	F	F
T	F	F	F
F	T	F	F
F	F	T	T

Since in every row the truth values for the two statements are equal, the two statements are logically equivalent.

Notice that this example gives us a way to “distribute” a negation over a disjunction (an “or”). We have a similar rule for distributing over conjunctions (“and”s):

This suggests there might be a sort of “algebra” you could apply to statements (okay, there is: it is called Boolean algebra) to transform one statement into another. We can start collecting useful examples of logical equivalence, and apply them in succession to a statement, instead of writing out a complicated truth table.

De Morgan's laws do not do not directly help us with implications, but as we saw above, every implication can be written as a disjunction:

With this and De Morgan's laws, you can take any statement and simplify it to the point where negations are only being applied to atomic propositions. Well, actually not, because you could get multiple negations stacked up. But this can be easily dealt with:

Let's see how we can apply the equivalences we have encountered so far.

Notice that the above example illustrates that the negation of an implication is NOT an implication: it is a conjunction! We saw this before, in Mathematical Statements, but it is so important and useful, it warants a second blue box here:

To verify that two statements are logically equivalent, you can use truth tables or a sequence of logically equivalent replacements. The truth table method, although cumbersome, has the advantage that it can verify that two statements are NOT logically equivalent.

Example 5

Are the statements $open parenthesis P ∨ Q close parenthesis → R$ and $open parenthesis P → R close parenthesis ∨ open parenthesis Q → R close parenthesis$ logically equivalent?

Note that while we could start rewriting these statements with logically equivalent replacements in the hopes of transforming one into another, we will never be sure that our failure is due to their lack of logical equivalence rather than our lack of imagination. So instead, let's make a truth table:

P

Q

R

open parenthesis P ∨ Q close parenthesis → R

open parenthesis P → R close parenthesis ∨ open parenthesis Q → R close parenthesis

Look at the fourth (or sixth) row. In this case, $open parenthesis P → R close parenthesis ∨ open parenthesis Q → R close parenthesis$ is true, but $open parenthesis P ∨ Q close parenthesis → R$ is false. Therefore the statements are not logically equivalent.

While we don't have logical equivalence, it is the case that whenever $open parenthesis P ∨ Q close parenthesis → R$ is true, so is $open parenthesis P → R close parenthesis ∨ open parenthesis Q → R close parenthesis$ . This tells us that we can deduce $open parenthesis P → R close parenthesis ∨ open parenthesis Q → R close parenthesis$ from $open parenthesis P ∨ Q close parenthesis → R$ , just not the reverse direction.

Deductions

Earlier we claimed that the following was a valid argument:

If Edith eats her vegetables, then she can have a cookie. Edith ate her vegetables. Therefore Edith gets a cookie.

How do we know this is valid? Let's look at the form of the statements. Let $P$ denote “Edith eats her vegetables” and $Q$ denote “Edith can have a cookie.” The logical form of the argument is then:

	$P \to Q$
	$P$
$∴$	$Q$

This is an example of a deduction rule, an argument form which is always valid. This one is a particularly famous rule called modus ponens. Are you convinced that it is a valid deduction rule? If not, consider the following truth table:

$P$	$Q$	$P \to Q$
T	T	T
T	F	F
F	T	T
F	F	T

This is just the truth table for $P \to Q$ , but what matters here is that all the lines in the deduction rule have their own column in the truth table. Remember that an argument is valid provided the conclusion must be true given that the premises are true. The premises in this case are $P \to Q$ and $P$ . Which rows of the truth table correspond to both of these being true? $P$ is true in the first two rows, and of those, only the first row has $P \to Q$ true as well. And lo-and-behold, in this one case, $Q$ is also true. So if $P \to Q$ and $P$ are both true, we see that $Q$ must be true as well.

Here are a few more examples.

Example 6

Show that

	$P \to Q$
	$\neg P \to Q$
$∴$	$Q$

This is a valid deduction rule.

We make a truth table which contains all the lines of the argument form:

$P$	$Q$	$P \to Q$	$\neg P$	$\neg P \to Q$
T	T	T	F	T
T	F	F	F	T
F	T	T	T	T
F	F	T	T	F

(we include a column for $\neg P$ just as a step to help getting the column for $\neg P \to Q$ ).

Now look at all the rows for which both $P \to Q$ and $\neg P \to Q$ are true. This happens only in rows 1 and 3. Hey! In those rows $Q$ is true as well, so the argument form is valid (it is a valid deduction rule).

Example 7

Decide whether

	$P \to R$
	$Q \to R$
	$R$
$∴$	$P ∨ Q$

This is a valid deduction rule.

Let's make a truth table containing all four statements.

$P$	$Q$	$R$	$P \to R$	$Q \to R$	$P ∨ Q$
T	T	T	T	T	T
T	T	F	F	F	T
T	F	T	T	T	T
T	F	F	F	T	T
F	T	T	T	T	T
F	T	F	T	F	T
F	F	T	T	T	F
F	F	F	T	T	F

Look at the second to last row. Here all three premises of the argument are true, but the conclusion is false. Thus this is not a valid deduction rule.

While we have the truth table in front of us, look at rows 1, 3, and 5. These are the only rows in which all of the statements $P \to R$ , $Q \to R$ , and $P ∨ Q$ are true. It also happens that $R$ is true in these rows as well. Thus we have discovered a new deduction rule we know is valid:

	$P \to R$
	$Q \to R$
	$P ∨ Q$
$∴$	$R$

Beyond Propositions

As we saw in Mathematical Statements, not every statement can be analyzed using logical connectives alone. For example, we might want to work with the statement:

All primes greater than 2 are odd.

To write this statement symbolically, we must use quantifiers. We can translate as follows:

$∀ x open parenthesis open parenthesis P open parenthesis x close parenthesis ∧ x greater than 2 close parenthesis → O open parenthesis x close parenthesis close parenthesis$

. In this case, we are using $P (x)$ to denote “ $x$ is prime” and $O (x)$ to denote “ $x$ is odd.” These are not propositions, since their truth value depends on the input $x$ . Better to think of $P$ and $O$ as denoting properties of their input. The technical term for these is predicates and when we study them in logic, we need to use predicate logic.

It is important to stress that predicate logic extends propositional logic (much in the way quantum mechanics extends classical mechanics). You will notice that our statement above still used the (propositional) logical connectives. Everything that we learned about logical equivalence and deductions still applies. However, predicate logic allows us to analyze statements at a higher resolution, digging down into the individual propositions $P$ , $Q$ , etc.

A full treatment of predicate logic is beyond the scope of this text. One reason is that there is no systematic procedure for deciding whether two statements in predicate logic are logically equivalent (i.e., there is no analogue to truth tables here). Rather, we end with a two examples of logical equivalence and deduction, to pique your interest.

Example 8

Suppose we claim that there is no smallest number. We can translate this into symbols as

$¬ ∃ x ∀ y open parenthesis x less than or equal to y close parenthesis$

(literally, “it is not true that there is a number $x$ such that for all numbers $y$ , $x$ is less than or equal to $y$ ”).

However, we know how negation interacts with quantifiers: we can pass a negation over a quantifier by switching the quantifier type (between universal and existential). So the statement above should be logically equivalent to

$∀ x ∃ y open parenthesis y less than x close parenthesis$

. Notice that $y < x$ is the negation of $x \leq y$ . This literally says, “for every number $x$ there is a number $y$ which is smaller than $x$ .” We see that this is another way to make our original claim.

Example 9

Can you switch the order of quantifiers? For example, consider the two statements:

$∀ x ∃ y P open parenthesis x, y close parenthesis and ∃ y ∀ x P open parenthesis x, y close parenthesis$

. Are these logically equivalent?

These statements are NOT logically equivalent. To see this, we should provide an interpretation of the predicate $P (x, y)$ which makes one of the statements true and the other false.

Let $P (x, y)$ be the predicate $x < y$ . It is true, in the natural numbers, that for all $x$ there is some $y$ greater than that $x$ (since there are infinitely many numbers). However, there is not a natural number $y$ which is greater than every number $x$ . Thus it is possible for $∀ x ∃ y P open parenthesis x, y close parenthesis$ to be true while $∃ y ∀ x P open parenthesis x, y close parenthesis$ is false.

We cannot do the reverse of this though. If there is some $y$ for which every $x$ satisfies $P (x, y)$ , then certainly for every $x$ there is some $y$ which satisfies $P (x, y)$ . The first is saying we can find one $y$ that works for every $x$ . The second allows different $y$ 's to work for different $x$ 's, but there is nothing preventing us from using the same $y$ that work for every $x$ . In other words, while we don't have logical equivalence between the two statements, we do have a valid deduction rule:

	$∃ y ∀ x P open parenthesis x, y close parenthesis$
$∴$	$∀ x ∃ y P open parenthesis x, y close parenthesis$

Put yet another way, this says that the single statement

$∃ y ∀ x P open parenthesis x, y close parenthesis → ∀ x ∃ y P open parenthesis x, y close parenthesis$

is always true. This is sort of like a tautology, although we reserve that term for necessary truths in propositional logic. A statement in predicate logic that is necessarily true gets the more prestigious designation of a law of logic (or sometimes logically valid, but that is less fun).

Consider the statement about a party, “If it's your birthday or there will be cake, then there will be cake.”

Translate the above statement into symbols. Clearly state which statement is $P$ and which is $Q$ .
Make a truth table for the statement.
Assuming the statement is true, what (if anything) can you conclude if there will be cake?
Assuming the statement is true, what (if anything) can you conclude if there will not be cake?
Suppose you found out that the statement was a lie. What can you conclude?

$P$ : it's your birthday; $Q$ : there will be cake. $open parenthesis P ∨ Q close parenthesis → Q$
Hint: you should get three T's and one F.
Only that there will be cake.
It's NOT your birthday!
It's your birthday, but the cake is a lie.

Geoff Poshingten is out at a fancy pizza joint, and decides to order a calzone. When the waiter asks what he would like in it, he replies, “I want either pepperoni or sausage. Also, if I have sausage, then I must also include quail. Oh, and if I have pepperoni or quail then I must also have ricotta cheese.”

Translate Geoff's order into logical symbols.
The waiter knows that Geoff is either a liar or a truth-teller (so either everything he says is false, or everything is true). Which is it?
What, if anything, can the waiter conclude about the ingredients in Geoff's desired calzone?

You should write down three statements using the symbols $P, Q, R, S$ . If Geoff is a truth-teller, then all three statements would be true. If he was a liar, then all three statements would be false. But in either case, we don't yet know whether the four atomic statements are true or false, since he hasn't said them by themselves.

A truth table might help, although is probably not entirely necessary.

Determine whether the following two statements are logically equivalent: $\neg (P \to Q)$ and $P ∧ ¬ Q$ . Explain how you know you are correct.

Make a truth table for each and compare. The statements are logically equivalent.

Simplify the following statements (so that negation only appears right before variables).

$\neg (P \to \neg Q)$ .
$open parenthesis ¬ P ∨ ¬ Q close parenthesis → ¬ open parenthesis ¬ Q ∧ R close parenthesis$ .
$¬ open parenthesis open parenthesis P → ¬ Q close parenthesis ∨ ¬ open parenthesis R ∧ ¬ R close parenthesis close parenthesis$ .
It is false that if Sam is not a man then Chris is a woman, and that Chris is not a woman.

$P ∧ Q$ .
$open parenthesis ¬ P ∨ ¬ R close parenthesis → open parenthesis Q ∨ ¬ R close parenthesis$ or, replacing the implication with a disjunction first: $open parenthesis P ∧ Q close parenthesis ∨ open parenthesis Q ∨ ¬ R close parenthesis$ .
$open parenthesis P ∧ Q close parenthesis ∧ open parenthesis R ∧ ¬ R close parenthesis$ . This is necessarily false, so it is also equivalent to $P ∧ ¬ P$ .
Either Sam is a woman and Chris is a man, or Chris is a woman.

Use De Morgan's Laws, and any other logical equivalence facts you know to simplify the following statements. Show all your steps. Your final statements should have negations only appear directly next to the sentence variables or predicates ( $P$ , $Q$ , $E (x)$ , etc.), and no double negations. It would be a good idea to use only conjunctions, disjunctions, and negations.

$¬ open parenthesis open parenthesis ¬ P ∧ Q close parenthesis ∨ ¬ open parenthesis R ∨ ¬ S close parenthesis close parenthesis$ .
$¬ open parenthesis open parenthesis ¬ P → ¬ Q close parenthesis ∧ open parenthesis ¬ Q → R close parenthesis close parenthesis$ (careful with the implications).
For both parts above, verify your answers are correct using truth tables. That is, use a truth table to check that the given statement and your proposed simplification are actually logically equivalent.

Consider the statement, “If a number is triangular or square, then it is not prime”

Make a truth table for the statement $open parenthesis T ∨ S close parenthesis → ¬ P$ .
If you believed the statement was false, what properties would a counterexample need to possess? Explain by referencing your truth table.
If the statement were true, what could you conclude about the number 5657, which is definitely prime? Again, explain using the truth table.

There will be three rows in which the statement is false.
Consider the three rows that evaluate to false and say what the truth values of $T$ , $S$ , and $P$ are there.
You are looking for a row in which $P$ is true, and the whole statement is true.

Tommy Flanagan was telling you what he ate yesterday afternoon. He tells you, “I had either popcorn or raisins. Also, if I had cucumber sandwiches, then I had soda. But I didn't drink soda or tea.” Of course you know that Tommy is the worlds worst liar, and everything he says is false. What did Tommy eat?

Justify your answer by writing all of Tommy's statements using sentence variables ( $P, Q, R, S, T$ ), taking their negations, and using these to deduce what Tommy actually ate.

Write down three statements, and then take the negation of each (since he is a liar). You should find that Tommy ate one item and drank one item. ( $Q$ is for cucumber sandwiches.)

Can you chain implications together? That is, if $P \to Q$ and $Q \to R$ , does that means the $P \to R$ ? Can you chain more implications together? Let's find out:

Prove that the following is a valid deduction rule:
$P \to Q$
$Q \to R$
$∴$ $P \to R$

Prove that the following is a valid deduction rule for any

n greater than or equal to 2

	$P sub 1 → P sub 2$
	$P sub 2 → P sub 3$
	$⋮$
	$P sub n minus 1 → P sub n$
$∴$	$P sub 1 → P sub n$ .

I suggest you don't go through the trouble of writing out a

2 to the power n

row truth table. Instead, you should use part (a) and mathematical induction.

For the second part, you can inductively assume that from the first $n minus 2$ implications you can deduce $P sub 1 → P sub n minus 1$ . Then you are back in the case in part (a) again.

We can also simplify statements in predicate logic using our rules for passing negations over quantifiers, and then applying propositional logical equivalence to the “inside” propositional part. Simplify the statements below (so negation appears only directly next to predicates).

$¬ ∃ x ∀ y open parenthesis ¬ O open parenthesis x close parenthesis ∨ E open parenthesis y close parenthesis close parenthesis$ .
$¬ ∀ x ¬ ∀ y ¬ open parenthesis x less than y ∧ ∃ z open parenthesis x less than z ∨ y less than z close parenthesis close parenthesis$ .
There is a number $n$ for which no other number is either less $n$ than or equal to $n$ .
It is false that for every number $n$ there are two other numbers which $n$ is between.

$∀ x ∃ y open parenthesis O open parenthesis x close parenthesis ∧ ¬ E open parenthesis y close parenthesis close parenthesis$ .
$∃ x ∀ y open parenthesis x greater than or equal to y ∨ ∀ z open parenthesis x greater than or equal to z ∧ y greater than or equal to z close parenthesis close parenthesis$ .
There is a number $n$ for which every other number is strictly greater than $n$ .
There is a number $n$ which is not between any other two numbers.

Simplify the statements below to the point that negation symbols occur only directly next to predicates.

$¬ ∀ x ∀ y open parenthesis x less than y ∨ y less than x close parenthesis$ .
$¬ open parenthesis ∃ x P open parenthesis x close parenthesis → ∀ y P open parenthesis y close parenthesis close parenthesis$ .

Simplifying negations will be especially useful in the next section when we try to prove a statement by considering what would happen if it were false. For each statement below, write the negation of the statement as simply as possible. Don't just say, “it is false that …” .

Every number is either even or odd.
There is a sequence that is both arithmetic and geometric.
For all numbers $n$ , if $n$ is prime, then $n plus 3$ is not prime.

It might help to translate the statements into symbols and then use the formulaic rules to simplify negations (i.e., rules for quantifiers and De Morgan's laws). After simplifying, you should get $∀ x open parenthesis ¬ E open parenthesis x close parenthesis ∧ ¬ O open parenthesis x close parenthesis close parenthesis$ , for the first one, for example. Then translate this back into English.

Suppose $P$ and $Q$ are (possibly molecular) propositional statements. Prove that $P$ and $Q$ are logically equivalent if any only if $P \leftrightarrow Q$ is a tautology.

What do these concepts mean in terms of truth tables?

Suppose $P sub 1, P sub 2, and so on, P sub n$ and $Q$ are (possibly molecular) propositional statements. Suppose further that

	$P sub 1$
	$P sub 2$
	$⋮$
	$P_{n}$
$∴$	$Q$

This is a valid deduction rule. Prove that the statement

$open parenthesis P sub 1 ∧ P sub 2 ∧ ⋯ ∧ P sub n close parenthesis → Q$

is a tautology.

Discrete Mathematics: An Open Introduction, 3rd edition, by Oscar Levin (discrete.openmathbooks.org), licensed under CC BY-SA 4.0; this adaptation is distributed under the same license. License: CC-BY-SA-4.0.