1.1 Propositional Logic and Truth Tables

Propositional logic is the foundation of logical reasoning in discrete math. It deals with statements that are either true or false, and uses symbols to represent complex ideas. This topic introduces the building blocks you'll use throughout logical arguments and proofs.

Truth tables are the main tool for working with propositional logic. They show every possible combination of truth values for a set of statements, which lets you see exactly how logical operators behave. Getting comfortable with truth tables now will pay off when you move into analyzing arguments and writing proofs.

Propositional Basics

Fundamental Components of Propositional Logic

A proposition is a declarative statement that is either true or false, with no middle ground. "The sky is blue" is a proposition (it has a definite truth value). A question like "What time is it?" is not a proposition, because it can't be true or false.

• Simple propositions express a single, complete thought: "5 is a prime number" (true), "Toronto is in France" (false)
• Compound propositions combine multiple simple propositions using logical connectives like and, or, not, if-then, and if and only if
• Propositions are typically represented by lowercase letters like $p$, $q$, and $r$

These simple and compound propositions form the building blocks of every logical argument you'll encounter in this course.

Constructing and Interpreting Truth Tables

A truth table is a systematic way to determine the truth value of a compound proposition for every possible combination of its components. Here's how to build one:

1. Identify all the distinct simple propositions ($p$, $q$, $r$, etc.)
2. Calculate the number of rows: $2^n$, where $n$ is the number of distinct propositions. Two propositions give you 4 rows; three give you 8
3. Create columns for each simple proposition, then additional columns for each sub-expression and the final compound proposition
4. Fill in truth values for the simple propositions first, using T (true) and F (false). A standard pattern for two propositions is TT, TF, FT, FF
5. Evaluate the compound expression column by column, applying one connective at a time, working from the innermost grouping outward

You read the finished table row by row. Each row tells you: "Given this combination of inputs, the compound statement evaluates to this."

Truth tables are especially useful for verifying whether two expressions are logically equivalent and for checking whether an argument is valid.

Logical Operators

Fundamental Logical Connectives

Each logical connective has a precise definition that determines how it combines truth values.

Negation (NOT) reverses the truth value of a single proposition. The symbol is $\neg$, so $\neg p$ reads "not p." If $p$ is true, $\neg p$ is false, and vice versa.

Conjunction (AND) combines two propositions and is true only when both are true. The symbol is $\wedge$, so $p \wedge q$ reads "p and q." Think of it as a strict requirement: both parts must hold.

Disjunction (OR) combines two propositions and is true when at least one is true. The symbol is $\vee$, so $p \vee q$ reads "p or q." This is the inclusive or, meaning it's also true when both are true.

Implication (IF-THEN) connects a hypothesis $p$ to a conclusion $q$. The symbol is $\rightarrow$, so $p \rightarrow q$ reads "if p, then q." The tricky part: an implication is false in only one case, when $p$ is true and $q$ is false. If the hypothesis is false, the implication is automatically true regardless of $q$. This "vacuous truth" trips up a lot of students, so watch for it.

Biconditional (IF AND ONLY IF) is true exactly when both propositions share the same truth value (both true or both false). The symbol is $\leftrightarrow$, so $p \leftrightarrow q$ reads "p if and only if q."

Truth Table Representations of Logical Operators

</>Code
p | q | p ∧ q
T | T |   T
T | F |   F
F | T |   F
F | F |   F

</>Code
p | q | p ∨ q
T | T |   T
T | F |   T
F | T |   T
F | F |   F

</>Code
p | ¬p
T |  F
F |  T

</>Code
p | q | p → q
T | T |   T
T | F |   F
F | T |   T
F | F |   T

</>Code
p | q | p ↔ q
T | T |   T
T | F |   F
F | T |   F
F | F |   T

A helpful way to remember implication: the only "broken promise" is when you say "if p then q," p happens, and q doesn't. In every other scenario, the promise holds.

Truth Table Outcomes

Special Types of Compound Propositions

Once you've filled out a truth table, look at the final column. The pattern there tells you what type of compound proposition you're dealing with:

• A tautology is always true, no matter what truth values the components take. The final column is all T's. Classic example: $p \vee \neg p$ ("p or not p"). Every row evaluates to true.
• A contradiction is always false, regardless of the components. The final column is all F's. Classic example: $p \wedge \neg p$ ("p and not p"). No combination of values can make it true.
• A contingency is everything else: sometimes true, sometimes false, depending on the input values. Most compound propositions you'll encounter, like $p \rightarrow q$, are contingencies.

Analyzing and Applying Truth Table Outcomes

These three categories matter because they show up constantly in proofs and logical reasoning.

Tautologies are guaranteed truths, so they're used to establish logical laws. If you can show that an argument's structure is a tautology, you've proven the argument is valid. Contradictions signal logical inconsistency. If your reasoning leads to a contradiction, something in your assumptions must be wrong (this is the basis of proof by contradiction, which you'll see later). Contingencies remind you that a statement's truth depends on context; you can't assume it's always true or always false without more information.

When you're asked to classify a compound proposition, build the truth table and check the final column. All T's means tautology, all F's means contradiction, and a mix means contingency.