Propositional Logic and Truth Tables

In this lesson you’ll learn what counts as a proposition, the three basic logical connectives (negation, conjunction, disjunction), the symbols mathematicians use for them, and how to build a truth table that settles any question about a compound statement.

This is the lesson where the symbols start. Here’s the whole set up front, so you can glance back at it any time:

A proposition is a statement that is either true or false, but not both.

These are propositions:

• “7 is a prime number.” (true)
• “Paris is the capital of Italy.” (false)
• "$3 + 4 = 12$" (false)

These are not propositions:

• “What time is it?” (a question)
• “Close the door.” (a command)
• "$x + 1 = 5$" (depends on $x$, so it has no fixed truth value)
• “This sentence is false.” (paradox, can’t be either)

We name propositions with letters: $p$, $q$, $r$. Each one has a truth value, either T (true) or F (false).

There are three basic ways to combine them, and each one has a physical form as a circuit component:

The negation of $p$ is written $\neg p$ and read “not $p$.” It flips the truth value.

If $p$ is “it is raining,” then $\neg p$ is “it is not raining.”

The conjunction of $p$ and $q$ is written $p \wedge q$ and read ”$p$ and $q$.” It is true only when both parts are true.

A useful memory hook: AND is demanding. One failure ruins it.

The disjunction of $p$ and $q$ is written $p \vee q$ and read ”$p$ or $q$.” It is true when at least one part is true.

Important: this is inclusive or. If both are true, the whole thing is still true. Everyday English often means “one or the other but not both” (“soup or salad”), but mathematical OR always includes the both case. When you specifically want to exclude the both case you use exclusive or, written $p \oplus q$, which is true when exactly one part is true.

A truth table lists every possible combination of truth values for the basic propositions, then works outward to the compound statement.

With $n$ distinct propositions there are $2^n$ rows. One proposition gives 2 rows, two give 4, three give 8, four give 16.

The standard procedure:

1. Write a column for each basic proposition and fill in all $2^n$ combinations.
2. Add a column for each intermediate piece, working from the inside of the expression outward.
3. Combine the intermediate columns to get the final answer.

You will see these symbols written several ways depending on the field:

They mean exactly the same things. If you’ve written an if statement, you already know propositional logic.

Just like arithmetic has an order of operations, so does logic. From highest to lowest:

So $\neg p \wedge q$ means $(\neg p) \wedge q$, not $\neg (p \wedge q)$. Use parentheses whenever there’s any doubt, and there’s usually doubt.

Example 1: Build a truth table for $\neg p \vee q$.

Two propositions, so 4 rows. Work inside out: first $\neg p$, then OR it with $q$.

Row 2 is the only false row. Notice that this table is going to look very familiar when we get to conditional statements.

Example 2: Build a truth table for $(p \wedge q) \vee \neg r$.

Three propositions, so 8 rows.

The statement is false in exactly 3 of 8 cases: whenever $r$ is true and $p \wedge q$ is not.

Example 3: Translate into symbols.

Let $p$ = “the server is online,” $q$ = “the database is reachable,” $r$ = “maintenance mode is on.”

Translate: “The server is online and the database is reachable, but maintenance mode is not on.”

Solution. The word “but” is just AND with attitude. It carries no different logical meaning.

Example 4: Tautology and contradiction.

A tautology is a statement that is true in every row. A contradiction is false in every row.

Check $p \vee \neg p$:

Always true, so it’s a tautology. This one is called the law of the excluded middle.

Now check $p \wedge \neg p$:

Always false, so it’s a contradiction. Good, because “it is raining and it is not raining” should never be true.

Every conditional in every program you’ve ever run is propositional logic. When you write:

if (isLoggedIn && !isBanned) { showDashboard(); }

you’ve written $p \wedge \neg q$. And when a bug turns out to be “this condition is wrong in one specific case,” a truth table finds it in about ninety seconds.

Digital circuits are built out of physical AND, OR, and NOT gates, and chip designers use truth tables to specify exactly what a circuit should do before building it. Database queries with WHERE active = true AND deleted = false are the same logic again.

Outside of computing, insurance policies, tax rules, and eligibility requirements (“you qualify if you are over 65 or have a documented disability, and you are not currently enrolled elsewhere”) are compound propositions. Writing them as symbols is often the fastest way to figure out whether you actually qualify.