context-free-grammardiscrete-mathematicspropositional-calculus

Using context free grammar to work with propositional logic symbols


i'm currently trying to use a context free grammar for propositional logic.

Im imagining that the set of terminals will looks like this:

T=(q,p,¬,∧,∨,→,⟷).

Now what i need is to define a set of productions, that can help me in achieving all legal compound propositions. Can anyone help me? I really dont know where to start, the high amount of terminals is kinda throwing me off


Solution

  • It might help to start by reducing the scope of your problem. Specifically, can you write a CFG for expressions when the only allowed symbols are p, q, and ∧? In that case, every expression is either

    That would give something like this:

    E → p | q | E ∧ E

    Now, how would you add in the ability to use ∨? How about the other symbols? See if you can take it from here.