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 even realizing it, you're using propositional logic—you're piecing together statements (like "My friend is available") and connecting them with if, and, or to draw practical conclusions.

Why bother with formalizing it? * Clarity: When you precisely define statements and connect them with logical rules, you reduce the chance of confusion and misunderstandings. * Universality: Propositional logic underpins much of mathematics, computer science, and even everyday reasoning. * Efficiency: Formalizing your reasoning can help you solve problems faster and more systematically.

Recall from Part 1

We saw how deductive reasoning uses premises and connectives to reach solid conclusions. Now we'll sharpen that method by diving into 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 (it's either true or false, but not both). In the context of propositional logic, we think of these as "building blocks" that can't be broken down into simpler statements within our logical system.

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 any moment in time, so each is a proposition.

Non-Propositions

Not every phrase is a proposition. For instance: * Incomplete thoughts: "2 + 2" doesn't tell you anything about truth or falsehood.
Questions: "Is it raining?" cannot be labeled true or false—it's a request for information, not a statement. * Commands: "Close the door" is neither true nor false—it's an instruction. * Opinions or subjective statements*: "Ice cream is delicious" might be considered more a matter of preference than a definite truth.

Common Misconception

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

Connectives: The "Glue" of Logical Statements

Propositional logic features connectives—words like not, and, and or—that link propositions together to form new 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"), ensuring we preserve or transform truth values consistently.

The Main Logical Connectives

In propositional logic, the most fundamental connectives are:

Negation ($\neg$): "not"
Conjunction ($\land$): "and"
Disjunction ($\lor$): "or"
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 $\neg$. If $p$ is a proposition, then $\neg p$ (read "not p") has the opposite truth value of $p$.

Rule for Negation: * If $p$ is true, then $\neg p$ is false. * If $p$ is false, then $\neg p$ is true.

Turning a Light Switch Off

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

Real-Life Example of Negation

$p$ = "I will go jogging today."
If it's true that you will go jogging, then $\neg p$ = "I will not go jogging" is false.
If you end up not going jogging, then $p$ is false, and $\neg p$ is true.

Example

Let $r$ be the statement "It is raining." Then $\neg r$ is "It is not raining."
If "It is raining" ($r$) is true, "It is not raining" ($\neg r$) must be false.
If "It is raining" ($r$) is false, "It is not raining" ($\neg r$) must be true.

Double Negation

When we negate a negation, we get back to the original statement. This is called double negation:

$\neg(\neg p) \equiv p$

For example, "It is not the case that it is not raining" means the same as "It is raining."

The Connective "And" (Conjunction)

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

Rule for Conjunction: * "$p \land q$" is true if both $p$ and $q$ are true. * "$p \land 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 separate 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 \land s$ means "It is raining, and I have my umbrella." * This new statement is only true if both it is raining and you actually have an umbrella with you.

Conjunction in Decision-Making

Conjunction is essential in decision-making 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 work correctly if the installation is complete and the system meets the minimum 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 $\lor$. In mathematics (and logic), "or" is almost always used in the non-exclusive sense: * "$p \lor q$" is true if $p$ is true, $q$ is true, or both are true. * "$p \lor q$" is only false if both $p$ and $q$ are false.

Common Misconception

In everyday English, we often use "or" in an exclusive sense (like a restaurant menu: "soup or salad?" implies one or the other, not both). But in logic, "$p \lor q$" does not exclude the possibility that both could be true.

Real-Life Example of Disjunction

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

The disjunction $r \lor s$ means "Either it is raining or I have my umbrella, or both."
* This would be considered true if it's raining, or if you have your umbrella, or if both statements 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 morning show and garden in the afternoon). If you truly wanted to exclude the possibility of doing both, you'd have to explicitly say something like "I will do either the movies or gardening, but not both" (an exclusive or, which is less common in formal logic).

Exclusive OR (XOR)

The exclusive or (often abbreviated as 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. * This can be written in standard logical notation as: $(p \lor q) \land \neg(p \land q)$

In some contexts, the symbol $\oplus$ is used to represent exclusive or.

Parentheses and Precedence

When combining propositions with multiple connectives, we use parentheses to clarify the intended grouping. For instance, $p \land (q \lor r)$ is generally different from $(p \land q) \lor r$.

Why Precedence Matters

Think of parentheses like clarifying instructions in cooking: * "Mix (flour and sugar) and whisk" is different from "(Mix flour) and (sugar and whisk)."
The parentheses help us know which actions apply to which ingredients first.

Default Rule: Negation ($\neg$) has higher precedence than and ($\land$) or or ($\lor$). This means: * $\neg p \land q$ is read as $(\neg p) \land q$, not $\neg(p \land q)$. * $p \lor \neg q$ is read as $p \lor (\neg q)$, not $\neg(p \lor q)$.

Removing Unnecessary Parentheses

From a fully parenthesized statement:
$(((¬p) \land q) \lor (¬(r \lor s)))$
We can remove some parentheses without changing the meaning:
Remove the outermost parentheses:
$((¬p) \land q) \lor (¬(r \lor s))$
Since negation binds tightly, we can rewrite: $(¬p \land q) \lor ¬(r \lor s)$

This is now shorter but still clear in meaning.

Order of Operations in Propositional Logic

Here's the standard order of operations (from highest to lowest): 1. Parentheses 2. Negation ($\neg$) 3. Conjunction ($\land$) and Disjunction ($\lor$) 4. Conditional ($\to$) and Biconditional ($\leftrightarrow$)

When operators have the same precedence level (like $\land$ and $\lor$), parentheses should be used to make the meaning clear.

Applications of Propositional Logic

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

Computer Science

Boolean Algebra: The foundation of digital circuit design uses the same principles
Programming: Conditional statements (if-else) and logical operators in code
Database Queries: SQL's WHERE clauses use logical operators to filter data

Law

Legal Reasoning: Breaking down complex laws into logical components
Contract Analysis: Ensuring all conditions are properly stated and connected

Mathematics

Set Theory: Understanding set operations (union, intersection)
Proof Techniques: Constructing valid mathematical arguments

Everyday Reasoning

Decision Trees: Mapping out choices and their consequences
Critical Thinking: Evaluating arguments for logical consistency
Problem Solving: Breaking down complex problems into simpler parts

Common Misconceptions

"And" means everything must be true in any scenario.
Reality: Only the two specific propositions connected by $\land$ must both be true for the "and" statement to be true; other aspects might be unrelated.

"Or" in logic means one or the other but not both.
Reality: Logic generally adopts the inclusive or: $p \lor q$ is still true if both are true.

"Negation" is just adding 'not' in English.
Reality: Yes, but be careful that negation flips the truth value and can drastically change how you interpret combined statements.

"All statements can be classified as propositions."
Reality: Questions, commands, exclamations, opinions, and ambiguous statements are not propositions because they lack definite truth values.

Exercises

Use the rules of propositional logic to build confidence and intuition. Remember to treat "or" as inclusive.

2.1. Write the negation of each of the following statements in everyday English: * (a) "I am taking a geometry class." * (b) "Tom plays hockey on Sundays." * (c) "There are three trees in the back yard." * (d) "Everyone likes ice cream with pickles."

2.2. Suppose the following statements are all we know: * "The sky is blue" (true) * "The sea is green" (true) * "The earth is pink" (false) * "The moon is purple" (false)

Determine whether each statement below is true or false given the above: * "The sky is blue and the sea is green." * "The sky is blue and the earth is pink." * "The earth is pink and the sea is green." * "The earth is pink and the moon is purple." * "The earth is pink or the sea is green." * "The sky is blue or the sea is green." * "The earth is pink or the moon is purple."

2.3. For each pair of statements, write a compound statement using conjunction ($\land$) and another using disjunction ($\lor$). Then determine when each compound statement would be true or false. * "It's sunny outside." and "The temperature is above 75°F." * "The train is delayed." and "I will be late for work." * "The dog is barking." and "Someone is at the door."

2.4. Translate the following statements into symbolic form using propositional variables and connectives: * "Either I'll study for the exam or I'll fail the course." * "The car won't start, and the battery is dead." * "I will go swimming if it's not raining and the pool is open." * "Neither the principal nor the teacher attended the meeting."

2.5. Write out what each of these symbolic statements means in everyday English: * $p \land \neg q$ * $\neg(p \lor q)$ * $\neg p \lor \neg q$ * $(p \land q) \lor r$

Remember to use the inclusive meaning of "or" when deciding the truth values.

Final Thoughts

Propositional logic provides a foundation for clear thinking by helping us:

Break down complex ideas into simpler components
Connect ideas using precisely defined logical operations
Evaluate the truth or falsity of compound statements
Reason systematically about various possibilities

The skills you develop with propositional logic will serve you in countless situations—from solving puzzles to programming computers, from legal reasoning to scientific discovery. The ability to recognize the logical structure of statements helps cut through ambiguity and focus on what matters.

By mastering propositional logic, you'll have a clear, structured way to handle everyday decisions, puzzle-like scenarios, and formal mathematical proofs alike. Next, we'll move on to explore Truth Tables—a powerful tool for visualizing and validating logical statements.