Deriving a Formula From a Simple Artificial Language

Question

The three rules of the language are:

The letters P and Q are sentences. If φ and ψ are sentences, then Nφ and (Iφψ) are sentences. Nothing else is a sentence.

(no more information was given about the language)

It then asks whether '(I(IPP)P)' is a sentence, and whether 'N(INNPNNQ)' is a sentence. I'm unsure how to unsure the first questions, due to my wondering whether 'IP' counts as a valid sentence (could the 'ψ' in the (Iφψ) rule be empty?), and whether, although '(IP)' and '(IPP)' may be legitimate sentences, whether putting (IPP) in the middle of (IP) is allowed. I'm guessing not, but I want to make sure. I also think the last one is a sentence too, but I'm not sure, and any help on how to grasp this sort of question would be much appreciated. Thanks!

Answer 1

Let me call $N\varphi$ rule 1 and $(I\varphi \psi)$ rule 2.

We know that $P$ is a sentence. Then, by rule 2 with $\varphi = P$ and $\psi = P$, we have that $(IPP)$ is a sentence. Then we can use rule 2 again with $\varphi = (IPP)$ and $\psi = P$ to obtain $(I(IPP)P)$, so this is a sentence. Can you do the second one from there?

Answer 2

Since "nothing else is a sentence" and neither of the two rules can possibly force the empty string to be a sentence, then the empty string is not a sentence.

IP is not a sentence because every sentence is either P or Q (and neither of these are the same string as IP) or starts with N (which IP doesnt) or starts with ( (which IP doesn't either).

(IP) is not a sentence either. Starting with (I is okay, but then there need to come two complete sentences before the ), and since there is only one letter in between, one of those sentences would need to be empty. And we already know that the empty string isn't a sentence.

(IPP) is a good sentence because if we set $\varphi=\mathtt P$ and $\psi=\mathtt P$ (which we know are sentences), then $\mathtt ( \mathtt I \varphi \psi \mathtt )$ is (IPP). So by the last of the rules, (IPP) is a sentence.

As for (I(IPP)P), what happens if you set $\varphi=\mathtt{(IPP)}$ and $\psi=\mathtt P$ (both of which you now know are sentences)?