context-free-grammar - 使用上下文无关文法处理命题逻辑符号

Question

我目前正在尝试将上下文无关语法用于命题逻辑。

我想象这组终端将如下所示：

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

现在我需要定义一组产品，这可以帮助我实现所有合法的复合命题。谁能帮我？我真的不知道从哪里开始，大量的终端有点让我失望

Answer 1

从缩小问题的范围开始可能会有所帮助。具体来说，当唯一允许的符号是 p、q 和 ∧ 时，您可以为表达式编写 CFG 吗？在这种情况下，每个表达式要么是

• 单个命题变量，或
• 两个表达式的合取 (∧)。

那会给出这样的结果：

E → p | 问 | E ∧ E

现在，您将如何添加使用∨的能力？其他符号呢？看看你能不能从这里拿走。