MT131 - Discrete Mathematics Lecture Flashcards

Flashcards covering the foundational vocabulary and concepts of MT131 Discrete Mathematics, including logic, set theory, number theory, counting, relations, and graph theory.

Proposition

A declarative statement that is either True (T) or False (F), but not both or somewhere in between.

Negation ($\neg p$)

An operator that defines the logical opposite of a proposition; it is true when the operand is false and false when the operand is true.

Conjunction ($p \land q$)

A binary operator that is true only if both propositions $p$ and $q$ are true; also known as the AND operator.

Disjunction ($p \lor q$)

A binary operator that is true if at least one of the propositions $p$ or $q$ is true; also known as the inclusive OR.

Exclusive-OR ($p \oplus q$)

A logical operator that is true if exactly one of the propositions is true, and false if both are true or both are false.

Implication ($p \rightarrow q$)

A logical operator where $p$ is the hypothesis and $q$ is the conclusion; it is false only when $p$ is true and $q$ is false.

Biconditional ($p \leftrightarrow q$)

A logical operator translated as 'p if and only if q', which is true only when $p$ and $q$ have the same truth value.

Tautology

A compound proposition that is always true, regardless of the truth values of the individual propositions it contains.

Contradiction

A compound proposition that is always false, regardless of the truth values of the individual propositions it contains.

Universal Quantifier ($\forall$)

A quantifier indicating that a propositional function $P(x)$ is true for every value of $x$ in the universe of discourse.

Existential Quantifier ($\exists$)

A quantifier indicating that there exists at least one element $x$ in the universe of discourse such that the propositional function $P(x)$ is true.

Set

An unordered collection of distinct objects, which are called elements or members of the set.

Power Set ($P(S)$)

The set containing all possible subsets of a set $S$; if $S$ has $n$ elements, then the power set has $2^n$ elements.

Cartesian Product ($A \times B$)

The set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$.

Inclusion-Exclusion Principle

A principle stating that the number of elements in the union of two sets is the sum of the elements in each set minus the number of elements in their intersection: $|A \cup B| = |A| + |B| - |A \cap B|$.

Injection

A function $f$ that is one-to-one, meaning $f(a) = f(b)$ implies $a = b$ for all $a$ and $b$ in the domain.

Surjection

A function $f$ from $A$ to $B$ that is onto, meaning that for every element $b \in B$, there is at least one element $a \in A$ such that $f(a) = b$.

Bijection

A function that is both injective (one-to-one) and surjective (onto), also called a one-to-one correspondence.

Floor Function ($\lfloor x \rfloor$)

A function that assigns to the real number $x$ the largest integer less than or equal to $x$.

Ceiling Function ($\lceil x \rceil$)

A function that assigns to the real number $x$ the smallest integer greater than or equal to $x$.

Arithmetic Progression

A sequence of the form $a, a+d, a+2d, \dots, a+nd, \dots$ where $a$ is the initial term and $d$ is the common difference.

Geometric Progression

A sequence of the form $a, ar, ar^2, \dots, ar^n, \dots$ where $a$ is the initial term and $r$ is the common ratio.

Division Algorithm

The theorem stating that for an integer $a$ and a positive integer $d$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = d \times q + r$ with $0 \le r < d$.

Modular Congruence ($a \equiv b \pmod m$)

The condition where two integers $a$ and $b$ have the same remainder when divided by a positive integer $m$, or equivalently, $m$ divides $a - b$.

Prime Number

A positive integer $p > 1$ whose only positive factors are 1 and $p$.

Composite Number

An integer greater than 1 that is not prime, meaning it can be factored into at least two integers greater than 1.

Greatest Common Divisor ($\text{gcd}(a, b)$)

The largest positive integer that is a divisor of both $a$ and $b$.

Least Common Multiple ($\text{lcm}(a, b)$)

The smallest positive integer that is a multiple of both $a$ and $b$.

Boolean Product ($A \odot B$)

An operation on zero-one matrices defined by $c_{ij} = (a_{i1} \land b_{1j}) \lor (a_{i2} \land b_{2j}) \lor \dots \lor (a_{ik} \land b_{kj})$.

Permutation ($P(n, r)$)

An ordered arrangement of $r$ distinct elements from a set of $n$ elements, calculated as $P(n, r) = \frac{n!}{(n-r)!}$.

Combination ($C(n, r)$)

An unordered selection of $r$ distinct elements from a set of $n$ elements, calculated as $C(n, r) = \frac{n!}{r!(n-r)!}$.

Bernoulli Trial

An experiment with exactly two possible outcomes, usually called success and failure.

Binary Relation

A set of ordered pairs representing a relationship between elements of two sets, specifically a subset of the Cartesian product $A \times B$.

Reflexive Relation

A relation $R$ on a set $A$ where every element is related to itself, such that $(a, a) \in R$ for every $a \in A$.

Symmetric Relation

A relation $R$ on a set $A$ where if $(a, b) \in R$, then $(b, a) \in R$ for all $a, b \in A$.

Transitive Relation

A relation $R$ on a set $A$ where if $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$ for all $a, b, c \in A$.

Equivalence Relation

A binary relation on a set $A$ that is simultaneously reflexive, symmetric, and transitive.

Partial Ordering

A relation on a set $S$ that is reflexive, antisymmetric, and transitive.

Poset

Short for 'partially ordered set', which consists of a set $S$ together with a partial ordering relation $R$.

Hasse Diagram

A visual representation of a partial ordering on a finite set that omits reflexive loops and transitive edges, with all edges pointing 'upward'.

Simple Graph

An undirected graph where each edge connects two different vertices and at most one edge connects any pair of vertices.

Handshaking Theorem

The theorem stating that the sum of the degrees of the vertices in an undirected graph is twice the number of edges: $\sum_{v \in V} \text{deg}(v) = 2|E|$.

Adjacency Matrix

A matrix $A = [a_{ij}]$ used to represent a graph, where $a_{ij}$ is 1 if there is an edge between vertices $v_i$ and $v_j$, and 0 otherwise.

Tree

A connected simple undirected graph with no simple circuits.

m-ary Tree

A rooted tree where every internal vertex has no more than $m$ children.

Binary Search Tree

A binary tree used for data storage where each node's key is larger than all keys in its left subtree and smaller than all keys in its right subtree.