[DM] Lecture 1 Flashcards
The study of mathematical structures that are fundamentally discrete rather than continuous.
Discrete Math
Those which are separated from (not connected to/distinct from) each other.
Discrete Objects
a declarative statement that’s either TRUE or FALSE (but not both).
Proposition
corresponds to English “and.”
Conjunction (∧)
corresponds to English “or.”
Disjunction (V)
It means either p or q, but not both
Exclusive-or (⊕)
the hypothesis (or antecedent).
p
the conclusion (or consequent).
q
corresponds to English “if p then q,” or “p implies q”, “p is sufficient for q”, “q when p”,”p only if q”, “a necessary condition for p is q”
Implication
it means “required”
Necessary
it means “enough”
Sufficient
corresponds to English “p if and only if q,”.
Double Implication
p → q and ¬q → ¬p
Contrapositive
p → q and q → p
Converse
p → q and ¬p → ¬q
Inverse
a proposition that’s always TRUE.
Tautology
a proposition that’s always FALSE.
Contradiction
The statement is true if P(x) is true for every x in D, and the statement is false if P(x) is false for at least one x in D.
Universally Quantified Statement
The statement is true if P(x) is true for at least one x in D, and the statement is false if P(x) is false for all values in D.
Existentially Quantified Statement
x in P(x) is called a ____
Free Variable
-set of two or more propositions related to each other in such a way that all but one of them (the premises) are supposed to provide support for the remaining one (the conclusion)
Argument
-transition from premises to conclusion upon which the argument relies.
Inference
All but final proposition in the argument
Premise
final proposition
Conclusion
if the truth of all of its premises implies that the conclusion is true
Valid
Steps to test an argument for validity
1) Identify the premises and the conclusion of the argument.
2) Construct a truth table including the premises and the conclusion.
3) Find rows in which all premises are true.
4) In each row of step 3, if the conclusion is true, then the argument is valid, otherwise the argument is invalid
the basis of the rule of inference called modus ponens , or the law of detachment.
(p∧(p → q))→ q
Modus Tollens
(-q ∧ (p → q)) → -p
Hypothetical Syllogism
((p → q) ∧ (q → r)) → (p → r)
Disjunctive Syllogism
((p v q) ∧ -p) → q
Addition
p → (p v q)
Simplification
(p ∧ q) → p
conjunction
((p) ∧ (q)) → (p ∧ q)
Resolution
((p v q) ∧ (-p v r)) → (q v r)
rule of inference used to conclude that P(c) is true, where c is a particular member of the domain, given the premise ∀xP(x)
Universal Instantiation
rule of inference that states ∀xP(x) is true, given that P(c) is true for all elements c in the domain
Universal Generalization
Used when ∀xP(x) is true by taking an arbitrary element c from the domain and showing that P(c) is true
Universal Generalization
Rule of inference for Universal instantiation
∀xP(x) → P(c)
rule that allows us to conclude that there is an element c in the domain for which P(c) is true if we know that ∃xP(x) is true
Existential Instantiation
rule of inference used to conclude that ∃xP(x) is true when a particular element c with P(c) true is known
Existential Generalization
Rule of inference for Universal Generalization
P(c) for an arbitrary c → ∀xP(x)
Rule of inference for Existential Generalization
P(c) for some element c → ∃xP(x)
Rule of inference for Existential Instantiation
∃xP(x) → P(c) for some element c
consists of axioms, definitions and undefined terms
Mathematical System
a proposition that has been proved to be true
Theorem
theorem that is usually not too interesting in its own right but is useful in proving another theorem.
Lemma
theorem that follows quickly from another theorem
Corollary
an argument that establishes the truth of a theorem
Proof
What are the 3 methods of proving
Direct Proof
Proof by Contraposition
Proof by Contradiction
Steps in Direct Proof
- Assume p is true
- use axioms, definitions, theorems, etc. to prove q is also true
Steps in Proof by Contraposition
- Make the statement -q → -p
- Assume -q is true
- use axioms, definitions, theorems, etc. to prove -p is also true
Steps in Proof by Contradiction
For 1 proposition only
- assume -p is true
- find a contradiction that shows -p is false, so that p is true
For implication p → q
- Assume p and -q are true
- Find a contradiction that shows p → q or -q → -p
