【Educoder离散数学实训】生成真值表

JZYshuraK 2023-07-26 原文

【Educoder离散数学实训】生成真值表

这个相当于是class的一个实际应用，体现出来了一点Python中类的强大

总体说一下想干啥：我们想用 $P y t h o n$ 做一个真值表，对于任意的一个公式。
我们先来从形式上解决这个问题：
首先，满足输入格式的公式中， $or$ 是用 $\setminus/$ 表示的， $an d$ 是用 $/\setminus$ 表示的等等，我们第一要解决的是翻译一下这些符号，方案有很多：比如我们可以给这些符号编个号啥的，不一一列举。
其次，是优先级的问题。有括号的存在，我们的处理会变得复杂，可以用栈强行操作，等等。
接着，处理好了符号和优先级，想处理真值表我们一定是搞一个二进制枚举，然后一一代入。遍历一下就可以得到有多少个不同元素，然后进行二进制枚举，并且把对应的变元替换成常元。这就到了计算了，我们需要不断地返回与、或、非、蕴含、等价五种的答案。输入就是 $T$ 或者 $F$ ，简单的很。
最后，就是把他们整合一下，然后按照格式输出了。
以上的思路是非常好想的，想明白了这些我们再来看这八道题就容易的多，也更容易理解了。

T1 创建语义对象

我们希望创建出一种 $c l a ss$ ，他可以帮助我们进行计算和优先级排序。这种 $c l a ss$ 并不是某个字符，而是一种运算对应一类。

class Proposition:
    def __init__(self, name):
        # 请删除下面的pass后完成Proposition类的初始化
        self.name = name


    def __eq__(self, other):
        if not isinstance(other, Proposition):
            return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))
  
class Not:
    def __init__(self, formula):
        # 请删除下面的pass后完成Not类的初始化
        self.formula = formula


    def __eq__(self, other):
        if not isinstance(other, Not):
            return False
        return self.formula == other.formula

    def __str__(self):
        return '~' + str(self.formula)

    def __hash__(self):
        return hash(str(self))

class And:
    def __init__(self, formula_a, formula_b):
        # 请删除下面的pass后完成And类的初始化
        self.formula_a = formula_a
        self.formula_b = formula_b

  
    def __eq__(self, other):
        if not isinstance(other, And):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s /\\ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Or:
    def __init__(self, formula_a, formula_b):
        # 请删除下面的pass后完成Or类的初始化
        self.formula_a = formula_a
        self.formula_b = formula_b


    def __eq__(self, other):
        if not isinstance(other, Or):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s \\/ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Implies:
    def __init__(self, formula_a, formula_b):
        # 请删除下面的pass后完成Implies类的初始化
        self.formula_a = formula_a
        self.formula_b = formula_b


    def __eq__(self, other):
        if not isinstance(other, Implies):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s -> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Equiv:
    def __init__(self, formula_a, formula_b):
        # 请删除下面的pass后完成Equiv类的初始化
        self.formula_a = formula_a
        self.formula_b = formula_b


    def __eq__(self, other):
        if not isinstance(other, Equiv):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s <-> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class BoolConstant:
    def __init__(self, name):
        # 请删除下面的pass后完成BoolConstant类的初始化
        self.name = name


    def __eq__(self, other):
        if not isinstance(other, BoolConstant):
          return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))

T2 提取公式中的命题词

这个就是找所有的关键词，方便用二进制枚举真值表。

class Proposition:
    def __init__(self, name):
        self.name = name
        self.value = None

    def divide(self):
        # 请删除下面的pass后完成函数功能
        ret = set()
        for x in self.name :
            if x.isalpha() :
                ret.add(x)
        return ret


    def __eq__(self, other):
        if not isinstance(other, Proposition):
            return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))
  
class Not:
    def __init__(self, formula):
        self.formula = formula

    def divide(self):
        # 请删除下面的pass后完成函数功能
        return self.formula.divide()


    def __eq__(self, other):
        if not isinstance(other, Not):
            return False
        return self.formula == other.formula

    def __str__(self):
        return '~' + str(self.formula)

    def __hash__(self):
        return hash(str(self))

class And:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        # 请删除下面的pass后完成函数功能
        return self.formula_a.divide() | self.formula_b.divide()

  
    def __eq__(self, other):
        if not isinstance(other, And):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s /\\ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Or:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        # 请删除下面的pass后完成函数功能
        return self.formula_a.divide() | self.formula_b.divide()


    def __eq__(self, other):
        if not isinstance(other, Or):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s \\/ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Implies:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        # 请删除下面的pass后完成函数功能
        return self.formula_a.divide() | self.formula_b.divide()


    def __eq__(self, other):
        if not isinstance(other, Implies):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s -> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Equiv:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        # 请删除下面的pass后完成函数功能
        return self.formula_a.divide() | self.formula_b.divide()


    def __eq__(self, other):
        if not isinstance(other, Equiv):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s <-> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class BoolConstant:
    def __init__(self, name):
        self.name = name
        if name == 'T':
            self.value = True
        elif name == 'F':
            self.value = False

    def divide(self):
        # 请删除下面的pass后完成函数功能
        ret = set()
        for x in self.name :
            if x.isalpha() :
                ret.add(x)
        return ret
        

    def __eq__(self, other):
        if not isinstance(other, BoolConstant):
          return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))

T3 给公式中的命题词赋值

这个题的作用是：枚举了二进制中的某一种情况，我希望用这个情况代替所有的变元。

class Proposition:
    def __init__(self, name):
        self.name = name
        self.value = None

    def divide(self):
        return {self}

    def assign(self, values):
        # 请删除下面的pass后完成函数功能
        self.value = values[self.name]

    def __eq__(self, other):
        if not isinstance(other, Proposition):
            return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))
  
class Not:
    def __init__(self, formula):
        self.formula = formula

    def divide(self):
        return self.formula.divide()

    def assign(self, values):
        # 请删除下面的pass后完成函数功能
        self.formula.assign(values)

    def __eq__(self, other):
        if not isinstance(other, Not):
            return False
        return self.formula == other.formula

    def __str__(self):
        return '~' + str(self.formula)

    def __hash__(self):
        return hash(str(self))

class And:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        # 请删除下面的pass后完成函数功能
        # self.formula_a.value = values[self.formula_a.name]
        # self.formula_b.value = values[self.formula_b.name]
        self.formula_a.assign(values)
        self.formula_b.assign(values)

  
    def __eq__(self, other):
        if not isinstance(other, And):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s /\\ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Or:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        # 请删除下面的pass后完成函数功能
        self.formula_a.assign(values)
        self.formula_b.assign(values)


    def __eq__(self, other):
        if not isinstance(other, Or):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s \\/ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Implies:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        # 请删除下面的pass后完成函数功能
        self.formula_a.assign(values)
        self.formula_b.assign(values)


    def __eq__(self, other):
        if not isinstance(other, Implies):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s -> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Equiv:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        # 请删除下面的pass后完成函数功能
        self.formula_a.assign(values)
        self.formula_b.assign(values)


    def __eq__(self, other):
        if not isinstance(other, Equiv):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s <-> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class BoolConstant:
    def __init__(self, name):
        self.name = name
        if name == 'T':
            self.value = True
        elif name == 'F':
            self.value = False

    def divide(self):
        return {self}

    def assign(self, values):
        pass

    def __eq__(self, other):
        if not isinstance(other, BoolConstant):
          return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))

T4 求命题公式在解释下的真值

这个题就是在求值了。
用的就是第一题对于每一种操作建立的类。

class Proposition:
    def __init__(self, name):
        self.name = name
        self.value = None

    def divide(self):
        return {self}

    def assign(self, values):
        self.value = values[self.name]

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        return self.value


    def __eq__(self, other):
        if not isinstance(other, Proposition):
            return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))
  
class Not:
    def __init__(self, formula):
        self.formula = formula

    def divide(self):
        return self.formula.divide()

    def assign(self, values):
        self.formula.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        return not self.formula.evaluate()


    def __eq__(self, other):
        if not isinstance(other, Not):
            return False
        return self.formula == other.formula

    def __str__(self):
        return '~' + str(self.formula)

    def __hash__(self):
        return hash(str(self))

class And:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        return self.formula_a.evaluate() & self.formula_b.evaluate()

  
    def __eq__(self, other):
        if not isinstance(other, And):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s /\\ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Or:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        return self.formula_a.evaluate() | self.formula_b.evaluate()


    def __eq__(self, other):
        if not isinstance(other, Or):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s \\/ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Implies:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        return (not self.formula_a.evaluate()) | self.formula_b.evaluate()


    def __eq__(self, other):
        if not isinstance(other, Implies):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s -> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Equiv:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        return self.formula_a.evaluate() == self.formula_b.evaluate()


    def __eq__(self, other):
        if not isinstance(other, Equiv):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s <-> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class BoolConstant:
    def __init__(self, name):
        self.name = name
        if name == 'T':
            self.value = True
        elif name == 'F':
            self.value = False

    def divide(self):
        return {self}

    def assign(self, values):
        pass

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        return self.value


    def __eq__(self, other):
        if not isinstance(other, BoolConstant):
          return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))

T5 命题逻辑编译器之雏形

很多人可能没理解，第五题在干啥。
讲白了，就是我们上面处理的优先级。
他引用了 $P y t h o n$ 里建好的一个运算系统，刚开始看可能有点蒙为啥要建立这么一个系统，因为确实没啥必要。一个一个算不行吗？我们都写好了运算类了直接用不就完事儿了？
但是由于括号的存在，我们无法有效的处理优先级（其实栈可以），所以我们就直接照搬了 $P y t h o n$ 的运算系统，他可以帮助我们处理括号。

from pyparsing import (alphanums, alphas, delimitedList, Forward,oneOf,
            Group, Keyword, Literal, opAssoc, operatorPrecedence,
            ParserElement, ParseException, ParseSyntaxException, Suppress,ZeroOrMore,
            Word)

ParserElement.enablePackrat()

##########################################################################
def propAction(tokens):
    return Proposition(tokens[0])

def notFormulaAction(tokens):
    return Not(tokens[0][1])

def boolConstantAction(tokens):
    #请删除pass后编程
    return BoolConstant(tokens[0])


def andFormulaAction(tokens):
    #请删除pass后编程
    return And(tokens[0][0], tokens[0][2])


def orFormulaAction(tokens):
    #请删除pass后编程
    return Or(tokens[0][0], tokens[0][2])


def impliesFormulaAction(tokens):
    #请删除pass后编程
    return Implies(tokens[0][0], tokens[0][2])


def equivFormulaAction(tokens):
    #请删除pass后编程
    return Equiv(tokens[0][0], tokens[0][2])


##########################################################################
def propParse(text):
    left_parenthesis = Literal('(').suppress()
    right_parenthesis = Literal(')').suppress()
    implies = Keyword("implies")
    equivalence = Keyword("equiv")
    or_ = Keyword("or")
    and_ = Keyword("and")
    not_ = Keyword("not")
    connective = and_ | or_ | implies | equivalence
    boolean = Keyword("F") | Keyword("T")
    proposition = Word(alphas[0:26].upper().replace('F', '').replace('T', '')).setParseAction(propAction)
    formula = Forward()

    connectiveFormula = Group(left_parenthesis + formula + connective + formula + right_parenthesis)
    notFormula = Group(not_ + formula)

    operand = proposition | connectiveFormula | boolean | notFormula

    formula << operatorPrecedence(operand, [
        (not_, 1, opAssoc.RIGHT, notFormulaAction),
        (and_, 2, opAssoc.LEFT, andFormulaAction),
        (or_, 2, opAssoc.LEFT, orFormulaAction),
        (implies, 2, opAssoc.LEFT, impliesFormulaAction),
        (equivalence, 2, opAssoc.LEFT, equivFormulaAction)])

    boolean.setParseAction(boolConstantAction)
    try:
        result = formula.parseString(text, parseAll=True)
        assert len(result) == 1
        return result[0]
    except (ParseException, ParseSyntaxException) as err:
        print("Syntax error:\n{0.line}\n{1}^".format(err,
                                                     " " * (err.column - 1)))
        return []

##########################################################################

class Proposition:
    def __init__(self, name):
        self.name = name
        self.value = None

    def divide(self):
        return {self}

    def assign(self, values):
        self.value = values[self.name]

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.value

    def __eq__(self, other):
        if not isinstance(other, Proposition):
            return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))
  
class Not:
    def __init__(self, formula):
        self.formula = formula

    def divide(self):
        return self.formula.divide()

    def assign(self, values):
        self.formula.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return not (self.formula.evaluate())

    def __eq__(self, other):
        if not isinstance(other, Not):
            return False
        return self.formula == other.formula

    def __str__(self):
        return '~' + str(self.formula)

    def __hash__(self):
        return hash(str(self))

class And:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.formula_a.evaluate() and self.formula_b.evaluate()
  
    def __eq__(self, other):
        if not isinstance(other, And):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s /\\ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Or:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.formula_a.evaluate() or self.formula_b.evaluate()

    def __eq__(self, other):
        if not isinstance(other, Or):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s \\/ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Implies:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return not (self.formula_a.evaluate()) or self.formula_b.evaluate()

    def __eq__(self, other):
        if not isinstance(other, Implies):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s -> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Equiv:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.formula_a.evaluate() == self.formula_b.evaluate()

    def __eq__(self, other):
        if not isinstance(other, Equiv):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s <-> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class BoolConstant:
    def __init__(self, name):
        self.name = name
        if name == 'T':
            self.value = True
        elif name == 'F':
            self.value = False

    def divide(self):
        return {self}

    def assign(self, values):
        pass

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.value

    def __eq__(self, other):
        if not isinstance(other, BoolConstant):
          return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))

T6 转换输入的合式公式

这个题干的是我们说的第一个事儿，就是把输入变成能看懂的样子。不管是 $an d$ 或者标号啥的，本质上讲都是方便我们处理因为那些意象化的符号确实很难判断。

def formatFormula(form):
    #请在此编程实现函数功能
    l = len(form)
    Connect = ['and', 'or', 'implies', 'equiv', 'not']
    Add = [2, 2, 2, 3, 1]
    Check = '/\-<~'
    i, ans = 0, ''
    while i < l :
        if form[i] in Check :
            idx = Check.index(form[i])
            if idx != 4 :
                ans = ans + ' ' + Connect[idx] + ' '
            else :
                ans = ans + Connect[idx] + ' '
            i += Add[idx]
        else :
            ans = ans + form[i]
            i += 1
    return ans

T7 生成所有解释

这就是二进制表示了，我们已知了所有的变元个数，直接枚举即可。方法是位运算，看不懂可以百度位运算。

def genInterpretations(n):
    # 请在下面编程，实现函数功能
    # n为整数，本函数返回一个列表，列表元素仍为一个列表
    ans = []
    for x in range(2 ** n) :
        mdl = []
        for i in range(n) :
            if x & (2 ** (n - i - 1)) :
                mdl.append(True)
            else :
                mdl.append(False)
        ans.append(mdl)
    return ans

T8 生成真值表

啥也没干，就把前七关整合一下。

from pyparsing import (alphanums, alphas, delimitedList, Forward,oneOf,
            Group, Keyword, Literal, opAssoc, operatorPrecedence,
            ParserElement, ParseException, ParseSyntaxException, Suppress,ZeroOrMore,
            Word)

ParserElement.enablePackrat()

##########################################################################
def propAction(tokens):
    return Proposition(tokens[0])

def notFormulaAction(tokens):
    return Not(tokens[0][1])

def boolConstantAction(tokens):
    #请删除pass后编程
    #pass
    return BoolConstant(tokens[0])

def andFormulaAction(tokens):
    #请删除pass后编程
    #pass
    return And(tokens[0][0], tokens[0][2])

def orFormulaAction(tokens):
    #请删除pass后编程
    #pass
    return Or(tokens[0][0], tokens[0][2])

def impliesFormulaAction(tokens):
    #请删除pass后编程
    #pass
    return Implies(tokens[0][0], tokens[0][2])

def equivFormulaAction(tokens):
    #请删除pass后编程
    #pass
    return Equiv(tokens[0][0], tokens[0][2])

##########################################################################
def propParse(text):
    left_parenthesis = Literal('(').suppress()
    right_parenthesis = Literal(')').suppress()
    implies = Keyword("implies")
    equivalence = Keyword("equiv")
    or_ = Keyword("or")
    and_ = Keyword("and")
    not_ = Keyword("not")
    connective = and_ | or_ | implies | equivalence
    boolean = Keyword("F") | Keyword("T")
    proposition = Word(alphas[0:26].upper().replace('F', '').replace('T', '')).setParseAction(propAction)
    formula = Forward()

    connectiveFormula = Group(left_parenthesis + formula + connective + formula + right_parenthesis)
    notFormula = Group(not_ + formula)

    operand = proposition | connectiveFormula | boolean | notFormula

    formula << operatorPrecedence(operand, [
        (not_, 1, opAssoc.RIGHT, notFormulaAction),
        (and_, 2, opAssoc.LEFT, andFormulaAction),
        (or_, 2, opAssoc.LEFT, orFormulaAction),
        (implies, 2, opAssoc.LEFT, impliesFormulaAction),
        (equivalence, 2, opAssoc.LEFT, equivFormulaAction)])

    boolean.setParseAction(boolConstantAction)
    try:
        result = formula.parseString(text, parseAll=True)
        assert len(result) == 1
        return result[0]
    except (ParseException, ParseSyntaxException) as err:
        print("Syntax error:\n{0.line}\n{1}^".format(err,
                                                     " " * (err.column - 1)))
        return []

##########################################################################

class Proposition:
    def __init__(self, name):
        self.name = name
        self.value = None

    def divide(self):
        return {self}

    def assign(self, values):
        self.value = values[self.name]

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.value

    def __eq__(self, other):
        if not isinstance(other, Proposition):
            return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))
  
class Not:
    def __init__(self, formula):
        self.formula = formula

    def divide(self):
        return self.formula.divide()

    def assign(self, values):
        self.formula.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return not (self.formula.evaluate())

    def __eq__(self, other):
        if not isinstance(other, Not):
            return False
        return self.formula == other.formula

    def __str__(self):
        return '~' + str(self.formula)

    def __hash__(self):
        return hash(str(self))

class And:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.formula_a.evaluate() and self.formula_b.evaluate()
  
    def __eq__(self, other):
        if not isinstance(other, And):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s /\\ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Or:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.formula_a.evaluate() or self.formula_b.evaluate()

    def __eq__(self, other):
        if not isinstance(other, Or):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s \\/ %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Implies:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return not (self.formula_a.evaluate()) or self.formula_b.evaluate()

    def __eq__(self, other):
        if not isinstance(other, Implies):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s -> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class Equiv:
    def __init__(self, formula_a, formula_b):
        self.formula_a = formula_a
        self.formula_b = formula_b

    def divide(self):
        return self.formula_a.divide() | self.formula_b.divide()

    def assign(self, values):
        self.formula_a.assign(values)
        self.formula_b.assign(values)

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.formula_a.evaluate() == self.formula_b.evaluate()

    def __eq__(self, other):
        if not isinstance(other, Equiv):
            return False
        return self.formula_a == other.formula_a and \
               self.formula_b == other.formula_b

    def __str__(self):
        return '(%s <-> %s)' % (self.formula_a, self.formula_b)

    def __hash__(self):
        return hash(str(self))

class BoolConstant:
    def __init__(self, name):
        self.name = name
        if name == 'T':
            self.value = True
        elif name == 'F':
            self.value = False

    def divide(self):
        return {self}

    def assign(self, values):
        pass

    def evaluate(self):
        # 请删除下面的pass后完成函数功能
        # pass
        return self.value

    def __eq__(self, other):
        if not isinstance(other, BoolConstant):
          return False
        return self.name == other.name

    def __str__(self):
        return self.name

    def __hash__(self):
        return hash(str(self))

################################################################
def formatFormula(form):
    correpond = {'/\\': ' and ', '\\/': ' or ', '->': ' implies ', '~': ' not ', '<->': ' equiv '}
    for item in ['/\\', '\\/', '<->', '->', '~']:
        form = form.replace(item, correpond[item])
    return form


def genInterpretations(n):
    if n < 1:
        return [[]]
    subtable = genInterpretations(n - 1)
    return [row + [v] for row in subtable for v in [False, True]]


def genTruthTable(formula):
    #编译所给的命题逻辑公式；
    form = propParse(formatFormula(formula))
    #获得该命题逻辑公式的所有命题词；
    propSet = form.divide()
    props = []
    for item in propSet:
        props.append(item.name)
    #对所有的命题词按照其名字的字典序排序
    props = sorted(props)
    #按照命题词个数，生成全部的解释；
    table = genInterpretations(len(props))

    #生成真值表的每一行数据
    n = len(props)
    for item in table:
        #删除pass后编程
        Dict = {}
        for i in range(n) :
            Dict[props[i]] = item[i]
        form.assign(Dict)
        item.append(form.evaluate())


    #显示真值表
    display(props, formula, table)


def display(props, formula, table):
    props.append(formula)
    columns = range(len(table[0]))
    col_width = [len(prop) for prop in props]
    symbol = {True: 'T', False: 'F'}

    hline = ""
    for col in columns:
        hline += "+-" + ("-" * col_width[col]) + "-"
    hline += "+"

    def line(row):
        l = ""
        for col in columns:
            if row[col] == True or row[col] == False:
                value = symbol[row[col]]
            else:
                value = row[col]

            if (col_width[col] - len(value)) % 2 == 0:
                l += "| " + (" " * ((col_width[col] - len(value)) // 2)) + value + (
                            " " * ((col_width[col] - len(value)) // 2)) + " "
            else:
                l += "| " + (" " * ((col_width[col] - len(value)) // 2 + 1)) + value + (
                            " " * ((col_width[col] - len(value)) // 2)) + " "
        l += "|"
        return l

    print(hline)
    print(line(props))
    print(hline)

    for onerow in table:
        print(line(onerow))

    print(hline)

这个题写完了其实是比较有成就感的，因为我们一步一步的处理好了一个看起来还是比较复杂的东西。
但最开始的形式化推导是必要的（跟建平学的），极其方便我们去理解，去把我中心。

有关【Educoder离散数学实训】生成真值表的更多相关文章

ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2
我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？最佳答案这是我通过查看rubyzip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d
ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2
在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',
ruby - 如何使用 Ruby aws/s3 Gem 生成安全 URL 以从 s3 下载文件 - 2
我正在编写一个小脚本来定位aws存储桶中的特定文件，并创建一个临时验证的url以发送给同事。(理想情况下，这将创建类似于在控制台上右键单击存储桶中的文件并复制链接地址的结果)。我研究过回形针，它似乎不符合这个标准，但我可能只是不知道它的全部功能。我尝试了以下方法:defauthenticated_url(file_name,bucket)AWS::S3::S3Object.url_for(file_name,bucket,:secure=>true,:expires=>20*60)end产生这种类型的结果:...-1.amazonaws.com/file_path/file.zip.A
ruby-on-rails - Ruby on Rails - 为文本区域和图片生成列 - 2
我是Rails的新手，所以请原谅简单的问题。我正在为一家公司创建一个网站。那家公司想在网站上展示它的客户。我想让客户自己管理这个。我正在为“客户”生成一个表格，我想要的三列是:公司名称、公司描述和Logo。对于名称，我使用的是name:string但不确定如何在脚本/生成脚手架终端命令中最好地创建描述列(因为我打算将其设置为文本区域)和图片。我怀疑描述(我想成为一个文本区域)应该仍然是描述:字符串，然后以实际形式进行调整。不确定如何处理图片字段。那么……说来话长:我在脚手架命令中输入什么来生成描述和图片列？最佳答案对于“文本”数
ruby-on-rails - 如何生成传递一些自定义参数的 `link_to` URL？ - 2
我正在使用RubyonRails3.0.9，我想生成一个传递一些自定义参数的link_toURL。也就是说，有一个articles_path(www.my_web_site_name.com/articles)我想生成如下内容:link_to'Samplelinktitle',...#HereIshouldimplementthecode#=>'http://www.my_web_site_name.com/articles?param1=value1¶m2=value2&...我如何编写link_to语句“alàRubyonRailsWay”以实现该目的？如果我想通过传递一些
ruby-on-rails - 如何在 Rails 3 中创建自定义脚手架生成器？ - 2
有这些railscast。http://railscasts.com/episodes/218-making-generators-in-rails-3有了这个，你就会知道如何创建样式表和脚手架生成器。http://railscasts.com/episodes/216-generators-in-rails-3通过这个，您可以了解如何添加一些文件来修改脚手架View。我想把两者结合起来。我想创建一个生成器，它也可以创建脚手架View。有点像RyanBates漂亮的生成器或web_app_themegem(https://github.com/pilu/web-app-theme)。我
ruby-on-rails - ruby 日期方程不返回预期的真值 - 2
为什么以下不同？Time.now.end_of_day==Time.now.end_of_day-0.days#falseTime.now.end_of_day.to_s==Time.now.end_of_day-0.days.to_s#true 最佳答案因为纳秒数不同:ruby-1.9.2-p180:014>(Time.now.end_of_day-0.days).nsec=>999999000ruby-1.9.2-p180:015>Time.now.end_of_day.nsec=>999999998
报告回顾丨模型进化狂飙，DetectGPT能否识别最新模型生成结果？ - 2
导读语言模型给我们的生产生活带来了极大便利，但同时不少人也利用他们从事作弊工作。如何规避这些难辨真伪的文字所产生的负面影响也成为一大难题。在3月9日智源Live第33期活动「DetectGPT：判断文本是否为机器生成的工具」中，主讲人Eric为我们讲解了DetectGPT工作背后的思路——一种基于概率曲率检测的用于检测模型生成文本的工具，它可以帮助我们更好地分辨文章的来源和可信度，对保护信息真实、防止欺诈等方面具有重要意义。本次报告主要围绕其功能，实现和效果等展开。（文末点击“阅读原文”，查看活动回放。）Ericmitchell斯坦福大学计算机系四年级博士生，由ChelseaFinn和Chri
python - 帮我找到合适的 ruby/python 解析器生成器 - 2
我使用的第一个解析器生成器是Parse::RecDescent，它的指南/教程很棒，但它最有用的功能是它的调试工具，特别是tracing功能(通过将$RD_TRACE设置为1来激活)。我正在寻找可以帮助您调试其规则的解析器生成器。问题是，它必须用python或ruby编写，并且具有详细模式/跟踪模式或非常有用的调试技术。有人知道这样的解析器生成器吗？编辑:当我说调试时，我并不是指调试python或ruby。我指的是调试解析器生成器，查看它在每一步都在做什么，查看它正在读取的每个字符，它试图匹配的规则。希望你明白这一点。赏金编辑:要赢得赏金，请展示一个解析器生成器框架，并说明它的
ruby - 如何为 pbcopy 生成富文本链接 - 2
我一直在玩一个脚本，它在Chrome中获取选定的文本并在Google中查找它，提供四个最佳选择，然后粘贴相关链接。它以不同的格式粘贴，具体取决于当前在Chrome中打开的页面-DokuWiki打开的DokuWiki格式，普通网站的HTML，我想要我的WordPress所见即所得编辑器的富文本。我尝试使用pbpaste-Preferrtf来查看没有其他样式的富文本链接在粘贴板上的样子，但它仍然输出纯文本。在文本编辑中保存文件并进行试验后，我想出了以下内容text=%q|{\rtf1{\field{\*\fldinst{HYPERLINK"URL"}}{\fldrsltTEXT}}}|te

【Educoder离散数学实训】生成真值表

【Educoder离散数学实训】生成真值表

T1 创建语义对象

T2 提取公式中的命题词

T3 给公式中的命题词赋值

T4 求命题公式在解释下的真值

T5 命题逻辑编译器之雏形

T6 转换输入的合式公式

T7 生成所有解释

T8 生成真值表

有关【Educoder离散数学实训】生成真值表的更多相关文章

随机推荐