Question

Construct a context-free grammar for the set of tautologies in $p$ - that is, the set of formulae in $\{p, \text{true}, \text{false}, \land, \lor, \lnot, (, )\}$ which evaluate to $\text{true}$ for any assignment to $p$.

My first step is to construct a CFG for all propositional formulae: $$ S \rightarrow S \land S \mid S \lor S \mid ( S ) \mid \lnot S\mid p \mid \text{true } \mid \text{ false} $$

What can I do from here?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top