1

我是布尔表达式的新手。

我被赋予了 F(w,x,y,z) = xy’ + x’z’ + wxz + wx’y使用 K 映射进行简化的任务。

我已经做到了，结果是wx’+w’y’+xyz。

现在我必须“以标准 SOP 形式编写。您需要提供获得标准 SOP 的步骤”。

我不知道该怎么做。我认为 k 映射后的结果是 sop。

4

3 回答 3

0

我们可以在 4 个变量中实现 K-Map 算法python，如下所示。该函数接受 SOP（乘积之和）形式的布尔函数和变量名称，并返回简化的简化表示。基本上，您需要创建包含 8、4、2 等 2 次幂的总项的矩形组，并尝试在一组中覆盖尽可能多的元素（我们需要覆盖所有元素）。

例如，函数可以表示为 F(w,x,y,z) = xy' + x'z' + wxz + wx'y SOP 形式为 f(w,x,y,z)=∑(0 ,2,4,5,8,10,11,12,13,15)，从下表可以看出：

在此处输入图像描述

从下一个代码片段的输出可以看出，程序输出简化形式x¬y + ¬x¬z + wyz，其中布尔变量x的否定表示为¬x代码中的。

from collections import defaultdict
from itertools import permutations, product
    
def kv_map(sop, vars):
    
    sop = set(sop)
    not_covered = sop.copy()
    sop_covered = set([])
    
    mts = [] # minterms
    
    # check for minterms with 1 variable
    all_3 = [''.join(x) for x in product('01', repeat=3)]
    for i in range(4):
        for v_i in [0,1]:
                if len(not_covered) == 0: continue
                mt = ('' if v_i else '¬') + vars[i]
                s = [x[:i]+str(v_i)+x[i:] for x in all_3]
                sop1 = set(map(lambda x: int(x,2), s))
                if len(sop1 & sop) == 8 and len(sop_covered & sop1) < 8: # if not already covered
                    mts.append(mt)
                    sop_covered |= sop1
                    not_covered = not_covered - sop1
        if len(not_covered) == 0:
           return mts
    
    # check for minterms with 2 variables
    all_2 = [''.join(x) for x in product('01', repeat=2)]
    for i in range(4):
        for j in range(i+1, 4):
            for v_i in [0,1]:
                for v_j in [0,1]:
                    if len(not_covered) == 0: continue
                    mt = ('' if v_i else '¬') + vars[i] + ('' if v_j else '¬') + vars[j]
                    s = [x[:i]+str(v_i)+x[i:] for x in all_2]
                    s = [x[:j]+str(v_j)+x[j:] for x in s]
                    sop1 = set(map(lambda x: int(x,2), s))
                    if len(sop1 & sop) == 4 and len(sop_covered & sop1) < 4: # if not already covered
                        mts.append(mt)
                        sop_covered |= sop1
                        not_covered = not_covered - sop1
    if len(not_covered) == 0:
        return mts

    # check for minterms with 3 variables similarly (code omitted)
    # ... ... ...
    
    return mts
    
mts = kv_map([0,2,4,5,8,10,11,12,13,15], ['w', 'x', 'y', 'z'])
mts
# ['x¬y', '¬x¬z', 'wyz']

下面的动画展示了上述代码如何（贪婪地）简化以 SOP 形式给出的布尔函数（基本目标是用最少的 2 次方块覆盖所有 1）。由于该算法是贪婪的，它可能会陷入某个局部最小值，我们需要小心。

在此处输入图像描述

于 2021-12-02T22:58:57.213 回答
0

是的，您已经以 SOP 形式拥有它。但第二个问题是关于标准（又名规范）SOP 形式的。这比必须使用 K-maps 更容易找到（但它通常很长），它只是 minterms 的总和。

于 2016-02-05T16:02:35.667 回答
0

我认为您的解决方案并未涵盖所有解决方案。这些卡诺图显示了原始表达式、简化版本（最小 SOP）和规范 SOP，其中每个产品都包含所有文字（所有给定变量或其否定）。

原始、简化和完整 SOP 的 K-map

原来的表达是

F(w,x,y,z) = x·¬y + ¬x·¬z + w·x·z + w·¬x·y

– 在对应的（第一个）K-map 中有两个四和两对。

使用 K-map 简化的原始表达式（如第二个所示）：

F(w,x,y,z) = x·¬y + ¬x·¬z + w·y·z

与您的不同，但您可以使用 wolframalpha 在线工具检查它是否是简化的原始表达式。

它也是最小的 DNF，但不是最小项的总和（输出等于 1），因为总和的每个乘积中并不存在所有变量。

第三个 K-map 显示了十个带圆圈的最小术语。它们形成了规范的 DNF：

F(w,x,y,z) = m0 + m2 + m4 + m5 + m8 + m10 + m11 + m12 + m13 + m15 =
           = ¬w·¬x·¬y·¬z + ¬w·¬x·y·¬z + ¬w·x·¬y·¬z + ¬w·x·¬y·z + w·¬x·¬y·¬z 
             + w·¬x·y·¬z + w·¬x·y·z + w·x·¬y·¬z + w·x·¬y·z + w·x·y·z

我检查了您的简化表达式，但并未涵盖所有表达式（即使有一些有用的不关心状态（标记为 X））。也许你打错了。还是原来的表达有错别字？

于 2016-07-11T10:02:46.977 回答