Part of the mathematical heritage of symbolic logic is the use of proofs or derivations to show how different relationships are connected. We begin with a basic set of rules that have already been established through the use of truth tables. These rules are of two kinds:
The first are inference rules that allow us to assert something as true on the basis of something else being assumed as true. These rules are most often seen as allowing either the elimination or the introduction of a signal. (For the sake of convenience, these are the only kind that we will consider in this course.)
The second are substitution rules that allow us to exchange one string for another.
A key difference between the two is that substitution rules can be used inside a string, but inference rules must deal only with the final letter of a string.
We can begin with a very simple set of rules to work with the signals A,C, and O:
PQA |- P or PQA |- Q -- A elim
P,Q |- PQA -- A int
PQA |- QPA or QPA |- PQA -- A subs
PQRAA |- PQARA or PQARA |- PQRAA -- AA subs
PQC, P |- Q -- C elim (note the importance of the left-to-right movement]
PQC |- QNPNC and QNPNC |- PQC -- C subs
PQO, PN |- Q or PQO, QN |- P -- O elim
P |- PQO or P |- QPO -- O int
PQO |- QPO and QPO |- PQO -- O subs
PQROO |- PQORO and PQORO |- PQROO -- OO subs
PQC |- PNQO and PNQO |- PQC -- CO subs
Taking the argument pattern
PQC, QNRO, RN |- PN
A derivation looks like this:
A numbered list pf premises, and a "show line" with the intended conclusion:
1. PQC
2. QNRO
3. RN \ show PN
Then there is a list of additional statements with the justification for each in terms of citing "call lines" and rules used to lead to the statement made:
4. QN...........2,3 O elim
5. QNPNC.....1 C subs
6. PN............4,5 C elim
This is an example of a direct derivation in which we move from the premises through to the conclusion by using our inference and substitution rules. Many patterns allow derivations with different combinations of steps. The same pattern could be worked through this way:
1. PQC
2. QNRO
3. RN \ show PN
4. QN..........2,3 O elim
5. PNQO......1 CO subs
6. PN...........4,5 O elim
Click on for more examples of simple direct derivations or go on to more rules and examples.
Go back to the starting page.