Ctrl+K

課題: プログラミングのない世界

課題: プログラミングのない世界#

See also

\[ f: \{0, 1\}^k \rightarrow \{0, 1\} \]
%%ai vioras
Pythonでxorと等価な入出力を持つ論理関数を自動的に合成する方法を教えてください

PythonでXORと等価な論理関数を自動的に合成するために、真理値表とブール代数を使用します。

ここでは、XORの真理値表を使用して、ブール関数を生成します。

XOR関数は2つの入力（A, B）に対して以下の出力（Y）を生成します：

| A | B | Y | |—|—|—| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 |

この真理値表から、ブール関数を生成することができます。ブール関数は、以下のように表すことができます：

$Y = (\neg A \land B) \lor (A \land \neg B)$

これは、ソレノイド表記では次のようになります：

$Y = (!A & B) | (A & !B)$

これをPython関数として書き出すと以下のようになります：

def xor(A, B):
    return (not A and B) or (A and not B)

ここで、andは論理積（AND）、orは論理和（OR）、notは否定（NOT）を表します。これらの演算子を組み合わせて、XOR関数を表現しています。

この関数は入力AとBがどちらも真または偽のときに偽を返し、入力が一方が真で一方が偽のときに真を返すので、XORの動作を模倣します。

以上がPythonでXORと等価な論理関数を自動的に合成する方法です。

Note

検証します

def xor(A, B):
    return (not A and B) or (A and not B)

import itertools
list(itertools.product([0, 1], repeat=2))

[(0, 0), (0, 1), (1, 0), (1, 1)]

[xor(*xy) for xy in itertools.product([0, 1], repeat=2)]

[0, 1, True, False]

from sympy import symbols
from sympy.logic.boolalg import ANFform, to_anf
A, B = symbols('A B')

to_anf((~ A & B) | (A & ~B))
\[\displaystyle A \veebar B\]

Note

ANFやCNF、DNFについて

CNF and DNF, ANF#

論理演算には相等な表現が無数に存在する。ある規約の下で「標準形」へ簡略化が可能:

%%ai vioras
sympyの`logic.boolalg.ANFform()`を使ってください

PythonのSymPyライブラリを使用して、XORと等価な論理関数を自動的に合成することが可能です。SymPyは数学のシンボリック計算を行うためのPythonライブラリで、ブール代数の関数も提供しています。logic.boolalg.ANFform()関数は、論理関数の代数的正規形（Algebraic Normal Form）を生成します。

以下に、XORと等価な論理関数を自動的に合成するPythonコードを示します：

from sympy import symbols
from sympy.logic.boolalg import Or, And, Not, truth_table, ANFform

# 入力AとBをシンボルとして定義します
A, B = symbols('A B')

# XOR関数を定義します
XOR = Or(And(A, Not(B)), And(Not(A), B))

# XOR関数の代数的正規形を生成します
ANF = ANFform(XOR)

# 結果を出力します
print(ANF)

このコードは、SymPyのシンボル、ブール関数、真理値表、そして代数的正規形の機能を使用しています。まず、入力AとBをシンボルとして定義します。次に、これらのシンボルを使用してXOR関数をブール関数として定義します。そして、ANFform()関数を使用してXOR関数の代数的正規形を生成します。

最後に、生成された代数的正規形を出力します。これがXORと等価な論理関数の自動的な合成です。

ANFform?

Signature: ANFform(variables, truthvalues)
Docstring:
The ANFform function converts the list of truth values to
Algebraic Normal Form (ANF).

The variables must be given as the first argument.

Return True, False, logical :py:class:`~.And` function (i.e., the
"Zhegalkin monomial") or logical :py:class:`~.Xor` function (i.e.,
the "Zhegalkin polynomial"). When True and False
are represented by 1 and 0, respectively, then
:py:class:`~.And` is multiplication and :py:class:`~.Xor` is addition.

Formally a "Zhegalkin monomial" is the product (logical
And) of a finite set of distinct variables, including
the empty set whose product is denoted 1 (True).
A "Zhegalkin polynomial" is the sum (logical Xor) of a
set of Zhegalkin monomials, with the empty set denoted
by 0 (False).

Parameters
==========

variables : list of variables
truthvalues : list of 1's and 0's (result column of truth table)

Examples
========
>>> from sympy.logic.boolalg import ANFform
>>> from sympy.abc import x, y
>>> ANFform([x], [1, 0])
x ^ True
>>> ANFform([x, y], [0, 1, 1, 1])
x ^ y ^ (x & y)

References
==========

.. [1] https://en.wikipedia.org/wiki/Zhegalkin_polynomial
File:      /opt/conda/lib/python3.11/site-packages/sympy/logic/boolalg.py
Type:      function

%%ai vioras
`ANFform`の使い方が間違っています。第一引数は論理変数のリストを、
第二引数はその組み合わせで得られる出力の値をリストで与えます

申し訳ありません、私の誤りです。ANFform関数の使用方法を正しく説明しましょう。

ANFform関数は、論理関数の代数的正規形（Algebraic Normal Form）を生成します。この関数には2つの引数が必要です：論理変数のリストと、それらの組み合わせで得られる出力の値のリストです。

以下の例は、XOR関数の代数的正規形を生成します：

from sympy import symbols
from sympy.logic.boolalg import ANFform

# 入力AとBをシンボルとして定義します
A, B = symbols('A B')

# XOR関数の結果をリストとして定義します
# 入力の組み合わせは (A=False, B=False), (A=False, B=True), (A=True, B=False), (A=True, B=True) の順になります
result = [False, True, True, False]

# XOR関数の代数的正規形を生成します
ANF = ANFform([A, B], result)

# 結果を出力します
print(ANF)

このコードは、ANFform関数に論理変数のリスト [A, B] と、それらの組み合わせで得られる出力の値のリスト result を引数として渡します。出力のリスト result は、入力の組み合わせ (A=False, B=False), (A=False, B=True), (A=True, B=False), (A=True, B=True) の順に対応しています。

最後に、生成された代数的正規形を出力します。これがXORと等価な論理関数の自動的な合成です。

from sympy import symbols
from sympy.logic.boolalg import ANFform

# 入力AとBをシンボルとして定義します
A, B = symbols('A B')

# XOR関数の結果をリストとして定義します
# 入力の組み合わせは (A=False, B=False), (A=False, B=True), (A=True, B=False), (A=True, B=True) の順になります
result = [False, True, True, False]

# XOR関数の代数的正規形を生成します
ANF = ANFform([A, B], result)

# 結果を出力します
print(ANF)

A ^ B

%%ai vioras
sympyのマニュアルによると、`ANFform`はZhegalkin polynomialを使っているそうです。その解説をしてください

Zhegalkin多項式（またはアルファベット多項式）は、ブール関数を代表する多項式の一種です。それはブール関数を一連のXORとAND演算子で表現します。Zhegalkin多項式は、ブール関数を分析し、最適化する際に非常に便利です。

Zhegalkin多項式は、ブール多項式の一種であり、その係数は2元体（つまり、値が0または1の体）になります。ブール多項式の各項は、一連の変数のAND（論理積）であり、全体の多項式はこれらの項のXOR（排他的論理和）です。

例えば、2つの変数AとBに対するXOR関数は、Zhegalkin多項式として次のように表現することができます：

$A \oplus B = A \land \neg B \lor \neg A \land B$

ここで $\oplus$ はXOR演算を表し、$\land$ はAND演算を表し、$\lor$ はOR演算を表します。$\neg$ は否定（NOT）を表します。

SymPyのANFform関数は、ブール関数をZhegalkin多項式の形式で表現します。これは、ブール関数の最小化や最適化、あるいはブール回路の設計などに役立ちます。

以上がZhegalkin多項式の基本的な説明です。Zhegalkin多項式はブール代数の強力なツールであり、ブール関数の分析や操作に広く利用されます。

See also

一桁の二進数の加算と等価な論理演算#

import itertools

from sympy.abc import x,y,z
from sympy.logic import simplify_logic

from sympy.logic.boolalg import ANFform, to_cnf, to_dnf

for i,j in itertools.product([0,1], repeat=2):
    print("{:d}+{:d}={:02b} ".format(i,j,i+j), end="")
    print("({:d},{:d})".format(*divmod(i+j,2)))

0+0=00 (0,0)
0+1=01 (0,1)
1+0=01 (0,1)
1+1=10 (1,0)

[divmod(i+j,2) for i,j in itertools.product([0,1], repeat=2)]

[(0, 0), (0, 1), (0, 1), (1, 0)]

list(zip(*[divmod(i+j, 2) for i, j in itertools.product([0,1], repeat=2)]))

[(0, 0, 0, 1), (0, 1, 1, 0)]

for qr in zip(*[divmod(i+j, 2) for i,j in itertools.product([0,1], repeat=2)]):
    print(ANFform([x, y], qr))

x & y
x ^ y
Contents