ブログの説明

学校に通わないで学んだことを記しています。間違っているところが何かありましたらご指摘下さると幸いです。コメントに対する返信が遅れる可能性があります。その場合は申し訳ありません。

このブログではサイドバーに広告を表示しています。このブログ内の投稿記事を検索するには右上の拡大鏡のアイコンを、アーカイブやラベル付けから投稿記事を閲覧するには左上の三重線のアイコンをクリックして下さい。

数式の表示にはMathJaxを利用させていただいています。数式の表示のためにJavaScriptが有効である必要があります。そうでない場合、訳の分からないLatexのコードが表示されます。幾何学図形やチャートの表示にはHTML5 CanvasやGoogle Chartを使用しています。その表示のためにもJavaScriptが有効である必要があります。

１＋１＝１になるとき。ブール代数、数理論理学、論理回路

ブール演算が扱う数は0と1の2つだけ。しかも位取くらいどりなし。つまり複数の桁を持たない。

0を偽に、1を真に、真理値として対応付けると、ブール演算を論理演算と同等に扱うことができる。その場合、偽はfalseの頭文字のF、真はtrueの頭文字のTと記されることがある。

あるいはまた、0をOFFに、1をONに、そしてまた、0を電圧の低さに、1を電圧の高さに対応付けることでブール演算をスイッチング演算と同様に見なすことができる。

集合演算もまた、これらと極めて近しい関係にあることを直感できるはず。

ちなみに数理論理学にはFとTに限られない2値以上の値を扱う多値論理演算がある。ここではそれらについては触れない。

ここでは数学としてよりもコンピューター科学としての目的に重きを置くため、ブール演算と2値論理演算とを同じものとして扱う。それらの定理の証明にはほとんど触れない。各々の論理演算は、コンピューターに使われているデジタル集積回路を構成するデジタル電子回路の基本単位となっている論理ゲートと呼ばれるものにそれぞれ対応している。

以下では、ブール演算のパターンと各々の真理値表、それらに対応する論理ゲートを表わすシンボルを記した。\( a, b, c, \cdots \)はここではブール変数を表わすものとする。

論理和 (OR)

ブール代数の加法は、与えられた数の内にどれか1つでも1が含まれていればその出力が必ず1になり、それ以外は0になる函数かんすうと見なすことができる。これに対応する論理演算は論理和。それはOR演算とも呼ばれ、\( a + b \)や\( a \vee b \)などと記されている。

ORは英語でorのこと。日本語では「または」という訳語が当てられていることが多いが、日本語の「または」には後に記す排他はいた的論理和の意味合いがあるので要注意。

\[ \begin{align*} 0 + 0 &= 0 \\ 0 + 1 &= 1 \\ 1 + 0 &= 1 \\ 1 + 1 &= 1 \end{align*} \]

論理和の真理値表は次のとおり。

論理和の真理値表
\( a \) \( b \) \( a + b \)
0 0 0
0 1 1
1 0 1
1 1 1

回路図では論理和演算がORゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

論理和は電気回路では並列回路に相当する。

論理積 (AND)

ブール代数の乗法は、1または0が揃った時にのみその出力が1になる函数と見なすことができる。これに対応する論理演算は論理積。それはAND演算とも呼ばれ、\( a \centerdot b \)や\( a \wedge b \)などと記されている。

ANDは英語でandのこと。日本語では「かつ」という訳語が当てられていることが多い。

\[ \begin{align*} 0 \centerdot 0 &= 0 \\ 0 \centerdot 1 &= 0 \\ 1 \centerdot 0 &= 0 \\ 1 \centerdot 1 &= 1 \end{align*} \]

論理積の真理値表は次のとおり。

論理積の真理値表
\( a \) \( b \) \( a \centerdot b \)
0 0 0
0 1 0
1 0 0
1 1 1

ちなみに、変数を使った表記では、通常の代数と同様にAND演算子の省略が次のように行われることがある。

\[ a b \]

回路図では論理積はANDゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

論理積は電気回路で直列回路に相当する。

論理否定 (NOT)

論理否定は、0が与えられれば1を出力し、1が与えられれば0を出力する函数と見なすことができる。英語ではthe complementと呼ばれているが、これは集合論で補集合を意味している。0か1しかないブール代数では、1の補集合は0となり、0の補集合は1となる。論理演算では論理否定はNOT演算とも呼ばれ、\( a^{\prime} \)や\( \overline{a} \)や\( \lnot a \)や\( \sim a \)などと記されている。

日本語では「ではない」という訳語が当てられていることがある。

\[ \begin{align*} \overline{0} &= 1 \\ \overline{1}&= 0 \end{align*} \]

論理否定の真理値表は次のとおり。

論理否定の真理値表
\( a \) \( \overline{a} \)
0 1
1 0

回路図では論理否定はNOTゲートとして次のようなシンボルによって伝統的に記されてきた。ちなみにNOTゲートはインバーターとも呼ばれている。

あなたのブラウザはCanvas要素に対応していません。

以上のブール演算が最も基本となる論理演算として用いられている。この他にも次のような論理演算（論理ゲート）がある。

否定論理和 (NOR)

否定論理和は論理和を論理否定する論理演算。それは論理和の補集合を意味するので、\( \overline{a + b} \)や\( \lnot(a + b) \)と記されている。NOR演算子として\( a \downarrow b \)が用いられることがある。

\[ \begin{align*} 0 \downarrow 0 &= 1 \\ 0 \downarrow 1 &= 0 \\ 1 \downarrow 0 &= 0 \\ 1 \downarrow 1 &= 0 \end{align*} \]

否定論理和の真理値表は次のとおり。

否定論理和の真理値表
\( a \) \( b \) \( a \downarrow b \)
0 0 1
0 1 0
1 0 0
1 1 0

回路図では否定論理和がNORゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

否定論理積 (NAND)

否定論理積は論理積を論理否定する論理演算。それは論理積の補集合を意味しているので、\( \overline{a \centerdot b} \)や\( \lnot(a \centerdot b) \)と記されている。NAND演算子には\( a \uparrow b \)が用いられることがある。

\[ \begin{align*} 0 \uparrow 0 &= 1 \\ 0 \uparrow 1 &= 1 \\ 1 \uparrow 0 &= 1 \\ 1 \uparrow 1 &= 0 \end{align*} \]

否定論理積の真理値表は次のとおり。

否定論理積の真理値表
\( a \) \( b \) \( a \uparrow b \)
0 0 1
0 1 1
1 0 1
1 1 0

回路図では否定論理積がNANDゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

排他的論理和 (XOR/EOR)

排他はいた的論理和は、1同士、0同士のときに0（偽）になり、互いに不一致のときに1（真）になる論理演算。XOR演算子として\( a \oplus b \)や\( a \veebar b \)が用いられている。

\[ \begin{align*} 0 \oplus 0 &= 0 \\ 0 \oplus 1 &= 1 \\ 1 \oplus 0 &= 1 \\ 1 \oplus 1 &= 0 \end{align*} \]

排他的論理和の真理値表は次のとおり。

排他的論理和の真理値表
\( a \) \( b \) \( a \oplus b \)
0 0 0
0 1 1
1 0 1
1 1 0

回路図では排他的論理和はXORゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

排他的否定論理和 (XNOR/ENOR)

排他的否定論理和は排他的論理和を論理否定する論理演算。排他的論理和の補集合を意味するので、\( \overline{a \oplus b} \)と記されている。XNOR演算子として\( a \odot b \)が用いられることがある。

\[ \begin{align*} 0 \odot 0 &= 1 \\ 0 \odot 1 &= 0 \\ 1 \odot 0 &= 0 \\ 1 \odot 1 &= 1 \end{align*} \]

排他的否定論理和の真理値表は次のとおり。

排他的否定論理和の真理値表
\( a \) \( b \) \( a \odot b \)
0 0 1
0 1 0
1 0 0
1 1 1

回路図では排他的否定論理和はXNORゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

論理包含 (IMPLY)

論理包含は条件付き論理を意味している。IMPLY演算子は\( a \Rightarrow b \)と記されている。数理論理学の\( P \Rightarrow Q \)に等しい。日本語では「ならば」という訳語が当てられていることが多い。

Pが前件、Qが後件と呼ばれることがある。前件が0（偽）の場合は後件が0（偽）でも1（真）でもいずれも1（真）になる。

\[ \begin{align*} 0 \Rightarrow 0 &= 1 \\ 0 \Rightarrow 1 &= 1 \\ 1 \Rightarrow 0 &= 0 \\ 1 \Rightarrow 1 &= 1 \end{align*} \]

論理包含の真理値表は次のとおり。

論理包含の真理値表
\( a \) \( b \) \( a \Rightarrow b \)
0 0 1
0 1 1
1 0 0
1 1 1

回路図では論理包含はIMPLYゲートとして次のようなシンボルによって伝統的に記されてきた。

あなたのブラウザはCanvas要素に対応していません。

このシンボルを見ると分かるとおり、論理包含演算\( a \Rightarrow b \)は次のような論理和\( \overline{a} + b \)と等しい。論理和の片方の入力変数（独立変数、すなわち引数）を論理否定すると論理包含演算になる。

ブール代数の公理と定理

ブール代数には次のような公理またはその定理がある。

同一則 (Identity Law)
論理和では0が単位元。論理積では1が単位元。
\[ \begin{align*} 0 + a &= a \tag{1} \\ 1 \centerdot a &= a \tag{2} \end{align*} \]
単位元たんいげんとは、その演算対象になる数を変えることがない数。
可換則 (Commutative Law)
通常の代数と同様に和と積において交換法則が成り立つ。
\[ \begin{align*} a + b &= b + a \tag{1} \\ a \centerdot b &= b \centerdot a \tag{2} \end{align*} \]
分配則 (Distributive Law)
\[ \begin{align*} (a + b) \centerdot (a + c) &= a + (b \centerdot c) \tag{1} \\ (a \centerdot b) + (a \centerdot c) &= a \centerdot (b + c) \tag{2} \end{align*} \]

次のような定理を導き出すことができることがよく知られている。

対合則／二重否定則 (Involution Law / Double Negation Law)

二重の否定によって元に戻る。

\[ \begin{align*} \overline{\overline{a}} &= a \tag{1} \\ \overline{\overline{\overline{a}}} &= \overline{a} \tag{2} \end{align*} \]

ただし、三重の否定によってまた否定になる。一般に、偶数回の否定では肯定になり、奇数回の否定では否定になる。

有界則／破棄則 (Domination/Annulment Law)
論理和の吸収元は1、論理積の吸収元は0。
\[ \begin{align*} a + 1 &= 1 \tag{1} \\ a \centerdot 0 &= 0 \tag{2} \end{align*} \]
吸収元きゅうしゅうげんとは、演算によってすべての数をその数に変えてしまう吸血鬼やゾンビのような数のこと。
相補則 (Complement Law)
\[ \begin{align*} a \centerdot \overline{a} &= 0 \tag{1} \\ a + \overline{a} &= 1 \tag{2} \end{align*} \]
べき等則 (Idempotent Law)
同じ数同士の論理和も論理積もその同じ数になる。
\[ \begin{align*} a + a &= a \tag{1} \\ a \centerdot a &= a \tag{2} \end{align*} \]
\( a + a = a \)の証明は次のとおり。
\[ \begin{align*} a + a &= (a + a) \centerdot 1 \\ &= (a + a) \centerdot (a + \overline{a}) \\ &= a + a \centerdot \overline{a} \\ &= a + 0\\ &= a \end{align*} \]
吸収則 (Absorption Law)
\[ \begin{align*} a + (a \centerdot b) &= a \tag{1} \\ a \centerdot (a + b) &= a \tag{2} \\ \end{align*} \]
結合則 (Associative Law)
論理和同士または論理積同士ならば演算の順番が自由。
\[ \begin{align*} a + (b + c) &= (a + b) + c \tag{1} \\ a \centerdot(b \centerdot c) &= (a \centerdot b) \centerdot c \tag{2} \end{align*} \]
対偶則 (Contraposition Law)
\[ a \Rightarrow b = \overline{b} \Rightarrow \overline{a} \]
ド・モルガンの定理 (DeMorgan’s Law)
論理積全体の論理否定は論理否定同士の論理和と等しく、論理和全体の論理否定は論理否定同士の論理積と等しい。
\[ \begin{align*} \overline{a \centerdot b} &= \overline{a} + \overline{b} \tag{1} \\ \overline{a + b} &= \overline{a} \centerdot \overline{b} \tag{2} \end{align*} \]
あなたのブラウザはCanvas要素に対応していません。
ド・モルガンの定理は任意の数の変数においても通用する。
\[ \begin{align*} \overline{a \centerdot b} + \overline{c \centerdot d} &= \overline{a} + \overline{b} + \overline{c} + \overline{d} \tag{1} \end{align*} \] \[ \begin{align*} \overline{(a + b) \centerdot (c + d)} &= \overline{a} \centerdot \overline{b} + \overline{c} \centerdot \overline{d} \tag{2} \end{align*} \]
さらに二重否定の場合でも通用する。
\[ \begin{align*} \overline{(\overline{a} + b) \centerdot (c + \overline{d})} &= a \centerdot \overline{b} + \overline{c} \centerdot d \end{align*} \]

双対性 (Duality)

ブール代数の公理または定理で示された(1)式と(2)式との関係を見ると、互いに対になっていることが分かる。定数の0と定数の1とを互いに置き換え、論理和と論理積とを互いに置き換えると、(1)式が(2)式へ、(2)式が(1)式へと置き換わる。この性質は双対性そうついせいと呼ばれている。

機能的完全性 (Functional Completeness)

論理和(OR)と論理積(AND)と論理否定(NOT)は基本論理演算もしくは基本論理ゲートと呼ばれている。

否定論理和(NOR)と否定論理積(NAND)は実用論理演算もしくは実用論理ゲートと呼ばれている。

それだけを互いに接続して他の論理ゲートを作ることができる論理ゲートは汎用はんようゲート(Universal Gates)とも呼ばれている。

汎用ゲートの代表格として最も利用されているのがNANDゲートとNORゲート。NANDゲートはこれだけを組み合わせて他の論理ゲートや様々な論理関数を作り出すことができる。NORゲートも同様にこれだけを組み合わせて他の論理ゲートや様々な論理関数を作り出すことができる。

NANDゲートやNORゲートが持っているこのような万能な特質は機能的完全性と呼ばれている。

今回はここまで。さらに詳しくはまたの機会に。

関連記事

コメント

コメントを投稿

このブログの人気の投稿

LATEXで数式：指数と順列などで使う添数・添字

累乗（べき乗）で使われる指数（べき）など、右上に添えられる数や文字や記号はキャレット記号を用いて次のように表記することができる。添えられる数や文字や記号が複数に及んだり数式になる場合はそれらを{}で囲う必要がある。ちなみに、・は\cdotを、÷は\divを、≠は\neqをそれぞれ用い、分数は\frac{}{}で乗根は\sqrt[]{}で表すことができる。スペースを有効にするには\をスペースの前に付ける。 aのn乗 \( a^n \) a^n \( a^3 = a \cdot a \cdot a \) a^3 = a \cdot a \cdot a \( a^{m+n} \) a^{m+n} 指数法則 \( a^0 = 1 \ (a \neq 0) \) a^0 = 1 \ (a \neq 0) 指数法則 \( a^{\frac{1}{n}} = \sqrt[n]{a} \) a^{\frac{1}{n}} = \sqrt[n]{a} 指数法則 \( a^{\frac{m}{n}} = \sqrt[n]{a^m} \) a^{\frac{m}{n}} = \sqrt[n]{a^m} 指数法則 \( a^{-\frac{m}{n}} = \frac{1}{\sqrt[n]{a^m}} \) a^{-\frac{m}{n}} = \frac{1}{\sqrt[n]{a^m}} 指数法則 \( a^m a^n = a^{m+n} \) a^m a^n = a^{m+n} 指数法則 \( \frac{a^m}{a^n} = \frac{1}{a^{n-m}} \ (m < n) \) \frac{a^m}{a^n} = \frac{1}{a^{n-m}} \ (m < n) 指数法則 \( (a^m)^n = a^{mn} \) (a^m)^n = a^{mn} 指数法則 \( (ab)^n = a^n b^n \) (ab)^n = a^n b^n 指数法則 \( \left(\frac{a}{b}\right)^n = \frac{a^n}{b^n} \) \left(\frac{a}{b}\right)^n = \frac{a^n}{b^n} 指数法則 \( \frac{a^m}{a^n}
続きを読む

10の補数と9の補数と2の補数と1の補数

10進数と10の補数 10進法の四則演算に慣れている人なら算術的な直感で分かるのが10の補数。 算盤 そろばん を使っている人は10の補数と5の補数を出力する函数を会得しているかもしれない。 例えば、2に対して10の補数はいくつかと問われればそれは8だと分かるし、6に対して10の補数はいくつかと問われればそれは4だと分かるし、5に対して10の補数はいくつかと問われれば5だと直感的に分かる。 また、3に対して5の補数はいくつかと問われればそれは2だと分かるし、2に対して5の補数はいくつかと問われれば3だと分かる。 10の補数とは、ある自然数に対してそれにいくつの自然数を加えれば10になるのかという問いに答えたもの。自然数とは、ここでは0, 1, 2, 3, 4, 5, 6, 7, 8, 9のこと。 ある自然数xに対する10の補数yは次のように計算することによって答えることができる。 \[ y = 10 - x \] 10進法の位取り記数法では、桁上がり（位上がり）が起こる数が10であるので、ある数にあといくつ足すと桁上がりが起こるかを理解していることは、その四則演算においてとても重要な暗記事項になっている。 10進法の四則演算に慣れた人の頭の中には次のような函数または対応表があるのかもしれない。 \[ f(x) = 10 - x \] xは引数。「xに対する10の補数」を出力してくれる函数f(x)。 10の補数の対応表 10進数 10の補数 0 10 1 9 2 8 3 7 4 6 5 5 6 4 7 3 8 2 9 1 10 0 補数のこの対応表を見ると、数値を小さい順から並べた昇順と数値を大きい順から並べた降順との写像（マッピング）関係に見える。 10の補数と桁上がり 例えば、\( 6 + 7 = \)を計算するとき、人は6または7の補数を瞬時に思い浮かべ、加える数がそれを上回っている場合に桁上がりが起こると即座に認識するはず。つまり、6に対する10の補数である4を思い浮かべ、その4より大きい7から4を引いた数である3と10を足し合わせて答えを計算するかもしれない。 \[ \begin{align*} 6 + 7 &=
続きを読む

Visual Studio 2019にはC++のためのフォームデザイナーがない件

イメージ
Visual Studio 2019を利用してC++でWindowsフォームアプリを作成しようと「新しいプロジェクトの作成」で「Windowsデスクトップアプリケーション」を選んでみたものの、フォーム・デザイナーが見当たらないことに気が付いた。ユーザー・インターフェイスはソースコードを直接いじれということか。これは厳しい。 C++を諦めてC#でフォームをデザインしろというのが常識的な対処法になるのかもしれないが、それでもC++で作る必要があるという隙間需要を考慮し、今回はこの問題に対処する二通りの対処法をインターネット上で見つけることができたので紹介したいと思う。 Visual Studio Installerでは、「.NETデスクトップ開発」と「C++によるデスクトップ開発」にチェックを入れてインストールしておいたのだけれど、これだけではデフォルトで「ビルドツールC++/CLIサポート」がインストールされないようだ。これを追加インストールする必要がまずあった。その手順は次のとおり。 対処法１ コードを追加する方法 Visual Studio Installerをまず起動した。 「インストール済み」のVisual Studio **** 2019に対して「変更」を選んだ。 「ワークロード」タブで「.NETデスクトップ環境」と「C++によるデスクトップ環境」の両方にチェックが入っていることを確認した。 「個別のコンポーネント」タブを選び、「C++/CLI」として検索した。そうするとビルドツールのC++/CLIサポートの一覧が表示された。 この執筆時点では「v142ビルドツール(14.27)のC++/CLIサポート」がどうやら最新版のように見えたのでこれにチェックを入れた。 そうしておいてからそのダイアログ・ボックス右下の「変更」ボタンを押した。 これでダウンロードとインストールが自動的に行われるので、しばらくの間待つ。 インストールが完了したが、「警告あり」と表示されてしまった。「問題の表示」によればMicrosoft.VisualStudio.AspNetDiagnosticPack.Msiのインストールに失敗したらしい。ここではこの問題には対処せず、無視して次の手順に進んだ。 Visual Studio Installerを終了
続きを読む