【BUAA】离散数学python挑战题的一种解决方案
离散数学是计算机科学与技术、软件工程等专业非常重要的课程之一。由于本校大多数学生没有在大一接触过python，同学们参与python挑战题不太积极，但不妨来了解一下做题思路吧！限于笔者的个人能力，我目前只能实现利用真值表形式判断两个公式是否等价。如果你会等值演算的方法，欢迎与我联系，我十分想学习其余的方法。
题目：通过Python语言，共三个函数（第三方库只允许使用numpy），编程实现：
（1）生成尽可能多的符合条件的合式公式，联结词集合{¬, ∧ , ∨ , → , ↔ , ⨁}变元数量为m，公式复杂度为n；
我们首先回顾一下命题逻辑合式公式及其复杂度的定义:
来吧，上代码!!!
细节已经标注在注释上了，若仍有问题请留言。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#生成max_num个合式公式（尽可能多），返回在列表之中
def Produce(m, n, max_num = 100):#python的特殊写法：第三个参数max_num默认为100，也可以不传参
formula = []#公式列表
for i in range(max_num):
f = generate_formula(m, n)
if f not in formula:
formula.append(f)#在列表尾加入合式公式
return formula#返回公式列表
def generate_formula(m, n, variables=None):
if variables is None: #存储已经使用过的变元
variables = []
if n == 0:#如果需要生成的合式公式复杂度为0
if(len(variables) == m):#选取已存在的变元
var = random.choice(variables)
else:#选取一个未选择的大写字母作为变元
var = random.choice(string.ascii_uppercase[:m])
while var in variables:
var = random.choice(string.ascii_uppercase[:m])
variables.append(var)
return var#命题变元是复杂度为0的合式公式
else:#如果需要生成的合式公式复杂度不为0
operator = random.choice(['¬', '∧', '∨', '→', '↔', '⨁'])#随机选择一个联结词
if operator == '¬':#联结词是非的情况
return f'¬{generate_formula(m, n-1, variables)}'
else:#联结词不是非的情况
if n == 1:#n为1的情况下，左侧右侧的合式公式复杂度一定为0
left_formula = generate_formula(m, n-1, variables)
right_formula = generate_formula(m, n-1, variables)
else:#n大于1时，左侧右侧合式公式复杂度至少有一个为n-1
if random.randint(1, 2) == 1:
left_formula = generate_formula(m, n-1, variables)
right_formula = generate_formula(m, random.randint(0, n-1), variables)
else:
right_formula = generate_formula(m, n-1, variables)
left_formula = generate_formula(m, random.randint(0, n-1), variables)
return f'({left_formula} {operator} {right_formula})'
（2）判断生成的公式是不是永真式，永假式，可满足式；
本题使用真值表方法判断生成的合式公式为哪种类别，因为题解要利用python中的eval函数，即把字符串转变为表达式并求值，因此让我们回顾一下不同的联结词在python中的语义。
辅助函数
1 | # 辅助函数：解析公式，可以参考上面的图 |
TrueOrNot的函数
细节已经标注在注释上了，若仍有问题请留言。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#第二个函数
def TrueOrNot(formula):
truth_table = generate_truth_table(formula)
is_tautology = True #永真的
is_contradiction = True #永假的
is_satisfiable = False #可满足的
for row in truth_table:
result = evaluate_expression(parse_formula(formula), row)#求每种可能的值
if not result:#一个为假就不是永真
is_tautology = False
else:#一个为真就不是永假
is_contradiction = False
is_satisfiable = True
if not is_tautology and not is_contradiction:#不是永真且不是永假直接结束
break
if is_tautology:
return 0
elif is_contradiction:
return 1
elif is_satisfiable:
return 2
（3）判断生成的两个公式否是逻辑等价
如同简介里描述的一样，笔者不会利用等值演算的方法，因此在这里只分享真值表方法。在理解完第（2）题后，大家应该也觉得第（3）题看起来没那么困难了吧！让我们利用第（2）题定义的辅助函数完成第三题吧。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17#第三个函数 真值表实现
def EqualOrNot(formula1, formula2):
variables1 = extract_variables(formula1)
variables2 = extract_variables(formula2)
if len(variables1) != len(variables2):#变量数目不一样的公式一定不等价
return False
else:#变量种类不同的公式一定不等价
for v in variables1:
if v not in variables2:
return False
truth_table = generate_truth_table(formula1)
for row in truth_table:
result1 = evaluate_expression(parse_formula(formula1), row)
result2 = evaluate_expression(parse_formula(formula2), row)
if result1 != result2:
return False
return True
效果检测
代码
1 | fs = Produce(4, 4) |
运行结果
1 | ((A ↔ (B → B)) ↔ (((C ⨁ B) ∨ D) → (A ⨁ B))) |