0

我昨天在更改下发布了这个问题，但没有意识到我的帐户在 9 个月后仍然有效，抱歉重复发布，我已经修复了 jellybean 指出的示例中的错误，我将进一步详细说明问题的背景.

我正在尝试处理在python中表示为嵌套列表和字符串的一阶逻辑公式，以便它处于析取范式，

IE

[
    '&', 
    ['|', 'a', 'b'], 
    ['|', 'c', 'd']
]

变成

[
    '|',
    [
        '|', 
        ['&', 'a', 'c'], 
        ['&', 'b', 'c']
    ], 
    [
        '|', 
        ['&', 'a', 'd'], 
        ['&', 'b', 'd']
    ]
]`

在哪里或并且|是和。&

目前我正在使用递归实现，它对公式进行多次传递，直到在“ands”的列表参数中找不到任何嵌套的“或”符号。它用于处理一组嵌套公式，表示为通用计算树逻辑的字符串和列表，因此它不仅具有|s 和&s，而且具有时间运算符。

这是我的实现，performDNF(form)是切入点。现在，dnfDistributivity()它对适用于较小输入的公式执行单次传递，但是当您使用较大的输入时，while 循环检查函数 ( ) 在s 内checkDistributivity()找不到s 并终止。帮助任何人，这让我发疯。|&

def dnfDistributivity(self, form):
    if isinstance(form, type([])):
        if len(form) == 3:
            if form[0] == '&':
                if form[1][0] == '|':
                    form = [
                               '|', 
                               ['&', form[2], form[1][1]], 
                               ['&', form[2], form[1][2]]
                           ]
                elif form[2][0] == '|':
                    form = [
                                '|', 
                                ['&', form[1], form[2][1]], 
                                ['&', form[1], form[2][2]]
                           ]
            form[1] = self.dnfDistributivity(form[1])
            form[2] = self.dnfDistributivity(form[2])
        elif len(form) == 2:
            form[1] = self.dnfDistributivity(form[1])
    return form

def checkDistributivity(self, form, result = 0):
    if isinstance(form, type([])):
        if len(form) == 3:
            if form[0] == '&':
                print "found &"
                if isinstance(form[1], type([])):
                    if form[1][0] == '|':
                        return 1
                elif isinstance(form[2], type([])):
                    if form[2][0] == '|':
                        return 1
                else:
                    result = self.checkDistributivity(form[1], result)
                    print result
                    if result != 1:
                        result = self.checkDistributivity(form[2], result)
                        print result
        elif len(form) == 2:
            result = self.checkDistributivity(form[1], result)
            print result
    return result

def performDNF(self, form):
    while self.checkDistributivity(form):
        form = self.dnfDistributivity(self.dnfDistributivity(form))
    return form
4

2 回答 2

3

首先，关于您的代码的两个一般性说明：

  • 使用return True而不是return 1.
  • 使用isinstance(form, list)而不是isinstance(form, type([])).

其次，其他一些观察：

  • 我假设您还想摆脱双重否定。目前您的代码不这样做。
  • 同样，您需要应用德摩根定律之一来将否定推向叶子。

除此之外，我认为这段代码的可读性可以大大提高。我将给出一个我认为是正确的替代实现。让我知道下面的代码是否适合您；我并没有因为创建表达式而疯狂，所以我可能错过了一个极端情况。最后，我将只关注常规命题连接词。应该清楚如何应用涉及 CTL 特定连接词的转换。

  1. 创建一个Op代表运算符（连接词）的类：

    class Op(list):
    def __init__(self, *args):
        super().__init__(args)

    to 的参数__init__是操作数。此代码按照PEP 3135super中的定义使用，并且仅适用于 Python 3.x 在 Python 2.x 中，您必须按照PEP 367中的定义使用：super

    class Op(list):
    def __init__(self, *args):
        super(Op, self).__init__(args)

  2. Op为每个运算符创建简单的子类。出于调试目的，您可能需要实现自定义__str__方法：

    class Neg(Op):
    def __str__(self):
        return '!(%s)' % tuple(self)
class And(Op):
    def __str__(self):
        return '(%s) & (%s)' % tuple(self)
class Or(Op):
    def __str__(self):
        return '(%s) | (%s)' % tuple(self)
class AX(Op):
    def __str__(self):
        return 'AX (%s)' % tuple(self)
...

    现在公式!(a & b)可以创建为Neg(And('a', 'b')).

  3. 创建非常简单的函数，这些函数一次应用某种转换。这将保持实现干净。注释这些函数，其中包含有关如何应用它们的一些信息。应该从上到下应用一个预排序函数：首先转换表达式树的根，然后递归。后序函数应在递归应用于子表达式后应用于表达式。用于isinstance检查连接词的类型。

    1. 我们开始简单：该函数removeDoubleNeg删除双重否定：

      @expressionTransformation('postorder')
def removeDoubleNeg(expr):
    if isinstance(expr, Neg) and isinstance(expr[0], Neg):
        return expr[0][0]

    2. 接下来，让我们定义一个德摩根定律：

      @expressionTransformation('preorder')
def deMorgan(expr):
    if isinstance(expr, Neg) and isinstance(expr[0], And):
        return Or(Neg(expr[0][0]), Neg(expr[0][1]))

    3. 现在这个问题的功能是：

      @expressionTransformation('preorder', 'postorder')
def distribute(expr):
    if isinstance(expr, And):
        if isinstance(expr[0], Or):
            return Or(And(expr[0][0], expr[1]), And(expr[0][1], expr[1]))
        if isinstance(expr[1], Or):
            return Or(And(expr[0], expr[1][0]), And(expr[0], expr[1][1]))

      哇！那是更少的代码！

  4. 好的，那么这是如何工作的？请注意，表达式转换f的任何简单实现都将涉及样板代码：

    1. 测试参数是否是连接词（而不是常量或变量）。
    2. 尝试将f应用于表达式树的根。
    3. 递归。
    4. 返回结果。

    根据f，可能需要颠倒第 1 步和第 2 步（postorder而不是preorder）。尽管如此，每个f的实现看起来都一样。您将希望避免使用样板代码，尤其是在您计划定义更多转换时。正是缺少这个样板，才使得上一步中定义的函数如此简洁（因此易于调试！）。函数返回的装饰器expressionTransformation解决了这个问题。其实现如下：

    from functools import wraps
def expressionTransformation(*args):
    def wrap(f):
        @wraps(f)
        def recursiveTransformation(expr):
            if not isinstance(expr, Op):
                return expr
            if 'postorder' in args:
                expr[:] = map(recursiveTransformation, expr)
            res = f(expr)
            expr = expr if res is None else res 
            if 'preorder' in args:
                expr[:] = map(recursiveTransformation, expr)
            return expr
        return recursiveTransformation
    return wrap

    这里发生的情况如下：

    1. 该函数expressionTransformation返回一个装饰器（名为wrap），它接收转换函数f作为其参数。
    2. wrap返回一个递归函数，仅当此参数是连接词时才recursiveTransformation适用f于其参数。expr
    3. 根据args提供给的参数expressionTransformation，f将在将f应用于子表达式之前或之后（或之前和之后）应用。
    4. 如果不进行任何转换，则做出f可能返回的假设。None

    该函数functools.wraps用于将 的某些属性（f例如其名称）复制到recursiveTransformation。此功能不是必需的。

    （请注意，创建前序和后序转换的方法比一遍又一遍地使用测试更有效，但为了清楚起见，我选择了这个。'postorder' in args）'preorder' in args

  5. 就这样。我们现在可以很容易地组合这些函数（注意这个函数不应该被修饰）：

    def toDNF(expr):
    return distribute(removeDoubleNeg(deMorgan(expr)))

  6. 您可以使用以下语句测试代码：

    toDNF(AX(And(Or('a', 'b'), And(Or('c', 'd'), Or('e', 'f')))))
toDNF(Neg(And(Or(Neg(Neg('a')), 'b'), And(Or('c', 'd'), Or('e', 'f')))))
于 2009-11-25T10:20:25.153 回答
0

你有：

    elif len(form) == 2:
        result = self.checkDistributivity(form[1], result)
        print result

那不应该是：

    elif len(form) == 2:
        result_1 = self.checkDistributivity(form[1], result)
        result_2 = self.checkDistributivity(form[2], result) 
        if result_1 or result_2:
            return 1
于 2009-11-25T03:24:24.850 回答