コンセンサス定理

変数入力			関数値
×	y	z	${\displaystyle xy\vee {\bar {x}}z\vee yz}$	${\displaystyle xy\vee {\bar {x}}z}$
0	0	0	0	0
0	0	1	1	1
0	1	0	0	0
0	1	1	1	1
1	0	0	0	0
1	0	1	0	0
1	1	0	1	1
1	1	1	1	1

AB ∨ A C ∨ BCのカルノー図。赤い四角形を省略しても覆われる領域は変わりません。

ブール代数では、コンセンサス定理またはコンセンサス規則^{[ 1 ]}は次の式で表される。

${\displaystyle xy\vee {\bar {x}}z\vee yz=xy\vee {\bar {x}}z}$

項 と の合意項または解決項はです。これは、一方の項では否定されずに他方の項では否定されるリテラルを除く、項の一意なリテラルすべての論理積です。に、 で否定される項が含まれる場合（またはその逆）、合意項は偽です。つまり、合意項は存在しません。 ${\displaystyle xy}$ ${\displaystyle {\bar {x}}z}$ ${\displaystyle yz}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle yz}$

この方程式の 連言双対は次のようになります。

${\displaystyle (x\vee y)({\bar {x}}\vee z)(y\vee z)=(x\vee y)({\bar {x}}\vee z)}$

証拠

${\displaystyle {\begin{aligned}xy\vee {\bar {x}}z\vee yz&=xy\vee {\bar {x}}z\vee (x\vee {\bar {x}})yz\\&=xy\vee {\bar {x}}z\vee xyz\vee {\bar {x}}yz\\&=(xy\vee xyz)\vee ({\bar {x}}z\vee {\bar {x}}yz)\\&=xy(1\vee z)\vee {\bar {x}}z(1\vee y)\\&=xy\vee {\bar {x}}z\end{aligned}}}$

コンセンサス

選言の2つの連言項のコンセンサスまたはコンセンサス項は、一方の項にリテラル が含まれ、もう一方の項にリテラル が含まれる場合、つまり対立 が定義されます 。コンセンサスは、 2つの項の連言からと、および重複するリテラルを省略したものです。例えば、とのコンセンサスはです。^{[ 2 ]}対立が2つ以上ある場合、コンセンサスは定義されません。 ${\displaystyle a}$ ${\displaystyle {\bar {a}}}$ ${\displaystyle a}$ ${\displaystyle {\bar {a}}}$ ${\displaystyle {\bar {x}}yz}$ ${\displaystyle w{\bar {y}}z}$ ${\displaystyle w{\bar {x}}z}$

規則の連言双対については、コンセンサスは解決推論規則から導出され、それを通して導出されます。これは、LHSがRHSから導出可能であることを示しています（A → BならばA → ABであり、AをRHSに、Bを(y∨z)に置き換えます） 。RHSは、LHSから連言消去推論規則によって簡単に導出できます。RHS → LHS、LHS → RHS（命題論理学）なので、LHS = RHS（ブール代数）となります。 ${\displaystyle y\vee z}$ ${\displaystyle (x\vee y)}$ ${\displaystyle ({\bar {x}}\vee z)}$

アプリケーション

ブール代数では、繰り返しコンセンサスは式のブレイク標準形を計算するアルゴリズムの中核を成す。^{[ 2 ]}

デジタルロジックでは、回路にコンセンサス項を含めることで競合の危険性を排除できる。^{[ 3 ]}

歴史

コンセンサスの概念は、1937年にアーチー・ブレイクによってブレイク標準形に関連して導入されました。^{[ 4 ]}これは1954年にサムソンとミルズによって再発見され、^{[ 5 ]} 、 1955年にはクワインによって再発見されました。 ^{[ 6 ]}クワインは「コンセンサス」という用語を造語しました。ロビンソンは1965年にこの用語を「解決原理」の基礎として条項に適用しました。^{[ 7 ] [ 8 ]}

参考文献

1. フランク・マーカム・ブラウン『ブール推論：ブール方程式の論理』第2版 2003年、44ページ
2. フランク・マーカム・ブラウン『ブール推論：ブール方程式の論理』第2版 2003年、p. 81
3. Rafiquzzaman, Mohamed (2014). 『デジタルロジックとマイクロコントローラの基礎』（第6版）John Wiley & Sons. p. 65. ISBN 978-1118855799。
4. 「ブール代数の標準表現」、シカゴ大学数学科博士論文、1937年、 ProQuest 301838818、JCC McKinsey, The Journal of Symbolic Logic 3 :2:93 (1938年6月) doi : 10.2307/2267634 JSTOR 2267634でレビュー。コンセンサス関数はpp. 29–31に示され、定義されている。  ${\displaystyle \sigma }$
5. エドワード・W・サムソン、バートン・E・ミルズ、空軍ケンブリッジ研究センター、技術報告書54-21、1954年4月
6. ウィラード・ヴァン・オーマン・クワイン、「真理関数の単純化の問題」、アメリカ数学月刊誌59 :521-531、1952年JSTOR  2308219
7. ジョン・アラン・ロビンソン、「解決原理に基づく機械指向ロジック」、 Journal of the ACM 12 :1:23–41。
8. ドナルド・アーヴィン・クヌース著『コンピュータプログラミングの芸術4A：組み合わせアルゴリズム』パート1、539ページ

さらに読む

• Roth, Charles H. Jr.、Kinney, Larry L. (2004, 2010). 『論理設計の基礎』第6版、66ページ以降。