Exam #1 Flashcards
Mathematical Statement
a declarative sentence that is either true or false, but not both.
When is P→Q false?
The only case in which P→Q is false is if P is true, but Q is false.
vacuously true
true by default
Even number definition
An integer a is even provided that there exists an
integer n such that a = 2n
Odd number definition
An integer a is odd provided that there exists an integer k such that
a = 2k + 1
Negation
¬P
Conjunction
P ∧ Q
Disjunction
P ∨ Q
Conditional
P → Q
Biconditional
P ⇔ Q
P if and only if Q
P ⇔ Q is equivalent to
(Q→P) ∧ (P→Q)
tautology
A tautology is a compound statement S that is true for
all possible combinations of truth values of the component
statements that are part of S.
Contradiction
A contradiction is a compound statement S that is false
for all possible combinations of truth values of the component
statements that are part of S
Double Negation
¬(¬P) ≡ P
DeMorgan’s Laws
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Negating Conditional Statements
¬(P → Q) ≡ P ∧ ¬Q
Is the negation of a conditional statement also a conditional statement?
The negation of a conditional statement is not a
conditional statement.
Contrapositive
Given a conditional statement
P→Q
the contrapositive of the statement is
¬Q → ¬P
Contrapositive Equivalence
A conditional statement is logically equivalent to its
contrapositive.
Converse
The converse of a conditional statement:
P→Q is Q → P
Converse Equivalence
A common mistake is to assume that a statement is logically
equivalent to its converse. This is not true.
Commutative
P ∧ Q ≡ Q ∧ P
P ∨ Q ≡ Q ∨ P
Associative
(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)
(P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)
Distributive
P∧(Q∨R)≡(P∧Q)∨(P∧R)
P∨(Q∧R)≡(P∨R)∧(P∨Q)
Identity
P∧t≡P
P∨c≡P
Negation
P∨¬P≡t
P∧¬P≡c
Double
Negation
¬(¬P)≡P
Idempotence
P∧P≡P
P∨P≡P
Universal bound
P∨t≡t
P∧c≡c
Negations of t and c
¬t≡c
¬c≡t
Implication
P → Q ≡ ¬P ∨ Q
Negation of a
conditional
¬(P→ Q) ≡ P ∧ ¬Q
Contrapositive
P → Q ≡ ¬Q → ¬P
Biconditional statement
P ↔ Q ≡ (P → Q) ∧ (Q → P)
Set
a well-defined collection of objects that can be thought of
as a single entity itself
Element
one of the objects in a set
Subset
A is called a subset of B, written A ⊆ B, if and only if every
element of A is also an element of B.
Set Equity
Two sets are equal if and only if they have exactly the same
elements.
Variable
A variable is a symbol representing an
unspecified object that can be chosen from a given set U
Universal set for the variable
It is
the set of specified objects from which objects may be
chosen to substitute for the variable.
Constant
A constant is a specific member of the universal set
open sentence (or predicate)
An open sentence (or predicate) is a sentence
P(x1, x2,· · · , xn) that contains a finite number of variables and
becomes a true or false statement when specific values are
substituted for the variables.
Truth Sets
If P(x) is a predicate with one variable, the truth
set of P(x) is the set of all elements in the universal set that
can be substituted for x to make P(x) true
The Universal quantifier
∀
(for all, for every, for each, given any, …)
The Existential quantifier:
∃
(there exists, there is a, there is at least one, for some, for at
least one, ···)
Negating Universal Statement
¬((∀x∈U) (P(x)))≡(∃x∈U)¬(P(x))
The negation of (∀x ∈U)(P(x) →Q(x))
(∃x ∈ U) ¬(P(x) → Q(x))
