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.
