Exam (elaborations)
Summary Hunter college Discrete structures study guide
- Course
- Institution
Summary Hunter college Discrete structures study guide
[Show more]
Content preview
Summary Hunter college Discrete structures study guidepower set - ANSWER The set of all subsets of a set A, denoted P(A). If A = {a, b},
then P(A) = {{a}, {b}, {a, b}, ∅}. The cardinality of P(A) is 2 raised to the cardinality of
A.
cardinality - ANSWER Denoted | A |, it is the number of distinct elements in A.
disjoint sets - ANSWER A ∩ B = ∅.
set difference - ANSWER The set of elements {x∈A | x∉B}.
implication - ANSWER Equivalent to ∼p ∨q and is false only when p is true and q is
false.
tautology - ANSWER A proposition that is always true, like p ∨ ~p.
contradiction - ANSWER A proposition that is always false, like p ∧ ~p.
disjunctive normal form (DNF) - ANSWER A form of writing propositions with a
disjunction of conjunctions where (1) every variable or its negation appears once in
each conjunction, called a minterm, and (2) each minterm appears only once.
dual - ANSWER A related to a proposition S, denoted S*, where
(1) ∧ becomes ∨
(2) ∨ becomes ∧
(3) T becomes F
(4) F becomes T.
Note that (S*)* = S. If S = T, then S* = T*.
functional complete set - ANSWER Every proposition is logically equivalent to
another using only the operators in the set. Examples of these sets include {~, ∧},
{NAND}, {NOR}, etc.
universal quantifier - ANSWER Denoted by ∀. The statement ∀x P(x) reads "P(x) for
all x in the universe of discourse."
existential quantifier - ANSWER Denoted by ∃. The statement ∃x P(x) reads "There
exists an x in the domain of discourse such that P(x)."
unique existential - ANSWER Denoted ∃!. The statement ∃! x P(x) reads "There is a
unique x such that P(x)."
Equivalently, ∃x∀y (P(x) ∧ P(y) → x = y).
De Morgan's Law for Quantifiers - ANSWER Negating a predicate forces ∀ to
become ∃ and vice versa.
, (1) ~∀x P(x) ≡ ∃x ~P(x)
(2) ~∃x P(x) ≡ ∀x ~P(x)
modus ponens - ANSWER 1. p→q
2. p
∴q
modus tollens - ANSWER 1. p → q
2. ~q
∴ ~p
direct proof - ANSWER For p → q, assume that p is true, then prove that q must be
true.
indirect proof - ANSWER For p → q, apply direct proof on the contrapositive ~q →
~p.
proof by contradiction - ANSWER To prove a statement p, assume ~p and show
that it leads to a contradiction.
constructive proof of existence - ANSWER 1. P(a)
∴ ∃x P(x).
Finding this P(a) can be an example or a general solution.
non-constructive proof of existence - ANSWER Proof using theorems to guarantee
existence or use of indirect proof like proof by contradiction. However, no actual
example is ever provided.
proof of unique existence - ANSWER To prove ∃! x P(x), prove existence first, then
assume a proposition that contradicts uniqueness and disprove it. It is identical to
proving these two parts:
∃x (P(x) ∧ ∀y (P(y) → y = x))
mathematical induction - ANSWER A method of proof in two parts:
1. basis step, P(a)
2. inductive step, P(k) → P(k+1)
∴ ∀n P(n)
strong induction - ANSWER Another form of induction:
1. basis step, P(a)
2. inductive step, P(1) ∧ ... ∧ P(k) → P(k+1)
∴∀n P(n)
structural induction - ANSWER A method of proof on recursively defined structures:
1. basis step, proof that P(x) for all x in the basis step of recursion
2. inductive step, proof that all future iterations preserve the property from before
∴ ∀n P(n)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller leonardmuriithi061. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $17.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
81298 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now