Propositional Logic - Language

DEFINITIONS

Definition 1.1. The symbols of L_P are:
(1) Parentheses: ( and ).
(2) Connectives: : ¬ and →.
(3) Atomic formulas: A0, A1, A2, . . . , An, . . .
We still need to specify the ways in which the symbols of L_P can
be put together.

Definition 1.2. The formulas of L_P are those finite sequences or strings of the symbols given in Definition 1.1 which satisfy the following
rules:
(1) Every atomic formula is a formula.
(2) If α is a formula, then (¬α) is a formula.
(3) If α and β are formulas, then (α → β) is a formula.
(4) No other sequence of symbols is a formula.

PROBLEMS AND PROPOSITIONS

Problem 1.1. Why are the following not formulas of L_P? There
might be more than one reason. . .
(1) A₋₅₆
(2) (Y → A)
(3) (A7 ← A4)
(4) A7 → (¬A5))
(5) (A₈A₉ → A_1043998
(6) (((¬A1) → (A_l → A₇) → A₇)
Symbols not in the language, unbalanced parentheses, lack of
connectives. . .

Problem 1.2. Show that every formula of L_P has the same number
of left parentheses as it has of right parentheses.
The key idea is to exploit the recursive structure of Definition 1.2 and proceed by induction on the length of the formula or on the number of connectives in the formula. As this is an idea that will be needed repeatedly in Parts I, II, and IV, here is a skeleton of the argument in this case:
Proof. By induction on n, the number of connectives (i.e. occurrences of ¬ and/or →) in a formula φ of L_P, we will show that any formula φ must have just as many left parentheses as right parentheses.
Base step: (n = 0) If φ is a formula with no connectives, then it
must be atomic. (Why?) Since an atomic formula has no parentheses
at all, it has just as many left parentheses as right parentheses.
Induction hypothesis: (n ≤ k) Assume that any formula with n ≤ k connectives has just as many left parentheses as right parentheses.
Induction step: (n = k + 1) Suppose φ is a formula with n = k +1
connectives. It follows from Definition 1.2 that φ must be either
(1) (¬α) for some formula α with k connectives or
(2) (β → γ ) for some formulas β and γ which have ≤ k connectives each.
(Why?) We handle the two cases separately:
(1) By the induction hypothesis, φ has just as many left parentheses
as right parentheses. Since φ, i.e. (¬α), has one more
left parenthesis and one more right parentheses than α, itmust
have just as many left parentheses as right parentheses as well.
(2) By the induction hypothesis, β and γ each have the same number of left parentheses as right parentheses. Since φ, i.e.
(β → α), has one more left parenthesis and one more right
parnthesis than β and γtogether have, it must have just as
many left parntheses as right parentheses as well.
It follows by induction that every formula φ of L_P has just as many
left parentheses as right parentheses.

Problem 1.3. Suppose α is any formula of L_P. Let l(α) be the length of α as a sequence of symbols and let p(α) be the number of parentheses (counting both left and right parentheses) in α. What are the minimum and maximum values of p(α)/l(α)?
Compute p(α)/l(α) for a number of examples and look for patterns. Getting a minimum value should be pretty easy.

Problem 1.4. Suppose α is any formula of L_P. Let s(α) be the number of atomic formulas in α (counting repetitions) and let c(α) be the number of occurrences of → in α. Show that s(α) = c(α) + 1.
Proceed by induction on the length of or on the number of connectives in the formula.

Problem 1.5. What are the possible lengths of formulas of L_P ?
Prove it.
Construct examples of formulas of all the short lengths that you can, and then see how you can make longer formulas out of shortones.

Problem 1.6. Find a way for doing without parentheses or other
punctuation symbols in defining a formal language for propositional
logic.
Hewlett-Packard sells calculators that use such a trick. A similar
one is used in Defiition 5.2.

Proposition 1.7. Show that the set of formulas of L_P is countable.
Observe that L_P has countably many symbols and that every
formula is a finite sequence of symbols. The relevant facts from set
theory are given in Appendix A.

Problem 1.8. Take a couple of English sentences with several connectives
and translate them into formulas of L_P. You may use ∧, ∨, and ↔ if appropriate.
Stick several simple statements together with suitable connectives.

Problem 1.9. Write out ((α ∨ β )∧( β → α)) using only ¬ and →.
This should be straightforward.

Problem 1.10. Write out ¬(α ↔ ¬δ)^β → ¬α → γ first with the
missing parentheses included and then as an official formula of L_P .
Ditto.