Member Avatar for logicalz

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
¬A
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! :)

  • 2 Contributors
  • 3 Replies
  • 88 Views
  • 5 Days Discussion Span
  • Latest Post Latest Post by sarehu
Member Avatar for sarehu

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

Member Avatar for logicalz

Hi,

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

Thanks again :)

Member Avatar for sarehu

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.