Section 1.2 Propositional Logic
31
home free. Ah, look at the form of step 7; it’s a disjunction, and the implication rule
says that we can transform a disjunction of a certain form into an implication. The
disjunction must have a negated wff on the left. We can do that:
8. C′ ~ D 7, comm
9. C S D 8, imp
so
10. D 5, 9, mp
As in Example 14, proof sequences involve a certain amount of rewriting just
because you can and a certain amount of keeping an eye on the desired goal and
what it would take to get there. Although not as mechanical as constructing a truth
table, the strict rules of the game nevertheless provide a more or less mechanical
way to construct the proof sequence. There are only a certain number of legitimate
things that can be done at any one point in the sequence. If one choice seems to
lead down a blind alley, go back and make another. Also, there may be more than
one correct proof sequence; as a relatively trivial instance, steps 6 and 7 could
have been done before step 5 in Example 14.
An analogy with programming, if not taken too literally, may be helpful. In
traditional programming, you have known input, a desired output, and you write
code to transform the given input into the desired output. You figure out the sequence of statements that will accomplish this transformation, and each program
statement in that sequence must conform to the exact syntax rules of the programming language you are using, be it C++, Java, Python, or whatever. In propositional logic, you have known “input” (the hypotheses), a desired “output” (the
conclusion), and you write “code statements” (a sequence of wffs) to transform
the hypotheses into the conclusion. The sequence of code statements, or at least
their justification, must conform to the exact syntax of the derivation rules for
propositional logic.
pRaCtiCe 11 Using propositional logic, prove the validity of the argument.
[(A ~ B′) S C] ` (C S D) ` A S D
tAbLe 1.13
derivation Hints
1. Modus ponens is probably the most intuitive inference rule. Think often about
trying to use it.
2. Wffs of the form (P ` Q)′ or (P ~ Q)′ are seldom helpful in a proof sequence. Try
using De Morgan’s laws to convert them into P′ ~ Q′ and P′ ` Q′, respectively,
which breaks out the individual components.
3. Wffs of the form P ~ Q are also seldom helpful in a proof sequence because
they do not imply either P or Q. Try using double negation to convert P ~ Q to
(P′)′ ~ Q, and then using implication to convert to P′ S Q.
31
home free. Ah, look at the form of step 7; it’s a disjunction, and the implication rule
says that we can transform a disjunction of a certain form into an implication. The
disjunction must have a negated wff on the left. We can do that:
8. C′ ~ D 7, comm
9. C S D 8, imp
so
10. D 5, 9, mp
As in Example 14, proof sequences involve a certain amount of rewriting just
because you can and a certain amount of keeping an eye on the desired goal and
what it would take to get there. Although not as mechanical as constructing a truth
table, the strict rules of the game nevertheless provide a more or less mechanical
way to construct the proof sequence. There are only a certain number of legitimate
things that can be done at any one point in the sequence. If one choice seems to
lead down a blind alley, go back and make another. Also, there may be more than
one correct proof sequence; as a relatively trivial instance, steps 6 and 7 could
have been done before step 5 in Example 14.
An analogy with programming, if not taken too literally, may be helpful. In
traditional programming, you have known input, a desired output, and you write
code to transform the given input into the desired output. You figure out the sequence of statements that will accomplish this transformation, and each program
statement in that sequence must conform to the exact syntax rules of the programming language you are using, be it C++, Java, Python, or whatever. In propositional logic, you have known “input” (the hypotheses), a desired “output” (the
conclusion), and you write “code statements” (a sequence of wffs) to transform
the hypotheses into the conclusion. The sequence of code statements, or at least
their justification, must conform to the exact syntax of the derivation rules for
propositional logic.
pRaCtiCe 11 Using propositional logic, prove the validity of the argument.
[(A ~ B′) S C] ` (C S D) ` A S D
tAbLe 1.13
derivation Hints
1. Modus ponens is probably the most intuitive inference rule. Think often about
trying to use it.
2. Wffs of the form (P ` Q)′ or (P ~ Q)′ are seldom helpful in a proof sequence. Try
using De Morgan’s laws to convert them into P′ ~ Q′ and P′ ` Q′, respectively,
which breaks out the individual components.
3. Wffs of the form P ~ Q are also seldom helpful in a proof sequence because
they do not imply either P or Q. Try using double negation to convert P ~ Q to
(P′)′ ~ Q, and then using implication to convert to P′ S Q.