Recursive Definition of Formula Length: Learn the Basics | Logics Course Help

[blackdvl666]

ok guys this is from my logics course!

this question may be very simple but i am just gettin stuck

give a recursive definition of the length of a well formed formula that is of the number of the symbols occurring in it. For example length of (p^(~q)) is 8.

 

[CompuChip]

OK, so if p is an atomic formula, the length is 1.
What possibilities do you have to make a new wff out of two wffs p and q?
For example, if p is a wff of length n, then (~p) is one of length n + 3.
If p and q are wff's of length n and m, respectively, then (p^q) is of length m+n+3.

 

[piercas]

A recursive definition is a way of defining a mathematical object or concept in terms of itself. In this case, we can define the length of a well-formed formula as follows:

1. The length of a variable (e.g. p, q) is 1.
2. The length of a logical constant (e.g. ^, ~) is 1.
3. The length of a well-formed formula that is a combination of two or more well-formed formulas (e.g. p^(~q)) is defined as the sum of the lengths of the individual formulas, plus 1 for each logical constant used to combine them.

Using this definition, we can see that the length of (p^(~q)) is calculated as follows:

length(p^(~q)) = length(p) + length(~q) + 1
= 1 + (length(q) + 1) + 1
= 1 + (1 + 1) + 1
= 4 + 1
= 5

Therefore, the length of (p^(~q)) is 5, as expected.

It is important to note that this recursive definition can be applied to any well-formed formula, no matter how complex it may be. It also allows us to easily calculate the length of a formula without having to manually count the symbols, which can be helpful in more complicated formulas.

I hope this helps clarify the concept for you. If you have any further questions, don't hesitate to ask your instructor or classmates for assistance. Good luck with your studies!