Using context free grammar to work with propositional logic symbols

0
votes

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

1
context-free-grammardiscrete-mathematicspropositional-calculus

1 Answers

0
votes

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

  • a single propositional variable, or
  • a conjunction (∧) of two expressions.

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.