2.2, 2.3, and 2.4 Notes
Logically Equivalent Statements
Logically Equivalent - Two expressions are logically equivalent provided that they have the same truth value for all possible combinations of truth values for all variables appearing in the two expressions.
Converse and Contrapositive
Converse - The converse of P→Q is Q→P
Contrapositive - The contrapositive of P→Q is -Q→-P
De Morgan’s Laws
The statement, -(P ^ Q) = -P v -Q
The statement, -(P v Q) = -P ^ -Q
Logical Equivalencies Related to Conditional Statements
Theorem 2.6
P →Q = -P v Q
-(P → Q) = P ^ -Q
P→ Q = -Q → -P
The Negation of a Conditional Statement
The negation of a conditional statement is not another conditional statement
Important Logical Equivalences
Biconditional Statement - (P ←→ Q) = (P → Q) ^ (Q → P)
Double Negation - -(-P) = P
Distributive Laws - P v (Q ^ R) = (P v Q) ^ (P v R)
P ^ (Q v R) = (P ^ Q) v (P ^ R)
Conditionals with Disjunctions - P → (Q v R) = (P ^ -Q) → R
(P v Q) → R = (P → R) ^ (Q → R)
Open Sentences and Sets
Sets and Set Notation
Set - A well-defined collection of objects that can be thought of as a single entity itself; {…}
Roster Method - Listing the elements of a set inside braces
Variables
Variable - A symbol representing an unspecified object that can be chosen from a given set U. The set U is called the UNIVERSAL SET FOR THE VARIABLE. It is the set of specified objects from which objects may be chosen to substitute the variable. A CONSTANT is a specific member of the universal set.
Number Systems
R - Real numbers
Q - Rational numbers
Z - Integers
N - Natural numbers
Some Set Notation
The set A is a SUBSET of a set B provided that each element of A is an element of B. In this case, we write A c B and also say that A is CONTAINED in B. When A is not a subset of B, we write A c/ B.
Variables and Open Sentences
Open Sentence - A sentence P(x1, …, xn) involving variables x1, …, xn with the property that when specific values from the universal set are assigned to x1, …, xn, then the resulting sentence is either true or false. That is, the resulting sentence is a statement. An open sentence is also called a PREDICATE or a PROPOSITIONAL FUNCTION.
Working with Open Sentences
Truth Set of an Open Sentence with One Variable - The collection of objects in the universal set that can be substituted for the variable to make the predicate a true statement. Also called TRUTH SET.
Set Builder Notation - The set is defined by stating a rule that all elements of the set must satisfy.
Quantifiers and Negations
An Introduction to Quantifiers
Universal Quantifier - “For every”; A
Existential Quantifier - “There exists… such that”; E
Theorem 2.16
For any sentence P(x),
-(Ax e U) [P(x)] = (Ex e U) [-P(x)], and
-(Ex e U) [P(x)] = (Ax e U) [-P(x)]
Important Set Theory Notation
Notation Description
y e A y is an element in the set A
{x e U | P(x)} set builder notation