Give context-free grammars that generate formulas in propositional calculus, taking into account:

  • variables represented by single lowercase letter
  • Operations are conjunction (∧), disjunction (∨), negation (¬),implication (→) and double implication (↔)
  • Parse trees should reflect the following precedence order, 1: Formulas in parentheses 2: ¬ 3: → and ↔ 4: ∧, 5: ∨

My attempt led me to:

Create a set grammar G = (V; E; R; S)

with V = {S, a, b, (, ), ¬,→, ↔, ∧, ∨},

E = {a,b,(, ), ¬,→, ↔, ∧, ∨},

R = {S→ epsilon,





S→ (a∨b)|¬(a∨b),


  • $\begingroup$ You are neglecting the third requirement, that of precedence order. $\endgroup$ – Yuval Filmus Mar 25 '18 at 13:50
  • $\begingroup$ What is your question, exactly? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 25 '18 at 15:41
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Mar 25 '18 at 15:42
  • $\begingroup$ I think the method of how to do this is covered by Raphael's answer at the duplicate question. $\endgroup$ – D.W. Mar 25 '18 at 15:43