Unit II: Logic and Sets

To communicate mathematical ideas with absolute precision, we rely on structured statements called propositions.

Definition: Proposition

A proposition is a declarative sentence that is objectively either true ($T$/$1$) or false ($F$/$0$), but cannot simultaneously be both. Sentences that are interrogative, exclamatory, imperative, or highly subjective do not qualify as propositions.

• Valid Proposition: "The number $\sqrt{2}$ is irrational." (This is a declarative statement with an objective truth value of True).
• Invalid Statement: "Matrix algebra is a beautiful subject." (This is a subjective claim that cannot be evaluated objectively).

Negation ($\neg p$)

The negation of a proposition $p$ is a statement that reverses the original truth value of $p$. It is written symbolically as $\neg p$ or $\sim p$. If $p$ is true, then $\neg p$ is false, and vice versa.

Simple propositions contain a single subject and a single predicate. We can combine multiple simple statements using logical connectives to build compound propositions.

1. Conjunction ($p \wedge q$)

A conjunction represents an logical "and" statement. The compound proposition $p \wedge q$ is true if and only if both component propositions $p$ and $q$ are true. If either statement is false, the entire conjunction is false.

2. Disjunction ($p \vee q$)

A disjunction represents an inclusive logical "or" statement. The compound proposition $p \vee q$ is false if and only if both component propositions $p$ and $q$ are false. If at least one statement is true, the disjunction evaluates as true.

3. Conditional Implication ($p \longrightarrow q$)

A conditional statement takes the form "If $p, \text{ then } q$". The component statement $p$ is called the premise (or antecedent), and $q$ is the conclusion (or consequent).

The conditional expression $p \longrightarrow q$ is false only when a true premise leads to a false conclusion. If the premise $p$ is false, the conditional statement evaluates as true by default, regardless of the truth value of $q$.

4. Biconditional ($p \longleftrightarrow q$)

A biconditional statement is read as "$p \text{ if and only if } q$". The expression $p \longleftrightarrow q$ is true when both component statements share identical truth values (meaning both are true, or both are false).

From a primary conditional statement $p \longrightarrow q$, we can construct three related conditional structures:

• Converse: $q \longrightarrow p$
• Inverse: $(\neg p) \longrightarrow (\neg q)$
• Contrapositive: $(\neg q) \longrightarrow (\neg p)$

Note on Equivalence: A conditional statement $p \longrightarrow q$ is always logically equivalent to its contrapositive $(\neg q) \longrightarrow (\neg p)$. Its converse and inverse are also logically equivalent to each other.

The tables below define the outputs for basic logical connectives across all possible input combinations ($1 = \text{True}, 0 = \text{False}$):

• Tautology: A compound proposition that evaluates as true across every single row of a truth table, regardless of the individual truth values of its components.
• Contradiction: A compound proposition that evaluates as false across every single row of a truth table.
• Contingency: A compound statement that yields a mix of true and false outputs depending on its input parameters.
• Logical Equivalence ($p \iff q$): Two propositions are logically equivalent if they share identical truth values across all analytical conditions. This occurs if and only if the statement $p \longleftrightarrow q$ forms a tautology.

A set is a well-defined gathering of distinct entities termed elements. The phrase "well-defined" means that an objective standard exists to determine whether any given entity belongs to the set.

Notations for Defining Sets

• Roster (Listing) Method: Enumerates every element explicitly between braces, separated by commas (e.g., $A = \{a, e, i, o, u\}$).
• Set-Builder Notation: Uses a variable and a conditional rule to describe a set's parameters (e.g., $\{x \mid x \text{ is an integer and } x > 5\}$).
• Descriptive Method: Uses a clear sentence to state the membership rules of the set.

Special Sets and Attributes

• Empty Set ($\emptyset$ or $\{\}$): A set containing no elements.
• Universal Set ($U$): The comprehensive set containing all possible entities under consideration for a specific analysis.
• Cardinality ($n(A)$): The total number of distinct elements present within a finite set $A$.
• Subset ($A \subseteq B$): Set $A$ is a subset of $B$ if every element contained in $A$ is also found in $B$.

Let $A$ and $B$ be sets existing within a universal space $U$.

Union ($A \cup B$)

Combines all elements from both sets:

$A \cup B = \{x \mid x \in A \text{ or } x \in B\}$

Intersection ($A \cap B$)

Isolates the shared elements common to both sets:

$A \cap B = \{x \mid x \in A \text{ and } x \in B\}$

Relative Complement / Set Difference ($A \setminus B$)

Isolates elements that belong to set $A$ but do not exist in set $B$:

$A \setminus B = \{x \mid x \in A \text{ and } x \notin B\}$

Absolute Complement ($A'$)

Isolates all elements in the universal set $U$ that do not belong to set $A$:

$A' = U \setminus A = \{x \mid x \in U \text{ and } x \notin A\}$