利用真值表法求取主析取范式及主合取范式

程序结构

├─ code
│  ├─logical_operation
│  │  ├─__init__.py
│  │  ├─Algorithm.py
│  │  └─operator.py
│  └─main.py

code：主程序文件夹
- logical_operation：定义与逻辑运算有关的符号及运算法则
  - __ init __.py：用于将文件夹变为一个python模块
  - Algorithm.py：定义逻辑运算符的运算法则
  - operator.py：定义逻辑运算符符号
- main.py：主程序

init .py

python">__all__ = ['operator', 'Algorithm']

表示将logical_operation模块中的operator.py、Algorithm.py对外暴露

operator.py

python">def _not_(value):"""定义否定联结词"""# 判断传入值是否为0/1if value not in [0, 1]:return -1# 返回否定式return 1 if value == 0 else 0def _conjunction_(value1, value2):"""定义合取联结词"""# 判断是否为0/1if (value1 not in [0, 1]) | (value2 not in [0, 1]):return -1return value1 & value2def _disjunctive_(value1, value2):"""定义析取联结词"""# 判断是否为0/1if (value1 not in [0, 1]) | (value2 not in [0, 1]):return -1return value1 | value2def _implied_(value1, value2):"""定义蕴涵联结词"""# 判断是否为0/1if (value1 not in [0, 1]) | (value2 not in [0, 1]):return -1return 0 if (value1 == 1 and value2 == 0) else 1def _equivalent_(value1, value2):"""定义等价联结词"""# 判断是否为0/1if (value1 not in [0, 1]) | (value2 not in [0, 1]):return -1return 1 if (value1 == value2) else 0def get_result(operator, *values):# 若联结词未定义，抛出异常if operator not in ['!', '&', '|', '>', '-']:return -1# 判断操作数数目是否正确if len(values) == 0:return -1if (operator == '!') and (len(values) >= 2):return -1if (operator in ['&', '|', '>', '-']) and (len(values) != 2):return -1# 进行运算res = -1if operator == '!':res = _not_(values[0])elif operator == '&':res = _conjunction_(values[0], values[1])elif operator == '|':res = _disjunctive_(values[0], values[1])elif operator == '>':res = _implied_(values[0], values[1])elif operator == '-':res = _equivalent_(values[0], values[1])return res

分别定义否定联结词、合取联结词、析取联结词、蕴涵联结词和等价联结词的运算规则（这几个联结词的定义见离散数据教科书），并定义一个供外界调用的函数get_result，参数为operator和values，其中operator为联结词符号（!代表否定联结词、&代表合取联结词、|代表析取联结词、>代表蕴涵联结词、-代表等价联结词），values代表操作数（其中!为单目运算符，有一个操作数，其它符号有两个操作数）。

Algorithm.py

该函数借鉴四则运算符，利用“栈”定义了逻辑运算符的运算法则。

python">"""
通过 栈 定义 逻辑运算
"""
from logical_operation import operator# 定义符号优先级
prority_dict = {"!": 1, "&": 2, "|": 3, ">": 4, "-": 5} # 1代表最高的优先级# 定义数字栈和符号栈
num_stack, ope_stack = [], []# 将 出栈运算 步骤封装
def temp():ope = ope_stack.pop()# 一元运算符if ope == '!':v = num_stack.pop()res = operator.get_result(ope, v)# 二元运算符else:v2 = num_stack.pop()v1 = num_stack.pop()res = operator.get_result(ope, v1, v2)num_stack.append(res)def algorithm(expression):for str in expression:# 若是数字，则直接加入数字栈((!1&1)|(1&!1))>0if str in '01':num_stack.append(int(str))continue# 若是符号，则判断入栈还是运算if (str in prority_dict.keys()) | (str in '()'):# 若符号栈为空、栈顶符号为‘(’、当前符号为‘(’，则直接入栈if (len(ope_stack) == 0) or (ope_stack[-1] == '(') or (str == '('):ope_stack.append(str)continueif str == ')':while ope_stack[-1] != '(':temp()ope_stack.pop()continue# 若当前符号优先级小于等于栈顶符号优先级，则进行运算# 直至栈为空，或者当前符号优先级大于栈顶符号优先级while prority_dict[str] > prority_dict[ope_stack[-1]]:temp()# 若栈已经为空、或栈顶符号为‘(’，则直接退出循环if (len(ope_stack) == 0) or (ope_stack[-1] == '('):breakope_stack.append(str)continue# 表达式遍历完成，检查符号栈中是否还有符号if len(ope_stack) == 0:return num_stack[-1]else:while len(ope_stack) != 0:temp()return num_stack[-1]

这一部分主要是对数据结构中“栈”的应用，没有别的需要注意的地方。

main.py

python">import logical_operation.Algorithm as al
import pandas as pd
import sysif __name__ == '__main__':exp = input("请输入表达式： ")# 指定变量var_name = ['p', 'q', 'r']result = list()# 生成0/1for i in range(2 ** len(var_name)):bin_list = list(str(bin(i))[2:].zfill(len(var_name)))# 将变量替换为01expt = expfor j in range(len(var_name)):expt = expt.replace(var_name[j], bin_list[j])res = al.algorithm(expt)if res == -1:print("error!!!")sys.exit(0)bin_list.append(res)result.append(bin_list)var_name.append(exp)result2 = pd.DataFrame(result, columns=var_name, index=None)M_list = list()m_list = list()for i in range(len(result)):if result[i][len(var_name)-1] == 0:M_list.append(f"M{i}")else:m_list.append(f"m{i}")print(f"主合取范式为：{ '^'.join(M_list) }")print(f"主析取范式为：{ 'v'.join(m_list) }")print(result2)

下面用一个例子来解释上述代码——p|q|!r：

表达式只能使用var_name中指定的变量
真值表的行数等于 $2^{变量数}$ ，如下图，三个变量的真值表有 $2^3=8$ 行
可见p、q、r对应的值即为python对应的下标的二进制（例如当python对应下标为5时，二进制为101，即p=1,q=0,r=1），因此可以根据下标生成p、q、r的值（以i=3为例）
- bin(i) = 0b11 ------> bin()函数生成0b开头的二进制
- str(bin(i)) = str(0b11) = “0b11” ------> 将二进制转换为字符串
- str(bin(i))[2:].zfill(len(v)) = “0b11”[2:].zfill(3) = “11”.zfill(3) = “011” ------> 从第三位取出字符串的值，并在前面填充0，使其长度达到3
- list(str(bin(i))[2:].zfill(len(v))) = list(“011”) = [“0”, “1”, “1”]
将输入表达式中的p、q、r替换为对应的0、1值
- 输入表达式为“p|q|!r”，则替换为“0|1|!1”
通过logical_operation模块的Algorithm方法计算值
- logical_operation.Algorithm(“0|1|!1”) = 1
将结果并入前面的列表
- 得到[“0”, “1”, “1”, 1]

循环结束后，可得到列表

[["0", "0", "0", 1],["0", "0", "1", 0],["0", "1", "0", 1],["0", "1", "1", 1],["1", "0", "0", 1],["1", "0", "1", 1],["1", "1", "0", 1],["1", "1", "1", 1],
]

将表达式并入变量名列表，可得到
- ```
python">["p", "q", "r", "p|q|!r"]
```
得到最终真值表
直接根据真值表得到主析取范式和主合取范式（具体方法见离散数学教材）
- 主合取范式为：M1
- 主析取范式为：m0vm2vm3vm4vm5vm6vm7

python对应下标	p	q	r	p\|q\|!r
0	0	0	0	1
1	0	0	1	0
2	0	1	0	1
3	0	1	1	1
4	1	0	0	1
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

最终代码

__ init __.py：

python">__all__ = ['operator', 'Algorithm']

operator.py：

python">def _not_(value):"""定义否定联结词"""# 判断传入值是否为0/1if value not in [0, 1]:return -1# 返回否定式return 1 if value == 0 else 0def _conjunction_(value1, value2):"""定义合取联结词"""# 判断是否为0/1if (value1 not in [0, 1]) | (value2 not in [0, 1]):return -1return value1 & value2def _disjunctive_(value1, value2):"""定义析取联结词"""# 判断是否为0/1if (value1 not in [0, 1]) | (value2 not in [0, 1]):return -1return value1 | value2def _implied_(value1, value2):"""定义蕴涵联结词"""# 判断是否为0/1if (value1 not in [0, 1]) | (value2 not in [0, 1]):return -1return 0 if (value1 == 1 and value2 == 0) else 1def _equivalent_(value1, value2):"""定义等价联结词"""# 判断是否为0/1if (value1 not in [0, 1]) | (value2 not in [0, 1]):return -1return 1 if (value1 == value2) else 0def get_result(operator, *values):# 若联结词未定义，抛出异常if operator not in ['!', '&', '|', '>', '-']:return -1# 判断操作数数目是否正确if len(values) == 0:return -1if (operator == '!') and (len(values) >= 2):return -1if (operator in ['&', '|', '>', '-']) and (len(values) != 2):return -1# 进行运算res = -1if operator == '!':res = _not_(values[0])elif operator == '&':res = _conjunction_(values[0], values[1])elif operator == '|':res = _disjunctive_(values[0], values[1])elif operator == '>':res = _implied_(values[0], values[1])elif operator == '-':res = _equivalent_(values[0], values[1])return res

Algorithm.py：

python">"""
通过 栈 定义 逻辑运算
"""
from logical_operation import operator# 定义符号优先级
prority_dict = {"!": 1, "&": 2, "|": 3, ">": 4, "-": 5} # 1代表最高的优先级# 定义数字栈和符号栈
num_stack, ope_stack = [], []# 将 出栈运算 步骤封装
def temp():ope = ope_stack.pop()# 一元运算符if ope == '!':v = num_stack.pop()res = operator.get_result(ope, v)# 二元运算符else:v2 = num_stack.pop()v1 = num_stack.pop()res = operator.get_result(ope, v1, v2)num_stack.append(res)def algorithm(expression):for str in expression:# 若是数字，则直接加入数字栈((!1&1)|(1&!1))>0if str in '01':num_stack.append(int(str))continue# 若是符号，则判断入栈还是运算if (str in prority_dict.keys()) | (str in '()'):# 若符号栈为空、栈顶符号为‘(’、当前符号为‘(’，则直接入栈if (len(ope_stack) == 0) or (ope_stack[-1] == '(') or (str == '('):ope_stack.append(str)continueif str == ')':while ope_stack[-1] != '(':temp()ope_stack.pop()continue# 若当前符号优先级小于等于栈顶符号优先级，则进行运算# 直至栈为空，或者当前符号优先级大于栈顶符号优先级while prority_dict[str] > prority_dict[ope_stack[-1]]:temp()# 若栈已经为空、或栈顶符号为‘(’，则直接退出循环if (len(ope_stack) == 0) or (ope_stack[-1] == '('):breakope_stack.append(str)continue# 表达式遍历完成，检查符号栈中是否还有符号if len(ope_stack) == 0:return num_stack[-1]else:while len(ope_stack) != 0:temp()return num_stack[-1]

main.py：

python">import logical_operation.Algorithm as al
import pandas as pd
import sysif __name__ == '__main__':exp = input("请输入表达式： ")# 指定变量var_name = ['p', 'q', 'r']result = list()# 生成0/1for i in range(2 ** len(var_name)):bin_list = list(str(bin(i))[2:].zfill(len(var_name)))# 将变量替换为01expt = expfor j in range(len(var_name)):expt = expt.replace(var_name[j], bin_list[j])res = al.algorithm(expt)if res == -1:print("error!!!")sys.exit(0)bin_list.append(res)result.append(bin_list)var_name.append(exp)result2 = pd.DataFrame(result, columns=var_name, index=None)M_list = list()m_list = list()for i in range(len(result)):if result[i][len(var_name)-1] == 0:M_list.append(f"M{i}")else:m_list.append(f"m{i}")print(f"主合取范式为：{ '^'.join(M_list) }")print(f"主析取范式为：{ 'v'.join(m_list) }")print(result2)