I have to prove the following task: "Prove that for every prefix of a well-formed propositional logic formula the number of left brackets is greater or equal than the number of right brackets."
The first exercise was to prove that a well-formed propositional logic has the same number of left and right brackets. That was pretty easy. But I do not know how to prove that.
Edit:
Definition of a well-formed formula:
Every propositional atom p,q,r,... and p1,p2,p3,... is a wellformed formula.
¬: If φ is a well-formed formula, then so is (¬φ).
∧: If φ and ψ are well-formed formulas, then so is (φ∧ψ).
∨: If φ and ψ are well-formed formulas, then so is (φ∨ψ).
→: If φ and ψ are well-formed formulas, then so is (φ → ψ)
Definition with Backus Naur Form BNF:
φ ::= p | (¬φ) | (φ∧φ) | (φ∨φ) | (φ → φ)
Can somebody explain me the following questions:
-
What is the prefix of a well formed formula?
-
Why is it possible that the number of left brackets could be greater than the number of right brackets?
-
How could I prove that?
Thank you.
Best Answer
A prefix of a formula is just some set of leftmost characters. So if $(A \wedge B) \vee C$ is well-formed in your notation, $(,$ and $(A \wedge B$ are both prefixes. Note that both these prefixes have more left brackets than right.
The usual way to prove these is by induction on complexity of the formula. First go through the atomic formulas you have and note that it is true. Then if you have a composition rule that says if $A$ and $B$ are well formed then $(A \wedge B)$ is also well formed, you note that any prefix of the new formula is either $($ plus a prefix of $A$, so will have at least as many more lefts than rights, or $(A$, (maybe with the $\wedge$), or $(A\wedge$ and a prefix of $B$. In any case you wind up with at least as many lefts as rights. You have to go through all the ways of building up formulas and show that the property is conserved.