Propositional logic studies statements that are either true or false and the rules for combining them. Truth tables make those rules concrete by listing every possible set of truth values.

Propositions and truth values

A proposition is a declarative statement that is either true or false, but not both. For example:

• $p$: “$42$ is divisible by $3$” is true.
• $q$: “$2+2=5$” is false.
• $r$: “Extraterrestrial life exists” has a truth value even though we do not currently know what it is.

A proposition's truth value belongs to the Boolean set

$$\mathbb B=\{0,1\}=\{\text{false},\text{true}\}.$$

Here, $0$ means false and $1$ means true.

Basic logical connectives

A logical connective combines or changes propositions.

The word “or” in $p\lor q$ is inclusive, so it includes the case where both propositions are true. Negation has higher priority than the binary connectives on this page, but parentheses are the clearest way to show the intended order.

Basic connective table

Logical equivalence

Two propositions are logically equivalent when they have the same truth value in every possible case. We write

$$P\equiv Q.$$

A truth table proves an equivalence when the final columns for the two expressions match row by row.

De Morgan's law

Consider

$$\neg(\neg p\land\neg q).$$

Build it from the inside out: first calculate $\neg p$ and $\neg q$, then their conjunction, and finally negate that conjunction.

The final two columns match, so

$$\boxed{\neg(\neg p\land\neg q)\equiv p\lor q}.$$

This is one form of De Morgan's law. The two forms are

$$\neg(p\land q)\equiv\neg p\lor\neg q, \qquad \neg(p\lor q)\equiv\neg p\land\neg q.$$

Logical identities

Logical identities closely parallel set identities. Conjunction acts like intersection, disjunction like union, and negation like taking a complement.

For example, the set identity $A\cap U=A$ corresponds to

$$p\land1\equiv p.$$

Some useful identities are

$$\begin{aligned} \neg\neg p&\equiv p &&\text{double negation},\\ p\lor(p\land q)&\equiv p &&\text{absorption},\\ p\land(p\lor q)&\equiv p &&\text{absorption}. \end{aligned}$$

First distributive law

Conjunction distributes over disjunction:

$$p\land(q\lor r)\equiv(p\land q)\lor(p\land r).$$

The intermediate columns show how each side is built. The two final expression columns match in every row.

Second distributive law

Disjunction also distributes over conjunction:

$$p\lor(q\land r)\equiv(p\lor q)\land(p\lor r).$$

Example: simplifying a proposition

Simplify

$$p\lor\neg(\neg p\lor\neg\neg q).$$

Work from the inner negations outward:

$$\begin{aligned} p\lor\neg(\neg p\lor\neg\neg q) &\equiv p\lor\neg(\neg p\lor q) &&\text{double negation}\\ &\equiv p\lor(\neg\neg p\land\neg q) &&\text{De Morgan's law}\\ &\equiv p\lor(p\land\neg q) &&\text{double negation}\\ &\equiv p &&\text{absorption.} \end{aligned}$$

Exclusive OR

Exclusive OR can be written using conjunction, disjunction, and negation:

$$p\oplus q\equiv(p\lor q)\land\neg(p\land q).$$

The first factor requires at least one true proposition. The second rules out the case where both are true.

Conditional and biconditional statements

Conditional

The conditional

$$p\Rightarrow q$$

can be read in three equivalent ways:

• “If $p$, then $q$.”
• “$q$ if $p$.”
• “$p$ only if $q$.”

Here, $p$ is the antecedent and $q$ is the consequent. A conditional makes one promise: whenever $p$ is true, $q$ must also be true. It is therefore false only when $p=1$ and $q=0$. When $p$ is false, the conditional is true regardless of $q$; this is called vacuous truth.

For example, “If I pay 1,000 dollars, then you bring me a coffee” is false only if I pay the money and no coffee arrives.

A conditional has the equivalent form

$$p\Rightarrow q\equiv\neg p\lor q.$$

Biconditional

The biconditional $p\Leftrightarrow q$ means that each proposition implies the other:

$$p\Leftrightarrow q \equiv(p\Rightarrow q)\land(q\Rightarrow p) \equiv\neg(p\oplus q).$$

It is true exactly when $p$ and $q$ have the same truth value.

Negating “only if”

Campus Wi-Fi example

Let

• $W$: you can access campus Wi-Fi;
• $S$: you are a student;
• $E$: you are an employee.

The statement

You can access campus Wi-Fi only if you are a student or an employee.

becomes

$$W\Rightarrow(S\lor E).$$

Its negation is

$$\begin{aligned} \neg[W\Rightarrow(S\lor E)] &\equiv\neg[\neg W\lor(S\lor E)]\\ &\equiv W\land\neg(S\lor E)\\ &\equiv W\land\neg S\land\neg E. \end{aligned}$$

The only row where the negation is true is $W=1$, $S=0$, and $E=0$. In words: you can access the Wi-Fi even though you are neither a student nor an employee.