Introduction to Propositional Logic

TL;DR

Propositional logic is a fundamental part of discrete maths that deals with statements that can be either true or false. You'll learn how to represent these statements using symbols and combine them with logical connectives like "and," "or," and "not." This helps you analyze arguments and build sound logical foundations for computation.

1. The Mental Model

Think of propositional logic as the basic building blocks for making precise statements. It's like having a special language where every sentence is either definitely true or definitely false, and you have clear rules for how to link these sentences together.

2. The Core Material

Propositional logic focuses on propositions, which are declarative sentences that are unambiguously either true (T) or false (F), but not both. Questions, commands, or subjective opinions aren't propositions.

For example:
* "The sky is blue." (True)
* "2 + 2 = 5." (False)
* "Go clean your room!" (Not a proposition)

2.1 Representing Propositions

We use lowercase letters (p, q, r, s, etc.) to represent propositions.
* Let p be "It is raining."
* Let q be "The sun is shining."

2.2 Logical Connectives

Connectives are what we use to combine propositions into more complex statements.

a) Negation ($\neg$) - "NOT"

The negation of a proposition p, denoted $\neg p$, is true when p is false, and false when p is true.
* If p is "It is raining," then $\neg p$ is "It is NOT raining."

b) Conjunction ($\land$) - "AND"

The conjunction of p and q, denoted $p \land q$, is true only when both p and q are true. Otherwise, it's false.
* If p is "I will eat pizza" and q is "I will eat salad," then $p \land q$ means "I will eat pizza AND I will eat salad."

c) Disjunction ($\lor$) - "OR" (Inclusive OR)

The disjunction of p and q, denoted $p \lor q$, is true if p is true, or q is true, or both are true. It's only false if both p and q are false. This is typically inclusive OR in logic.
* If p is "I will study" and q is "I will watch TV," then $p \lor q$ means "I will study OR I will watch TV (or both)."

d) Implication ($\rightarrow$) - "IF... THEN..."

The implication $p \rightarrow q$ means "If p, then q." It's false only when p is true and q is false. In all other cases, it's true. Think of it as a promise: the promise is broken only if the condition (p) is met, but the result (q) doesn't happen.
* If p is "It rains" and q is "The ground gets wet," then $p \rightarrow q$ means "IF it rains, THEN the ground gets wet."
* If it rains (T) and the ground gets wet (T), the promise is kept (T).
* If it doesn't rain (F) and the ground gets wet (T), the promise is still kept (T) – something else could've wet the ground.
* If it doesn't rain (F) and the ground doesn't get wet (F), the promise is kept (T).
* If it rains (T) but the ground doesn't get wet (F), the promise is broken (F).

e) Biconditional ($\leftrightarrow$) - "IF AND ONLY IF" (IFF)

The biconditional $p \leftrightarrow q$ means "p if and only if q." It's true when p and q have the same truth value (both true or both false). Otherwise, it's false. It's equivalent to $(p \rightarrow q) \land (q \rightarrow p)$.
* If p is "You pass the exam" and q is "You study hard," then $p \leftrightarrow q$ means "You pass the exam IF AND ONLY IF you study hard."

2.3 Truth Tables

Truth tables are a systematic way to list all possible truth values for one or more propositions and their combinations using connectives. They show the truth value of a compound proposition for every possible combination of truth values of its simple propositions.

Here's how the truth values for our connectives work:

graph TD
    subgraph Negation
        P_neg[P] --> NOT_P[NOT P (¬P)]
        P_neg -- True --> NOT_P_F[False]
        P_neg -- False --> NOT_P_T[True]
    end

    subgraph Conjunction
        P_conj[P]
        Q_conj[Q]
        P_conj --> AND_PQ[P AND Q (P ^ Q)]
        Q_conj --> AND_PQ
        P_conj -- T --> Q_conj -- T --> AND_PQ_T[True]
        P_conj -- T --> Q_conj -- F --> AND_PQ_F1[False]
        P_conj -- F --> Q_conj -- T --> AND_PQ_F2[False]
        P_conj -- F --> Q_conj -- F --> AND_PQ_F3[False]
    end

    subgraph Disjunction
        P_disj[P]
        Q_disj[Q]
        P_disj --> OR_PQ[P OR Q (P v Q)]
        Q_disj --> OR_PQ
        P_disj -- T --> Q_disj -- T --> OR_PQ_T1[True]
        P_disj -- T --> Q_disj -- F --> OR_PQ_T2[True]
        P_disj -- F --> Q_disj -- T --> OR_PQ_T3[True]
        P_disj -- F --> Q_disj -- F --> OR_PQ_F[False]
    end

    subgraph Implication
        P_imp[P]
        Q_imp[Q]
        P_imp --> IF_THEN_PQ[IF P THEN Q (P -> Q)]
        Q_imp --> IF_THEN_PQ
        P_imp -- T --> Q_imp -- T --> IF_THEN_PQ_T1[True]
        P_imp -- T --> Q_imp -- F --> IF_THEN_PQ_F[False]
        P_imp -- F --> Q_imp -- T --> IF_THEN_PQ_T2[True]
        P_imp -- F --> Q_imp -- F --> IF_THEN_PQ_T3[True]
    end

    subgraph Biconditional
        P_bicond[P]
        Q_bicond[Q]
        P_bicond --> IFF_PQ[P IFF Q (P <-> Q)]
        Q_bicond --> IFF_PQ
        P_bicond -- T --> Q_bicond -- T --> IFF_PQ_T1[True]
        P_bicond -- T --> Q_bicond -- F --> IFF_PQ_F1[False]
        P_bicond -- F --> Q_bicond -- T --> IFF_PQ_F2[False]
        P_bicond -- F --> Q_bicond -- F --> IFF_PQ_T2[True]
    end

3. Worked Example

Let's construct a truth table for the compound proposition: $(p \land q) \rightarrow (\neg p \lor q)$.

First, identify the simple propositions: p and q. With two propositions, there are $2^2 = 4$ possible truth value combinations.

Next, break down the compound proposition into smaller parts, working from the innermost operations outwards:
1. $p \land q$
2. $\neg p$
3. $\neg p \lor q$
4. $(p \land q) \rightarrow (\neg p \lor q)$ (the full expression)

Notice that the final column is always true. This type of proposition, which is always true regardless of the truth values of its components, is called a tautology.

4. Key Takeaways

• Propositions are declarative sentences that are definitively true or false.
• Logical connectives ($\neg, \land, \lor, \rightarrow, \leftrightarrow$) combine simple propositions into complex ones.
• Negation ($\neg p$) flips the truth value of p.
• Conjunction ($p \land q$) is true only when both p and q are true.
• Disjunction ($p \lor q$) is true if at least one of p or q is true.
• Implication ($p \rightarrow q$) is false only when p is true and q is false.
• Biconditional ($p \leftrightarrow q$) is true when p and q have the same truth value.
• Truth tables systematically list all possible truth values for a compound proposition.

Common Mistakes to Avoid:
* Confusing inclusive OR ($\lor$) with exclusive OR (which means "one or the other, but not both"). In propositional logic, "or" generally means inclusive.
* Misinterpreting implication ($p \rightarrow q$). Remember it's only false in one specific case (T implies F).
* Forgetting the order of operations if not specified by parentheses (negation usually has highest precedence, then conjunction, then disjunction, then implication/biconditional).
* Trying to analyze sentences that aren't propositions (e.g., questions, commands).

5. Now Try It

Construct a truth table for the proposition $(p \lor \neg q) \leftrightarrow (\neg p \land q)$.
What to do:
1. List all possible truth value combinations for p and q.
2. Calculate the truth values for $\neg q$.
3. Calculate the truth values for $\neg p$.
4. Calculate the5. Calculate the truth values for $(p \lor \neg q)$.
6. Calculate the truth values for $(\neg p \land q)$.
7. Finally, calculate the truth values for the full biconditional expression.

What success looks like: You should have a truth table with 5 columns (p, q, p $\lor \neg q$, $\neg p \land q$, and the final biconditional). The final column will show the truth values (T/F) for the entire statement under all conditions.