Hi all,

I have been trying to solve this question for a while with no luck at all. This is related to Propositonal Logic. Can someone please help? Here's the question -

" The propositional formulas in prefix notation (PN) are defined as follows:
• every atom is a PN formula
• if A is a PN formula then
is a PN formula
• for any binary boolean connective op, if A, B are PN formulas then
op A B
is a PN formula.
An example of a formula in PN notation is
¬ _ p q
which in infix notation is ¬(p _ q).
Prove that if two strings A and B are PN formulas and A is a prefix of B,
then A = B.

Thanks in advance! :)

Make an argument regarding how many arguments are needed after a given formula in order to make it a PN formula.


Thanks for your reply. Would you please be able to explain how will that prove A=B?

Thanks again :)

Well, since A is a prefix of B, showing that A = B merely requires showing that A and B have the same length. So ask yourself, if you have a prefix notation formula p, is it possible to add stuff after the formula so that it still remains a prefix notation formula? Is there some string x such that both p and p x are valid prefix notation formulas? I think not. Prove why not.