Discrete Mathematics and Its Applications - Core Concepts and Foundations

Flashcards covering foundational topics in discrete mathematics, including propositional logic, predicate calculus, methods of proof, set theory, functions, sequences, matrices, algorithms, complexity theory, number theory, cryptography, mathematical induction, and recursion.

What is a proposition in logic?

A proposition is a declarative sentence that is either true or false, but not both.

How is the negation of a proposition $p$, denoted by $\neg p$, defined?

The negation of $p$ is the statement "It is not the case that $p$", which has the opposite truth value of $p$.

Under what condition is the conjunction $p \wedge q$ of two propositions true?

The conjunction $p \wedge q$ is true when both $p$ and $q$ are true, and is false otherwise.

How does an inclusive disjunction $p \vee q$ differ from an exclusive or $p \oplus q$?

The inclusive disjunction $p \vee q$ is true when at least one of $p$ or $q$ is true, whereas the exclusive or $p \oplus q$ is true when exactly one of $p$ and $q$ is true, and false when both are true or both are false.

When is the conditional statement $p \rightarrow q$ false?

The conditional statement $p \rightarrow q$ is false only when the hypothesis $p$ is true and the conclusion $q$ is false; it is true in all other cases.

Given the conditional statement $p \rightarrow q$, what are its converse, contrapositive, and inverse, and which is logically equivalent to $p \rightarrow q$?

The converse is $q \rightarrow p$, the contrapositive is $\neg q \rightarrow \neg p$, and the inverse is $\neg p \rightarrow \neg q$. Only the contrapositive is logically equivalent to $p \rightarrow q$.

Under what condition is the biconditional statement $p \leftrightarrow q$ true?

The biconditional statement $p \leftrightarrow q$ is true when $p$ and $q$ have the same truth value, and is false otherwise.

What are a tautology, a contradiction, and a contingency?

A tautology is a compound proposition that is always true, a contradiction is a compound proposition that is always false, and a contingency is a compound proposition that is neither a tautology nor a contradiction.

What are De Morgan's laws for propositional logic?

De Morgan's laws state that $\neg(p \wedge q) \equiv \neg p \vee \neg q$ and $\neg(p \vee q) \equiv \neg p \wedge \neg q$.

When is a compound proposition said to be satisfiable?

A compound proposition is satisfiable if there is at least one assignment of truth values to its variables that makes it true; otherwise, it is unsatisfiable.

What are the negations of the quantified statements $\forall x P(x)$ and $\exists x P(x)$?

By De Morgan's laws for quantifiers, $\neg \forall x P(x) \equiv \exists x \neg P(x)$ and $\neg \exists x P(x) \equiv \forall x \neg P(x)$.

What is the rule of inference known as modus ponens?

Modus ponens states that from the premises $p$ and $p \rightarrow q$, the conclusion $q$ validly follows.

What is the rule of inference known as modus tollens?

Modus tollens states that from the premises $\neg q$ and $p \rightarrow q$, the conclusion $\neg p$ validly follows.

What is the rule of inference known as resolution?

Resolution states that from the premises $p \vee q$ and $\neg p \vee r$, the resolvent $q \vee r$ validly follows.

What is the logical error in the fallacy of affirming the conclusion?

It incorrectly treats the conditional statement $p \rightarrow q$ and the premise $q$ as implying $p$, which is an invalid argument form based on a contingency rather than a tautology.

How does a direct proof differ from a proof by contraposition for a conditional statement $p \rightarrow q$?

A direct proof assumes $p$ is true and shows that $q$ must be true. A proof by contraposition is an indirect proof that assumes $\neg q$ is true and shows that $\neg p$ must be true.

How is a proof by contradiction constructed to show that a proposition $p$ is true?

It assumes that $\neg p$ is true and demonstrates that this assumption leads to a contradiction $r \wedge \neg r$ for some proposition $r$, proving that $p$ must be true.

What distinguishes a constructive existence proof from a nonconstructive existence proof?

A constructive existence proof explicitly finds an element $a$ such that $P(a)$ is true, whereas a nonconstructive existence proof proves that such an element exists without identifying it.

What two parts are required to prove that an object satisfying a property is unique?

Existence, by proving that an element $x$ with the property exists; and uniqueness, by proving that if both $x$ and $y$ have the property, then $x = y$.

What is the power set of a set $S$, and how many elements does it contain if $|S| = n$?

The power set $\mathcal{P}(S)$ is the set of all subsets of $S$. If $|S| = n$, then the power set has $2^n$ elements.

How is the Cartesian product $A \times B$ of two sets defined?

The Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ such that $a \in A$ and $b \in B$, that is, $A \times B = \{(a, b) \mid a \in A \wedge b \in B\}$.

For a function $f: A \rightarrow B$, what are the domain, codomain, and range?

The set $A$ is the domain, the set $B$ is the codomain, and the range is the subset of $B$ consisting of all images $f(a)$ for all $a \in A$.

When is a function $f$ said to be one-to-one (injective)?

A function $f$ is one-to-one if and only if $f(a) = f(b)$ implies $a = b$ for all $a$ and $b$ in its domain.

When is a function $f: A \rightarrow B$ said to be onto (surjective)?

A function $f$ is onto if and only if for every element $b \in B$, there is an element $a \in A$ such that $f(a) = b$.

Under what condition is a function $f$ invertible, and what is its inverse function $f^{-1}$?

A function $f$ is invertible if and only if it is a bijection (both one-to-one and onto). Its inverse $f^{-1}$ assigns to each $b \in B$ the unique element $a \in A$ such that $f(a) = b$.

How are the floor function $\lfloor x \rfloor$ and the ceiling function $\lceil x \rceil$ defined for a real number $x$?

The floor function $\lfloor x \rfloor$ assigns the largest integer less than or equal to $x$, and the ceiling function $\lceil x \rceil$ assigns the smallest integer greater than or equal to $x$.

What is the closed formula for the sum of the terms of a geometric progression $\sum_{j=0}^n ar^j$ when $r \neq 1$?

The sum is given by $\sum_{j=0}^n ar^j = \frac{ar^{n+1} - a}{r - 1}$.

How is the Fibonacci sequence $f_0, f_1, f_2, \dots$ defined recursively?

It is defined by initial conditions $f_0 = 0$, $f_1 = 1$, and the recurrence relation $f_n = f_{n-1} + f_{n-2}$ for $n \ge 2$.

What is a countable set, and what symbol denotes the cardinality of an infinite countable set?

A set is countable if it is finite or has the same cardinality as the set of positive integers. The cardinality of an infinite countable set is denoted by $\aleph_0$ (aleph null).

How does the Cantor diagonalization argument show that the real numbers are uncountable?

It assumes the real numbers in $(0, 1)$ can be listed sequentially, and then constructs a real number whose $i$th decimal digit differs from the $i$th decimal digit of the $i$th number in the list for every $i$, producing a number not in the list.

What does the Schröder-Bernstein theorem state?

If $A$ and $B$ are sets such that $|A| \le |B|$ and $|B| \le |A|$, then $|A| = |B|$, meaning there is a one-to-one correspondence between $A$ and $B$.

What condition is required for the matrix product $AB$ to be defined?

The number of columns in $A$ must equal the number of rows in $B$.

What are the defining characteristics of an algorithm?

An algorithm must satisfy input, output, definiteness, correctness, finiteness, effectiveness, and generality.

What are the worst-case time complexities of linear search and binary search on an ordered list of $n$ elements?

Linear search has worst-case time complexity $\Theta(n)$, whereas binary search has worst-case time complexity $\Theta(\log(n))$.

What is the halting problem, and what did Alan Turing prove regarding its computability?

The halting problem asks whether a procedure exists that can decide whether an arbitrary program will eventually halt when run on a given input. Alan Turing proved that it is an unsolvable problem.

What is the formal definition of '$f(x)$ is $O(g(x))$'?

$f(x)$ is $O(g(x))$ if there exist constants $C$ and $k$ such that $|f(x)| \le C|g(x)|$ whenever $x > k$.

How are big-$\Omega$ and big-$\Theta$ defined in terms of function growth?

$f(x)$ is $\Omega(g(x))$ if there exist positive constants $C$ and $k$ such that $|f(x)| \ge C|g(x)|$ for $x > k$, and $f(x)$ is $\Theta(g(x))$ if $f(x)$ is both $O(g(x))$ and $\Omega(g(x))$.

What does the Division Algorithm state for an integer $a$ and a positive integer $d$?

There exist unique integers $q$ and $r$, with $0 \le r < d$, such that $a = dq + r$, where $q = a \text{ div } d$ is the quotient and $r = a \bmod d$ is the remainder.

What does it mean for two integers $a$ and $b$ to be congruent modulo $m$, denoted $a \equiv b \pmod m$?

It means that the positive integer $m$ divides $a - b$, which is equivalent to $a \bmod m = b \bmod m$.

What is the Fundamental Theorem of Arithmetic?

Every integer greater than $1$ can be written uniquely as a prime or as the product of two or more primes, where the prime factors are listed in order of nondecreasing size.

What does Bézout's theorem state for two positive integers $a$ and $b$?

There exist integers $s$ and $t$ such that $\gcd(a, b) = sa + tb$, where $s$ and $t$ are called Bézout coefficients of $a$ and $b$.

What does the Chinese Remainder Theorem state?

If $m_1, m_2, \dots, m_n$ are pairwise relatively prime positive integers greater than $1$, then the system of linear congruences $x \equiv a_i \pmod{m_i}$ has a unique solution modulo $m = m_1 m_2 \cdots m_n$.

What does Fermat's Little Theorem state?

If $p$ is prime and $a$ is an integer not divisible by $p$, then $a^{p-1} \equiv 1 \pmod p$. Furthermore, for every integer $a$, $a^p \equiv a \pmod p$.

How are encryption and decryption carried out in the RSA cryptosystem?

With public key $(n, e)$ where $n = pq$ and $\gcd(e, (p-1)(q-1)) = 1$, a message block $M$ is encrypted as $C = M^e \bmod n$. Using the private key $d$, the inverse of $e \pmod{(p-1)(q-1)}$, it is decrypted as $M = C^d \bmod n$.

What are the two steps in a proof by the Principle of Mathematical Induction?

The basis step shows that $P(1)$ is true. The inductive step shows that the conditional statement $P(k) \rightarrow P(k+1)$ is true for all positive integers $k$, assuming the inductive hypothesis that $P(k)$ is true.

How does the inductive hypothesis of strong induction differ from that of mathematical induction?

Mathematical induction assumes only that $P(k)$ is true to prove $P(k+1)$, whereas strong induction assumes that $P(j)$ is true for all integers $j$ from the base case up to $k$ to prove $P(k+1)$.

What does the well-ordering property of the positive integers state?

Every nonempty set of nonnegative (or positive) integers has a least element.

What two steps constitute a proof by structural induction for a recursively defined set?

The basis step verifies that the statement holds for all elements in the basis step of the definition. The recursive step verifies that if the statement holds for all elements used to construct new elements in the recursive step, it also holds for the new elements.

In program verification, what is a loop invariant?

A loop invariant is an assertion $p$ that remains true before and after each execution of the body of a loop, ensuring that if $p$ is true initially, it remains true throughout and upon loop termination.

What is the worst-case time complexity of the merge sort algorithm for sorting a list of $n$ elements?

The merge sort algorithm has a worst-case time complexity of $O(n \log(n))$.