Introduction to Logic, Quantifiers, and Proofs

Vocabulary practice flashcards covering definitions, logical connectives, equivalences, quantifiers, and proof terminology.

Proposition

A declarative sentence that is either true (denoted $T$ or $1$) or false (denoted $F$ or $0$), but not both.

Negation

For a proposition $P$, the proposition $\neg P$ which is true when $P$ is false, and false when $P$ is true.

Conjunction

The proposition $P \wedge Q$ formed from propositions $P$ and $Q$, which is true if both $P$ and $Q$ are true, and false otherwise.

Disjunction

The proposition $P \vee Q$ formed from propositions $P$ and $Q$, which is true if at least one of $P$ or $Q$ is true, and false otherwise.

Implication

The proposition $P \Rightarrow Q$ ("P implies Q"), which is false only when $P$ is true and $Q$ is false. If $P$ is false, the implication is true regardless of the truth value of $Q$.

Converse

For a conditional statement $P \Rightarrow Q$, the implication $Q \Rightarrow P$.

Contrapositive

For a conditional statement $P \Rightarrow Q$, the implication $\neg Q \Rightarrow \neg P$.

Biconditional

The proposition $P \Leftrightarrow Q$ ("P is equivalent to Q"), which is true whenever $P$ and $Q$ have the same truth value, and coincides with $(P \Rightarrow Q) \wedge (Q \Rightarrow P)$.

Logical Equivalence

Two propositions $P$ and $Q$ are logically equivalent ($P \equiv Q$) if they share the same truth table, meaning they have the same truth value for every assignment of truth values to their variables.

De Morgan's Laws (Propositional Logic)

The logical equivalences $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$ and $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$.

Predicate

A declarative statement $P(x)$ or $P(x_1, x_2, \dots, x_n)$ about one or more variables whose truth value depends on the value of the variable(s).

Domain

The set of possible values (also called the universe) that a variable can take in a predicate.

Universal Quantifier ($\forall$)

The quantification $\forall x \in E : P(x)$, read as "for all", "for every", or "for each", which is true if $P(x)$ is true for every element $x$ in domain $E$.

Existential Quantifier ($\exists$)

The quantification $\exists x \in E : P(x)$, which is true if $P(x)$ is true for at least one element $x$ in domain $E$.

Unique Existential Quantifier ($\exists!$)

The quantification $\exists! x \in E : P(x)$, read as "there exists a unique" or "there is exactly one", which is true if $P(x)$ is true for exactly one element $x$ in domain $E$.

Negation of Quantifiers

The logical equivalences $\neg(\forall x \in E : P(x)) \equiv \exists x \in E : \neg P(x)$ and $\neg(\exists x \in E : P(x)) \equiv \forall x \in E : \neg P(x)$.

Principle of Mathematical Induction

For a family of statements $P(n)$ where $n_0 \in \mathbb{N}$, if the base case $P(n_0)$ is true and the inductive step $P(n) \Rightarrow P(n+1)$ holds for every integer $n \ge n_0$, then $P(n)$ is true for every integer $n \ge n_0$.

Counterexample

An element $x_0$ satisfying the hypothesis $P(x_0)$ while violating the conclusion $Q(x_0)$ (satisfying $P(x_0) \wedge \neg Q(x_0)$), demonstrating that a universal statement $\forall x : P(x) \Rightarrow Q(x)$ is false.

Geometric Sum

For $k \in \mathbb{R}$ with $k \neq 1$ and every $n \in \mathbb{N}$, the identity given by $\sum_{i=0}^n k^i = \frac{k^{n+1} - 1}{k - 1}$.