CLEP College Mathematics – Mathematical Logic and Set Theory

Logic
– Critical thinking skill.
Open and Closed Sentences
– Open: Sentence with variable. ex:) x+2=8, It is my favorite color.

– Closed: Sentence without a variable. ex:) 6+2=8, The grass is green.

Open Sentences
– Open: Sentence with variable. ex:) x+2=8, It is my favorite color.
Closed Sentences
– Closed: Sentence without a variable. ex:) 6+2=8, The grass is green.
Sentences have a truth value
– They are either true, false, or open.

– They must be closed to be truth/false.

– ex:) True: A square has equal side lengths.

False: A pentagon has 67 sides.

Open: It has a right angle.

Negation
– Giving the opposite truth value.

– Symbol ~

Symbols: Representations of sentences, usually in letter form.

ex.) P: I passed my test.

negation: ~P

I did not pass my test.

We will write a custom essay sample on
Any topic specifically for you
For only $13.90/page
Order Now
And / Or
– And (Conjunction): Two things depend on each other. Symbol: ^.

To be true, both parts must be true.

– Or (Disjunction): Two things do not depend on each other. Symbol: V.

– Examples:

And- C= All cats bark.

E= 7+4=11

C^E (False)

~C^E (True)

C^~E (False)

~E^~C (False)

Or- M= I go to the mall.

B: I buy sneakers.

MVB (True)

~MVB (True)

MV~B (True)

~MV~B (False)

And (Conjunction)
wo things depend on each other. Symbol: ^.

To be true, both parts must be true.

Or (Disjunction)
Two things do not depend on each other. Symbol: V.
Negation of Phrases
– Distribute the negative.

– Flip the sign.

– Symbol: ~.

– Ex.) ~(P^Q) : ~PV~Q

~(~CVB) : C^~B

Conditional
– Means to imply.

– A compound sentence.

– Every action has a reaction.

– Parts of the sentence:

*hypothesis- Sentence or phrase that starts with “if.”

*conclusion- Sentence or phrase that starts with “then.”

ex.) If I eat a lot of icecream, then I get a brainfreeze.

– Symbol: ->

ex.) P: I go on a field trip, W: I miss schoolwork.

P->W (Truth Value- T->T equals T)

P Q P-> Q

T T T

T F F

F T T

F F T

hypothesis
Sentence or phrase that starts with “if.”
conclusion
Sentence or phrase that starts with “then.” ex.) If I eat a lot of icecream, then I get a brainfreeze.

– Symbol: ->

T
T T
F
T F
T
F T
T
F F
Biconditional
– If and only if.

– Symbol: <-->.

ex.) P: A triangle is isosceles. (T)

Q: A triangle has 2 congruent sides. (T)

P <--> Q (T)

P Q P<-->Q

T T T
T F F
F T F
F F T

Inverse
– Changing the truth value of the conditional.

– Change the sign.

– ex.) If I like chocolate, then I eat kisses.

If I do not like chocolate, then I do not eat kisses.

Converse
– Changing the order of the conditional.

– Change order.

– ex.) If I put on shoes, then I tie my shoes.

If I tie my shoes, then I put on my shoes.

Contrapositive
– Logically equilvilant.

– Change the order and the sign.

– Same truth value.

– ex.) If I get married, then I say I do.

If I do not say I do, then I do not get married.

categorical proposition
A proposition that relates two classes, or categories
ex. American Idol contestants hope for recognition
4 Types of Categorical Propositions
(1) those that assert that the whole subject class is included in the predicate class, (2) those that assert that part of the subject class is included in the predicate class, (3) those that assert that the whole subject class is excluded from the predicate class, and (4) those that assert that part of the subject class is excluded from the predicate class.
standard form categorical proposition
A categorical proposition that expresses these relations with complete clarity
Forms of Standard form categorical proposition
All S are P.
No S are P.
Some S are P.
Some S are not P.
quantifiers
they specify how much of the subject class is included in or excluded from the predicate class. (ex. all, no, or some)
copula
they link (or “couple”) the subject term with the predicate term. (ex. are and are not)
quality
either affirmative or negative depending on whether it affirms or denies class membership
affirmative quality
ex: “All S are P” and “Some S are P”
negative quality
“No S are P” and “Some S are not P”
quantity
categorical proposition is either universal or particular, depending on whether the statement makes a claim about every member or just some member of the class denoted by the subject term
universal statements
ex: “All S are P” and “No S are P” each assert something about every member of the S class
particular statements
ex: “Some S are P ” and “Some S are not P ” assert something about one or more members of the S class
A proposition
universal affirmative
E proposition
universal negative
I proposition
particular affirmative
O proposition
particular negative
distribution
an attribute of the terms (subject and predicate) of propositions – ( A term is said to be distributed if the proposition makes an assertion about every member of the class denoted by the term; otherwise, it is undistributed)
Venn Diagrams
a system of diagrams to represent the information expressed (created by John Venn)
modern square of opposition
diagram that represents the relationship of mutually contradictory pairs of propositions
contradictory relation
two propositions that necessarily have opposite truths
immediate references
have only one premise (ex:Some trade spies are not masters at bribery.
Therefore, it is false that all trade spies are masters at bribery.)
unconditionally valid
used to describe Arguments that are valid from the Boolean standpoint because they are valid regardless of whether or not their terms refer to existing things
existential fallacy
a formal fallacy that is committed whenever an argument is invalid merely because the premise is interpreted as lacking existential import
(ex: 1. All A are B.
Therefore, some A are B.
2. No A are B.
Therefore, some A are not B.
conversion
it consists in switching the subject term with the predicate term. (ex: No foxes are hedgehogs & “No hedgehogs are foxes)
logically equivalent statements
when two statements necessarily have the same truth value
obversion
requires two steps: (1) changing the quality (without changing the quantity), and (2) replacing the predicate with its term complement
class complement
is the group consisting of everything outside the class (ex. the complement of dogs would be: fish, trees, cats)
term complement
the word or group of words that denotes the class complement (ex: “dog” is “non-dog)
contraposition
requires two steps: (1) switching the subject and predicate terms and (2) replacing the subject and predicate terms with their term complements (ex: “All goats are animals” is contraposed, the resulting statement is “All non-animals are non-goats.” )
Law of Disjunctive Inference
pVq

~p

*q

Definition of Conjunction
pΛq

*p *q

Law of Detachment
p→q

p

*q

Definition of Disjunction
p q

*pVq *pVq

Law of Contrapositive
p→q

*~q→~p

Law of Syllogism (Chain Rule)
p→q

q→r

*p→r

Law of Modus Tollens
p→q ~q→~p

~q p

*~p *q

DeMorgan’s Law
(pΛq)↔ ~(~pV~q) (pVq)↔ ~(~pΛ~q)
~(pΛq)↔ (~pV~q) ~(pVq)↔ (~pΛ~q)
Law of Detachment
p–>q

p

q

DeMorgan’s Law
~(p^q) or ~(p v q)
/
~p v ~q or ~p ^ ~q
Law of Contrapositive
p –> q
/
~q –> p
Law of Contrapositive Inference
p –> q

~q
/
~p

Law of Disjunctive Inference

“the maid or butler did it”

p v b or p v b

~p or ~b
/
b or p

Well-Ordering Principle
Every nonempty set S of nonnegative integers contains a least element; that is, there is some integer a in S such that a≤b for all b’s in S
First Principle of Finite Induction
Let S be a set of positive integers with the following properties:
(a) 1 is in S
(b) If k is in S , then k + 1 is in S.
Then S is the set of all positive integers
Second Principle of Finite Induction
Let S be a set of positive integers with the following properties:
(a) 1 is in S
(b) If k is a positive integer such that 1, 2, . . . , k are in S , then k +1 is S.
Then S is the set of all positive integers
The Division Algorithm
Given integers a and b, with b > 0, there exist unique integers q and r satisfying a = qb + r and 0 ≤ r < b. The integers q and r are called, respectively, the quotient and the remainder
Euclid’s Lemma
If a l bc, with gcd(a,b) = 1, then a l c

Proof:

since the gcd(a,b)=1, 1=ax+by for x,y in Z

so c=(ax+by)c=acx+bcy

since a l ac and a l bc, a l (acx + bcy)

so a l c(ax+by). Therefore a l c

Fundamental Theorem of Arithmetic
Every positive integer n > 1 can be expressed as a product of primes; this representation is unique, apart from the order in which the factors appear.
Euclid’s Theorem
There are infinitely many primes
Fermat’s Theorem
Let p be a prime and suppose that p does not divide a. Then a^p-1 ≡ 1 (mod p)

Corollary:

If p is a prime, then a^p ≡ a (mod p) for any integer a.

Chinese Remainder Theorem
Let n1, …, nr be positive integers such that gcd(ni,nj)=1 for i≠j. The system of congruence

x ≡ a1 (mod n1)

.

.

.

x ≡ ar (mod nr)

has a simultaneous solution, which is unique modulo n = n1n2 . . . nr

Commutative Laws: For all sets A & B
(a) A U B = B U A
(b) A inter B = B inter A
Associative Laws: For all sets A,B, & C
(a) (A U B) U C = A U (B U C)
(b) (A inter B) inter C = A inter (B inter C)
Distributive Laws: For all sets A, B, & C
(a)A U (B inter C) = (A U B) inter (A U C)
(b)A inter (B U C) = (A inter B) U (A inter C)
Identity Laws: For all sets A
(a)A U 0 = A
(b)A inter 0 = 0
Complement Laws
(a)A U A^c^ = Univ
(b)A inter A^c^ = 0
Double Complement Laws: For all sets A
(A^c^)^c^=A
Idempotent Laws: For all sets A
(a)A U A = A
(b)A inter A = A
Universal Bound Laws: For all sets A
(a)A U Univ = Univ
(b)A inter 0 = 0
De Morgan’s Laws: For all sets A and B
(a)(A U B)^c^ = A^c^ inter B^c^
(b)(A inter B)^c^ = A^c^ U B^c^
Absorption Laws: For all sets A and B
(a)A U (A inter B) = A
(b)A inter (A U B) = A
Complements of U and 0
(a)Univ^c^=0
(b)0^c^=Univ
Set Different Law: For all sets A & B
A – B = A inter B^c^
Set
a collection of objects
element
each object (member) in a set
subset
a set that contains some or all of the elements of a set
union
a set that contains all elements of both sets
empty set
a set that contains no elements
intersection
a set that contains only those elements that are in both sets
compliment
all the elements not in the set
universal set
the set containing all elements of a problem under consideration
SET
Collection of items

ex. A={1, 2, 3, 4}

ELEMENT
item in a set
UNION
a set of all the elements of the original sets
INTERSECTION
set containing the elements the original sets have in common
EMPTY SET
contains no elements
UNIVERSE (OR UNIVERSAL SET)
contains all elements relating to situation
COMPLIMENT
set of all elements that weren’t in the original set
SUBSET
a set contained within another set
CROSS PRODUCT (CARTESIAN PRODUCT)
a set where elements are ordered pairs
The symbol for element
The symbol for sub set
the symbol for intersection
The symbol for union
the symbol for no intersection
the symbol for empty set
{ }
The symbol for complement
Elements/Members
Objects belonging to the set; Designated in 3 ways: A Word Description, Listing Method, & Set Builder Notation.
Empty Set/Null Set
The set containing no elements. Symbols: ∅ or { } .
SET
A collection of objects.
∈ & ∉
Replaces the words: “is an element of.” & ∉ means “not an element of”
Natural or Counting Numbers
{ 1, 2, 3, 4, . . . }
Whole Numbers
{ 0, 1, 2, 3, 4, . . . }
Integers
{ . . . ,-3, -2, -1, 0, 1, 2, 3, 4, . . . }
Rational Numbers
{ p/q | p and q are integers and q ≠ 0 }
Real Numbers
Anything on the number line; { x| x is a number that can be expressed as a decimal }
Irrational Numbers
{ x| x is a real number that can not be expressed as a quotient of integers }
Cardinal Number/Cardinality
The number of elements in a set. n(A) or “n of A,” represents the cardinal number of set A. If they repeat in a set, they are not counted more than once.
Finite Set
The cardinal number of this set is a particular whole number (0 or counting number/a counting number).
Infinite Set
A cardinal number is not found; too large too count. ∞ (symbol).
Set Equality
Set A is equal to set B provided the following two conditions are met: 1. Every element of A is an element of B and 2. Every element of B is an element of A. Regardless of order.
Non-Overlapping Venn Diagram
“None”
Overlapping Venn Diagram
“Some”
Subset Venn Diagram
“All” or “Some”
Converse
Switch statement front to back
Inverse
Opposite of both parts of statement
Contrapositive
Opposite of both parts of the statement AND switch front to back
Validity of Three Statements
End of Statement 1 matches beginning of Statement 2.

Statement 3 is made of the beginning of Statement 1 and the end of statement 2.

If A, then B.
If B, then C.
If A, then C.

Conditional statements (conditionals):
If-then statements
Biconditional statement:
“if and only if” statements
– p if and only if q
– used if you can prove that a conditional statement and its converse are true.
Hypothesis (p):
The part in the “if”
Conclusion (q):
the part in the “then”
If p,
then q.
Converse:
If q, then p.
Inverse:
If not p, then not q.
Contrapositive:
If not q, then not p.
Logically equivalent statements:
– statements are logically equivalent if they are both true or both false
– only true for statement and contrapositive, converse and inverse
Compound statements:
2 statements joined by or (∨) or and (∧)
Conjunction:
a compound statement joined by “and”
Disjunction:
a compound statement joined by “or”
basic truth table: OR
p q p OR q
————
T T T
T F T
F T T
F F F
basic truth table: AND
p q p AND q
————
T T T
T F F
F T F
F F F
basic truth table: THEN
p q p –> q
————
T T T
T F F
F T T
F F T

***Note this is only false when the conclusion is false and the hypotheses is true.

Tautology:
a statement that is always true (The last column of the truth table is all T’s)
Modus ponens
B follows from A and A ⇒ B
Generalisation
(∀x_i)A follows from A
Logical Axiom A1
A ⇒ (B ⇒ A)
Logical Axiom A2
(A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C))
Logical Axiom A3
(¬B ⇒ ¬A) ⇒ ((¬B ⇒ A) ⇒ B)
Logical Axiom A5
(∀x_i)(A ⇒ B) ⇒ (A ⇒ (∀x_i)B)
Particularisation Rule A4
If t is free for x in A(x) then (∀x)A(x)⊦A(t)
Existential Rule E4
Let t be a term that is free for x in a wf A(x,t), and let A(t,t) arise from A(x,t) by replacing all free occurrences of x by t. Then A(t,t) ⊦ (∃x)A(x,t)
S1
x = y ⇒ (x = z ⇒ y = z)
S2
x = y ⇒ x’ = y’
S3
0 ≠ x’
S4
x’ = y’ ⇒ x = y
S5
x + 0 = x
S6
x + y’ = (x + y)’
S7
x⋅0 = 0
S8
x⋅(y’) = (x⋅y) + x
S9 or The Principle of Mathematical Induction
For any wf A(x) of S, A(0) ⇒ ((∀x)(A(x) ⇒ A(x’)) ⇒ ((∀x)A(x))
Proof t = t
1. t+0 = t (S5′)
2. (t+0=t) ⇒ (t+0 = t ⇒ t=t) (S1′)
3. t+0 = t ⇒ t = t (1,2,MP)
4. t=t (1,3,MP)
t < s
(∃w)(w≠0 ∧ w + t = s)
t ≤ s
t < s ∨ t = s
t > s
s < t
t ≥ s
s ≤ t
Number Theoretic Function
A function whose arguments and values are natural numbers.
Number Theoretic Relation
A relation whose arguments are natural numbers.
Expressible In K
A number-theoretic relation R of n arguments is said to be this, if and only if there is a wf A(x_1, …, x_n) of K with n free variables such that, for any natrual numbers k_1, …, k_n, the following hold:
1. If R(k_1, …, k_n) is true, then ⊦K A(bar{k}_1,…, bar{k}_n)
2. If R(k_1, …, k_n) is false, then ⊦K ¬ A(bar{k}_1,…, bar{k}_n)
Representable in K
A number-theoretic function f on n arguments is said to be this, if and only if there is a wf A(x_1, …, x_n+1) of K with the free variables x_1, …, x_n+1 such that, for any natural numbers k_1, …, k_n, m, the following hold:
1. If f(k_1, …, k_n) = m then ⊦K A(bar{k}_1,…, bar{k}_n, m)
2. ⊦K (∃_1 x_n+1) A(bar{k}_1,…, bar{k}_n, x_n+1)
Strongly Representable in K
If f is this, then f is representable in K and
2′. ⊦K (∃_1 x_n+1) A(x_1,…, x_n, x_n+1)
Characteristic Function
C_R (x_1, …, x_n) = {
0 if R(x_1, …, x_n) is true
1 if R(x_1, …, x_n) is false
Initial Functions
1. Zero Function Z(x) = 0
2. Successor Function N(x) = x + 1 for all x
3. Projection Functions
U_i^n (x_1, …, x_n) = x_i for all x_1, …, x_n
Primitive Recursive
A function f is this, if and only if it can be obtained from the initial functions by any finite number of substitutions and recursions.
Recursive
A function f is this, if and only if it can be obtained from the initial functions by any finite number of substitutions, recursions and the μ-operator
contrapositive
the statement formed when you negate the hypothesis and conclusion of the converse of a conditional statement logically equivalent to conditional
counter example
an example that shows a conjecture is false
proof
the act of validating
implication
any proposition written in if ….then format
premise
a statement that is assumed to be true and from which a conclusion can be drawn
sound
a valid agrument with true premises
not
the word used to express the negation of a proposition
antecedent
The If clause of an implication is called the
converse
For any proposition p==>q, a proposition that reverses the Order of the premises to produce q===>p
modus tollens
a syllogism of form if p then q. Not q. Therefore not p. proves something wrong
hypothetical syllogism
a valid syllogism that resembles the transitive property in algebra.
negation
if proposition p is true then the____of P is false
given
a reason a proof that is not a logical tool
if and only if
key four word phrase indicating a biconditional
proposition
any statement is logic
reduction ad absurdum
Latin name for an indirect argument in which one temporarily assimes the negation of the desired conclusion and reasons until he reaches a contridiction of a known fact
venn diagram
graphic representation of an argument in logic
and
the key word used to indicate that a proposition is a conjunction
or
disjunction is indicated by the keyword
disjunction
a proposition that is false only when both of its premises are false
substitution
If angle 1 an angle 2 are supplementary and angle 2= angle 3 the angle 1 and angle 3 are supplementary.
subset
If all members of Group B are also members of a larger group A, then we say that Group B is a(n)_________ of Group A
some
the word commonly used as a principal existenial quantifier
consequent
the then clause of an implication
modus ponens
valid syllogism in the form if P the Q. P is true. Therefore Q is true
logically equivalent
two propositions with the same truth table values
truth table
a systematic arrangement of all possible truth values for a logical proposition
jingoism
the unwarranted, exaggerated patriotism loyalty to a person, institution, or ideal without adequate logical justification
intersection
a venn diagram of the logical conjunction is represented by points that lie in the __________
conclusion
a statement logically inferred from other statement
transitive
If the measure of angle k is equal j. j=37 the angle k=37 is an illustration of this property
accentuation
logical slight of hand. the attempt to distract the reader from the main issue by placing emphasis upon a tangential issue
hypothesis
an educated guess about what will be the outcome of an experiment. sometimes refered to the antecedent of an implication
biconditional
if both the conditional and the converse of a proposition are true then the proposition
All
affirmative universal quantifier
fallacy
an error in logic which may concern either the form of the argument or the truthfulness of its premises
stereotyping
logically fallacy in which one attributes distorted exaggerated characterisics of a class of items or people to a specific indivudial with out justification
syllogism
a set of premises whose form always produces a true conclusion
false dilema
artificial reduction of all possible choices to two choices either of which result in negative consequences when in truth there are better options
truth value
either true or false but not both
slippery slope
logically fallacy that infers an inevitable sequence of causes and effects such that the occurence of the first cause must produce the final effect
inverse
implication that negates both the antecedent and the consequent of the conditional
amphiboly
logical fallacy resulting from the grammatical ambiguity of sentence structure
valid
form guarantees a true conclusion anytime that the premises are true
strawman
we exaggerate
contridiction
indirect proof, one temporary assumes the negation of the conclusion and reasons logically until he finds a _________
no
most common negative universal quantifier
hasty conclusion
inference drawn from insufficient premises, the premises may not have accounted for all possible contributing influences leading to the inference.
ad hominem
logical fallacies that are an attack against the person offering an argument itself
begged
assumes the conclusion as a premise in the argument to produce a circular reasoning pattern
ad misericordium
makes a decision about an issue based upon sympathy for the issue instead of genuine qualifications for the issue
faulty clause
accepts the assertion that an event is the result of one factor when it is really the result of another
Statement
p -> q
Converse
q -> p
Inverse
~p -> ~q
Contrapositive
~q -> ~p
Law of Detachment
p -> q
and p
______
.. q
Law of Contraposition
p -> q
and ~q
______
.. ~p
Law of Syllogism (transitive)
p -> q
q -> r
p
____
.. r
Law of Disjunctive sullogism
p or q
~p
____
. . q
AND
p ^ q True only if both True
OR
p V q False only if both false
NEGATION
~p opposite
IF … THEN
p | r | if p then q
T | T | T
T | F | F
F | T | T
F | F | T
Implication
p — > q
Converse
q –> p
Inverse
~ p –> ~ q
Contrapositive
~ q –> ~ p
Logically Equivalent Conditions
Original (p –> q) === Contrapositive (~q –> ~p)
OR
Converse (q –> p) === Inverse (~p –> ~q)
~ (p –> q) ===
p ^ ~ q
p ^ ~ q ===
~ (p –> q)
p — > q (Orig) ===
~ q –> ~ p (Contrapositive)
q –> p (Converse) ===
~ p –> ~ q (Inverse)
~ q –> ~ p (Contrapositive) ===
p — > q (Orig)
~ p –> ~ q (Inverse) ===
q –> p (Converse)
Conditional: If today is Easter, then tomorrow is Monday (write the Contrapositive)
Contrapositive: If tomorrow is not Monday, then today is not Easter
Negation of p –> q
p ^ ~ q
Conditional: If today is Easter, then tomorrow is Monday (write the Converse)
Converse: If tomorrow is Monday, then today is Easter.
Conditional: If today is Easter, then tomorrow is Monday (write the Inverse)
Inverse: If today is not Easter, the tomorrow is not Monday.
Conditional: If Tom is Ann’s father, then Jim is her uncle and Sue is her aunt. (write Contrapositive)
Contrapositive: If either Jim is not Ann’s uncle or Sue is not her aunt, then Tom is not her father
Conditional: If X, then Y AND Z
Contrapositive: If EITHER not Y OR not Z, then not X
Conditional: If X, then Y OR Z
Contrapositive: If not Y AND Z, then not X
Modus Ponens
p –> q
p
… q [VALID]
modus ponendo ponens: “the way that affirms by affirming”
Modus Tollens
p –> q
~ q
… ~ p [VALID]
modus tollendo tollens: “the way that denies by denying”
Elimination
p v q
~ p
… q [VALID]
Transitivity
p –> q
q –> r
… p –> r [VALID]
Generalization
p
… p v q
Specialization
p ^ q
… p
Proof by Division into cases
p v q
p –> r
q –> r
… r [VALID]
Conjunction
p
q
… p ^ q
Contradiction
~ p –> C
… p
Converse Error
p –> q
q
… p [INVALID]
Inverse Error
p –> q
~ p
… ~ q [INVALID]
p OR q ===
~ p –> q
DeMorgans Laws
~(p ^ q) === ~p v ~q
~(p v q) === ~p ^ ~q
p –> q ===
~ p v q
p –> q ===
~q –> ~p
p <--> q ===
(p –> q) ^ (q –> p)
(p ^ q) v (~p ^ ~q)
Vacuously True
Hypothesis is False
Implication is False
ONLY when hyp (p) is T and conc (q) is F
(p(T) –> q(F))
Law of Detachment
P implies Q, P is true … Q is true
Chain Rule/Law of Syllogism
P implies Q, Q implies R … P implies R/If..and..then
Biconditional
P<-->Q, P is true … Q is true / If and only if
Contraposition
P implies Q, Q is false … P is false
Disjunctive Inference
P or Q, P is not true … Q is true
Denying the Premise/Hypothesis
P implies Q, P is false … Q is false
Asserting the Conclusion
P implies Q, Q is true … P is true
True conjunction
A conjunction is true if and only if both conjunct are true
True Biconditional
(p→q) ∧ (q→p).
Law of disjunctive inference
If a disjunction is true and one of its disjuncts is false, then the other disjunct must be true.
[(p ∨ q) ∧ ~p] → q
Law of detachment
If the antecedent of a true conditional is true then the consequent of the same conditional must be true.
[(p → q) ∧ p ]→ q
Law of double negation
p → ~(~p)
Law of the contraposative
A contraposative of a true conjunction has the same meaning as the original conjunction.
(p → q) ↔ (~q → ~p)
Converse
q → p
Contraposative
~q → ~p
Inverse + Converse
Inverse
~p → ~q
Replacement Set
The domain
Law of Modus Tollens
If the consequent of a true conditional statement is false, then the antecedent must be false.

[(p → q) ∧ ~p] → ~q

Law of Syllogism
If (p → q) and (q → r) are true, then (p → r) is true
Demorgan’s Law
~(p ∧ q) ↔ (~p ∨ ~q)
~(p ∨ q) ↔ (~p ∧ ~q)
QED!
which was to be demonstrated (latin)
Disjunctive addition
p → (p ∨ q)
Disjunctive equivalent of a conditional
Every conditional has a disjunctive equivalent
(p → q) ↔ (~p ∨ q)
Negation of Conditionals
~(p → q) ↔ ~(~p ∨ q)
can use demorgans law to find:
~(p → q) ↔ ~(~p) ∧ ~q
then law of double negation:
~(p → q) ↔ p ∧ ~q
Conjunctive Addition
If two conjuncts are true, their conjunction will be true.
p ∧ q → (p ∧ q)
Given the statements p and q, an implication is a statement that is false when p is true and q is false, and true otherwise.
A biconditional statement is true whenever the truth value is the same for both p and q and false otherwise.
‘NOT:’Negation – a method of assigning the opposite truth value to the statement.
¬
AND:’ Given p and q, a conjunction is the proposition that is true when both p and q are true and is false otherwise.
‘OR:’ Given p and q, a disjunction is the proposition that is false when both p and q are false, but is true otherwise.
‘XOR:’ An exclusive or is a proposition which is true when exactly one of p and q is true and is false otherwise.
The universal quantification of P(x) is the proposition “P(x) is true for all values x in the universe of discourse.”
The existential quantification of P(x) is the proposition “There exists an element x in the universe of discourse such that P(x) is true.”
conditional statement
a statement in the form of “if p, then q”
converse statement
the converse of a conditional statement is formed by negating the hypothesis and the conclusion to become “if q, then p”
inverse statement
the inverse of a conditional statement is formed by negating the hypothesis and the conclusion to become “if not p, the not q”
contrapositive statement
the contrapositive of a conditional statement is formed by reversing AND negating the hypothesis and the conclusion to become “if not q, then not p”
counterexample
shows the hypothesis (if part) of a conditional can be true without the conclusion (then part) also being true
biconditional
a condition whose converse is also true. (denoted with a double ended arrow)
proportion
an equation showing that two ratios are equivalent
ratio
a comparison of two or more numbers using division
similar
having exactly the same shape, but not necessarily the same size. similar figures have proportional corresponding sides and congruent corresponding angles
(triangle) side-angle inequality
the longest side is opposite the largest angle and the smallest side is opposite the smallest angle
triangle inequality
any side of a triangle must be greater than the difference and smaller than the sum of the other two sides
Ad Hominem
The fallacy of personal attack; debater introduces irrelevant personal facts about his opponent
Ad Miscordium
An appeal to pity; someone tries to win support for their argument or idea by exploiting his or her opponents feelings of pity or guilt
All
universal quantification; the notion that something is true for everything (or every relevant thing)
Amphiboly
Fallacy of ambiguation: involves the use of sentences which can be interpreted in multiple ways with equal justification
And
a two place logical connective that has the value true if both operants are true
Antecedent
The first half of a hypothetical situation. Follows “if”
Begged (the question)
When one assumes his conclusion as a premise in his argument to produce a circular reasoning pattern
Biconditional
logical operator connective two statements to assert “P if an only Q”
Conclusion
“logical consequence”;the relationship between the premises and the conclusion of a valid argument. It is the relation that holds between a set of propositions and another proposition when the former imply the latter. EX. “Kermit is green” is the logical consequence of “all frogs are green”
Conjunction
(same as and) a two-place logical connective that has the value true if both of its operants are true
Consequent
The second half of a hypothetical proposition. The part that follows ‘then’
Contradiction
logical incompatibility between two or more propositions. When two propositions yield conclusions that are logical inversions of each other
Contrapositive
the statement formed when you negate the hypothesis and conclusion of the converse of a conditional statement; if not “p then not q”
Converse
the statement formed by switching the hypothesis and conclusion of a conditional statement; ” No Romans are Philosophers” = “No Philosophers are Romans”
counter example
An exception to a proposed general rule that proves it false.
disjunction
logical operator that results in true when one or more of its operands are true
Fallacy
misconception resulting from false reasoning in logical argumentation
False dilemma
a situation in which only two alternatives are considered, when in fact there are other options
Faulty Cause (-and effect)
Correlation does not prove causation
given
an assumption that is taken for granted
hasty conclusion
inference drawn from insufficient premises, the premises may not have accounted for all possible contributing influences leading to the inference.
hypothesis
a proposal intended to explain certain facts or observations
hypothetical syllogism
” rule of inferenece”;If one implies the other, and that other implies a third, the first implies the third.
If and only If
used with the biconditional
Implication
the “If” clause; relationship between two propositions where the truth of one requires the truth of the other.
inverse
the statement formed when you negate the hypothesis and conclusion of a conditional statement
jingoism
A fallacy of irrelevancy; unwarranted, often exaggerated, patriotism or loyalty to a person , institution, or ideal without adequate logical justification
Logically Equivalent
possessing the same logical content. “If lisa is in France, she is in Europe” = “If Lisa is not in Europe, she is not in France.”
Modus Ponens
affirming the antecedent; if the weather forecast calls for rain ill need the umbrella. The forcast calls for rain. Therefore, ill need my umbrella
modus tollens
denying the consequent; if i have strep throat, then the culture will be positive. The culture was not positive. Therefore i dont have strep throat
negation
(logic) a proposition that is true if and only if another proposition is false
no
a negative
not
Expresses Logical negation; Takes the truth to fallacy. Usually precedes a statement.
or
Expresses Logical Disjunction; Results in true when one or more of its operands are true.
premise
a statement that is assumed to be true and from which a conclusion can be drawn
Proof
logical argument that shows a statement is true
Proposition
any statement in logic
reductio ad absurdum
disproof by showing that the consequences of the preposition are absurd or contradicting
Slippery Slope
Fallacy; states that a relatively small first step inevitably leads to a chain of related events culminating in some significant impac
some
term associated with the existential qualifier
Existential Qualifier
property or relation holds true to at least one member of the domain
stereotyping
attributing distorted or exaggerated characteristics of a class of items or people to a specific individual without proper justification.
strawman
logical fallacy based on misrepresentation of an opponents position
subset
a set whose members are members of another set
syllogism
deductive reasoning in which a conclusion is derived from two premises
truth table
a systematic arrangement of all possible truth values for a logical proposition
truth value
whether a statement is true or false
valid
logically convincing; sound; legally acceptable; effective; Ex. valid reasoning/passport
venn diagram
A diagram that shows relationships among sets of objects.
Symbol for intersection
Symbol for union
Symbol for proper subset (strictly smaller than)
Symbol for subset (equal to or smaller than)
Complement of set A (objects not in set A)
A’
Symbol for conjunction
Symbol for disjunction (note: you need to know exclusive disjunction too)
Symbol for negation (“not”)
Symbol for element of a set
finite elements in the set (not infinite)
finite set
infinite (endless) elements in the set (e.g. the set of real numbers is infinite)
infinite set
the set encompassing all elements
universal set
all elements in the universe that is not in A
complement of set A
Symbol for the null (empty) set
A set and its complement do not intersect (it is impossible for an element to be in a set and its complement)
A∩A’=∅
A set and its complement is equal to the universal set
A∪A’=U
the size (number of elements) of the set A
n(A)
the size of A equals the size of the universe minus everything not in A
n(A) = n(U)-n(A’)
Double Negation
∼(∼p) ∴(p)
Definition of Conjunction
p, q ∴(p ∧ q)
Conjunctive Simplification
p ∧ q ∴(p)
Disjunctive Addition
p ∴(p ∨ q)
Disjunctive Inference
p ∨ q, ∼q ∴(p)
De Morgan’s
∼(p ∨ q) ∴(∼p ∧ ∼q)
Chain Rule
p → q, q → r ∴(p → r)
Detachment
p → q, p ∴(q)
Modus Tollens
p → q, ∼q ∴(∼p)
Material Implication
p → q ∴(∼p ∨ q)
Alternate Exterior Angles
angles that lie outside the two lines on opposite sides of a transveral
Alternate Interior Angles
angles that lie between two lines on opposite sides on the transversal
Biconditional
conditional statement and converse
Conclusion
comes after “then”
Conditional
statement in “if” “then” format
Conjecture
conclusion reached by using inductive reasoning
Consecutive Int.
angles that lie between two lines on the same side of the transveral
Contrapositive
switches and negates the hypothesis and the conclusion
Converse
switches the hypothesis and conclusion
Corrseponding Angles
angles that lie in matching positions
Counterexample
shows conditonal if false (counter the conclusion)
Deductive Reasoning
process of reasoning logically from given statements to a conclusion
Hypothesis
comes after “if”
Inducitve Reasoning
reasoning based on patterns
Inverse
negates the hypothesis
Negation
not, denial of the statement
Transversal
a line that intersects two or more coplanar lines at different points
Truth Value
true or false