ブール代数：基本法則
1. 概要
このチュートリアルでは、ブール代数で使用される基本法則を学習します。
ブール代数が形式論理のより複雑なシステムの構築において持つ役割を研究することから始めます。 そうすることで、後者がブール代数にどのように基づいているか、そしてその法則がどのようにそれを形作るかを学びます。
次に、ブール代数の基本および二次論理演算について学習します。 また、真理値表を解釈する方法と、それらを使用して定理を証明する方法についても学びます。
最後に、基本法則自体を研究し、真理値表の観点からそれらを示します。 その後、これらの法則を適用して、式間の同等性の単純な演習を解決します。
このチュートリアルの最後では、ブール代数の基礎に精通し、ブール演算と真理値表の観点からその基本法則を証明する方法を理解します。
2. ブール代数と論理の関係
命題論理と一階述語論理に関する以前の記事では、命題と述語の間の論理演算について説明しました。 これらの演算が可能なのは、ブール項間で代数演算を実行するための基本的なルールが存在するためです。 この記事では、続いて、ブール代数の基本的なルールを研究します。その上に、他のより複雑な形式論理システムが構築されます。
このテキスト全体で使用する表記法に関する1つの予備的な注意事項：コンピュータサイエンスに関する記事の実践に従って、ここでは1と0のバイナリ表記法を使用して、それぞれ真実と
一階述語論理に関する前回の記事では、一階述語論理は命題論理の一般化であると主張しました。 これは、一階述語論理には命題論理が含まれるという考察につながりました。 ブール代数が命題論理と一階述語論理の両方の前提条件であるという意味で、後者の2つは最初のものを含むと見なすことができます。
この考えを表現するためのより正式な方法は、ブール代数の法則が命題論理と一階述語論理の両方で有効であると言うことです。
3. 利用規約
3.1. ブール用語
ブール項は、ブール代数方程式の項です。 命題および一階述語論理で使用した用語の定義とは対照的に、ブール用語は、の2つの値のうちの1つだけを想定できる単なる変数です。バイナリフィールド。 命題論理の場合のように、世界についての事実の知識に関連するなど、それらには他の条件はありません。 または、一階述語論理の場合のように、関係に関連します。
ブール変数は、、、、、などのラテンアルファベットのイタリック文字で示すことができます。 ブール代数とその法則は、変数に割り当てられた特定の値に関係なく有効になるように構築されています。 したがって、主題に関する文学の実践に従って、ここでは、定理を証明する方法として真理値表を提供します。
真理値表は、ブール変数の有限集合の値のすべての可能な組み合わせを示す単なる表です。 セットにブール変数が含まれている場合、そのセットに対する操作の真理値表には、次の変数の値のさまざまな組み合わせに対応する行が含まれます。
この表は、行ごとに読むことで自然言語で解釈できます。 最初の行から始めると、「そして両方とも偽である」と言うことができます。 2行目は、代わりに「falseとtrue」と表示され、他のすべての行についても同様に続行できます。 真理値表の列に示されている2つの式は、すべての値が完全に一致していれば同等であると言えます。
3.2. 基本的なブール演算
3つの基本的な演算がブール代数で定義されており、これらは多くの論理演算子に対応しています。 これらの演算子は次のとおりです。
- 単項演算子、pではありません
- 二項演算子、pおよびq
- そして、別の二項演算子、pまたはq
これらの演算子は、以下に列挙されている真理値を保持しています。
この表は、前の表と同じ方法で読み取ることができます。 最初の行は、たとえば、「とが両方ともfalseの場合、true、false、およびfalse」と読み取ることができます。 同様の方法で、他のすべての行を読み取り、各操作の入力と出力へのマッピングを完了することができます。
これらの操作は、任意の数の変数に対する他のすべての操作を、 not 、 and 、およびまたは操作の順序付けられた連続に減らすことができるため、「基本」と呼ばれます。 これは、実践的な演習の解決に特化したセクションで説明するように、表現に基本法則を繰り返し適用することによって行われます。
3.3. 二次操作
基本的な操作のシーケンスに還元できるため、セカンダリと呼ばれる他のブール演算を定義することもできます。 これらの中で最も一般的なものは次のとおりです。
- 材料条件付き、 if p then q
- 対応または同等性、 p は、q と同等であり、q の場合に限り、pとも同等です。
- 排他的論理和演算子pxor q 、またはpまたはq
これらの演算子は、基本的な操作の観点から再定式化できるため、セカンダリと呼ばれます。
等価演算子は、二重条件付きと呼ばれることもあり、両方の変数に面した二重矢印で示されます。 この表記法は、定理証明などの特定のコンテキストで特に使用され、デモンストレーションでの仮説と理論の互換性を示しますが、それ以外の場合は、スコープに影響を与えません。
次の表は、基本操作と二次操作の間の対応の真理値表に関するデモンストレーションを示しています。
二次演算子を使用した数式と、基本演算子のみを使用して書き直された数式との同等性を簡単にテストできます。 これは、上記の表のそれぞれの列を比較し、とによって想定される値に関係なく、それらがどのように同等であるかに注目することによって行われます。
4. ブール代数の基本法則
4.1. アイデンティティ、消滅、べき等、および二重否定
ブール代数の法則は、変数、定数、およびブール演算子で構成される2つの一連のブール項として表現でき、それらの間で有効なIDが得られます。 この意味で、たとえば、最初の項が式で、2番目の項がである場合、その変数の任意の値に対して有効である場合、アイデンティティは法則です。
最初のクラスの法則は、必要に応じて定数とともに、1つの単一の変数を入力として受け取る法則で構成されます。 これらの法則は、二項演算子に関するアイデンティティ、消滅、およびべき等です。
これらの法則の最初の2つは、2つの演算子とのIDで構成されています。 ブール代数の2つの定数、1と0は、それぞれ、および：の単位元です。
2番目の法則は、いわゆる消滅剤に関するものです。 消滅子は、変数とともに2項演算子への入力として使用される場合、その変数が演算の出力に与える寄与を無効にする定数です。 定数0と1は、それぞれとの消滅子です。
1つの変数のみに関係する3番目の法則のペアは、べき等と呼ばれるものです。 すべての変数は、演算子と。に関してそれ自体とべき等であると見なされます。 これは、その変数が2回使用され、2項演算子に両方の入力を提供する場合、演算子の出力はその変数の値に対応するためです。
個々の変数に関する最後の法則は、いわゆる二重否定の法則です。 この法則は、単一の変数への否定演算子の二重適用がその変数に対応することを示しています：
4.2. 可換性と吸収
2番目のクラスの法則は、2つの異なる変数の使用とそれらの関係に関するものです。 これらの最初のグループは、との可換法則です。 この法則は、基本演算子の出力は、2つの変数が入力される順序とは無関係であると述べています。
2つの変数を含む2番目の法則のペアは、反対の、および反対のいわゆる吸収特性に関するものです。 このプロパティは、 2つの異なる変数間で二項演算が実行され、この演算の出力が使用されなかった二項演算子に入力された場合、最初に実行された二項演算は全体に影響を与えないことを示します。式の結果。
正式な表記法では、法律は次のように述べています。
これは、これらの法則を表形式で表したものです。
4.3. 結合性と分配性
3番目のクラスは、3つの変数に作用する法則で構成されます。 これらの法則は、および演算子の結合法則と分配法則です。
との結合法則は、これらの演算子の1つだけを含む一連の演算は任意の順序で計算でき、同じ結果になると述べています。
そして、これはこれらの法律の表形式の表現です。 3番目の要素を挿入すると、行数がからに増加することに注意してください。
法則の最後のペアは、に関する、およびに関するの分配法則に関するものです。 これらの法則は、二項演算が他の二項演算の出力を入力として持っている場合、前者は後者の各入力に対して計算でき、全体的な結果に違いはありません。 正式な表記法では、分配法則は次のように対応します。
そして、これは分配法則の表形式の表現です。
4.4. ド・モルガンの法則
最後の一連の法則は、いわゆる推論の規則に関するものです。 正式なシステムでの推論の規則により、論理式に対して推論推論を実行できます。 ブール代数では、推論の規則はド・モルガンの法則の名前を取ります。
これらの法則は、基本的な二項演算子ごとに、その演算子の否定が他の演算子への入力の否定の出力に対応することを示しています。 正式な言葉で言えば、彼らは次のように述べています。
次のセクションの演習で、それらを適用する方法を見ていきます。
5. ブール代数の法則の使用
5.1. これらの法律をいつ使用するか
ブール代数の法則により、非常に複雑な式をより扱いやすい式に単純化することができます。 これは、情報検索などのコンテキストで特に重要です。検索クエリの最適化により、ターゲットドキュメントの取得にかかる時間が大幅に短縮される可能性があります。 この単純化は、それ以外の場合は複雑すぎるブール式に関するド・モルガンの法則など、ブール代数の法則を適用することによって行われます。
プログラミングにおけるこれらの法則のもう1つの典型的なアプリケーションは、ネストされたifステートメントの単純化に関するものです。これは、ネストされたステートメントをより短い形式に単純化する特殊なルールエンジンを使用して実行できます。 ブール法則の最後の使用例の1つは、論理回路の単純化に関するものです。これは、最近、量子回路の単純化の必要性によって義務付けられています。
これらすべての場合において、私たちが適用する規則は、私たちが上で研究した法則に完全に対応しています。 この意味で、ブール代数は上記で定義された法則の下で完全であると言えます。
5.2. ブール法則を使用した演習：分配法則
これで、ブール法則を使用して、2つの複雑なブール式をより管理しやすい式に単純化する方法を確認できます。 このセクションと次のセクションは、ブール法の適用に関するガイド付きの演習として読むことができます。
この式から始めることができます：
この式には、2つの変数、、、および合計4つの明示的な演算子、1つの単項演算子、および両方のタイプのバイナリが含まれています。 私たちが試すことができる最初のアプローチは、分配法則の適用にあります。 実際、フォームの式は。と同等であることがわかっています。
overの分配法則により、最初に、括弧の間の項の順序を逆にすることで式を書き直すことができます。これは、可換法則により可能です。
次に、分配法則を使用して、を抽出できます。
なぜなら、式を次のように書き直すこともできます。
最後に、0はの単位元であるため、次のように単純に同一性の法則を適用することで書き直すことができます。
この引数は、式と、の同等性を示しており、最初の式から2番目の式を単純化することができます。
5.3. ブール法則を使用した演習：De Morgan
これで、ド・モルガンの法則の適用におけるガイド付きの演習を見ることができます。 この式を考えてみましょう：
この用語が、上記で定義したド・モルガンの第2法則にどのように対応しているかに注目してください。 次に、用語を次のように置き換えることができます。
数式全体がド・モルガンの最初の法則に似ています。つまり、これを同等のものに置き換えることができます。
括弧内の式へのDeMorganの最後の適用は、次のようになります。
当然のことながら、元の表現よりもはるかに扱いやすく、同時にそれと同等です。
最後に、使用したメソッドをアルゴリズムで複製する方法に注目してください。 このような2つのアルゴリズム手法、K-mapとQuine-McCluskeyアルゴリズムは、コンピューターサイエンスで一般的に使用されています。 これらはブール代数のルールの適用に基づいており、ブール関数の自動簡略化を実行して、複雑な式から単純な数式を抽出できるようにします。
6. 結論
この記事では、ブール代数の基本法則を研究し、ブール式の簡略化にそれらを適用する方法を示しました。
最初に、真理値表の観点からブール演算子について説明しました。 また、二次演算子が常に基本演算子の観点からどのように表現できるかを観察しました。
次に、それらの正式な表記法とそれに関連する真理値表の基本法則を研究しました。 そうすることで、これらの法則がそれらの変数のすべての値に対して有効であることを証明する方法を学びました。
最後に、いくつかの複雑なブール式を単純化するためにブール代数の基本法則を適用する方法を研究しました。 特に、トレーニング演習の解決に分配法則とド・モルガンの法則を適用する方法を見ました。
