Propositional Logic

17 min read

Every proof you write, every if statement you debug, and every database query that returns the wrong rows comes back to one question: when is a statement true? Propositional logic is the rulebook. It strips a sentence down to a single bit, true or false, and fixes exactly how those bits combine under “not,” “and,” “or,” “if-then,” and “if and only if.” Once the rules are mechanical, the truth value of a long compound statement is forced by its parts, with no room for opinion. That determinacy is what lets logic drive proofs, circuits, and code.

By the end of this page you can:

• Test any sentence against the definition of a proposition.
• Give the symbol, the read-aloud name, and the truth rule for all five connectives.
• Build a complete truth table for a compound proposition.
• Name the one row that makes a conditional false, and explain why a false hypothesis makes it vacuously true.
• Apply operator precedence to parenthesize an unparenthesized expression correctly.

Why it matters: a processor is millions of AND, OR, and NOT gates wired together; a SQL WHERE clause is a compound proposition; a SAT solver decides whether one of these formulas can be made true, and that single capability verifies chip designs, finds security exploits, and schedules airlines. The notation on this page is the shared language under all of it.

Quick Reference

Before You Start

Check each box you can do from memory. A box you cannot check yet is not a problem; it points you to a quick refresher, not a grade.

• I can tell a declarative sentence (one that is either true or false) from a question or a command.
• I can read a propositional variable such as $p$ back as the English sentence it stands for.
• I can say how many true-or-false combinations $n$ variables produce. (Set-Builder and Roster Notation)

A 60-second self-check. Pick an answer, then reveal the reasoning.

Try This First

Before any symbol or formula, sort these five English sentences into two piles: a pile that is either true or false, and a pile that is neither.

1. Two plus two equals four.
2. Read the next page.
3. The year 1066 is after the year 1492.
4. Is this sentence short?
5. $x + 1 = 5$.

The Idea Behind Propositional Logic

A proposition is a process view of a sentence: feed it the facts of the world, and it returns one of exactly two outputs, true or false. Propositional logic is the study of how these true-or-false outputs combine when you join sentences with words such as “not,” “and,” “or,” “if-then,” and “if and only if.”

The reason this matters: once a statement is reduced to its true-or-false skeleton, the truth value of a complicated compound statement is forced by the truth values of its parts. There is no room for opinion. “It is raining and the streets are wet” is true exactly when both parts are true, no matter what the sentences are about. That mechanical determinacy is what lets logic drive proofs, circuit design, and database queries.

Each connective (“not,” “and,” “or,” and so on) is a fixed rule that takes the truth values of its inputs and returns a single output truth value. A truth table is the complete record of that rule across every possible input.

Prerequisite Hub

graph LR
    subgraph Builds_On["Builds On"]
        A["Set-Builder and<br/>Roster Notation"]
    end

    subgraph ThisSkill["This Skill"]
        C["Propositional<br/>Logic"]
    end

    subgraph Unlocks
        D["Applications of<br/>Propositional Logic"]
        E["Propositional<br/>Equivalences"]
        F["Predicates and<br/>Quantifiers"]
    end

    A --> C
    C --> D
    C --> E
    C --> F

    style C fill:#d1fae5,stroke:#a565f0,stroke-width:3px

    click C "propositional-logic.html"
    click D "../ch1-sec2/applications-of-propositional-logic.html"

Builds on:

Unlocks (what this section feeds into next):

Cross-course prerequisites: none.

Official Definitions

Each definition below is quoted from Rosen, 8th edition, Section 1.1, with the page citation. These are the canonical statements to put on the board and on a study sheet.

Proposition

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.

Rosen 8e, Section 1.1, p. 2 (subsection 1.1.2 Propositions).

The two possible outputs are called truth values, written $\text{T}$ (true) and $\text{F}$ (false). A letter such as $p$, $q$, or $r$ used to stand for a proposition is a propositional variable.

Negation (Definition 1)

Let $p$ be a proposition. The negation of $p$, denoted by $\neg p$ (also denoted by $\overline{p}$), is the statement “It is not the case that $p$.” The proposition $\neg p$ is read “not $p$.” The truth value of the negation of $p$ is the opposite of the truth value of $p$.

Rosen 8e, Section 1.1, Definition 1, p. 3.

Conjunction (Definition 2)

Let $p$ and $q$ be propositions. The conjunction of $p$ and $q$, denoted by $p \wedge q$, is the proposition “$p$ and $q$.” The conjunction $p \wedge q$ is true when both $p$ and $q$ are true and is false otherwise.

Rosen 8e, Section 1.1, Definition 2, p. 4.

Disjunction (Definition 3)

Let $p$ and $q$ be propositions. The disjunction of $p$ and $q$, denoted by $p \vee q$, is the proposition “$p$ or $q$.” The disjunction $p \vee q$ is false when both $p$ and $q$ are false and is true otherwise.

Rosen 8e, Section 1.1, Definition 3, p. 5.

The disjunction is the inclusive or: $p \vee q$ is true when $p$ is true, when $q$ is true, and when both are true.

Conditional Statement (Definition 5)

Let $p$ and $q$ be propositions. The conditional statement $p \rightarrow q$ is the proposition “if $p$, then $q$.” The conditional statement $p \rightarrow q$ is false when $p$ is true and $q$ is false, and true otherwise. In the conditional statement $p \rightarrow q$, $p$ is called the hypothesis (or antecedent or premise) and $q$ is called the conclusion (or consequence).

Rosen 8e, Section 1.1, Definition 5, p. 6.

Biconditional Statement (Definition 6)

Let $p$ and $q$ be propositions. The biconditional statement $p \leftrightarrow q$ is the proposition “$p$ if and only if $q$.” The biconditional statement $p \leftrightarrow q$ is true when $p$ and $q$ have the same truth values, and is false otherwise.

Rosen 8e, Section 1.1, Definition 6, p. 10.

Truth Table

A truth table displays the relationships between the truth values of propositions; it lists every possible combination of truth values of the propositional variables that occur in a compound proposition and gives the resulting truth value of the compound proposition for each combination.

Rosen 8e, Section 1.1, subsection 1.1.4 Truth Tables of Compound Propositions, p. 8-9.

The Five Connectives at a Glance

Two representations of each connective sit side by side here: the worded rule (when is it true) and the symbolic form. Read across each row and translate one into the other.

Truth Tables of Compound Propositions

The defining truth tables for the four binary connectives. Each row is one combination of inputs; the last column is the forced output.

And negation, which takes one input:

The conditional row to study most carefully is the bottom two: when $p$ is false, $p \rightarrow q$ is true no matter what $q$ is. A conditional with a false hypothesis is called vacuously true.

Precedence of Logical Operators

When a compound proposition is written without enough parentheses, the connectives apply in a fixed order. Rosen lists this precedence in subsection 1.1.5 (p. 15-16).

So $\neg p \wedge q$ means $(\neg p) \wedge q$, not $\neg (p \wedge q)$, because negation binds tighter than conjunction. When in doubt, add parentheses.

Quick check. The three things students misread most often: the one false row of a conditional, the inclusive “or,” and precedence.

Worked Examples

Worked Example 1: Building a Truth Table for a Compound Proposition

Problem. Construct the truth table for $(p \vee \neg q) \rightarrow q$.

Predict first. Before computing, predict: this statement starts with a disjunction inside, then feeds it into a conditional with conclusion $q$. A reasonable guess is that the conditional fails (is false) whenever the conclusion $q$ is false but the hypothesis is true. Hold that prediction.

Step 1. List all $2^2 = 4$ combinations of $p$ and $q$, and add a column for the inner pieces.

Step 2. Compute $\neg q$, then $p \vee \neg q$, then the full conditional.

Step 3. Read off the final column: the compound proposition is true in rows 1 and 3, and false in rows 2 and 4.

Check the prediction. The statement is false exactly in the rows where the hypothesis $p \vee \neg q$ is true and the conclusion $q$ is false (rows 2 and 4). That matches the prediction. The two false rows are precisely the “true-hypothesis, false-conclusion” cases, which is the only way a conditional is false.

Worked Example 2: Translating English into Symbols

Problem. Let $p$ be “You complete the lab” and $q$ be “You pass the course.” Write each English sentence in symbols.

(a) “If you complete the lab, then you pass the course.” (b) “You complete the lab and you do not pass the course.” (c) “You pass the course if and only if you complete the lab.”

Solution.

(a) “If $p$, then $q$” is the conditional: $p \rightarrow q$.

(b) “$p$ and not $q$”: the negation binds to $q$ first, then the conjunction joins: $p \wedge \neg q$.

(c) “$q$ if and only if $p$” is the biconditional: $q \leftrightarrow p$. Because a biconditional is true exactly when both sides share a truth value, $q \leftrightarrow p$ and $p \leftrightarrow q$ have identical truth tables.

Check. Sentence (b) is exactly the situation that makes the conditional in (a) false: $p$ true and $q$ false. Symbolically, $p \wedge \neg q$ is true only in the row where $p \rightarrow q$ is false. That is the same row, which confirms the two statements are describing opposite verdicts about the same case.

Worked Example 3: Applying Operator Precedence

Problem. Evaluate $\neg p \vee q \wedge p$ when $p$ is true and $q$ is false. Insert the parentheses the precedence rules require.

Predict first. With $p$ true, $\neg p$ is false. With $q$ false, the conjunction $q \wedge p$ also looks false. A disjunction of two false-looking pieces is probably false. Hold that prediction.

Step 1. Apply precedence. Negation is highest, then conjunction, then disjunction. So the expression groups as

$$(\neg p) \vee (q \wedge p).$$

Step 2. Substitute $p = \text{T}$, $q = \text{F}$.

• $\neg p = \neg \text{T} = \text{F}$.
• $q \wedge p = \text{F} \wedge \text{T} = \text{F}$.
• $(\neg p) \vee (q \wedge p) = \text{F} \vee \text{F} = \text{F}$.

Check the prediction. The result is false, matching the prediction. The danger row to avoid is misreading the expression as $\neg (p \vee q) \wedge p$, which groups differently and can give a different answer. Precedence, not left-to-right reading, decides the grouping.

Common Misconceptions

Practice Problems

Mastery Checklist

Novice (Level 1-2):

• I can state, from memory, what a proposition is and test a sentence against the definition.
• I can give the symbol, the worded rule, and the read-aloud name for each of the five connectives.
• I can evaluate a small compound proposition for given truth values of its variables.

Competent (Level 3-4):

• I can build a complete truth table for a compound proposition with two variables.
• I can translate an English “and,” “or,” “not,” “if-then,” “if and only if” sentence into symbols and back.
• I can name the single combination of truth values that makes a conditional false.

Proficient (Level 5):

• I can apply operator precedence to insert the correct parentheses in an unparenthesized expression.
• I can produce a specific row of truth values to show two readings of an expression disagree.
• I can explain why a conditional with a false hypothesis is vacuously true.

Mental Model

The “two-output machine” view. Picture each proposition as a small machine that takes the facts of the world as input and returns exactly one of two outputs, true or false. A connective is a wiring rule that combines the outputs of smaller machines into the output of a bigger machine. The truth table is the full specification sheet for that wiring: every input row, with the one output it forces. Nothing about meaning or topic enters; only the true-or-false outputs travel through the wires.

Connections

Looking back:

• Set-Builder and Roster Notation gives the variable-and-set notation that the symbolic connectives reuse.

Looking ahead:

• Applications of Propositional Logic (Section 1.2): translating English sentences, system specifications, and logic puzzles into these connectives.
• Propositional Equivalences (Section 1.3): proving that two compound propositions always share a truth value, which is what tautologies and logical equivalence formalize.
• Predicates and Quantifiers (Section 1.4): extending to sentences with variables, such as the “$x + 1 = 5$” case from the opener, where a truth value appears only once the variable is fixed.

Real-world connections:

• Digital circuits realize $\wedge$, $\vee$, and $\neg$ directly as AND, OR, and NOT gates.
• Database search conditions combine clauses with the same connectives.
• Program control flow (“if condition then action”) is the conditional applied to runtime facts.

Go Deeper (optional)

None of this is needed to build a correct truth table or to pass the section. It is here for readers who want to see where these five connectives lead.

These are the logic gates in every processor. Conjunction, disjunction, and negation are the AND, OR, and NOT gates etched into silicon. A 64-bit adder, the comparison that drives an if, the decoder that picks one memory cell out of billions: each is a compound proposition realized in hardware. When you simplify a truth table by hand, you are doing what a chip’s synthesis tool does to shrink area and power. Section 12 of this course, Boolean algebra, makes that link formal.

This is the engine behind SAT solvers, and SAT is the first NP-complete problem. Ask whether some assignment of truth values can make a formula true, and you have the Boolean satisfiability problem, SAT. It was the first problem proven NP-complete (Cook, 1971), so it anchors the whole P-versus-NP question. In practice, modern solvers handle formulas with millions of variables, and industry runs them constantly: to prove a CPU design has no logic bug before fabrication (formal verification), to find security holes by encoding “can an input reach this unsafe state” as a formula (symbolic execution), and to schedule and route systems where a hand search would never finish.

Why a careers reader should care.

• Software engineering: every compound if or while condition is one of these formulas. De Morgan’s laws, in the next section, are how you correctly negate !(a && b) without shipping a bug.
• Cybersecurity: access-control policies, firewall rules, and constraint-based exploit finding are propositional formulas a solver reasons about.
• Data science and databases: a SQL WHERE clause is a compound proposition, and the query planner rewrites it with the equivalences from Section 1.3 to run faster.

A subtlety worth noticing. The conditional $p \rightarrow q$ being vacuously true when $p$ is false bothers almost everyone at first. It is a deliberate choice: defining it this way is the only rule that keeps “if every number in the list is positive, then the sum is positive” true for the empty list, which is the behavior proofs and loops need. The material conditional claims no causal link between $p$ and $q$; it only records, row by row, when the promise “$p$ forces $q$” is broken.

Check Yourself

Close the notes and answer each from memory, then reveal it. Pulling an idea back from memory is one of the strongest ways to make it stick.

Resources

Last updated: 2026-06-16