76 LOGIC, PART I: THE PROPOSITIONAL CALCULUS Chapter 2
Figure 2.9 Truth table deJining the Shefer stroke.involving A and - only. [Note, however, from your answers to Exercise 1qb) that
expressions using A and - only are lengthier and more complicated in form than
equivalent expressions in which all five connectives may be used.)] Because of this,
we say that the pair of connectives A and - is adequate for the propositional cal-
culus. A kind of question that is of interest to logicians (although of no practical
application in mainstream undergraduate mathematics) is whether there is, among
the 16 possible binary connectives [recall Exercise 2(b), Article 2.11 any single con-
nective that is adequate. The answer is "yes," as the following exercises demonstrate:
We define the connective /, called the Shefer stroke, by the table in Figure 2.9.
(a) Show that (pip) t-+ -p is a tautology.
(b) Show that (p/q)/(q/p) +N p A q is a tautology.
(c) Combine the results of Exercises lqa) and 1 l(a, b) to find expressions involving
the Sheffer stroke only that are equivalent to p v q, p + q, and p t, q. Conclude
from this that any statement form involving any of the five connectives of the
propositional calculus has an equivalent representation that uses the Sheffer
stroke only. [Note, however, that as in Exercise 1qb) the cost of this economy in
number of connectives is the necessity for much lengthier, more complicated,
and far less meaningful expressions.]
2.4 Analysis of Arguments for
Logical Validity, Part 1 (Optional)An interesting and useful application of the propositional calculus is the
analysis of certain kinds of arguments for logical validity. An argument
consists of a series of "given" statements, whose conjunction constitutes the
premise of the argument (the individual statements comprising the premise
may each be called a partial premise) and a conclusion.DEFINITION 1
An argument consisting of the premise p, ~p, A.. ~p, and a conclusion
9 is said to be a valid argument if and only if the statement form
(p, A p2 A... A pn) -+ 9 is a tautology.The requirement of Definition 1 is that the conclusion be true in all cases
in which each of the partial premises is true; that is, the conjunction of the