Predicates and Quantifiers

Flashcards covering core vocabulary, terms, and concepts for Predicates and Quantifiers in predicate logic.

Predicate Logic

A system of logic that models statements using variables, predicates, and quantifiers to express relationships that propositional logic cannot represent.

Variable

The subject of a statement in predicate logic, typically denoted by letters such as $x$, $y$, or $z$.

Predicate

The property or relationship referring to what the subject of a statement can have, denoted by $P(x)$ where $P$ represents the predicate and $x$ represents the variable.

Propositional Function

A statement involving variables, such as $P(x)$, that becomes a proposition with a truth value of true or false when its variables are assigned values from the domain or bound by a quantifier.

Domain

The set or range of values that a variable in a propositional function can hold, often denoted by $U$ (universe of discourse).

Universal Quantifier

A quantifier represented by the symbol $\forall$, read as "for all" or "for every", asserting that a proposition $P(x)$ is true for all values of $x$ in the domain.

Existential Quantifier

A quantifier represented by the symbol $\boxminus$ (or \negthickspace \raisebox{0.1em}{\tiny\text{I}}\negthickspace\text{E} / $\negthickspace \text{E}$ / $\text{E}$ symbol rendered as $\text{E}$ rotated / $\text{E}$ back turned, denoted as $\text{E}$ / $\text{E}$ symbol for existence or $\negthickspace\text{E}$ or $\text{E}$ rotated, standard $\text{E}$ reverse / $\negthickspace\text{E}$ / $\text{E}$ back or $\text{E}$ backwards / $\negthickspace \text{E}$ / $\negthickspace \text{E}$ / $\text{E}$ flipped / $\text{E}$ mirrored, standard notation $\text{E}$ reversed / $\text{E}$ inverted or $\text{E}$ rotated symbol rendered in text as $\text{E}$ flipped horizontally / $\text{E}$ mirrored / $\text{E}$ flipped symbol rendered as $\text{E}$ mirrored / $\text{E}$ flipped / $\text{E}$ rotated or $\text{E}$ symbol rendered in transcript as 3 or $\text{E}$ mirrored / $\text{E}$ flipped, standard LaTeX $\exists$), read as "there exists" or "for at least one", asserting that $P(x)$ is true for some value(s) of $x$ in the domain.

Counterexample

A specific value within the domain or universe that proves a universal statement or proposition is false.

Universal and Existential Quantifiers Comparison

A comparative summary showing the conditions under which universal ($\forall x P(x)$) and existential ($\exists x P(x)$) quantifications are true or false, along with their expanded conjunction and disjunction representations.

De Morgan's Laws for Quantifiers

Logical equivalences stating that the negation of an existential quantification is equivalent to a universal quantification of the negated predicate ($\neg \exists x P(x) \equiv \forall x \neg P(x)$), and the negation of a universal quantification is equivalent to an existential quantification of the negated predicate ($\neg \forall x P(x) \equiv \exists x \neg P(x)$).

Conclusion Symbol ($\therefore$)

A logical symbol used to represent a conclusion, serving as a replacement for the word "therefore".