102 CHAPTER 2 Formal Logic
x
(a) _
z(b) Y
x
z(c) ZYz- Prove Theorem 1, the Principle of Induction on Formulas. (Hint: If ¢ V 4 is a formula
containing n occurrences of the logical operators, then 0 and V' each are formulas
containing fewer than n logical operators. By the inductive hypothesis, both 0 and Vf
are in J7, so by the closure rules, 0 v VV is in .F.) - (a) What is the relationship between the number of propositional connectives in a
formula and the number of parentheses? Prove your answer.
(b) What is the relationship between the number of A's, V's, -'s, and +'s in a for-
mula and the number of proposition letters in the formula? Prove your answer.
(c) What is the relationship between the number of -,'s in a formula and the number
of proposition letters in the formula? Prove your answer.
(d) How many left parentheses may a formula contain? Prove your answer.
(e) How many total symbols may a formula contain? Count each occurrence of each
proposition letter as one symbol, so (P123 A P123) contains five symbols-that is,
(, P123, A, P123, and ). For example, can a formula contain exactly two symbols?
Exactly 17 symbols? Prove your answer.
Truth and Logical Truth
The semantics of a language is the relationship between strings of symbols in a language
and their meaning. Consider a formula, such as4' = (-'p V q) --* (r -+ p)