使用python编写一个函数terms(s:str),输入s为一合式公式,返回s的主析取范式中包含合取式的数量。其中,s中的联结词仅可能包含¬,Λ,V,分别用not,and,or表示,s中的变元包含且仅包含P,Q,R。
时间: 2024-05-15 13:15:47 浏览: 93
求公式的主合取范式和主析取范式
5星 · 资源好评率100%
首先需要将输入的公式转化为主析取范式,然后统计其中包含合取式的数量。
可以使用递归的方法,将公式不断进行分解,直到分解为原子命题或否定的原子命题。然后根据主析取范式的定义,将公式转化为若干个合取式的析取,并统计其中包含合取式的数量。
以下是代码实现:
```python
def terms(s: str) -> int:
# 将公式转化为主析取范式
def to_dnf(s: str) -> str:
if s[0] == "¬":
if s[1] == "¬":
return to_dnf(s[2:])
elif s[1] == "(":
i = find_matching_parentheses(s)
return to_dnf("¬" + to_dnf(s[2:i])) + to_dnf(s[i+1:])
else:
return s
elif s[0] == "(":
i = find_matching_parentheses(s)
return to_dnf(s[1:i]) + to_dnf(s[i+1:])
elif "V" in s:
i = s.index("V")
return to_dnf(s[:i]) + to_dnf(s[i+1:])
else:
return s
# 找到与左括号匹配的右括号的位置
def find_matching_parentheses(s: str) -> int:
stack = []
for i, c in enumerate(s):
if c == "(":
stack.append(i)
elif c == ")":
if len(stack) == 1:
return i
else:
stack.pop()
raise ValueError("No matching parentheses")
# 统计主析取范式中包含合取式的数量
def count_conjunctions(s: str) -> int:
if s[0] == "(":
i = find_matching_parentheses(s)
return count_conjunctions(s[1:i]) + count_conjunctions(s[i+1:])
elif "Λ" in s:
i = s.index("Λ")
return count_conjunctions(s[:i]) + count_conjunctions(s[i+1:])
elif "V" in s:
return count_conjunctions(s[s.index("V")+1:])
else:
return 1
dnf = to_dnf(s)
return count_conjunctions(dnf)
```
例如,输入公式"¬PΛ(QV¬R)",输出2,表示主析取范式中包含两个合取式。
阅读全文