Propositional Logic
Logic gives mathematical statements precise meaning and lets us judge whether arguments are valid. It has practical uses in circuit design, program construction, and program verification.
What Is a Proposition?
A proposition is a declarative statement that carries a truth value — it is either true or false, with no middle ground. Propositions are sometimes called atomic statements.
Example: Consider three propositions:
- P: A grizzly is a bear.
- Q: A bear is a mammal.
- R: A grizzly is a mammal.
These can be combined: P ∧ Q → R ("If a grizzly is a bear and a bear is a mammal, then a grizzly is a mammal.")
Simple vs. Complex Statements
A simple statement contains only a single idea with no logical connectives. They are typically represented by uppercase letters (P, Q, R, ...).
A complex statement combines two or more simple statements using one or more logical connectives. There are five connective types in propositional logic:
- Negation
- Conjunction
- Disjunction
- Conditional
- Biconditional
Logical Connectives
Negation (¬ or ~)
A negation reverses the truth value of a statement. If P is true, then ¬P is false, and vice versa.
The negation symbol represents phrases like: "not", "it is not the case that", "it is false that".
Tip: When translating to symbolic form, keep simple statements positive where possible. Negating a statement is different from simply denying it.
Conjunction (∧ or &)
A conjunction claims that both of two statements are true simultaneously. It is represented by ∧, &, or •.
Conjunction keywords: and, but, also, however, yet, still, moreover, although, nevertheless, both
Example: "It is raining and my sunroof is open" → R ∧ O
Disjunction (∨)
A disjunction claims that at least one of two statements is true. It uses the symbol ∨ (called "vel").
Disjunction keywords: or, unless, either, neither
Example: "I will go to the movies or stay home" is true as long as at least one option is chosen.
Conditional (→)
A conditional (or implication) is false only when the hypothesis (antecedent) is true but the conclusion (consequent) is false.
Form: P → Q ("If P, then Q")
- Antecedent (P): the part before the arrow
- Consequent (Q): the part after the arrow
Conditional keywords: if, if…then, only if, whenever, when, implies, provided that, means, entails, is a sufficient condition for, is a necessary condition for, given that, on the condition that, in case
Important: Order matters in a conditional. Unlike conjunction and disjunction, swapping P and Q changes meaning and truth value.
The Three Related Forms of a Conditional
Given: "If it rains tonight (P), I will sleep well (Q)."
| Form | Structure | Example |
|---|---|---|
| Inverse | ¬P → ¬Q | "If it does not rain tonight, I will not sleep well." |
| Converse | Q → P | "I will sleep well if it rains tonight." |
| Contrapositive | ¬Q → ¬P | "I will not sleep well if it does not rain tonight." |
Necessary and Sufficient Conditions
- A sufficient condition guarantees the truth of something else (P → Q: P is sufficient for Q).
- A necessary condition must hold for something else to be true (P → Q: Q is necessary for P).
- "Only if" introduces the consequent, not the antecedent.
Biconditional (↔)
A biconditional holds when a condition is both necessary and sufficient. It is true whenever both sides have the same truth value.
Form: P ↔ Q ("P if and only if Q")
Biconditional keywords: if and only if, when and only when, just in case, is a necessary and sufficient condition for
Unlike conditionals, order does not change the meaning of a biconditional.
Translating English into Propositional Logic
Assign letter variables to simple statements, then build compound statements using connectives.
Example — define:
- V: Victor hit the ball.
- R: Reineil caught the ball.
- L: Lucas chased the ball.
| English sentence | Symbolic form |
|---|---|
| Victor did not hit the ball | ¬V |
| Either Victor hit or Reineil caught | V ∨ R |
| Lucas chased, but Reineil caught | L ∧ R |
| If Reineil caught, Lucas did not chase | R → ¬L |
| Lucas chased if and only if Victor hit | L ↔ V |
Identifying the main connective:
| Formula | Main Operator | Sentence Type |
|---|---|---|
| P | None | Simple |
| ¬P ∧ Q | ∧ | Conjunction |
| ¬(P ∧ Q) | ¬ | Negation |
| P ∨ (Q → R) | ∨ | Disjunction |
| [(P ∧ ¬Q) ↔ R] → P | → | Conditional |
Syntax and Semantics
Syntax describes the formal structure of logical expressions — the rules for building valid formulas.
Semantics deals with the meaning of those expressions — specifically, their truth values.
Symbols used:
- Proposition letters: P, Q, R, ..., X, Y, Z
- Unary operator: ¬ (negation)
- Binary connectives: ∧, ∨, →, ↔
- Grouping symbols: ( ), [ ]
Well-Formed Formulas (WFF)
A formula is well-formed if it satisfies these rules:
- Any single capital letter is a WFF.
- If φ is a WFF, then ¬φ is also a WFF.
- If φ and ψ are WFFs, then (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), and (φ ↔ ψ) are all WFFs.
Parentheses matter: ¬(P ∧ Q) and ¬P ∧ Q are different formulas with different truth values.
Truth Tables
A truth table lists every possible combination of truth values for the variables in a formula, and shows the resulting truth value of the whole formula.
Number of rows = 2ⁿ, where n = number of distinct variables.
Negation (¬P)
| P | ¬P |
|---|---|
| T | F |
| F | T |
Conjunction (P ∧ Q)
True only when both P and Q are true.
| P | Q | P ∧ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Disjunction (P ∨ Q)
False only when both P and Q are false.
| P | Q | P ∨ Q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Conditional (P → Q)
False only when P is true and Q is false.
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Contrapositive (¬Q → ¬P)
| P | Q | ¬Q → ¬P |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Biconditional (P ↔ Q)
True when P and Q have the same truth value.
| P | Q | P ↔ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Nature of Propositions
- Tautology: A proposition that is always true regardless of variable values. The last column of its truth table contains only T.
- Contradiction: A proposition that is always false. The last column contains only F.
- Contingency: A proposition that is neither always true nor always false — the last column contains both T and F.
Logically Equivalent Statements
Two compound statements are logically equivalent (≡) when they have identical truth values for every possible combination of variable values.
Example: P → Q ≡ ¬P ∨ Q
Proof by truth table:
| P | Q | P → Q | ¬P | ¬P ∨ Q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Both columns match, confirming the equivalence.
Exercises — Propositional Logic
Exercise 1.1 — Identifying Propositions
Which of the following are propositions?
- Study hard!
- The Apple Macintosh is a 16-bit computer.
- 1 is an even number.
- Why are we here?
- 8 + 7 = 13
Exercise 1.2 — Negation and Symbolization
Let p = "x < 50" and q = "x > 40". Write as simply as you can: a. ¬p b. ¬q c. p ∧ q d. p ∨ q e. ¬p ∧ q f. ¬p ∧ ¬q
Exercise 1.3 — Symbolic Notation
Let C = "Critical thinker", D = "Dota player", S = "Studying well".
- Von is a Dota player.
- If Miguel is a critical thinker and not studying well, then he is a Dota player.
- Sae is studying well and a Dota player.
- What is the negation of "All cows eat grass"?
- If p = "You tell everyone to support the government" and q = "You are blinded by privilege", write the symbolic notation for "If you tell everyone to support the government, then you are blinded by privilege."
Exercise 1.4 — Truth Tables (Construction)
Construct the truth table for each of the following:
- P ∧ (Q ∨ R)
- (P ∧ Q) ∨ R
- (P ∧ ¬Q) ∨ ¬P
- P ⇒ (Q ∨ ¬R)
- ¬((¬P ⇒ Q) ∨ (P ⇒ R))
Free Sample
That was 1 of 17 reviewers with answer keys in Discrete Structures 1. Unlock all of them for the semester.
Unlock all reviewers →