Section 2.1 – Valid and Sound Arguments
Logical Consequence – when a statement follows validly from given premises, it
is also a logical consequence of the premises
Section 2.2 – Methods of Proof
Identity Elimination – given b=c, anything that holds true of b also holds true of c
Identity Introduction – a=a can always be inferred from any set of premises,
even no premises
Identity Symmetry – given a = b, b = a
*Transitivity of Identity – if a = b, and b = c, then a = c
Chapter 4 – The Logic of Boolean Connectives
Truth-functional – describes connectives, which, when used in a complex
sentence, allows one to know the truth value of the complex sentence simply by
looking at the truth values of the sentence's immediate constituents.
Examples include ^, v, and the negation connective.
Section 4.1 – Tautologies and Logical Truth
Logical necessity – sentences that cannot be false, no matter the premises. Such
a sentence is true in every logically possible circumstance.
Ex. a = a
Three forms of derivation:
2) Truth tables
3) If one can prove a sentence using no premises whatsoever
Logical possibility – a sentence that could be (or could have been) true, at least
on logical grounds
Ex. Going faster than the speed of light. Tautology – a simple kind of logical necessity; it is any sentence whose truth table
has only T's in the column under its main connective.
All tautologies are logically necessary; their truth is guaranteed by the structure
and meaning of the truth-functional connectives, independent of the truth values of
its constituent sentences.
However, not all logically necessary claims are tautologies.
Ex. a = a
Section 4.2 – Logical and Tautological Equivalence
Logical Equivalence – sentences that have the same truth values in every
possible circumstance; having the same truth conditions
Tautological Equivalence – sentences that can be seen to be equivalent simply in
virtue of the meanings of the truth-functional connectives.
All tautologically equivalent sentences are logically equivalent, but the reverse is
usually not true.
1) The negation of a conjunction is logically equivalent to the disjunction of the
negations of the original conjuncts.
2) The negation of a disjunction is equivalent to the conjunction of the negations
of the original disjuncts
Section 4.3 – Logical and Tautological Consequence
Logical Consequence – sentence S is a logical consequence of set of premises
P1... Pn, if it is impossible for the premises all to be true while the conclusion S is
Logical truths are sentences that are a logical consequence of a set of
Logically equivalent sentences are sentences that are a logical consequence of
Tautological consequence – a strict form of logical consequence; P is a tautological consequence of Q when all instances in which Q is true are also
instances in which P is true.
Section 4.5 – Pushing Negation Around
Substitution of Equivalents – if P and Q are logically equivalent, then the results
of substituting one for the othe in the context of a larger sentence are also logically
Ex. If P is logically equivalent to Q, then S(P) is logically equivalent to S(Q).
Examples of substitution of logical equivalents:
1) Associativity of Conjunctions
A sentence P ^ (Q ^ R) is logically equivalent to (P ^ Q) ^ R, which is in turn
equivalent to P ^ Q ^ R.
2) Associativity of Disjunctions
A sentence P v (Q v R) is logically equivalent to (P v Q) v R, which is in turn
equivalent to P v Q v R.
3) Commutativity of Conjunctions
A conjunction P ^ Q is logically equivalent to Q ^ P.
4) Commutativity of Disjunctions
A disjunction P v Q is logically equivalent to Q v P.
5) Idempotence of Conjunctions
A conjunction P ^ P is equivalent to P.
Thus, with Commutativity, P ^ Q ^ P is equivalent to P ^ Q.
6) Idempotence of Disjunctions
A disjunction P v P is equivalent to P.
Thus, with Commutativity, P v Q v P is equivalent to P v Q.
Section 4.6 – Conjunctive and Disjunctive Normal Forms Distributive laws:
1) Distribution of ^ over v: P ^ (Q v R) is logically equivalent to (P ^ Q) v (P ^ R)
2) Distribution of v over ^: P v (Q ^ R) is logically equivalent to (P v Q) ^ (P v R)
Section 5.1 – Valid Inference Steps
1) Conjunction elimination (simplification)
From P ^ Q, we can infer either P or Q.
2) Conjunction introduction
From P and Q, we can infer P ^ Q.
3) Disjunction introduction (addition)
From P, we can infer P v Q.
Section 5.2 – Proof by Cases
Disjunction elimination (proof by case):
If our goal is S, and we have proven P v Q, then if