Comprehensive Study Guide for Discrete Structure 1

Introduction to Discrete Structures

• Foundations: Both mathematics and computer science are based on logic as a tool to establish truth through various techniques of proof. Discrete Structure 1 (COMP 20043) introduces mathematical concepts essential for high-level computer science courses.
• Course Topics:     - Propositional and predicate logic.     - Proof techniques.     - Set theory.     - Functions and relations.     - Number theory.     - Elementary combinatorics and counting methods.     - Graph theory.

Chapter 1: Propositional Logic

• The Rule of Logic: Logic provides precise meaning to mathematical statements and distinguishes valid from invalid arguments. It is used in computer circuit design, program construction, and verification.
• Definition of Proposition: A proposition is a declarative sentence (declares a fact) that is either true ($T$) or false ($F$), but not both.     - Example 1: "Marikina is the Capital of the Philippines" (False); "$1 + 2 = 3$" (True).     - Non-Propositions: Questions ("What time is it?"), commands ("Read this carefully"), or sentences with variables ("$x + 1 = 2$") unless values are assigned to the variables.
• Propositional Variables: Conventional letters used are $p, q, r, s, \dots$.
• History: Developed by Aristotle 2300 years ago. The three laws of Aristotelian logic are:     - Law of Identity: "A statement is itself."     - Law of Excluded Middle: "A statement is either true or false but not both."     - Law of Non-Contradiction: "No statement is both true and false."
• Logical Operators:     - Negation ($\neg p$): The statement "It is not the case that $p$." The truth value is the opposite of $p$.         - Example: If $p$ is "Michael’s PC runs Linux," $\neg p$ is "Michael’s PC does not run Linux."     - Conjunction ($p \wedge q$): The statement "$p$ and $q$." It is true only when both $p$ and $q$ are true; false otherwise.     - Disjunction ($p \vee q$): The statement "$p$ or $q$." This is an inclusive or. It is false only when both $p$ and $q$ are false; true otherwise.     - Exclusive Or ($p \oplus q$): The statement "$p \text{ or } q \text{ but not both}$." It is true when exactly one of $p$ and $q$ is true; false otherwise.     - Conditional Statement / Implication ($p \rightarrow q$): The statement "if $p$, then $q$." Here, $p$ is the hypothesis (antecedent/premise) and $q$ is the conclusion (consequence). It is false only when $p$ is true and $q$ is false.         - Terminology for $p \rightarrow q$: "$p$ is sufficient for $q$," "$q$ is necessary for $p$," "$p$, only if $q$," "$q$ unless $\neg p$."     - Biconditional Statement ($p \leftrightarrow q$): The statement "$p$ if and only if $q$." True when $p$ and $q$ have the same truth values.         - Note: $p \leftrightarrow q$ has the same truth value as $(p \rightarrow q) \wedge (q \rightarrow p)$.
• Precedence of Logical Operators:     1. Negation ($\neg$)     2. Conjunction ($\wedge$)     3. Disjunction ($\vee$)     4. Conditional ($\rightarrow$)     5. Biconditional ($\leftrightarrow$)

Logic and Bit Operations

• Bit: A symbol with two possible values: $0$ (False) and $1$ (True). The term "bit" was introduced by John Tukey in 1946.
• Boolean Variable: A variable whose value is either true or false.
• Bit Operations: Correspond to logical operators. OR ($\vee$), AND ($\wedge$), and XOR ($\oplus$).
• Bit String: A sequence of zero or more bits. The length is the number of bits in the string.     - Bitwise OR, AND, XOR: Applied to strings of the same length by operating on corresponding bits.     - Example: Bitwise XOR of $01\,1011\,0110$ and $11\,0001\,1101$ is $10\,1010\,1011$.

Propositional Equivalences

• Classification of Compound Propositions:     - Tautology: Always true (e.g., $p \vee \neg p$).     - Contradiction: Always false (e.g., $p \wedge \neg p$).     - Contingency: Neither a tautology nor a contradiction.
• Logical Equivalence ($\equiv$ or $\Leftrightarrow$): Propositions $p$ and $q$ are equivalent if $p \leftrightarrow q$ is a tautology.
• De Morgan’s Laws:     - $\neg(p \wedge q) \equiv \neg p \vee \neg q$     - $\neg(p \vee q) \equiv \neg p \wedge \neg q$
• Other Key Equivalences:     - Double Negation Law: $\neg(\neg p) \equiv p$     - Commutative Laws: $p \vee q \equiv q \vee p$; $p \wedge q \equiv q \wedge p$     - Distributive Laws: $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$; $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$     - Implication Equivalence: $p \rightarrow q \equiv \neg p \vee q$ (Used in converting negated implications: $\neg(p \rightarrow q) \equiv p \wedge \neg q$).

Predicate Logic and Quantifiers

• Predicate Logic: Extends propositional logic to reason about properties of objects and relationships.
• Predicates: Statements like "$x > 3$". Here, $x$ is the subject and "is greater than $3$" is the predicate ($P(x)$). Once a value is assigned to $x$, $P(x)$ becomes a proposition.     - n-ary Predicates: Involve multiple variables, e.g., $R(x, y, z)$ for "$x + y = z$".
• Programming Application: Predicates serve as preconditions (valid input descriptions) and postconditions (conditions for output correctness).
• Quantification:     - Universal Quantifier ($\forall$): The statement "$P(x)$ for all values of $x$ in the domain." $\forall xP(x)$ is false if there is at least one counterexample.     - Existential Quantifier ($\exists$): The statement "There exists an element $x$ in the domain such that $P(x)$ is true." $\exists xP(x)$ is false only if $P(x)$ is false for every element in the domain.     - Uniqueness Quantifier ($\exists!$ or $\exists_{1}$): "There exists a unique $x$ such that $P(x)$."
• Binding Variables:     - Bound Variable: A variable to which a quantifier is applied.     - Free Variable: An occurrence of a variable not bound by a quantifier.     - Scope: The part of the logical expression to which the quantifier applies.

Sets and Set Operations

• Set: An unordered collection of objects called elements ($a \in A$).
• Representation:     - Roster Method: Listing elements within braces, e.g., $\{a, e, i, o, u\}$.     - Set-Builder Notation: Defining by properties, e.g., $\{x \in \mathbb{Z}^{+} \mid x \text{ is odd and } x < 10\}$.
• Common Sets:     - $\mathbb{N} = \{0, 1, 2, \dots\}$ (Natural numbers)     - $\mathbb{Z} = \{\dots, -1, 0, 1, \dots\}$ (Integers)     - $\mathbb{Q} = \{p/q \mid p, q \in \mathbb{Z}, q \neq 0\}$ (Rational numbers)     - $\mathbb{R}$ (Real numbers), $\mathbb{C}$ (Complex numbers)
• Empty Set ($\emptyset$ or $\{\}$): A set containing no elements.
• Subsets ($A \subseteq B$): Every element of $A$ is also in $B$.
• Cardinality ($|S|$): The number of distinct elements in a finite set.
• Power Set ($\mathcal{P}(S)$): The set of all subsets of set $S$. If $|S| = n$, then $|\mathcal{P}(S)| = 2^{n}$.
• Set Operations:     - Union ($A \cup B$): Elements in either $A$ or $B$ or both.     - Intersection ($A \cap B$): Elements in both $A$ and $B$. If $A \cap B = \emptyset$, the sets are disjoint.     - Difference ($A - B$ or $A \setminus B$): Elements in $A$ but not in $B$. Note: $A - B = A \cap \overline{B}$.     - Complement ($\overline{A}$): Elements in the universal set $U$ that are not in $A$.

Functions

• Definition: A function $f : A \rightarrow B$ assigns exactly one element of $B$ to each element of $A$.     - Domain: Set $A$.     - Codomain: Set $B$.     - Range: The set of all images $f(a)$.
• Types of Functions:     - One-to-One / Injective: $f(a) = f(b)$ implies $a = b$.     - Onto / Surjective: For every $b \in B$, there exists $a \in A$ such that $f(a) = b$.     - One-to-One Correspondence / Bijective: Both injective and surjective.
• Inverse Function ($f^{-1}$): Only possible if $f$ is bijective.
• Composition ($f \circ g$): $(f \circ g)(a) = f(g(a))$. The range of $g$ must be a subset of the domain of $f$.
• Partial Function: Assignment for a subset of the domain. If it covers the whole domain, it is a total function.

Cardinality of Sets (Extended)

• Countable Sets: Sets that are finite or have the same cardinality as positive integers ($\aleph_{0}$ or aleph null).     - Example: The set of all integers is countable.
• Uncountable Sets: Sets that cannot be listed, such as the set of real numbers $\mathbb{R}$. This is proven using Cantor's diagonalization argument.

Relations

• Properties of Relations (on set $A$):     - Reflexive: $(a, a) \in R$ for all $a \in A$.     - Symmetric: If $(a, b) \in R$, then $(b, a) \in R$.     - Antisymmetric: If $(a, b) \in R$ and $(b, a) \in R$, then $a = b$.     - Transitive: If $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.
• Equivalence Relation: Reflexive, symmetric, and transitive.
• Partial Ordering / Poset ($S, R$): Reflexive, antisymmetric, and transitive.     - Comparable: If $a \preceq b$ or $b \preceq a$.     - Total Order: Every pair of elements is comparable (also called a chain).     - Well-Ordered Set: A total order where every non-empty subset has a least element.

Sequences and Summations

• Sequence: A function from a subset of integers to a set $S$.     - Geometric Progression: $a, ar, ar^{2}, \dots, ar^{n}, \dots$ (common ratio $r$).     - Arithmetic Progression: $a, a+d, a+2d, \dots, a+nd, \dots$ (common difference $d$).
• Recurrence Relations: Expressing $a_{n}$ in terms of previous terms (e.g., Fibonacci sequence: $f_{n} = f_{n-1} + f_{n-2}$ with $f_{0}=0, f_{1}=1$).
• Summations: $\sum_{j=m}^{n} a_{j} = a_{m} + a_{m+1} + \dots + a_{n}$.

Number Theory

• Divisibility: $a \mid b$ if there is an integer $c$ such that $b = ac$ ($a$ is a factor, $b$ is a multiple).
• Division Algorithm: For integer $a$ and positive integer $d$, there exist unique $q$ and $r$ such that $a = dq + r$ with $0 \leq r < d$.     - $q = a \text{ div } d$; $r = a \text{ mod } d$.
• Modular Arithmetic: $a \equiv b \pmod{m}$ if $m \mid (a - b)$.
• Base Expansions: Integers can be represented in base $b > 1$. Common bases: Binary (base 2), Octal (base 8), Hexadecimal (base 16).
• Primes: Integer $p > 1$ whose only positive factors are $1$ and $p$.     - Fundamental Theorem of Arithmetic: Every integer $>1$ is uniquely expressed as a product of primes.     - Trial Division: Compound $n$ has a prime divisor $\leq \sqrt{n}$.
• GCD and LCM:     - Greatest Common Divisor (GCD): Largest shared divisor.     - Euclidean Algorithm: Method for finding GCD using successive applications of the division algorithm.     - Bézout’s Theorem: $gcd(a, b) = sa + tb$ for some integers $s, t$.
• Chinese Remainder Theorem: Solves systems of congruences with pairwise relatively prime moduli.
• Fermat’s Little Theorem: If $p$ is prime and $a \nmid p$, then $a^{p-1} \equiv 1 \pmod{p}$.

Cryptography

• Caesar Cipher: Shifts letters by 3 positions ($f(p) = (p + 3) \pmod{26}$).
• Cryptosystem: A five-tuple $(P, C, K, E, D)$ where $P$=plaintext, $C$=ciphertext, $K$=keys, $E$=encryption, $D$=decryption.
• RSA Cryptosystem: Public key system using large primes $p$ and $q$. Modulus $n = pq$.     - Encryption: $C = M^{e} \pmod{n}$.     - Decryption: $M = C^{d} \pmod{n}$, where $d$ is the inverse of electric exponent $e \pmod{(p-1)(q-1)}$.

Counting

• Product Rule: If tasks have $n_{1}$ and $n_{2}$ ways respectively, total ways = $n_{1} \times n_{2}$.
• Sum Rule: If tasks are disjoint, total ways = $n_{1} + n_{2}$.
• Subtraction Rule (Inclusion-Exclusion): $|A \cup B| = |A| + |B| - |A \cap B|$.
• Permutations ($P(n, r)$): Ordered arrangements. $P(n, r) = \frac{n!}{(n - r)!}$.
• Combinations ($C(n, r)$): Unordered selections. $C(n, r) = \frac{n!}{r!(n - r)!}$.

Graph Theory

• Basic Definitions:     - Graph $G=(V, E)$ where $V$=vertices, $E$=edges.     - Adjacent: Vertices connected by an edge.     - Degree ($deg(v)$): Number of edges incident with a vertex. Loops count twice.
• Handshaking Theorem: $2m = \sum_{v \in V} deg(v)$, where $m$ is the number of edges.
• Directed Graphs:     - In-degree ($deg^{-}(v)$): Edges ending at $v$.     - Out-degree ($deg^{+}(v)$): Edges starting at $v$.
• Representations:     - Adjacency Matrix: $n \times n$ matrix where $a_{ij}=1$ if vertices are adjacent.     - Incidence Matrix: $n \times m$ matrix showing relationships between vertices and edges.