用python语言实现一个函数 terms(s:str),输入s为一合式公式,返回s的主析取范式中包含合取式的数量。其中,s中的联结词仅可能包含一,^,V,分别用 not,and,or 表示,s中的变元包含且仅包含P,Q,R。
时间: 2023-05-30 21:01:18 浏览: 132
思路:首先将输入的公式化为主合取范式,然后统计主合取范式中包含合取式的数量。
具体实现:
1. 将输入的字符串转化为列表,方便处理。
2. 定义一个函数`to_cnf`,将公式化为主合取范式。主要思路是利用 De Morgan 定律将公式中的否定词移至变量上方,然后利用分配律将合取词移至最外层,形成主合取范式。
3. 定义一个函数`count_conj`,统计主合取范式中包含合取式的数量。主要思路是遍历主合取范式中的每一个子句,如果其中包含一个合取式,就将计数器加一。
代码如下:
```python
def to_cnf(s):
# 将字符串转化为列表,方便处理
tokens = list(s)
# 将 ~P 转化为 not P
for i in range(len(tokens)):
if tokens[i] == '~':
tokens[i] = 'not'
tokens[i+1] = tokens[i+1].upper()
# 将 P ^ Q 转化为 (P and Q)
i = 0
while i < len(tokens):
if tokens[i] == '^':
tokens[i-1] = '(' + tokens[i-1]
j = i+1
while j < len(tokens) and tokens[j] != 'V':
j += 2
tokens[j-1] = tokens[j-1] + ')'
tokens[i] = 'and'
i += 1
# 将 P V Q 转化为 (P or Q)
i = 0
while i < len(tokens):
if tokens[i] == 'V':
tokens[i-1] = '(' + tokens[i-1]
j = i+1
while j < len(tokens) and tokens[j] != '^':
j += 2
tokens[j-1] = tokens[j-1] + ')'
tokens[i] = 'or'
i += 1
return ''.join(tokens)
def count_conj(s):
cnf = to_cnf(s)
tokens = cnf.split()
count = 0
for token in tokens:
if 'and' in token:
count += 1
return count
```
示例:
```python
s = '(P ^ Q) V (R ^ ~P)'
print(to_cnf(s)) # ((P or R) and (Q or R) and (not P or R))
print(count_conj(s)) # 3
```
阅读全文