Logic and Quantifiers glossary

Clear, one-line definitions of the Logic and Quantifiers terms used across the OgbonLab textbooks. Each entry links to the interactive sections where the idea is taught.

arbitrary

A variable is arbitrary in a proof when no special properties are assumed; whatever is proved holds for every value.

biconditional

P ⇔ Q ('P iff Q'), true when P and Q have the same truth value; equivalent to (P ⇒ Q) and (Q ⇒ P).

See: The Conditional and Biconditional Connectives, Proofs Involving Conjunctions and Biconditionals

bound variable

A variable governed by a quantifier or set-builder; renaming it does not change the meaning.

bounded existential

A quantifier of the form ∃x ∈ S, P(x) restricting the witness to a specific set S.

bounded quantifier

A quantifier restricted to a specific set, e.g., ∀x ∈ S, P(x) or ∃x ∈ S, P(x).

See: Bounded Quantifiers and Restricted Domains

bounded universal

A quantifier of the form ∀x ∈ S, P(x) restricting the claim to elements of a specific set S.

conditional

A statement P ⇒ Q (if P then Q), true whenever P is false OR Q is true; only false when P is true and Q is false.

See: Joint, conditional, marginal, Debiasing checks and conditional bias

conjunction

P ∧ Q ('P and Q'), true only when both P and Q are true.

See: Proofs Involving Conjunctions and Biconditionals

contingency

A propositional formula whose truth table has both T and F rows; its value depends on the inputs.

contrapositive

The contrapositive of 'if P then Q' is 'if not Q then not P'; logically equivalent to the original.

converse

The converse of 'if P then Q' is 'if Q then P'; it does not always share the original's truth value.

disjunction

P ∨ Q ('P or Q'), true when at least one of P or Q is true (inclusive or).

See: Proofs Involving Disjunctions

element

An object belonging to a set; we write a ∈ A to mean a is an element of A.

See: Sets and Elements

existential quantifier

∃x, P(x), read 'there exists at least one x for which P(x) holds.'

free variable

A variable not governed by any quantifier; the formula's truth value depends on its assigned value.

implication

A logical statement of the form 'if P then Q'; false only when P is true and Q is false.

intersection

The set A ∩ B containing only the elements that are in both A and B.

logical equivalence

Two formulas are logically equivalent (≡) when they have the same truth value in every row of the joint truth table.

negation

¬P ('not P'), true exactly when P is false.

See: Proofs Involving Negations and Conditionals

quantifier

A symbol like ∀ (for all) or ∃ (there exists) specifying the range of a variable in a logical statement.

See: Quantifiers, Proofs Involving Quantifiers

set

A well-defined collection of distinct objects, called its elements.

statement

A formula with no free variables; assigns a definite truth value (true or false).

subset

A set A is a subset of B if every element of A is also an element of B; written A ⊆ B.

tautology

A propositional formula true in every row of its truth table, such as P ∨ ¬P (law of excluded middle).

truth table

A complete listing of every truth-value assignment to the variables, showing the resulting truth value of a compound formula.

See: Truth Tables

union

The set A ∪ B containing every element that is in A, in B, or in both.

universal quantifier

∀x, P(x), read 'for every x, P(x) holds.'

well-formed formula

A propositional formula built from atomic statements and connectives according to grammatical rules; abbreviated wff.