Ch. 7 - Natural Deduction in Propositional Logic

Natural deduction

A method of deriving the conclusion of a valid argument in which each step is justified by a rule of inference.

Rules of inference

A rule by means of which the conclusion of an argument is derived from the premises.

Pure hypothetical syllogism

A valid argument form/rule of inference: “If p then q / If q then r // If p then r.”

Constructive dilemma

A valid argument form/rule of inference: “If p then q, and if r then s / p or r // q or s.”

Simplification

A valid rule of inference, “p and q // p.”

Conjunction

(1) A statement having a dot as its main operator; (2) a valid rule of inference: “p / q // p and q,”; comparison of with ordinary language; truth-functional definition of.

Addition

A valid rule of inference.

Double colon (::)

The metalogical symbol that designates logical equivalence.

Axiom of replacement

An axiom that states that logically equivalent expressions may replace one another in a proof sequence.

De Morgan’s rule

A valid rule of inference that allows tildes to be moved inside and outside of parentheses.

Commutativity

A valid rule of inference that provides for the rearrangement of conjunctions and disjunctions.

Associativity

A valid rule of inference that allows for the relocation of parentheses in conjunctions and disjunctions.

Double negation

A valid rule of inference that allows the introduction of deletion of pairs of negation signs.

Transposition

A valid rule of inference that allows the antecedent and consequent of a conditional statement to switch places if and only if both are negated.

Material implication

(1) The relation expressed by a truth-functional conditional; (2) a valid rule of inference that allows an implication sign to be replaced by a disjunction sign if and only if the antecedent is negated; comparison with ordinary language.

Material equivalence

(1) The relation expressed by a truth-functional biconditional; (2) a valid rule of inference that allows an equivalence statement to be replaced by a conjunctive statement or a disjunctive statement.

Exportation

A valid rule of inference that allows conditional statements having conjunctive antecedents to be replaced with conditional statements having conditional consequents, and vice versa.

Tautology

(1) A tautologous statement; (2) A rule of inference that eliminates redundancy in conjunctions and disjunctions.

Conditional proof

A method of proof that consists of assuming the antecedent of a required conditional statement on the first line of an indented sequence, deriving the consequent on a subsequent line, and then discharging the indented sequence in a conditional statement that exactly replicates the one to be obtained.

Indirect proof

A method of proof that consists of assuming the negation of a required statement on the first line of an indented sequence, deriving a contradiction on a subsequent line, and then discharging the indented sequence by asserting the negation of the assumed statement.