Discrete Mathematics: Propositional Logic, Quantifiers, and Set Theory

Comprehensive vocabulary flashcards covering Propositional Logic, Quantifiers, and Set Theory from Math 231 lecture notes.

Proposition

A sentence that is true or false, but not both.

Compound Proposition

A proposition formed by manipulating or combining propositions using logical operations.

Negation

A logical operation that creates a proposition that is true when $p$ is false and false when $p$ is true, denoted $\neg p$.

Disjunction Truth Table

The truth table for the disjunction of propositions $p$ and $q$ ($p \lor q$), which produces a compound proposition that is false when both $p$ and $q$ are false and true otherwise.

Conjunction

A compound proposition that is true when both propositions $p$ and $q$ are true and false otherwise, denoted $p \land q$.

Conditional Statement (Implication) Truth Table

The truth table representing $p \to q$, which is defined to be false if hypothesis $p$ is true while conclusion $q$ is false, and true otherwise.

Vacuously True

The status of a conditional proposition $p \to q$ being true specifically because its hypothesis $p$ is false, regardless of the truth value of the conclusion.

Converse

The conditional proposition $q \to p$ formed relative to the conditional statement $p \to q$.

Inverse

The conditional proposition $\neg p \to \neg q$ formed relative to the conditional statement $p \to q$.

Contrapositive

The conditional proposition $\neg q \to \neg p$ formed relative to the conditional statement $p \to q$.

Necessary Condition

A condition that must be satisfied given that proposition $p$ is true; represented by the conclusion of a true conditional statement.

Sufficient Condition

A condition that suffices to guarantee that proposition $q$ is true; represented by the hypothesis of a true conditional statement.

Biconditional Proposition

The compound proposition $p \leftrightarrow q$, standing for "p if and only if q" and defined by $(p \to q) \land (q \to p)$.

Logical Equivalence

The relationship between two compound propositions $P$ and $Q$ that share identical truth values across all possible combinations of truth values of their component propositions, denoted $P \equiv Q$.

Tautology

A compound proposition that is always true regardless of the truth values of the propositions it comprises.

Contradiction

A compound proposition that is always false regardless of the truth values of the propositions it comprises.

Propositional Function

A sentence containing a finite number of variables that becomes a proposition when specific values are substituted for those variables.

Domain of a Variable

The set of all values that may be substituted for a variable within a propositional function.

Universally Quantified Statement

A statement of the form "for all $x \in D$, $P(x)$" (denoted $\forall x \in D, P(x)$), which is true if and only if $P(x)$ is true for every element $x$ in domain $D$.

Counterexample

A specific choice of an element $x$ from domain $D$ for which $P(x)$ is false, proving that the universally quantified statement $\forall x, P(x)$ is false.

Existentially Quantified Statement

A statement of the form "there exists $x \in D$ such that $P(x)$" (denoted $\exists x \in D, P(x)$), which is true if and only if $P(x)$ is true for at least one element $x$ in domain $D$.

Set

A collection of objects where order and repetition are not taken into account, introduced into formal mathematics by Georg Cantor in $1879$.

Empty Set (Null Set)

The unique set containing no objects, denoted $\emptyset$ or by the set-bracket notation $\{\}$.

Cardinality

The number of elements contained in a finite set $S$, denoted $|S|$.

Subset

A relationship between sets $S$ and $T$, written $S \subseteq T$, where all elements of $S$ also belong to $T$.

Proper Subset

A subset $S$ of set $T$ such that $S \neq T$, denoted $S \subset T$.

Universe

A background set $U$ in which all sets currently under consideration are subsets.

Power Set

The set of all subsets of a set $X$, ranging from $\emptyset$ to $X$, denoted $\mathcal{P}(X)$, with cardinality $2^{|X|}$ for finite $X$.

Venn Diagram

A visualization tool for sets where sets are drawn as circles, often contained inside a rectangle depicting the universe $U$.

Union

The set of all elements that belong to set $S$ or set $T$ (possibly both), denoted $S \cup T$.

Intersection

The set of all elements that belong to both set $S$ and set $T$, denoted $S \cap T$.

Disjoint Sets

Two sets $S$ and $T$ that share no elements, satisfying $S \cap T = \emptyset$.

Relative Difference

The set of all elements in $S$ that are not in $T$, denoted $S \setminus T$ or $S - T$.

Complement

The set consisting of all elements in the universe $U$ that are not in set $T$, denoted $\overline{T}$, $T^c$, or $T'$.

Direct Product (Cartesian Product)

The set denoted $S \times T$ whose elements are ordered pairs $(s, t)$ such that $s \in S$ and $t \in T$.

Inclusion-Exclusion Principle

The basic counting rule stating that for finite sets $S$ and $T$, $|S \cup T| = |S| + |T| - |S \cap T|$.

Function

A subset $f$ of $X \times Y$ having the property that for every $x \in X$ there exists a unique $y \in Y$ such that $(x, y) \in f$.

Codomain

The target set $Y$ designated in a function specification $f: X \to Y$.

Range

The subset of the codomain $Y$ consisting of all actual output values of $f$, defined as $f(X) = \{y \in Y \mid \exists x \in X \text{ such that } y = f(x)\}$.

One-to-One Function (Injective)

A function $f: X \to Y$ such that for each $y \in Y$ there exists at most one $x \in X$ satisfying $y = f(x)$.

Onto Function (Surjective)

A function $f: X \to Y$ such that for each $y \in Y$ there exists at least one $x \in X$ satisfying $y = f(x)$.

Bijection

A function that is simultaneously one-to-one and onto.

Inverse Function

The bijection from $Y$ to $X$ denoted $f^{-1} = \{(y, x) \mid (x, y) \in f\}$, defined when $f: X \to Y$ is a bijection.

Composition of Functions

The function from $X$ to $Z$ denoted $f \circ g$ defined by the rule $(f \circ g)(x) = f(g(x))$ for functions $g: X \to Y$ and $f: Y \to Z$.

Pairwise Disjoint Family

A family of sets $\mathcal{S} = \{S_i \mid i \in I\}$ such that for all $i, j \in I$, either $S_i = S_j$ or $S_i \cap S_j = \emptyset$.

Partition

A family $\mathcal{C} = \{P_i \mid i \in I\}$ of nonempty, pairwise disjoint sets indexed by $I$ such that $\bigcup_{i \in I} P_i = S$.

Russell's Set Theory Paradox

The contradiction arising from defining the set $R = \{S \in U \mid S \notin S\}$, which would have to contain itself if and only if it does not contain itself, proving $R$ is ill-defined.