Quiz 1 Flashcards
A set whose elements can be listed in a sequence
Countable set
A countable set
Discrete set
The study of discrete (i.e. countable) objects and the relationship between them
Discrete mathematics
Consists of a new vocabulary word together with its description using already known terms
Definition
A declarative sentence that is both true or false, but not both
Proposition (a statement)
A sequence of sentences demonstrating the truth of a claim
Argument (a proof)
OR (∨)
AND (∧)
Negation/ NOT (~)
Implication implies/ if-then (→)
If and only if (⇔)
Logical operators (connectives)
Two propositional forms p and q are ________ if and only if they have the same truth values for each possible substitution of propositions into their component propositional variables
Logically equivalent
Theorem:
~(p ∨ q) ≡ ~p ∧ ~q
~(p ∧ q) ≡ ~p ∨ ~q
DeMorgan’s Law
A propositional form that is always true, denoted t
Tautology
A propositional form that is always false, denoted c
Contradiction
p ∧ q ≡ q ∧ p
p ∨ q ≡ q ∨ p
Commutative Law
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Associative Law
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Distributive Law
p ∧ t ≡ p
p ∨ c ≡ p
Identity Law
p ∨ ~p ≡ t
p ∧ ~p ≡ c
Negation Law
~(~p) ≡ p
Double Negation Law
p ∧ p ≡ p
p ∨ p ≡ p
Idempotent Law
p ∨ t ≡ t
p ∧ c ≡ c
Universal bound
p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p
Absorption Law
~t ≡ c
~c ≡ t
Negation of t and c
p ∨ q → r ≡ (p → r) ∧ (q → r)
Division into cases
p → q ≡ ~p ∨ q
Theorem 1
Negating p → q:
~(p → q) ≡ p ∧ ~q
Theorem 2
p → q ≡ ~ q → ~p
Contrapositive
p → q ≢ q → p
Converse
p → q ≡ ~p → ~q
Inverse
q → p
p if q
“If not q, then p”, which by contraposition is logically equivalent to p → q
p only if q
≡ (p → q) ∧ (q → p)
≡ (~p ∨ q) ∧ (~q ∨ p)
p ⇔ q
“If not p, then not q”, which by contraposition is logically equivalent to q → p
Necessary
“If p, then q”
Sufficient
≡ (p ∨ q) ∧ (~p ∧ ~q)
p ⊕ q
An argument where every case the premise is proven true, the conclusion is also true
Valid Argument
