Discrete Mathematics
82 flashcards by MentisLibrary
Logic, proofs, sets, relations, counting, recurrences, graphs, and number theory, the mathematical backbone of computer science. Every card gives the definition and the trap that comes with it.
- What is a proposition?
- A statement that is either true or false, but not both
- What are the truth values of $p \land q$ (and)?
- True only when both $p$ and $q$ are true
- What are the truth values of $p \lor q$ (or)?
- True when at least one of $p$, $q$ is true
- When is the implication $p \to q$ false?
- Only when $p$ is true and $q$ is false
- When is the biconditional $p \leftrightarrow q$ true?
- When $p$ and $q$ have the same truth value
- What is a tautology and what is a contradiction?
- A tautology is true under every assignment, a contradiction is false under every assignment
- What does it mean for two statements to be logically equivalent?
- They have identical truth tables, written $p \equiv q$
- What are De Morgan's laws?
- $\neg(p \land q) \equiv \neg p \lor \neg q$ and $\neg(p \lor q) \equiv \neg p \land \neg q$
- What are the converse, inverse, and contrapositive of $p \to q$?
- Converse $q \to p$, inverse $\neg p \to \neg q$, contrapositive $\neg q \to \neg p$
- What do the quantifiers $\forall$ and $\exists$ mean?
- $\forall$ means 'for all', $\exists$ means 'there exists at least one'
- How do you negate a quantified statement?
- Flip the quantifier and negate the inside
- What is modus ponens?
- From $p \to q$ and $p$, conclude $q$
- What is modus tollens?
- From $p \to q$ and $\neg q$, conclude $\neg p$
- What is a direct proof?
- Assume the hypothesis and derive the conclusion by a chain of valid steps
- What is a proof by contraposition?
- Prove $\neg q \to \neg p$ instead of $p \to q$
- What is a proof by contradiction?
- Assume the statement is false, derive an impossibility, and conclude it must be true
- What is a counterexample?
- A single instance that makes a universal claim false
- What are the steps of mathematical induction?
- Prove the base case, assume the claim for $n=k$, then prove it for $n=k+1$
- What is strong induction?
- Assume the claim for all values up to $k$, not just $k$, then prove it for $k+1$
- What is set-builder notation?
- A description of a set by a defining property
- What are union, intersection, and difference of sets?
- Union collects all elements, intersection keeps shared elements, difference removes the second set's elements
- What is the complement of a set?
- Everything in the universal set that is not in $A$, written $A^c$ or $\bar{A}$
- What is a subset and how does it differ from a proper subset?
- $A \subseteq B$ means every element of $A$ is in $B$. Proper subset $A \subset B$ also requires $A \neq B$
- What is a power set and how large is it?
- The set of all subsets of $A$, with $2^{|A|}$ elements
- What is a Cartesian product?
- The set of all ordered pairs from two sets
- What is the cardinality of a set?
- The number of elements it contains, or its size class if it is infinite
- What are the distributive laws for sets?
- $A\cap(B\cup C) = (A\cap B)\cup(A\cap C)$ and $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$
- What makes a function injective?
- Different inputs always give different outputs, so it is one to one
- What makes a function surjective?
- Every element of the codomain is hit by some input, so the range equals the codomain
- What is a bijection?
- A function that is both injective and surjective, pairing the two sets perfectly