PythonでPOS形式をSOP形式に変換するプログラムの実装方法

本記事では、次の問題に対する解決方法について詳しく解説します。

問題定義
標準POS形式(Product of Sums:和の積)で表された論理式が与えられたとき、それを等価な標準SOP形式(Sum of Products:積和)へ変換すること。

変換の基本的な手順は、まずPOS形式に含まれる変数(アルファベット)の総数を数え、続いてすべての最大項(maxterm)と最小項(minterm)を計算していくというものです。

処理の流れ

• 変数の個数をカウント: POS式の中で最初の「.(ドット)」より前に現れるアルファベットの数を数えます。
• 最大項の抽出: 各括弧内の項を読み取り、補数(‘)付きの変数を「1」、通常の変数を「0」とみなして2進数列を作成し、10進整数に変換してリストへ格納します。
• 最小項の生成: 最大項として現れない組み合わせ(0〜2ⁿ−1)を求め、各ビットの値に応じて変数名と補数記号を連結し、SOP形式の論理式を組み立てます。

それでは、実際の実装を通してこの考え方を確認してみましょう。

コード例

# 標準POS形式を標準SOP形式に変換するPythonコード

# 変数の個数を数える関数
def count_no_alphabets(POS):
    i = 0
    no_var = 0
    # 最初の「.」より前にあるアルファベットの総数を数える
    while (POS[i] != '.'):
        # 文字がアルファベットかどうかを判定
        if (POS[i].isalpha()):
            no_var += 1
        i += 1
    return no_var

# 最大項を整数値として抽出する関数
def Cal_Max_terms(Max_terms, POS):
    a = ""
    i = 0
    while (i < len(POS)):
        if (POS[i] == '.'):
            # 2進数を10進数へ変換
            b = int(a, 2)
            # 項(整数型)をリストに追加
            Max_terms.append(b)
            # 文字列を空に戻す
            a = ""
            i += 1
        elif (POS[i].isalpha()):
            # 変数が補数(')付きかどうかをチェック
            if (i + 1 != len(POS) and POS[i + 1] == "'"):
                # 文字列に「1」を連結
                a += '1'
                # アルファベット分と記号「'」分の2文字ぶん進める
                i += 2
            else:
                # 文字列に「0」を連結
                a += '0'
                i += 1
        else:
            i += 1
    # 最後の項(整数型)をリストに追加
    Max_terms.append(int(a, 2))

# 最小項を2進数で生成し、最終的にSOP形式へ変換する関数
def Cal_Min_terms(Max_terms, no_var, start_alphabet):
    # リストの宣言
    Min_terms = []
    # 全変数から生成される項の総数 = 2^no_var
    max_val = 2 ** no_var
    for i in range(0, max_val):
        # 現在の項が最大項リストに存在しないか確認
        if (Max_terms.count(i) == 0):
            # 整数を2進数へ変換
            b = bin(i)[2:]
            # 各積項の桁数を変数の個数に揃えるため、
            # 2進数の先頭に0を挿入するループ
            while (len(b) != no_var):
                b = '0' + b
            # 項をリストに追加
            Min_terms.append(b)
    SOP = ""
    # 最小項がなくなるまで繰り返し処理
    for i in Min_terms:
        # 先頭の変数を取得
        value = start_alphabet
        # 各ビット(0と1)について処理
        for j in i:
            # 変数が補数(反転)かどうかをチェック
            if (j == '0'):
                # 値と補数演算子「'」を連結
                SOP = SOP + value + "'"
            # 補数でない変数の場合
            else:
                # 値のみを連結
                SOP = SOP + value
            # 変数を隣接する次のアルファベットへ進める
            value = chr(ord(value) + 1)
        # 「+」演算子を連結
        SOP = SOP + "+"
    # 余分な末尾の「+」を削除
    SOP = SOP[:-1]
    return SOP

# メイン関数
def main():
    # 入力となるPOS形式の論理式
    POS_expr = "(A'+B'+C).(A+B+C').(A+B'+C).(A'+B+C)"
    Max_terms = []
    no_var = count_no_alphabets(POS_expr)
    Cal_Max_terms(Max_terms, POS_expr)
    SOP_expr = Cal_Min_terms(Max_terms, no_var, POS_expr[1])
    print("Standard SOP form of " + POS_expr + " ==> " + SOP_expr)

# ドライバーコード
if __name__ == "__main__":
    main()

出力結果

Standard SOP form of (A'+B'+C).(A+B+C').(A+B'+C).(A'+B+C) ==>
A'B'C'+A'BC+AB'C+ABC

すべての変数はローカルスコープ内で宣言されており、それぞれの参照範囲も上記のコードから確認できます。

まとめ

本記事では、Pythonを使って標準POS形式の論理式を標準SOP形式へ変換する方法を解説しました。「変数のカウント → 最大項の抽出 → 残りの組み合わせを最小項として生成」という一連の手順を理解すれば、任意のPOS形式の論理式を自動的にSOP形式へ変換できるようになります。論理回路設計やブール代数による式の簡略化など、幅広い場面で役立つテクニックですので、ぜひ実際にコードを動かして試してみてください。