algorithm - SOP のブール式

Question

私はブール式が初めてです。

F(w,x,y,z) = xy’ + x’z’ + wxz + wx’yK マップを使用して単純化するタスクが与えられました 。

私はそれをやったし、結果はwx’+w’y’+xyzです。

ここで、「標準 SOP フォームで記述します。標準 SOP を取得するための手順を提供する必要があります」。

そして、私はそれを行う方法がわかりません。kマップ後の結果はsopだと思いました。

Answer 1

はい、すでに SOP 形式になっています。しかし、2 番目の質問は、標準 (別名正規) SOP 形式に関するものです。これは、K マップを使用するよりもはるかに簡単に見つけることができます (ただし、多くの場合、長くなります)。これは、minterms の合計です。

Answer 2

あなたのソリューションはすべてのものをカバーしていないと思います。これらのカルノー マップは、元の式、簡略化されたバージョン (最小 SOP)、およびすべての積にすべてのリテラル (指定されたすべての変数またはそれらの否定) が含まれる正規の SOP を示しています。

元の表現は

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

– 2 つの 4 と 2 つのペアが、対応する (最初の) K マップに円で囲まれています。

K-map を使用して単純化された元の式 (2 番目の式を参照):

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

はあなたのものとは異なりますが、たとえば wolframalpha オンライン ツールで、簡略化された元の式であることを確認できます。

これは最小 DNF でもありますが、最小項 (出力が 1 に等しい) の合計ではありません。これは、合計のすべての積にすべての変数が存在するわけではないためです。

3 番目の K マップは、丸で囲まれた 10 個の最小項を示しています。それらは正規の 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

簡略化された式を確認しましたが、すべてがカバーされているわけではありません(いくつかの有用なdo not care状態 (X マーク) があったとしても)。多分あなたはタイプミスをしました。それとも、元の表現にタイプミスがあるのでしょうか?

Answer 3

python以下に示すように、4 つの変数に対してK-Map アルゴリズムを実装できます。この関数は、SOP (積和) 形式のブール関数と変数の名前を受け入れ、単純化された縮小表現を返します。基本的には、8、4、2 のように 2 の累乗の合計項を含む長方形のグループを作成し、1 つのグループでできるだけ多くの要素をカバーするようにする必要があります (すべての要素をカバーする必要があります)。

たとえば、関数は 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 をカバーすることです)。このアルゴリズムは貪欲であるため、注意が必要な局所的な最小値に行き詰まる可能性があります。