Prove the number of symbols in a well-formed formula may be any
positive integer except 2, 3 or 6. (Each bracket is counted to be a symbol.)
I think these facts may come in handy:
Fact 1: Every well-formed formula has the same number of left brackets
as right brackets
Fact 2: Let W be any well formed formulae. Let b(W) be the number of times a binary connective occurs
and p(W) the number of times propositional variables occur in W. Then
p(W) = b(W) + 1
My definition of well formed formulae is 1)Propositional variables
2) if x and y are WFFs then so are (~x), (X^Y), (XvY), (X=>Y),(X<=>Y)
3 A string of sybols is not a WFF unless formed by a finite number of applications of 1) and 2
positive integer except 2, 3 or 6. (Each bracket is counted to be a symbol.)
I think these facts may come in handy:
Fact 1: Every well-formed formula has the same number of left brackets
as right brackets
Fact 2: Let W be any well formed formulae. Let b(W) be the number of times a binary connective occurs
and p(W) the number of times propositional variables occur in W. Then
p(W) = b(W) + 1
My definition of well formed formulae is 1)Propositional variables
2) if x and y are WFFs then so are (~x), (X^Y), (XvY), (X=>Y),(X<=>Y)
3 A string of sybols is not a WFF unless formed by a finite number of applications of 1) and 2
-
So, (x) is not a WFF? Fair enough. We can add 3 characters to any WFF by using x ---> (~x), so it remains to prove that we have WFFs of length 1, 5, and 9. Why? Because they cover all modulo classes of 3, and are the least length WFF of each modulo class, according to the proposition. Clearly x is a WFF (given x is a propositional variable), so we have 1. This gives us 4, 7, 10, 13, ... as follows:
(~x)
(~(~x))
(~(~(~x)))
(~(~(~(~x))))
...
For 5, we have any of the other atomic WFF, for example (XvY). Again, this gives us:
(~(XvY))
(~(~(XvY)))
(~(~(~(XvY))))
...
for 8, 11, 14, ... For 9, we can make something like this:
(Xv(YvZ))
and again, we can get 12, 15, 18, ...
(~(Xv(YvZ)))
(~(~(Xv(YvZ))))
(~(~(~(Xv(YvZ)))))
...
That covers every number except 2, 3, 6. To prove that you can't get 2, 3, 6, note that the application of each rule increases the length of the formula by at least 3. If we apply no rules, we have propositional variables of length 1. Apply one rule, we have a string of at least length 4, which eliminates 2 and 3 right off the bat. In applying one rule, we can only have propositional variables substituted for X and Y, so it means we are limited to statements of the form:
(~X), (X^Y), (XvY), (X=>Y), (X<=>Y)
where X and Y are length 1 WFFs (propositional variables). All of these have length 4 or 5. If we apply another rule, we must add at least 3 to the length, which means we have at least 7 in our WFF after two rules. Thus, we can't get 6 either. Therefore, we can get every number except 2, 3, and 6.
Hope that helps!
(~x)
(~(~x))
(~(~(~x)))
(~(~(~(~x))))
...
For 5, we have any of the other atomic WFF, for example (XvY). Again, this gives us:
(~(XvY))
(~(~(XvY)))
(~(~(~(XvY))))
...
for 8, 11, 14, ... For 9, we can make something like this:
(Xv(YvZ))
and again, we can get 12, 15, 18, ...
(~(Xv(YvZ)))
(~(~(Xv(YvZ))))
(~(~(~(Xv(YvZ)))))
...
That covers every number except 2, 3, 6. To prove that you can't get 2, 3, 6, note that the application of each rule increases the length of the formula by at least 3. If we apply no rules, we have propositional variables of length 1. Apply one rule, we have a string of at least length 4, which eliminates 2 and 3 right off the bat. In applying one rule, we can only have propositional variables substituted for X and Y, so it means we are limited to statements of the form:
(~X), (X^Y), (XvY), (X=>Y), (X<=>Y)
where X and Y are length 1 WFFs (propositional variables). All of these have length 4 or 5. If we apply another rule, we must add at least 3 to the length, which means we have at least 7 in our WFF after two rules. Thus, we can't get 6 either. Therefore, we can get every number except 2, 3, and 6.
Hope that helps!