Discrete Mathematics 01: Logic, Proofs, and Set Theory

Vocabulary flashcards covering foundational concepts in propositional logic, predicate logic, deduction, mathematical induction, and set theory based on the lecture series.

Proposition

Informally, a declarative sentence (a statement) in a language that is subject to be true or false.

Negation

The operation on a proposition $P$, denoted by $\neg P$, representing 'not $P$', 'It is not the case that $P$', or '$P$ is not true', which takes the opposite truth value of $P$.

Conjunction

The statement '$P$ and $Q$', denoted by $P \wedge Q$, which is true if both $P$ and $Q$ are true, and false otherwise.

Disjunction

The statement '$P$ or $Q$' (maybe both), denoted by $P \vee Q$, which is false if both $P$ and $Q$ are false, and true otherwise.

Exclusive Or

The statement '$P$ or $Q$ but not both', denoted by $P \oplus Q$, which is true if exactly one of $P$ and $Q$ is true, and false otherwise.

Conditional Statement

An implication denoted by $P \rightarrow Q$ ('if $P$ then $Q$' or '$P$ implies $Q$'), which is false when $P$ is true and $Q$ is false, and true otherwise.

Converse

For a conditional statement $P \rightarrow Q$, the conditional statement $Q \rightarrow P$.

Contrapositive

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

Inverse

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

Biconditional Statement

The statement '$P$ if and only if $Q$' (or '$P$ is necessary and sufficient for $Q$'), denoted by $P \leftrightarrow Q$, which is true when both $P$ and $Q$ are true or both are false.

Tautology

A compound proposition that is always true no matter the truth values of its propositional variables.

Contradiction

A compound proposition that is always false no matter the truth values of its propositional variables.

Logical Equivalence (Propositional)

The relationship between two propositions $P$ and $Q$ when they have the same truth value in all possible cases, denoted by $P \equiv Q$ (meaning $P \leftrightarrow Q$ is a tautology).

De Morgan Laws

Pair of logical equivalences stating that $\neg (P \wedge Q) \equiv \neg P \vee \neg Q$ and $\neg (P \vee Q) \equiv \neg P \wedge \neg Q$.

Boolean Variable

A variable that can take two values: True or False, which is represented in computing by a bit taking states $1$ or $0$.

Term (Predicate Logic)

An expression that represents 'an object' or 'a thing'.

Predicate

A symbol that represents a property or relation.

Domain of Discourse

Informally, 'the set of all the objects in our theory' or 'the universe of possible objects that we might consider to be subject to predicates', usually denoted by $U$.

Universal Quantifier

The symbol $\forall$, where $\forall x P(x)$ means the predicate $P$ is true for all elements $x$ within the domain of discourse.

Existential Quantifier

The symbol $\exists$, where $\exists x P(x)$ means there exists at least one element $x$ in the domain of discourse for which the predicate $P(x)$ is true.

Negation of Quantifiers

Logical rules stating that for a predicate $P$, $\neg \forall x P(x) \equiv \exists x \neg P(x)$ and $\neg \exists x P(x) \equiv \forall x \neg P(x)$.

Rule of Inference

A tautology of the form $(A_1 \wedge \dots \wedge A_n) \rightarrow Q$ in propositional logic that allows valid argumentation to deduce true $Q$ from true premises $A_1, \dots, A_n$.

Principle of Mathematical Induction

A theorem stating that if $P$ is a predicate for natural numbers where basis step $P(0)$ holds and inductive step $P(k) \rightarrow P(k+1)$ holds, then $P(n)$ is true for every $n \in \mathbb{N}$.

Basis Step

The foundational step in an inductive proof that establishes the truth of the predicate for the initial natural number, $P(0)$.

Strong Induction

A theorem stating that if basis step $P(0)$ holds and inductive step $(P(0), P(1), \dots, P(k)) \rightarrow P(k+1)$ holds, then predicate $P(n)$ is true for every $n \in \mathbb{N}$.

Set

Intuitively, an unordered collection of objects (called elements or members) defined solely by the elements belonging to it, with no repeated elements.

Empty Set

The unique set containing no elements, denoted by $\emptyset$.

Equal Sets

Two sets $A$ and $B$ that have the same elements, written as $A = B$, which holds if $\forall x(x \in A \leftrightarrow x \in B)$.

Subset

A set $A$ in relation to a set $B$ where every element of $A$ is an element of $B$, denoted by $A \subseteq B$.

Cartesian Product

The set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$, denoted by $A \times B = \{(a, b) \mid a \in A \wedge b \in B\}$.

Truth table output for $P \wedge \neg Q$ given order $(T, T)$, $(T, F)$, $(F, T)$, $(F, F)$

1. $$(T, T) \rightarrow F$$

2. $$(T, F) \rightarrow T$$

3. $$(F, T) \rightarrow F$$

4. $$(F, F) \rightarrow F$$

Truth table output for $(P \vee Q) \rightarrow P$ given order $(T, T)$, $(T, F)$, $(F, T)$, $(F, F)$

1. $$(T, T) \rightarrow T$$

2. $$(T, F) \rightarrow T$$

3. $$(F, T) \rightarrow F$$

4. $$(F, F) \rightarrow T$$

Truth value of $(P \oplus Q) \leftrightarrow (P \wedge Q)$ when $P = T$ and $Q = F$

False. $P \oplus Q$ evaluates to True and $P \wedge Q$ evaluates to False, making $T \leftrightarrow F$ False.

Truth table values for $(P \rightarrow Q) \wedge (Q \rightarrow P)$ given order $(T, T)$, $(T, F)$, $(F, T)$, $(F, F)$

1. $$(T, T) \rightarrow T$$

2. $$(T, F) \rightarrow F$$

3. $$(F, T) \rightarrow F$$

4. $(F, F) \rightarrow T$ (Note: This expression is logically equivalent to $P \leftrightarrow Q$).

Classification of $(P \wedge (P \rightarrow Q)) \rightarrow Q$ as a tautology, contradiction, or contingency

Tautology (Modus Ponens). It evaluates to True under all truth assignments of $P$ and $Q$.

Truth table evaluation of $\neg (P \vee Q) \leftrightarrow (\neg P \wedge \neg Q)$ across all possible truth assignments

True for all rows (T, T, T, T), proving that this De Morgan Law is a tautology.

Classification of $P \wedge \neg (P \vee Q)$ as a tautology, contradiction, or contingency

Contradiction. Since $P \wedge \neg (P \vee Q) \equiv P \wedge \neg P \wedge \neg Q \equiv F \wedge \neg Q$, it evaluates to False for all assignments.

Truth value of $(P \wedge Q) \rightarrow R$ when $P = T$, $Q = T$, and $R = F$

False. The premise $P \wedge Q$ is True and the conclusion $R$ is False, making $T \rightarrow F$ False.

Truth table values for $(P \rightarrow Q) \vee (Q \rightarrow R)$ for the 8 standard rows from $(T, T, T)$ to $(F, F, F)$

1. $$(T, T, T) \rightarrow T$$

2. $$(T, T, F) \rightarrow F$$

3. $$(T, F, T) \rightarrow T$$

4. $$(T, F, F) \rightarrow T$$

5. $$(F, T, T) \rightarrow T$$

6. $$(F, T, F) \rightarrow T$$

7. $$(F, F, T) \rightarrow T$$

8. $$(F, F, F) \rightarrow T$$

Step-by-step logical equivalence proof showing $P \rightarrow (Q \rightarrow R) \equiv (P \wedge Q) \rightarrow R$

1. $P \rightarrow (Q \rightarrow R) \equiv \neg P \vee (\neg Q \vee R)$ (Conditional Law)

2. $\equiv (\neg P \vee \neg Q) \vee R$ (Associative Law)

3. $\equiv \neg (P \wedge Q) \vee R$ (De Morgan's Law)

4. $\equiv (P \wedge Q) \rightarrow R$ (Conditional Law)

Union (Set Theory)

For sets $A$ and $B$, the set $A \cup B = \{x \mid x \in A \vee x \in B\}$ containing all elements that are in $A$, $B$, or both.

Intersection (Set Theory)

For sets $A$ and $B$, the set $A \cap B = \{x \mid x \in A \wedge x \in B\}$ containing all elements belonging to both $A$ and $B$.

Set Difference

For sets $A$ and $B$, the set $A - B = \{x \mid x \in A \wedge x \notin B\}$ containing all elements of $A$ that are not in $B$.

Disjoint Sets

Two sets $A$ and $B$ that have no elements in common, meaning their intersection is empty ($A \cap B = \emptyset$).

Power Set

For a set $A$, the set of all subsets of $A$, denoted by $\mathcal{P}(A)$ or $P(A)$.

Inductive Step

The step in an inductive proof showing that if the predicate holds for an arbitrary natural number $k$ ($P(k)$), then it must also hold for $k+1$ ($P(k+1)$).

Bit Operations

Logical operations such as NOT (unary inversion) as well as binary operations AND, OR, and XOR performed on bits taking states $1$ (True) or $0$ (False).

Modus Ponens

A rule of inference based on the tautology $((P \wedge (P \rightarrow Q)) \rightarrow Q)$, allowing one to deduce $Q$ from premises $P$ and $P \rightarrow Q$.

Modus Tollens

A rule of inference based on the tautology $$((\neg Q \wedge