Propositional Logic

by Suraj Rampure
Last modified: March 21, 2019

Often introduced with set theory is the concept of propositional logic. Knowledge of propositional logic is crucial to formalizing proof techniques, which we will do in the following chapter. This article will be relatively interactive - it’s in your best interest to do the examples yourself as you read.

A proposition is a statement that is has a definitive value - either true or false. We usually denote a proposition that depends on some variable $x$ is usually denoted by $P(x)$.

For example, “13 is prime” and “it is currently 93 degrees outside” are propositions. Each of these statements is either definitively true, or definitively false. However, statements like “LeBron James is the best basketball player of all time” or “statistics is a hard subject” are NOT propositions - they are opinions, and their “truth value” varies from person to person.

The statements “$x$ is prime” and $a > b$ are also propositions, but they depend on variables. We might use $P(x)$ to represent the proposition “$x$ is prime”, and $G(a, b)$ to represent “$a > b$”. For example, $P(15)$ is false, and $G(10, 3)$ is true.

There are three commonly used logical operators, and each has a counterpart that we’ve already studied in set theory.

The intersection ($\cap$) operation over two sets corresponds to the and ($\wedge$) operation over two propositions.

The set $A \cap B$ is the set of elements that are in $A$ AND in $B$; similarly, the proposition $P \wedge Q$ is true only when both $P$ is true AND $Q$ is true. We can say $A \cap B = \{ x : x \in A \wedge x \in B \}$ . The “and” operation is sometimes referred to as a conjunction.

The following truth table defines the AND operation. It gives the output of $P \wedge Q$ on all possible combinations of inputs. Since $P$ is either true or false, and $Q$ is either true or false, we have four rows.

The union ($\cup$) operation over two sets corresponds to the or ($\vee$) operation over two propositions.

The set $A \cup B$ is the set of elements that are in $A$ OR in $B$; similarly, the proposition $P \vee Q$ is true when $P$ is true OR when $Q$ is true. We can say $A \cup B = \{ x : x \in A \vee x \in B \}$. Remember, in mathematical logic, “or” is not exclusive – if both $P$ and $Q$ are true, $P \vee Q$ is still true. The “or” operation is sometimes referred to as a disjunction.

Again, we give the truth table:

The analogue of the complement of a set is the negation ($\neg$) of a proposition. We say $\neg P$ is true only when $P$ is not true, and false only when $P$ is not false. We can say $A^C = \{ x : \neg (x \in A) \}$.

We can use the above logical operators to create more complex logical expressions, which themselves also take on the value true or false. For example, if $P$ is true only when $x$ is prime, $E$ is true only when $x$ is positive and even, and $U$ is true only when $x$ is under 100, the expression $P \vee (\neg E \wedge U)$ is a logical expression that depends on $x$ and is true only when $x$ is prime or both not even and under 100.

Example: Exclusive OR

Another important definition at this point is the XOR operation, represented by the $\oplus$ symbol. The standard “A or B” operation evaluates to true in each of the following cases:

• Only $A$ is true
• Only $B$ is true
• Both $A$ and $B$ are true

For example, if someone asks “are you in EE 16A or CS 61A?”, you answer yes, whether you’re in 16A, 61A, or both. The XOR operation, instead, is exclusive – it is only true when either $A$ is true, or $B$ is true, but not both. For example, when getting a sub combo at Subway, you’re asked if you want chips or a cookie – you get either chips, or a cookie, but not both.

We mentioned above that all logical statements can be decomposed into some combination of conjunctions, disjunctions and negations. $A \oplus B$ should be true when either $A$ or $B$ is true, and false when both are true (or both are false). The first clause can be represented by $A \vee B$, and the latter by $\neg (A \wedge B)$. Chaining these together with a $\wedge$, we have

Let’s prove this with a truth table.

If we think of $A$ and $B$ being bits instead – i.e. 1 when True, 0 when False – then we have that $A \oplus B = 1$ when $A + B$ is odd, and $A \oplus B = 0$ when $A + B$ is even.

De Morgan’s Laws allow us to simplify and re-write negations. Recall, we saw in the first note that the following rules apply for sets $A, B$:

It turns out that the same rules apply for propositions $P, Q$!

Notice, we flip our conjunctions into negations, and vice versa.

We can actually use truth tables to prove De Morgan’s Laws. We use truth tables to prove that two logical expressions are equivalent, i.e. that upon the same inputs, they produce the same outputs. (The $\equiv$ symbol translates to “equivalent.”)

Let’s prove the equivalence $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$:

Since the columns for $\neg(P \wedge Q)$ and $\neg P \vee \neg Q$ are identical, we say that the two expressions are equivalent. We’ll leave the truth table for $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$ as an exercise.

Example

Let’s find the negation of the statement, “$t$ is even and not prime or irrational and prime”.

The first step is to convert the statement into propositional logic. We can use $E$ to represent the proposition “$t$ is even”, $P$ for $t$ is prime, and $I$ for $t$ is irrational. Our statement then reads, $(E \wedge \neg P) \vee (I \wedge P)$.

Using De Morgan’s Laws, we can propagate a negation through the expression:

In English, the negation reads, “$t$ is not even or prime, and not irrational or not prime.” At this point in the course/book, we haven’t started talking about how to prove such statements; for now, we’re only concerned about the construction of them. We’ll start proving such statements in Chapter 2.

Crucial in the study of propositional logic is the implication operation, which itself is a composition of the basic logical operators we saw above (though this might not be immediately obvious).

The implication operation $P \implies Q$ says that if $P$ is true, then $Q$ must be true; if $P$ is false, it says nothing about $Q$ ($Q$ could either be true or false). In English, implications often read “if $P$, then $Q$”, or “$Q$ if $P$”.

An example of an implication is the proposition “if today is Christmas, it is December.”, However, if today is not Christmas, then it may or may not be December.

We use implications to prove statements to be true; if we can make a series of implications starting from a proposition that we know is true and ending with the proposition we want to prove, we have proven the final statement. We will explore this further in the next chapter.

As we mentioned above, the implication statement is a composition of the elementary logical operators - it turns out that $P \implies Q \equiv \neg P \vee Q$. The following truth table proves this equivalence:

It’s important to remember that implications are no different than conjunctions and disjunctions in the sense that they are propositonal statements with truth values. Another way to reason about the truth values of implications: Suppose I make the promise to you that if it rains tomorrow, I will give you 100 dollars. The “truth value” of this implication is whether or not I held my promise:

• If it rains tomorrow, and I give you 100 dollars, I held my promise! (T)
• If it rains tomorrow, and I don’t give you 100 dollars, I did not hold my promise. (F)
• If it does not rain tomorrow, and I give you 100 dollars, I held my promise! (T)
• If it does not rain tomorrow, and I don’t give you 100 dollars, I still held my promise! (T)

The following are common logical expressions that are related to the implication of $P \implies Q$.

The contrapositive, $\neg Q \implies \neg P$, of an implication is actually logically equivalent to the implication itself! You should prove this to yourself using a truth table. However, without using a truth table we can see that:

Why does the contrapositive exist, then, if it’s equivalent to the standard implication? That’s a question that’ll be answered in the following chapter in great detail.

For now, let’s look at an example. Consider the statement “if it is sunny outside, I will wear sunglasses”. Its contrapositive is “if I don’t wear sunglasses, it is not sunny outside” - both statements mean the same thing, as we expect. Another, more mathematical example: the contrapositive of the statement “if $x$ is even, $x^2$ is even” is the statement “if $x^2$ is not even, $x$ is not even”.

The converse, $Q \implies P$ of an implication, however, is not equivalent to the implication. If today is Christmas ($P$), then it implies that the current month is December ($Q$), however it being December ($Q$) doesn’t mean that today is Christmas ($P$). In general, if an implication is true, it does not mean that its converse is true! There are some cases where a statement and its converse are both true, though. We have a name for that, which you’ll read about shortly.

Another way we can represent the equivalence of two statements $A \equiv B$ is with the if and only if ($\iff$) symbol: $A \iff B$. If and only if (sometimes shortened to “iff”) is a term that says one statement is true only when the other statement is true, and is false only when the other statement is false - in other words, that two statements are equivalent. $A \iff B$ means that both $A \implies B$ and $B \implies A$ hold, i.e. both a statement and its converse hold.

For example, “it is Christmas if and only if it is December 25th”, which we can decompose into the two statements “it is Christmas if it is December 25th” and “it is December 25th if it is Christmas” is just a fancy way of saying “Christmas is on December 25th”.

Consider the following truth table:

What this says, is that if two expressions imply one another, then they are equal. Today being Christmas implies that today is December 25th, and today being December 25th implies that today is Christmas - since these two propositions imply one another, we can say they’re equivalent.

An understanding of implication and “if and only if” statements will go a long way in understanding how proof techniques work.

Let’s take a look at a few implications, alongside their contrapositives and converses.

Notice that in statements 1, 2, and 3, the converse means something entirely different than the original statement. However, in the fourth statement, both the original statement (if two sets $A, B$ are disjoint, then the cardinality of their intersection is 0) and its converse (if the cardinality of the intersection of two sets $A, B$ is 0, they are disjoint) are true.

In this case, we could say “the cardinality of the intersection of two sets $A, B$ is 0 if and only if they are disjoint.”

Quantifiers are the “glue” that allow us to write mathematical statements precisely. There are two:

• the universal quantifier ($\forall$, read as “for all”), and
• the existential quantifier ($\exists$, read as “there exists”).

We actually used these quantifiers already in Chapter 1.2, when defining what a surjective function is. We said a function $f: A \rightarrow B$ is surjective when $\forall b \in B, \exists a \in A : b = f(a)$, which translates to “for all $b$ in the codomain, there exists some $a$ in the domain such that $f$ maps $a$ to $b$.”

Let’s illustrate their usage with examples. Suppose we want a statement to denote that all natural numbers are either even or odd. We can have $E(x)$ represent “$x$ is even” and $U(x)$ represent “$x$ is odd”. Then, the statement $\forall x \in \mathbb{N}, E(x) \vee U(x)$ reads “for all natural numbers $x$, $x$ is even or odd”. This statement happens to always be true, but something like $\forall x \in \mathbb{N}, E(x) \wedge U(x)$ is not true, as it is not the case that $x$ is both even and odd for all positive integers $x$. In fact, there isn’t a single positive integer for which is this is true.

In general, you cannot reverse the order of different existential quantifiers. That is,

Let’s reason about this with an example. Consider $P(x, y): y = x^2$ (note here we’re implicitly letting our universe $\mathbb{U} = \mathbb{R}$). The first statement says that for all $x$, there is some $y$ such that $y = x^2$. In other words, it says that every real number $x$ has a square. This statement happens to be true. The second statement says that there is some magical $y$ that is equal to the square of every single $x$. That is, this $y$ (let’s call it $y_0$) is such that $y_0 = 1^2, y_0 = \pi^2, y_0 = 100^2, …$. This statement is definitely very false. These are both saying very different things!

To round out our discussion on propositional logic, we need to once again look at De Morgan’s Laws, but for existential quantifiers.

As an example, suppose $P(x)$ is the statement “$x$ is prime”, and suppose we restrict our universe to be the positive integers.

1. The first version tells us the statements “it is not true that $x$ is prime for all $x$” and “there exists some $x$ that is not prime” are equivalent
2. The second version tells us the statements “it is not true that there exists an $x$ that is prime” and “for all $x$, $x$ is not prime” are equivalent

Since we know that it is false that all positive integers are prime, it must be true that there is at least one positive integer that isn’t prime, and indeed that is true (this is because if a statement is false, its negation must be true, and vice versa).

We can extend this principle to multivariate propositions:

Notice how the negation symbol propagates down the statement, flipping $\forall$ to $\exists$ and vice versa.

Let’s look at an example. Suppose $Q(x, y): y = x^2$. For example, $Q(3, 4)$ is the proposition that $4 = 3^2$, which happens to be false.

• Equation 1: The left hand side, $ \neg ((\forall x)(\exists y) \neg Q(x, y))$, states that “it is not the case that every $x$ has some $y$ such that $y = x^2$”, i.e. “it is not the case that every real number $x$ has as square.” The right hand side, $(\exists x)(\forall y) \neg Q(x,y)$, is “there exists some $x$, such that for all $y$, $y \neq x^2$”, i.e. “there exists some real number $x$ that does not have a square.” These two statements are saying the same thing: if not all real numbers have squares, there must exist some real number without a square.
• Equation 2: The left hand side, $\neg ((\exists x)(\forall y)Q(x, y))$, states that “it is not the case that there exists some $x$ such that for all $y$, $y = x^2$”, i.e. “there is no $x$ that satisfies $y = x^2$ for all $y$.” The right hand side, $(\forall x)(\exists y) \neg Q(x,y)$, says that “every $x$ has some $y$ such that $y \neq x^2$.” Again, these two statements are saying the same thing: if there is no $x$ that satisfies $y = x^2$ for every single $y$, then every $x$ has some value of $y$ such that $y \neq x^2$.

These statements are slightly difficult to parse. Make sure you read them carefully!

We can even apply De Morgan’s Laws to conjunctions and disjunctions AND existential quantifiers at the same time. For example, the statement

reads “all natural numbers $q$ have an inverse or are equal to 0.” Its negation,

reads “there exists some non-zero rational number $q$ that does not have an inverse.”

We can even propagate a negation through a long chain of propositions and quantifiers:

Let’s take a look at examples of converting sentences in English to precise, mathematical statements using the tools we’ve studied in this chapter. It should be noted, there isn’t necessarily only one right way to re-write a statement in English into logic.