welljormed strings. They will be defined in a recursive way. We begin with
the
ATOMS: P, Q, and R are called atoms. New atoms are formed by appending
primes onto the right of old atoms-thus, R', Q", P"', etc. This gives
an endless supply of atoms. All atoms are well-formed.Then we have four recursiveFORMATION RULES: If x and yare well-formed, then the following four
strings are also well-formed:(1) -x
(2) < xAy>
(3) < xvy>
(4) <x:::>y>For example, all of the following are well-formed:P
-P
--P
Q'
-Q'
<PA-Q'>
-<PA-Q'>
<--P:::>Q'>
<-<PA-Q'>V< --P:::>Q'»atom
by (1)
by (1)
atom
by (1)
by (2)
by (1)
by (4)
by (3)The last one may look quite formidable, but it is built up straightforwardly
from two components-namely the two lines just above it. Each of them is
in turn built up from previous lines ... and so on. Every well-formed string
can in this way be traced back to its elementary constituents-that is, atoms.
You simply run the formation rules backwards until you can no more. This
process is guaranteed to terminat(~, since each formation rule (when run
forwards) is a lengthening rule, so that running it backwards always drives
you towards atoms.
This method of decomposing strings thus serves as a check on the
well-formedness of any string. It is a top-down decision procedure for well-
formedness. You can test your understanding of this decision procedure by
checking which of the following strings are well-formed:(1) <P>
(2) <-P>
(3) <PAQAR>
(4) <PAQ>
(5) «PAQ>A<Q-AP»
(6) <PA-P>
(7) «Pv<Q:::>R»A<-Pv--R'»
(8) <PAQ>A<QAP>182 The Propositional Calculus