实现一个函数 terms(s:str),输入s为一合式公式,返回s的主析取范式中包含合取式的数量。其中,s中的联结词仅可能包含¬,∧,∨,分别用not,and,or表示,s中的变元包含且仅包含P,Q,R。
时间: 2024-05-21 21:10:23 浏览: 10
思路:
主析取范式是由合取式连接而成的析取式,因此我们可以先将原始公式转化为主合取范式,然后再将其转化为主析取范式。
具体来说,我们可以先将s中的每个子公式转化为主合取范式,然后再将它们合并为一个主析取范式。转化为主合取范式的方法是利用德摩根定理将所有否定符号移到变元上,然后利用分配律将与运算转化为多个或运算的合取式。
例如,对于公式s = "P and (not Q or R)",我们可以先将not Q转化为Q的否定形式not(not Q),然后利用分配律将s转化为"(P and not Q) or (P and R)",这就是s的主合取范式。然后我们再将它转化为主析取范式"(P or P) and (P or R) and (not Q or P) and (not Q or R)",其中包含了4个合取式。
代码实现如下:
def terms(s:str) -> int:
# 将公式转化为主合取范式
def cnf(s:str) -> str:
# 将否定符号移到变元上
s = s.replace("not P", "¬P").replace("not Q", "¬Q").replace("not R", "¬R")
# 利用分配律将与运算转化为多个或运算的合取式
s = s.replace("P and Q", "(P or ¬Q) and (Q or ¬P)")
s = s.replace("P and R", "(P or ¬R) and (R or ¬P)")
s = s.replace("Q and R", "(Q or ¬R) and (R or ¬Q)")
return s
# 将主合取范式转化为主析取范式
def dnf(s:str) -> str:
# 将合取式拆分为多个或运算
clauses = s.split(" and ")
# 生成所有可能的合取式
combinations = [[]]
for clause in clauses:
new_combinations = []
for c in clause.split(" or "):
for combination in combinations:
new_combinations.append(combination + [c])
combinations = new_combinations
# 将合取式转化为主析取范式
result = ""
for combination in combinations:
result += "(" + " or ".join(combination) + ") and "
return result[:-5]
s = cnf(s)
s = dnf(s)
return s.count(" and ") + 1
# 测试
print(terms("P and (not Q or R)")) # 4
print(terms("(not P or Q) and (P or R)")) # 2
print(terms("(P and Q) or (not P and R)")) # 2
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)