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?


Every formula in $p$ is equivalent to one of four formulas: true, false, $p$, $\lnot p$. This suggests having four different nonterminals, which generate exactly formulas which have this truth values. Calling these $T,F,P,N$, we have, for example, $$ T \to T \land T \mid T \lor S \mid S \lor T \mid P \lor N \mid N \lor P \mid (T) \mid \lnot F \mid \mathrm{true}, $$ where $S \to T \mid F \mid P \mid N$; this additional nonterminal is only used as shorthand.

In the same way, you can write rules that generate all tautologies over any fixed number of variables.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.