Part 2: Propositional Logic

Why Propositional Logic Matters

Imagine you're organizing a surprise party. You might think to yourself:
- "If my friend is available ($p$), then we'll book the venue on Friday ($q$)."
- "But if the weather forecast is bad ($r$), we may delay or choose a different date."

Without realizing it, you're using propositional logic — piecing together statements (like "My friend is available") and connecting them with if, and, or to draw practical conclusions.

Why bother formalizing this?
- Clarity: By precisely defining statements and connecting them with logical rules, you reduce the chance of confusion and misunderstanding.
- Universality: Propositional logic underpins much of mathematics, computer science, and everyday reasoning.
- Efficiency: Formalizing your reasoning can help you solve problems more systematically.

Recall from Part 1

We saw how deductive reasoning uses premises and logical structure to reach solid conclusions. Now we'll sharpen that method with propositional logic, where we assign truth values to statements and see how they combine.

---

What Is a Proposition?

A proposition is a statement that has a definite truth value (either true or false, but not both). In propositional logic, we treat these statements as indivisible units or "building blocks" that we can combine using logical connectives.

Everyday Propositions

• "It is raining right now." (True or false?)
• "My phone battery is at 50%." (True or false?)
• "2 + 2 = 4." (True or false?)

Each of these can be true or false at a given time, so each is a proposition.

Non-Propositions

Not every sentence is a proposition. For example: - Incomplete thought: "2 + 2" by itself isn’t a complete statement with a truth value.
- Question: "Is it raining?" isn't true or false — it's a request for information.
- Command: "Close the door." is neither true nor false — it's an instruction.
- Opinion: "Ice cream is delicious" is subjective; its truth value can differ by person and isn't objectively true or false in the logical sense.

What Counts as a Proposition?

Some people think any statement in English is automatically a proposition. But questions, commands, and incomplete sentences do not have truth values, so they're not propositions.

---

Connectives: The "Glue" of Logical Statements

Propositional logic features connectives — words like not, and, or, if...then — that link propositions together to form new, compound statements. The grammar of propositional logic tells us how to place these connectives and how to interpret the resulting statements.

Why Connectives Matter

Just as grammatical connectors (like "because," "although," "since") shape complex sentences in English, logical connectives shape complex logical statements. They let us build from simple truths ("It is raining") to nuanced claims ("It is raining, and I have an umbrella"), while preserving or transforming truth values in a consistent way.

The Main Logical Connectives

In propositional logic, the fundamental connectives are:

• Negation ($\mathrm{\neg }$): "not"
• Conjunction ($\wedge$): "and"
• Disjunction ($\vee$): "or" (in the inclusive sense)
• Conditional ($\to$): "if...then"
• Biconditional ($\leftrightarrow$): "if and only if"

In this section, we'll focus on the first three, and cover conditionals and biconditionals in later sections.

---

The Connective "Not" (Negation)

In propositional logic, "not" is represented by the symbol $\mathrm{\neg }$. If $p$ is a proposition, then $\mathrm{\neg }p$ (read "not p") has the opposite truth value of $p$.

Rule for Negation:
- If $p$ is true, then $\mathrm{\neg }p$ is false.
- If $p$ is false, then $\mathrm{\neg }p$ is true.

Flipping a Switch

Think of negation like flipping a light switch:
- If the light is on (p = true), flipping the switch turns it off ($\mathrm{\neg }p$ = false).
- If the light is off (p = false), flipping the switch turns it on ($\mathrm{\neg }p$ = true).

Real-Life Example of Negation

• $p$ = "I will go jogging today."
• If this is true, then $\mathrm{\neg }p$ = "I will not go jogging today" is false.
• If you end up not going jogging, then $p$ is false and $\mathrm{\neg }p$ is true.

Example

Let $r$ be the statement "It is raining." Then $\mathrm{\neg }r$ is "It is not raining."
- If "$r$" ("It is raining") is true, then "$\mathrm{\neg }r$" ("It is not raining") is false.
- If "$r$" is false, then "$\mathrm{\neg }r$" is true.

Double Negation

If you negate a negation, you return to the original statement. This is called double negation:

$$\mathrm{\neg }(\mathrm{\neg }p)\equiv p$$

For example, "It is not the case that I am not jogging" means the same as "I am jogging."

---

The Connective "And" (Conjunction)

The and connective is symbolized by $\wedge$ (sometimes written as "&"). It asserts that both statements it connects are true.

Rule for Conjunction:
- "$p\wedge q$" is true if both $p$ and $q$ are true.
- "$p\wedge q$" is false if either $p$ is false, $q$ is false, or both are false.

Two Keys to Open a Door

Imagine a locked door that requires two different keys to open. If you have both keys, the door opens (true). If you're missing even one key, the door stays locked (false).

Real-Life Example of Conjunction

• $r$ = "It is raining."
• $s$ = "I have my umbrella."

The conjunction $r\wedge s$ means "It is raining and I have my umbrella."
- This new statement is true only if both it is raining and you actually have an umbrella with you.

Conjunction in Decision-Making

Conjunction is crucial when all conditions must be met: - "I'll buy this house if it has three bedrooms and is close to good schools."
- "The software will run if the installation is complete and the system meets the requirements."
- "A student passes the course if their attendance is above 80% and they score at least 60% on the final exam."

---

The Connective "Or" (Disjunction)

The or connective is symbolized by $\vee$. In logic (and math), "or" is typically used in the inclusive sense:

• "$p\vee q$" is true if $p$ is true, $q$ is true, or both are true.
• "$p\vee q$" is false only if both $p$ and $q$ are false.

Inclusive vs. Exclusive 'Or'

In everyday English, we often use "or" in an exclusive way (e.g., a menu might say "soup or salad?" implying one or the other, but not both). In logic, "$p\vee q$" does not exclude the possibility that both $p$ and $q$ are true. If we need to exclude "both," we explicitly specify "either...or...but not both" (this is the exclusive or).

Real-Life Example of Disjunction

• $r$ = "It is raining."
• $s$ = "I have my umbrella."

The disjunction $r\vee s$ means "Either it is raining or I have my umbrella (or both)."
- This statement is true if it's raining, or if you have your umbrella, or if both are true.

Choosing Activities

Suppose it's the weekend and you think: "I will go to the movies or do some gardening." In logical terms, this doesn't exclude doing both (maybe you watch a movie in the morning and garden in the afternoon). If you truly want to exclude doing both, you'd say something like "I will do either the movies or gardening, but not both" (an exclusive or, which is a different concept).

Exclusive OR (XOR)

The exclusive or (often abbreviated XOR) is a variant of disjunction where both statements cannot be true simultaneously:
- "$p$ XOR $q$" is true if either $p$ is true or $q$ is true, but not both.
- In logical notation, we can write XOR as: \($(p\vee q)\wedge \mathrm{\neg }(p\wedge q)$\)
- Sometimes the symbol $\oplus$ is used to represent exclusive or.

---

Parentheses and Precedence

When combining propositions with multiple connectives, we use parentheses to clarify grouping. For instance, $p\wedge (q\vee r)$ generally means something different from $(p\wedge q)\vee r$.

Why Precedence Matters

Think of parentheses like clarifying instructions in a recipe: - "Mix (flour and sugar) and then whisk" is different from "(Mix flour) and (sugar and whisk)." The parentheses tell us which actions or ingredients go together first.

Default Precedence Rules: In logic, by convention: - Negation ($\mathrm{\neg }$) has higher precedence than and ($\wedge$) or or ($\vee$). This means $\mathrm{\neg }p\wedge q$ is read as $(\mathrm{\neg }p)\wedge q$, not $\mathrm{\neg }(p\wedge q)$. Likewise, $p\vee \mathrm{\neg }q$ is read as $p\vee (\mathrm{\neg }q)$.
- And ($\wedge$) and Or ($\vee$) have higher precedence than $\to$ and $\leftrightarrow$ (which we'll cover later).

If in doubt, use parentheses to make the intended meaning clear.

Removing Unnecessary Parentheses

Starting expression:
$(((\neg p) \land q) \lor (\neg (r \lor s)))$
We can remove some parentheses without changing the meaning: 1. Remove the outermost parentheses:
$( (\neg p) \land q) \lor (\neg (r \lor s))$
2. Since negation binds tightly, we can rewrite:
$(\neg p \land q) \lor \neg(r \lor s)$

The expression is now simpler but still clear in meaning.

Order of Operations in Propositional Logic

Standard precedence (from highest to lowest) is: 1. Parentheses
2. Negation ($\mathrm{\neg }$)
3. Conjunction ($\wedge$) and Disjunction ($\vee$)
4. Conditional ($\to$) and Biconditional ($\leftrightarrow$)

When connectives have the same precedence level (e.g. $\wedge$ and $\vee$), use parentheses to avoid ambiguity.

---

Applications of Propositional Logic

Propositional logic isn't just abstract — it has practical applications in many fields:

Computer Science

• Boolean Algebra & Circuits: Digital circuit design uses the same logical principles (e.g., an AND gate corresponds to $\wedge$, an OR gate to $\vee$).
• Programming: Conditional statements (if-else) and logical operators (&&, ||, ! in many languages) mirror propositional logic.
• Database Queries: SQL WHERE clauses use logical operators (AND, OR, NOT) to filter data.

Law

• Legal Reasoning: Breaking down complex laws into combinations of conditions (propositions) with logical structure (e.g., "If act X and circumstance Y, then consequence Z").
• Contract Analysis: Ensuring contracts spell out conditions and outcomes clearly using logical structure ("if and only if" appears often to set exact conditions).

Mathematics

• Set Theory & Counting: Logical connectors relate to set operations (AND ~ intersection, OR ~ union).
• Proof Techniques: Constructing valid mathematical proofs often boils down to using propositional logic correctly (e.g., proof by contradiction uses negation).

Everyday Reasoning

• Decision Trees: We often draw simple flowcharts for decisions that mimic logical statements (if condition, then outcome).
• Critical Thinking: Evaluating arguments in debates or articles involves checking if the conclusion really follows from the premises (propositional logic helps reveal hidden assumptions or fallacies).

Common Misconceptions

• "If $p$ is false, then $p\to q$ must be false."
  Reality: If $p$ is false, the statement $p\to q$ is considered true (because a false hypothesis trivially makes the implication true – see the truth table in Part 4).

• "In logic, 'or' means only one or the other, not both."
  Reality: Unless explicitly stated as exclusive, "or" in logic is inclusive. $p\vee q$ allows for both $p$ and $q$ being true.

• "Formalizing statements is unnecessary work."
  Reality: Writing statements symbolically can reveal ambiguities or hidden assumptions that are easy to overlook in natural language.

Exercises

Understanding Connectives

For each informal statement, identify the logical connectives and rewrite it using logical symbols (let $p$, $q$, $r$ represent basic propositions): 2.1. "I will go to the park if it is sunny and I have finished my homework."
2.2. "Either we win this game or we learn a valuable lesson (or both)."
2.3. "It is not true that both team A and team B can win the championship."

Translating to English

Describe in plain English what the following propositional logic statements mean: 2.4. $\mathrm{\neg }p\vee q$
2.5. $(p\wedge q)\to \mathrm{\neg }r$
2.6. $p\leftrightarrow q$

Applications

2.7. Give a real-world scenario that could be modeled by the expression $(p\wedge q)\vee r$. Explain what $p$, $q$, and $r$ represent in your scenario.
2.8. Write a simple set of conditions (like a mini-puzzle or rule set) and express them with propositional logic. For example, "If the light is on and the switch works, then electricity is flowing."

---

Next: In Part 3: Truth Tables, we'll learn a systematic method to determine the truth of complex statements under every possible scenario.