Discreet Math - Chapter 3.1 - " Predicates and Quantified Statements I". FLASHCARDS

Vocabulary flashcards covering core concepts of predicates, quantifiers, universal and existential statements, truth sets, bound variables, and implicit quantification.

Predicate

A sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables.

Domain of a Predicate Variable

The set of all values that may be substituted in place of a predicate variable.

Truth Set

Given a predicate $P(x)$ with domain $D$, the set of all elements of $D$ that make $P(x)$ true when substituted for $x$, denoted as $\{x \in D \mid P(x)\}$.

Quantifier

A word or symbol that refers to quantities such as 'some' or 'all' and tells for how many elements a given predicate is true.

Universal Quantifier

The symbol $\forall$, read as 'for every', 'for each', 'for any', 'given any', or 'for all'.

Universal Statement

A statement of the form "$\forall x \in D, Q(x)$", defined to be true if and only if $Q(x)$ is true for each individual $x$ in $D$, and false if $Q(x)$ is false for at least one $x$ in $D$.

Counterexample

A specific value for $x$ in domain $D$ for which $Q(x)$ is false, proving that the universal statement "$\forall x \in D, Q(x)$" is false.

Method of Exhaustion

A technique used to show the truth of a universal statement by verifying the truth of the predicate separately for each individual element in a finite domain.

Existential Quantifier

The symbol $\exists$, denoting 'there exists', 'there is a', 'we can find a', 'there is at least one', 'for some', or 'for at least one'.

Existential Statement

A statement of the form "$\exists x \in D \text{ such that } Q(x)$", defined to be true if and only if $Q(x)$ is true for at least one $x$ in $D$, and false if $Q(x)$ is false for all $x$ in $D$.

Universal Conditional Statement

A statement of the form "$\forall x\text{, if } P(x) \text{ then } Q(x)$".

Bound Variable

A variable in a statement that is controlled by a quantifier, whose scope begins when the quantifier introduces it and ends at the end of the quantified statement.

Scope of a Bound Variable

The portion of a quantified statement that begins when the quantifier introduces the variable and ends at the conclusion of the statement.

Implicit Universal Quantification

A universal quantification expressed without explicit quantifier words such as 'all' or 'every', often indicated by an indefinite article like 'a' or 'an'.

Implicit Existential Quantification

An existential quantification expressed without explicit quantifier symbols, where the existential meaning is supplied by context.

$\implies$ Notation

The notation $P(x) \implies Q(x)$ indicating that every element in the truth set of $P(x)$ is in the truth set of $Q(x)$, or equivalently $\forall x, P(x) \rightarrow Q(x)$.

$\iff$ Notation

The notation $P(x) \iff Q(x)$ indicating that $P(x)$ and $Q(x)$ have identical truth sets, or equivalently $\forall x, P(x) \leftrightarrow Q(x)$.

Tarski's World Grid

A computer-based visual grid arrangement of geometric blocks of various shapes, sizes, and colors used to demonstrate and evaluate the truth of quantified logical statements.