Set Theory and Mathematical Logic

🧩 Set Theory and Mathematical Logic

This module covers the fundamental building blocks of discrete mathematics: Set Theory and Propositional Logic. These concepts are the bedrock of relational databases, programming logic, and formal verification.

🟢 Part 1: Set Theory Foundations

A set is a well-defined collection of distinct objects, called elements. In computer science, sets are the formal foundation for data structures like HashSet and relational models (SQL).

1. Basic Notation and Membership

$a \in A$ : Element $a$ belongs to set $A$ .
$a \notin A$ : Element $a$ does not belong to set $A$ .
$\emptyset$ or $\{\}$ : The empty set (contains no elements).
$A \subseteq B$ : $A$ is a subset of $B$ (every element of $A$ is also in $B$ ).

2. Set Builder Notation

Used to define a set based on a property $P(x)$ : $S = \{ x \mid P(x) \}$ Example: $\{x \mid x \in \mathbb{Z}, x > 0\}$ represents the set of all positive integers.

3. Fundamental Set Operations

These operations have direct mappings to SQL and data processing:

Union ( $A \cup B$ ): $\{x \mid x \in A \lor x \in B\}$ . Corresponds to UNION in SQL.
Intersection ( $A \cap B$ ): $\{x \mid x \in A \land x \in B\}$ . Corresponds to INTERSECT in SQL.
Difference ( $A \setminus B$ ): $\{x \mid x \in A \land x \notin B\}$ . Corresponds to EXCEPT or MINUS in SQL.
Complement ( $A^c$ ): $\{x \mid x \notin A, x \in U\}$ where $U$ is the universal set.

4. Advanced Set Concepts

Cartesian Product ( $A \times B$ ): The set of all possible ordered pairs $(a, b)$ where $a \in A$ and $b \in B$ . This defines a Cross Join in databases.
Power Set ( $\mathcal{P}(A)$ ): The set of all subsets of $A$ . If $|A| = n$ , then $|\mathcal{P}(A)| = 2^n$ .
Partitions: A collection of non-empty disjoint subsets that cover the entire set. This is the basis for Database Sharding.

🟡 Part 2: Propositional Logic

Logic is the study of truth values and how they are combined. In programming, this is the foundation of if-else statements and boolean expressions.

1. Propositions and Connectives

A proposition is a statement that is either True (T) or False (F).

Conjunction ( $\land$ ): AND operation.
Disjunction ( $\lor$ ): OR operation.
Negation ( $\neg$ ): NOT operation.
Exclusive Or ( $\oplus$ ): XOR operation (true if exactly one is true).

2. Truth Tables

$p$	$q$	$p \land q$	$p \lor q$	$p \oplus q$	$p \implies q$
T	T	T	T	F	T
T	F	F	T	T	F
F	T	F	T	T	T
F	F	F	F	F	T

3. Implications and Equivalences

Implication ( $p \implies q$ ): “If $p$ , then $q$ .” Only false if $p$ is true and $q$ is false.
Contrapositive ( $\neg q \implies \neg p$ ): Logically equivalent to $p \implies q$ .
Converse ( $q \implies p$ ): NOT necessarily equivalent to the original implication.

4. De Morgan’s Laws

Crucial for simplifying complex boolean logic in code and SQL queries:

$\neg(p \land q) \equiv \neg p \lor \neg q$
$\neg(p \lor q) \equiv \neg p \land \neg q$

🔴 Part 3: Predicate Logic and Quantifiers

Predicate logic extends propositional logic by allowing variables and quantifiers.

1. Predicates

A predicate $P(x)$ is a property that a variable $x$ can have. It becomes a proposition once $x$ is assigned a value. Example: $P(x): x > 5$ . $P(10)$ is True, $P(2)$ is False.

2. Quantifiers

Universal Quantifier ( $\forall x$ ): “For all $x$ ”. The statement must be true for every element in the domain.
Existential Quantifier ( $\exists x$ ): “There exists an $x$ ”. There must be at least one element in the domain for which the statement is true.

3. Tautologies and Contradictions

Tautology: A statement that is always true (e.g., $p \lor \neg p$ ).
Contradiction: A statement that is always false (e.g., $p \land \neg p$ ).

💻 Programming Example: Set Operations in Python

# Defining sets
set_a = {1, 2, 3, 4, 5}
set_b = {4, 5, 6, 7, 8}

# Union
print(f"Union: {set_a | set_b}") # {1, 2, 3, 4, 5, 6, 7, 8}

# Intersection
print(f"Intersection: {set_a & set_b}") # {4, 5}

# Difference
print(f"Difference (A-B): {set_a - set_b}") # {1, 2, 3}

# Symmetric Difference (XOR)
print(f"Symmetric Difference: {set_a ^ set_b}") # {1, 2, 3, 6, 7, 8}

Understanding these logical and set-based foundations allows you to write cleaner code and design more efficient data models.