如何将这些子句简化为蕴涵图的蕴涵？

Question

对于一个大学项目，我必须从子句创建一个蕴涵图。

例如，从子句

(a or b)

，我可以确定这些含义：

• ←a -> b
• b -> a

但我真的找不到从该条款中添加的正确含义：

(a and b) or (¬a and b)

有什么方法可以简化它，以便我可以确定正确的含义？

尝试将“and”子句翻译成“or”子句，但没有成功..

Answer 1

正如@Mad Physicist所评论的，您可以使用德摩根定理将表达式转换为合取范式（CNF）。

(a and b) or (~a and b) = ~(~(a and b) and ~(~a and b))
                        = ~((~a or ~b) and {a and ~b))
                        = ~((~a and ~b) or (a and ~b) or ~b)
                        = ~(~a and ~b) and ~(a and ~b) and b
                        = (a or b) and (~a or b) and b
                        = b

对于较大的表达式，Tseytin 变换是保持中间表达式较小的常用方法：

原始表达式被分解为子表达式：

F := (a and b) or (not a and b)

转变为

F := x or y
x := a and b
y := ~a and b

每个子表达式都被翻译成一组 CNF 子句：

(~x or F) 
(~y or F)
(x or y or ~F)

(a or ~x)
(b or ~x)
(~a or ~b or x)

(~a or ~y)
(b or ~y)
(a or ~b or y)

输出

F

被断言为

true

。这导致：

(x or y)

(a or ~x)
(b or ~x)
(~a or ~b or x)

(~a or ~y)
(b or ~y)
(a or ~b or y)

此表格应该能让您得出其含义。