Given the alphabet of ${P, P_1, …, Q, Q_1, …, R, R_1, …, …, ¬, ∧, ∨, →, (, ) }$, write a Backus normal form grammar that generates all legal propositional formulas. For the start it is given that
digit ::= $“0” | “1” | “2” | “3” | … | “8” | “9”$
integer ::= digit | digit, integer
$A ::= P \mid P, \text{integer} \quad $ // generates $P, P_1, …$
$B ::= Q \mid Q, \text{integer} \quad $ // generates $Q, Q_1, …$
$C ::= R \mid R, \text{integer} \quad$ // generates $R, R_1, …$
It suffices to generate fully parenthesized formulas that have no omission of parentheses. You may use $“…”$ to indicate omission as in the above BNF grammar.
My Progress: I have managed to understand the Backus normal form topic and its applications, but I had struggled to associate Backus normal form grammar with legal propositional rules. Obviously, these rules are well-known and understandable, but I did not realize how to indicate fully parenthesized formulas?
Best Answer
Let us first write the BNF grammar of all atomic propositional formulas (denoted by $\mathcal{A}$):
\begin{align} \mathcal{A} ::= A \mid B \mid C \mid \dots \end{align}
where $A$, $B$, $C$, $\dots$ are defined in the original post. Note that this definition does not require any form of induction, apart from the one used in definition of integer in the original post.
Then, the BNF grammar of all propositional formulas (denoted by $\mathcal{F}, \mathcal{G}$, $\dots$) is the following:
\begin{align} \mathcal{F}, \mathcal{G} ::= \mathcal{A} \mid \lnot \mathcal{F} \mid (\mathcal{F} \land \mathcal{G}) \mid (\mathcal{F} \lor \mathcal{G}) \mid (\mathcal{F} \to \mathcal{G}) \end{align}
Note that, according this definition, $P \to Q$ is not a propositional formula, because parentheses are missing. The correct propositional formula in this case is $(P \to Q)$.
This massive use of parentheses is required to avoid ambiguous expressions such as $P \land Q \lor R$ can be considered as propositional formulas. Indeed, in $P \land Q \lor R$ it is not clear what is the principal connective. Correct propositional formulas are $((P \land Q) \lor R)$ and $(P \land (Q \lor R))$, where no ambiguity arises.