Discrete-mathematics-boolean-expressions-functions

ブール式と関数

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

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

ブール関数

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

例-Let、$ 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 $

ブール式

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

例-$ AB’C $はブール式です。

ブールID

二重補数法

$ \ sim（\ sim A）= A $

補則

$ A + \ sim A = 1 $（またはフォーム）

$A . \ sim A = 0 $（およびフォーム）

べき等法

$ A + A = A $（ORフォーム）

$A . A = A $（ANDフォーム）

アイデンティティ法

$ A + 0 = A $（ORフォーム）

$A . 1 = A $（およびフォーム）

支配法

$ A + 1 = 1 $（またはフォーム）

$A . 0 = 0 $（およびフォーム）

可換法

$ A + B = B + A $（ORフォーム）

$A. B = B A $（およびフォーム）

連想法

$ A （B + C）=（A + B） C $（ORフォーム）

$A. (B . C）=（A。 B) . C $（ANDフォーム）

吸収法

$A. （A + B）= A $

$ A +（A。 B）= A $

簡素化法

$A . （\ sim A + B）= A B$

$ A +（\ sim A。 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）= \ sim A \ sim B $

正規形

ブール式の場合、2種類の正準形があります-

• ミンタームの合計（SOM）フォーム
• maxterms（POM）形式の積

Sumterm of Minterms（SOM）またはSum of Products（SOP）フォーム

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

F（変数のリスト）= ∑（1-mintermインデックスのリスト）

and

F '（変数のリスト）= ∑（0最小項インデックスのリスト）

A	B	C	Term	Minterm
0	0	0	x’y’z’	m0
0	0	1	x’y’z	m1
0	1	0	x’yz’	m2
0	1	1	x’yz	m3
1	0	0	xy’z’	m4
1	0	1	xy’z	m5
1	1	0	xyz’	m6
1	1	1	xyz	m7

例

Let、$ F（x、y、z）= x 'y' z '+ x y' z + x y z '+ x y z $

または、$ 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' y z + x 'y' z + x 'y z' + x y '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）$

Product of Maxterms（POM）またはProduct of Sums（POS）フォーム

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

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

and

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

A	B	C	Term	Maxterm
0	0	0	x + y + z	M0
0	0	1	x + y + z’	M1
0	1	0	x + y’ + z	M2
0	1	1	x + y’ + z’	M3
1	0	0	x’ + y + z	M4
1	0	1	x’ + y + z’	M5
1	1	0	x’ + y’ + z	M6
1	1	1	x’ + y’ + z’	M7

例

$ 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ゲート

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

A	~A
0	1
1	0

ANDゲート

ANDゲートは、すべての入力が高い場合にのみ高い出力を与える論理ゲートであり、そうでない場合は低い出力を与えます。 AND演算を示すためにドット（。）が使用されます。

A	B	A.B
0	0	0
0	1	0
1	0	0
1	1	1

ORゲート

ORゲートは、少なくとも1つの入力が高い場合に高い出力を与える論理ゲートです。 OR演算を示すためにプラス（＆plus;）が使用されます。

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

NANDゲート

NANDゲートは、すべての入力が高い場合にのみ低い出力を与える論理ゲートであり、そうでない場合は高い出力を与えます。

A	B	~(A.B)
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（排他的OR）ゲート

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