5.1 Propositional logic and truth tables

Propositional logic gives us a formal system for representing statements and evaluating whether they're true or false. In semantics, this matters because it provides the backbone of truth-conditional meaning: the idea that knowing the meaning of a sentence means knowing the conditions under which it would be true. This unit covers the basic building blocks of propositional logic, how to construct truth tables, and how to test whether arguments are valid.

Propositional Logic Fundamentals

Components of propositional logic

A proposition is any statement that can be either true or false. "It's raining today" is a proposition. "Close the door" is not, because commands don't have truth values.

We use lowercase letters like $p$, $q$, and $r$ to stand in for propositions. These are called propositional variables. Each one has a truth value: either true (T) or false (F).

Logical connectives let you combine simple propositions into compound ones:

• Negation ($\neg p$): "not p." Flips the truth value. If $p$ is true, $\neg p$ is false.
• Conjunction ($p \land q$): "p and q." True only when both $p$ and $q$ are true.
• Disjunction ($p \lor q$): "p or q." True when at least one of them is true. This is inclusive or, so it's also true when both are true.
• Implication ($p \rightarrow q$): "if p, then q." False only when $p$ is true and $q$ is false. This one trips people up because $p \rightarrow q$ is true whenever $p$ is false, regardless of $q$.
• Biconditional ($p \leftrightarrow q$): "p if and only if q." True when $p$ and $q$ have the same truth value.

Construction of truth tables

A truth table lists every possible combination of truth values for the component propositions, then shows the resulting truth value of the compound expression. Here's how to build one:

1. Identify all the propositional variables. With $n$ variables, you'll have $2^n$ rows. Two variables give you 4 rows; three give you 8.
2. List every combination of T and F for those variables.
3. Apply the connective rules column by column, working from the innermost parts outward, until you reach the final compound proposition.

Here's the truth table for conjunction ($p \land q$):

And here's implication ($p \rightarrow q$), since it's the least intuitive:

Notice the last two rows: when $p$ is false, the implication is true no matter what. This is called vacuous truth, and it's a common source of confusion. Think of it this way: the implication only makes a promise about what happens when $p$ is true. If $p$ is false, the promise hasn't been broken.

Logical Equivalence and Argument Validity

Rules of logical equivalence

Two formulas are logically equivalent (written $\equiv$) when they produce the same truth value in every possible row of a truth table. You can always verify equivalence by building truth tables for both sides and checking that the columns match.

Several equivalence rules come up repeatedly:

• Double negation: $\neg(\neg p) \equiv p$. Negating a negation returns you to the original.
• De Morgan's laws:
  • $\neg(p \land q) \equiv \neg p \lor \neg q$. Negating an "and" turns it into an "or" of the negations.
  • $\neg(p \lor q) \equiv \neg p \land \neg q$. Negating an "or" turns it into an "and" of the negations.
  • A natural language example: "It's not the case that it's sunny and warm" means the same as "It's not sunny, or it's not warm (or both)."
• Commutativity: $p \land q \equiv q \land p$ and $p \lor q \equiv q \lor p$. Order doesn't matter for "and" or "or."
• Associativity: $(p \land q) \land r \equiv p \land (q \land r)$ and $(p \lor q) \lor r \equiv p \lor (q \lor r)$. Grouping doesn't matter for repeated "and" or repeated "or."
• Distributivity:
  • $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$. Conjunction distributes over disjunction.
  • $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$. Disjunction distributes over conjunction.

De Morgan's laws are especially useful in semantics when you're analyzing the scope of negation in natural language sentences.

Validity of propositional arguments

An argument is valid when there's no possible situation where all the premises are true but the conclusion is false. Validity is about the structure of the argument, not whether the premises are actually true in the real world.

Testing validity with truth tables:

1. Assign propositional variables to each simple statement in the argument.
2. Build a truth table that includes columns for each premise and for the conclusion.
3. Look at only the rows where all premises come out true.
4. If the conclusion is also true in every one of those rows, the argument is valid. If there's even one row where the premises are all true and the conclusion is false, the argument is invalid.

Two classic valid argument forms to know:

• Modus ponens: From $p \rightarrow q$ and $p$, conclude $q$. ("If it rains, the ground is wet. It's raining. Therefore the ground is wet.")
• Modus tollens: From $p \rightarrow q$ and $\neg q$, conclude $\neg p$. ("If it rains, the ground is wet. The ground is not wet. Therefore it's not raining.")

Two classic invalid forms (formal fallacies) to watch for:

• Affirming the consequent: From $p \rightarrow q$ and $q$, concluding $p$. (The ground being wet doesn't prove it rained; maybe someone used a hose.)
• Denying the antecedent: From $p \rightarrow q$ and $\neg p$, concluding $\neg q$. (Not raining doesn't mean the ground can't be wet.)

Testing validity with equivalence rules:

1. Express the argument in propositional notation.
2. Form the conditional: $(premise_1 \land premise_2 \land \ldots) \rightarrow conclusion$.
3. Use equivalence rules to simplify. If the result is a tautology (true in every row), the argument is valid. If not, it's invalid.

This algebraic method is faster than truth tables when you have many variables, but truth tables are more straightforward when you're first learning.