ブール式と関数

ブール代数は論理の代数です。これは、0(False)と1(True)の2つの離散値を持つことができる変数を扱います。および論理的に重要な操作。シンボリックロジックを操作する最も初期の方法は、George Booleによって発明され、その後ブール代数として知られるようになりました。

ブール代数は、スイッチング理論、基本的な電子回路の構築、デジタルコンピュータの設計に幅広く適用できるため、コンピュータサイエンスに欠かせないツールになりました。

ブール関数

A Boolean functionは特殊な種類の数学関数$ f:X ^ n \ rightarrow X $の次数nです。ここで$ X = \ lbrace {0、1} \ rbrace $はブール領域であり、nは非負の整数です。ブール入力からブール出力を導出する方法について説明します。

Example− $ F(A、B)= A'B '$とします。これは、ブール変数の順序対のセットからセット$ \ lbrace {0、1} \ rbrace $までの次数2の関数です。ここで、$ F(0、0)= 1、F(0、1)= 0、 F(1、0)= 0 $および$ F(1、1)= 0 $

ブール式

A Boolean expression常にブール値を生成します。ブール式は、ブール定数(TrueまたはFalse)、ブール変数、および論理接続の組み合わせで構成されます。各ブール式はブール関数を表します。

Example − $ AB'C $はブール式です。

ブールID

二重補数法

$ \ sim(\ sim A)= A $

補法

$ A + \ sim A = 1 $(またはフォーム)

$ A。\ sim A = 0 $(ANDフォーム)

べき等法

$ A + A = A $(またはフォーム)

$ A。A = A $(およびフォーム)

アイデンティティ法

$ A + 0 = A $(またはフォーム)

$ A。1 = A $(およびフォーム)

支配法

$ A + 1 = 1 $(またはフォーム)

$ A。0 = 0 $(およびフォーム)

可換法則

$ A + B = B + A $(またはフォーム)

$ A。B = B。A $(およびフォーム)

結合法則

$ A +(B + C)=(A + B)+ C $(またはフォーム)

$ A。(B。C)=(A。B)。C $(およびフォーム)

吸収法則

$ A。(A + B)= A $

$ A +(A。B)= A $

単純化法

$ A。(\ sim A + B)= A。B $

$ A +(\simA。B)= A + B $

分配法則

$ A +(B。C)=(A + B)。(A + C)$

$ A。(B + C)=(A。B)+(A。C)$

ド・モルガンの法則

$ \ sim(A。B)= \ sim A + \ sim B $

$ \ sim(A + B)= \ simA。\ sim B $

正準形式

ブール式には、2種類の正規形があります-

  • 最小項の合計(SOM)フォーム
  • maxterms(POM)フォームの積

最小項の合計(SOM)または製品の合計(SOP)フォーム

mintermは、直接形式または補完形式のいずれかで取得されたすべての変数の積です。任意のブール関数は、その1分項の合計として表すことができ、関数の逆関数は、その0分項の合計として表すことができます。したがって、

F(変数のリスト)= ∑(1分間のインデックスのリスト)

そして

F '(変数のリスト)= ∑(0-mintermインデックスのリスト)

A B C 期間 ミンターム
0 0 0 x'y'z ' m 0
0 0 1 x'y'z m 1
0 1 0 x'yz ' m 2
0 1 1 x'yz m 3
1 0 0 xy'z ' m 4
1 0 1 xy'z m 5
1 1 0 xyz ' m 6
1 1 1 xyz m 7

Example

ましょう、$ F(X、Y、Z)= X 'Y' Z '+ XY' Z + XYZ」+ XYZ $

または、$ F(x、y、z)= m_0 + m_5 + m_6 + m_7 $

したがって、

$ F(x、y、z)= \ sum(0、5、6、7)$

ここで、$ F(x、y、z)$の補集合が見つかります

$ F '(x、y、z)= x'yz + x'y' z + x'yz '+ xy'z' $

または、$ F '(x、y、z)= m_3 + m_1 + m_2 + m_4 $

したがって、

$ F '(x、y、z)= \ sum(3、1、2、4)= \ sum(1、2、3、4)$

Maxtermsの積(POM)または合計の積(POS)フォーム

maxtermは、直接形式または補完形式のいずれかで取得されたすべての変数の加算です。任意のブール関数は、その0-maxtermsの積として表すことができ、関数の逆関数は、その1-maxtermsの積として表すことができます。したがって、

F(変数のリスト)= $ \ pi $(0-maxtermインデックスのリスト)。

そして

F '(変数のリスト)= $ \ pi $(1-maxtermインデックスのリスト)。

A B C 期間 Maxterm
0 0 0 x + y + z M 0
0 0 1 x + y + z ' M 1
0 1 0 x + y '+ z M 2
0 1 1 x + y '+ z' M 3
1 0 0 x '+ y + z M 4
1 0 1 x '+ y + z' M 5
1 1 0 x '+ y' + z M 6
1 1 1 x '+ y' + z ' M 7

LET $ F(X、Y、Z)=(X + Y + Z)。(x + y + z ')。(x + y '+ z)。(x '+ y + z)$

または、$ F(x、y、z)= M_0。M_1。M_2。M_4 $

したがって、

$ F(x、y、z)= \ pi(0、1、2、4)$

$ F ''(x、y、z)=(x + y '+ z')。(x '+ y + z')。(x '+ y' + z)。(x '+ y' + z ')$

または、$ F(x、y、z)= M_3。M_5。M_6。M_7 $

したがって、

$ F '(x、y、z)= \ pi(3、5、6、7)$

論理ゲート

ブール関数は、論理ゲートを使用して実装されます。以下は論理ゲートです-

ゲートではありません

NOTゲートは、1ビットの入力を1ビットの出力に反転します。

A 〜A
0 1
1 0

ANDゲート

ANDゲートは、すべての入力がハイの場合にのみハイ出力を提供する論理ゲートであり、それ以外の場合はロー出力を提供します。ドット(。)は、AND演算を示すために使用されます。

A B AB
0 0 0
0 1 0
1 0 0
1 1 1

またはゲート

ORゲートは、入力の少なくとも1つがハイの場合にハイ出力を提供する論理ゲートです。プラス(+)は、OR演算を示すために使用されます。

A B A + B
0 0 0
0 1 1
1 0 1
1 1 1

NANDゲート

NANDゲートは、すべての入力がハイの場合にのみロー出力を提供する論理ゲートであり、それ以外の場合はハイ出力を提供します。

A B 〜(AB)
0 0 1
0 1 1
1 0 1
1 1 0

NORゲート

NORゲートは、両方の入力が低い場合に高い出力を提供する論理ゲートであり、そうでない場合は低い出力を提供します。

A B 〜(A + B)
0 0 1
0 1 0
1 0 0
1 1 0

XOR(排他的論理和)ゲート

XORゲートは、入力が異なる場合に高出力を提供する論理ゲートであり、そうでない場合は低出力を提供します。

A B A⊕B
0 0 0
0 1 1
1 0 1
1 1 0

X-NOR(排他的NOR)ゲート

EX-NORゲートは、入力が同じ場合は高出力を提供し、それ以外の場合は低出力を提供する論理ゲートです。

A B A X-NOR B
0 0 1
0 1 0
1 0 0
1 1 1