Section 1.4 Predicate Logic
69
In addition to logical thinking in its pure sense, the notions of formal rules of
inference have two very direct applications to computer science. An entire system
of programming, and some programming languages, are based on applying rules
of inference. We will see such a language in Section 1.5. Similarly, rules of inference can be applied to formally prove program correctness, leading to increased
confidence that code is error-free. We’ll look at some of the inference rules for
program correctness in Section 1.6.
eXAMPLe 36
The hunting grounds of a medieval king were forbidden to commoners, and anyone caught poaching the royal deer was subject to death. The hapless poacher was,
however, granted a means to choose the manner of death. He (or she) was allowed
to make a final statement. If the statement were judged to be true, death would be
by beheading with a sword; if false, death would come by arrow shot from the
bow of the best royal marksman. One day a particularly clever poacher was apprehended and allowed the usual final statement. The poacher said, “I will be shot
to death by an arrow.”
The king’s court faced a conundrum. If the poacher were shot to death by an
arrow, then the statement he made would prove to be true, in which case he should
have been beheaded. But if he were beheaded, then the statement he made would
be false, in which case he should have been shot by an arrow. Unable to decide the
manner of death, the court appointed the clever poacher to the post of king’s press
secretary, where he served happily for many years.
This sort of paradox—a riddle with no solution—has to be carefully constructed,
and we will not spend any more time reflecting on the potential shortcomings of
classical logic systems that it may reveal.
S e c t I o n 1 . 4 Review
tecHnIQueS
• Apply derivation rules for predicate logic.
• Use predicate logic to prove the validity of a verbal argument.
MAIn IdeA
• The predicate logic system is correct and complete; valid arguments and only valid arguments
are provable.
W
W
eXeRcISeS 1.4
For Exercises 1–6, decide what conclusion, if any, can be reached from the given hypotheses and justify your
answer.
1. All flowers are plants. Pansies are flowers.
2. All flowers are plants. Pansies are plants.
3. All flowers are red or purple. Pansies are flowers. Pansies are not purple.
4. Some flowers are purple. All purple flowers are small.
5 Some flowers are red. Some flowers are purple. Pansies are flowers.
6. Some flowers are pink and have thorns. All thorny flowers smell bad. Every flower that smells bad is a
weed.
69
In addition to logical thinking in its pure sense, the notions of formal rules of
inference have two very direct applications to computer science. An entire system
of programming, and some programming languages, are based on applying rules
of inference. We will see such a language in Section 1.5. Similarly, rules of inference can be applied to formally prove program correctness, leading to increased
confidence that code is error-free. We’ll look at some of the inference rules for
program correctness in Section 1.6.
eXAMPLe 36
The hunting grounds of a medieval king were forbidden to commoners, and anyone caught poaching the royal deer was subject to death. The hapless poacher was,
however, granted a means to choose the manner of death. He (or she) was allowed
to make a final statement. If the statement were judged to be true, death would be
by beheading with a sword; if false, death would come by arrow shot from the
bow of the best royal marksman. One day a particularly clever poacher was apprehended and allowed the usual final statement. The poacher said, “I will be shot
to death by an arrow.”
The king’s court faced a conundrum. If the poacher were shot to death by an
arrow, then the statement he made would prove to be true, in which case he should
have been beheaded. But if he were beheaded, then the statement he made would
be false, in which case he should have been shot by an arrow. Unable to decide the
manner of death, the court appointed the clever poacher to the post of king’s press
secretary, where he served happily for many years.
This sort of paradox—a riddle with no solution—has to be carefully constructed,
and we will not spend any more time reflecting on the potential shortcomings of
classical logic systems that it may reveal.
S e c t I o n 1 . 4 Review
tecHnIQueS
• Apply derivation rules for predicate logic.
• Use predicate logic to prove the validity of a verbal argument.
MAIn IdeA
• The predicate logic system is correct and complete; valid arguments and only valid arguments
are provable.
W
W
eXeRcISeS 1.4
For Exercises 1–6, decide what conclusion, if any, can be reached from the given hypotheses and justify your
answer.
1. All flowers are plants. Pansies are flowers.
2. All flowers are plants. Pansies are plants.
3. All flowers are red or purple. Pansies are flowers. Pansies are not purple.
4. Some flowers are purple. All purple flowers are small.
5 Some flowers are red. Some flowers are purple. Pansies are flowers.
6. Some flowers are pink and have thorns. All thorny flowers smell bad. Every flower that smells bad is a
weed.