Section 1.2 Propositional Logic
27
This argument has the two hypotheses:
1. If George Washington was the first president of the United States, then
John Adams was the first vice president.
2. George Washington was the first president of the United States.
and the conclusion
John Adams was the first vice president.
A symbolic representation of this argument has the form
(A S B) ` A S B
A truth table or algorithm TautologyTest establishes that this argument is a tautology. The argument is valid; its form is such that the conclusion follows inevitably
from the hypotheses. In fact, this form of argument, known by its Latin name of
modus ponens (“method of assertion”), is one of the rules of reasoning we will use
to build propositional logic.
To test whether a wff P 1 ` P 2 ` P 3 ` … ` P n S Q is a tautology, we could
build a truth table or use algorithm TautologyTest. Instead, we will turn to formal
logic, which uses a system of derivation rules that manipulate wffs in a truthpreserving manner. You begin with the hypotheses P 1 , … , P n (assumed true) and
attempt to apply the manipulation rules in such a way as to end up with the conclusion Q (which must then also be true because truth is preserved under the rules).
Definition Proof sequence
A proof sequence is a sequence of wffs in which each wff is either a hypothesis
or the result of applying one of the formal system’s derivation rules to earlier
wffs in the sequence.
Using formal logic to prove that Q is a valid conclusion from P 1 , … , P n , we
must produce a proof sequence of the form
P 1
(hypothesis)
P 2
(hypothesis)
(
P n
(hypothesis)
wff 1 (obtained by applying a derivation rule to earlier wffs)
wff 2 (obtained by applying a derivation rule to earlier wffs)
(
Q
(obtained by applying a derivation rule to earlier wffs)
The derivation rules for a formal system must be carefully chosen. If they
are too powerful, then they won’t be truth preserving and we’ll be able to deduce
anything at all from a given set of hypotheses. If they are too weak, there will
be logical conclusions that we won’t be able to prove from given hypotheses. We
want a formal logic system that is correct (only valid arguments should be provable) and complete (every valid argument should be provable). In addition, the
27
This argument has the two hypotheses:
1. If George Washington was the first president of the United States, then
John Adams was the first vice president.
2. George Washington was the first president of the United States.
and the conclusion
John Adams was the first vice president.
A symbolic representation of this argument has the form
(A S B) ` A S B
A truth table or algorithm TautologyTest establishes that this argument is a tautology. The argument is valid; its form is such that the conclusion follows inevitably
from the hypotheses. In fact, this form of argument, known by its Latin name of
modus ponens (“method of assertion”), is one of the rules of reasoning we will use
to build propositional logic.
To test whether a wff P 1 ` P 2 ` P 3 ` … ` P n S Q is a tautology, we could
build a truth table or use algorithm TautologyTest. Instead, we will turn to formal
logic, which uses a system of derivation rules that manipulate wffs in a truthpreserving manner. You begin with the hypotheses P 1 , … , P n (assumed true) and
attempt to apply the manipulation rules in such a way as to end up with the conclusion Q (which must then also be true because truth is preserved under the rules).
Definition Proof sequence
A proof sequence is a sequence of wffs in which each wff is either a hypothesis
or the result of applying one of the formal system’s derivation rules to earlier
wffs in the sequence.
Using formal logic to prove that Q is a valid conclusion from P 1 , … , P n , we
must produce a proof sequence of the form
P 1
(hypothesis)
P 2
(hypothesis)
(
P n
(hypothesis)
wff 1 (obtained by applying a derivation rule to earlier wffs)
wff 2 (obtained by applying a derivation rule to earlier wffs)
(
Q
(obtained by applying a derivation rule to earlier wffs)
The derivation rules for a formal system must be carefully chosen. If they
are too powerful, then they won’t be truth preserving and we’ll be able to deduce
anything at all from a given set of hypotheses. If they are too weak, there will
be logical conclusions that we won’t be able to prove from given hypotheses. We
want a formal logic system that is correct (only valid arguments should be provable) and complete (every valid argument should be provable). In addition, the