4

给定一组 n 个元素U和一组 m 个属性P，其中 P 的每个元素定义一个从 U 到布尔值的函数。

给定以下形式的两个复合逻辑表达式（递归定义）：

p1 : true iff p1(x) is true
e1 and e2 : means e1 and e2 are both true
e1 or e2 : means e1 and e2 are not both false
not e1 : true iff e1 is false
(e1) : true iff e1

这些逻辑表达式被解析为表达式语句（解析树）。

假设对于任何 p1、p2：所有四个集合（p1 和 p2）、（p1 和非 p2）、（非 p1 和 p2）、（非 p1 和非 p2）都是非空的。

我想确定逻辑表达式 L1 是否是 L2 的子集。即对于 U 中的每个元素 x，如果 L1(x) 为真，则 L2(x) 为真。

例如：

is_subset(not not p1, p1) is true
is_subset(p1, p2) is false
is_subset(p1 and p2 and p3, (p1 and p2) or p3) is true

我想我需要以某种方式“规范化”解析树，然后比较它们。任何人都可以概述一种方法或勾勒出一个架构吗？

4

3 回答 3

1

由于您不对对象 (x) 做任何事情，因此您似乎需要命题逻辑，其中p1to的所有真值组合pn都是可能的。

所以本质上你想在命题逻辑中做定理证明。

Youris_subset(e1,e2)转换为逻辑运算符e1 implies e2，与not e1 or e2. 要知道这些是否普遍适用，您可以使用诸如DPLL之类的可满足性检查算法来检查否定是否不可满足。

这只是一个起点，还有许多其他选项可以证明命题逻辑中的定理。

于 2012-11-27T06:36:11.093 回答
0

我认为您的讲师本质上是希望您实施Quine-McCluskey 算法 请注意，正如另一个答案所暗示的那样，执行时间增长得非常快，因为问题是-NP Hard。

于 2012-11-26T00:04:27.443 回答
0

您可以将每个公式转换为析取范式，并查找其中一个是否包含另一个中的连接子句的子集。这种方法的复杂性随着提到的 pn 数量的指数而增加。

于 2012-11-25T23:56:39.320 回答