§ — — Discrete Structures 1
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.
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:
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.")
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:
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.
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
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.
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")
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.
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." |
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.
Assign letter variables to simple statements, then build compound statements using connectives.
Example — define:
| 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 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:
A formula is well-formed if it satisfies these rules:
Parentheses matter: ¬(P ∧ Q) and ¬P ∧ Q are different formulas with different truth values.
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.
| P | ¬P |
|---|---|
| T | F |
| F | T |
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 |
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 |
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 |
| P | Q | ¬Q → ¬P |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
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 |
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.
Which of the following are propositions?
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
Let C = "Critical thinker", D = "Dota player", S = "Studying well".
Construct the truth table for each of the following:
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 →Done with this module? Track it — your progress shows on the subject list.
Up next
Lesson 2: Proof Techniques in Propositional Logic→