1.4: Propositional Logic - Sets and Functions

# 1.4: Propositional Logic

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.

## Set Operations as Logical Operators

### Definition: Proposition

A proposition is a statement that is has a definitive value - either true or false. 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. (In my opinion, LeBron is the greatest of all time, though!)

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

### Conjunction ($\wedge$)

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.

### Disjunction ($\vee$)

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.

### Negation ($\neg$)

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. 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 under 100 or both prime and not even.

## Implications and Truth Tables

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).

For example, if all we know about today’s date is that it’s Christmas, we also know that the current month is December. However, if we don’t know that it’s 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.

In logic, a question we are commonly faced with is proving that two expressions are logically equivalent. We do this by constructing what is known as a truth table, where we look at all possible values of each proposition and show that the expression holds the same value in each case. (This is similar to proving trigonometric identities, but far less mechanical.)

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 $\equiv$ sign means “equivalence”; we will see this more when we study modular arithmetic). The following truth table proves this equivalence:

$P$ $Q$ $P \implies Q$ $\neg P \vee Q$
True True True True
True False False False
False True True True
False False True True

Notice there are four rows - one for TT, one for TF, one for FT and one for FF. If we had expressions that depended on three propositions, we would have eight rows, and so on.

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)

### 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

$A \oplus B \equiv (A \vee B) \wedge \neg(A \wedge B)$

Let’s prove this with a truth table.

$A$ $B$ $A \oplus B$ $(A \vee B) \wedge \neg(A \wedge B)$
True True False False
True False True True
False True True True
False False False False

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.

A good exercise at this point is to practice proving a few equivalence relations on your own, so we present some sample problems below. You don’t need to do them all.

• $\neg (P \wedge Q) \equiv \neg P \vee \neg Q$ (De Morgan’s Law)
• $\neg P \wedge \neg Q \equiv \neg (P \vee Q)$ (De Morgan’s Law)
• $P \implies Q \implies R \equiv (P \wedge \neg Q) \vee R$
• $P \wedge \neg P \equiv \text{TRUE}$ (Tautology)

The first two exercises in the above prove the result known as De Morgan’s Laws. These allow us to convert from AND operations to OR operations, with the distribution of a negation. They have analogues in set theory, as we saw in Chapter 1.1.

## Extensions of the Implication

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

### Contrapositive: $\neg Q \implies \neg P$

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:

\begin{aligned}\neg Q \implies \neg P &\equiv \neg (\neg Q) \vee (\neg P) \\ &\equiv Q \vee \neg P \\ &\equiv \neg P \vee Q \\ &\equiv P \implies Q \end{aligned}

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 will not 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”.

### Converse: $Q \implies P$

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$). Instead, the converse helps us in proving the equivalence of two statements.

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

Statement Contrapositive Converse
If it rains tomorrow, I will bring an umbrella. I will not bring an umbrella if it does not rain tomorrow. I will bring an umbrella if it rains tomorrow.
If the clock is between 12PM and 2PM and I am hungry, then it is lunch time. It is not lunchtime if the clock is not between 12PM and 2PM or I am not hungry. It is lunchtime if the clock is between 12PM and 2PM and I am hungry.
If your final grade in this course is at least 70%, you will pass. You will not pass if your final grade in this course is not at least 70%. You will pass if your final grade in this course is at least 70%.
If two sets $A, B$ are disjoint, then the cardinality of their intersection is 0. The cardinality of the intersection of two sets $A, B$ is not 0 if they are not disjoint. The cardinality of the intersection of two sets $A, B$ is 0 if they are disjoint.

### If and only iff: $\iff$

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 widely used term to say that 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. 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:

$A$ $B$ $A \iff B$ $(A \implies B) \wedge (B \implies A)$
True True True True
True False False False
False True False False
False False True True

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.

## Existential Quantifiers

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,

$(\forall x) (\exists y) P(x, y) \not \equiv (\exists y) (\forall x) P(x, y)$

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!

### De Morgan’s Laws for Existential Quantifiers

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

$\neg(\forall x, P(x)) \equiv \exists x, \neg P(x) \\ \neg(\exists x, P(x)) \equiv \forall x, \neg P(x)$

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 states “if it is not true that $x$ is prime for all $x$, then there must exist some $x$ that is not prime.”
2. The second version states “if it is not true that there exists an $x$ that is prime, then for all $x$, $x$ is not prime.”

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:

$\neg ((\forall x)(\exists y)Q(x, y)) \equiv (\exists x)(\forall y) \neg Q(x, y) \: \: \: \: (1) \\ \neg ((\exists x)(\forall y)Q(x, y)) \equiv (\forall x)(\exists y) \neg Q(x,y) \: \: \: \: (2)$

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, but we won’t be so involved in this course.

## Examples

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.

English Propositional Logic
There exists an integer solution to the equation $x^2 + 2x + 1 = 0$ $(\exists x \in \mathbb{Z})(x^2 + 2x + 1 = 0)$
There are no three positive integers $a$, $b$, $c$ that satisfy the equation $a^n + b^n = c^n$ for any integer value of $n$ greater than 2. $\neg(\exists a,b,c,n \in \mathbb{Z}^+)(n > 2 \wedge a^n + b^n = c^n)$
$\sqrt{2}$ is a rational number. $(\exists a, b \in \mathbb{Z})(\sqrt{2} = \dfrac{a}{b})$
For $-1 < r < 1, r \in \mathbb{R}$, the sum of the series $1 + r + r^2 + r^3 + \cdots$ is equal to $\dfrac{1}{1-r}$. $(\forall r \in \mathbb{R} : -1 < r < 1)(\sum_{n=0}^{\infty} r^n = \dfrac{1}{1-r})$