2019年8月29日・30日
タイトル：NAND回路の設計とラグランジュの補間公式
サブタイトル：〜数学的思考とその応用〜
電子回路は、ゲートといわれるものを組み合わせて作ります。ゲートのひとつが NAND と呼ばれるもので、２つの入力と、１つの出力からなり、２つの入力が両方とも ON（通常1であらわします） のときのみ、OFF（通常0であらわします）、それ以外は、ON（1）を出力します。この NAND ゲートだけをいくつか使い線でつないで、足し算を計算する回路を作ることを考えたいと思います。
LOGIC LAB: http://www.neuroproductions.be/logic-lab/ （ブラウザーによっては、設定で Flash Player を使えるようにする必要があります）
平面上に二点が与えられているとその二点を結ぶ直線が一本あります。三点が与えられていると、その三点を通る、二次関数は、いつでもありますか。それは、ひとつだけですか。点の数を、四点、五点と増やしていくとどうなるのでしょうか。考えてみましょう。
この２つの全くことなると思われる問題の背後にある、数学の考え方のいくつかを、一緒に学ぶことができればと考えています。ツールが必要な場合には、そのときに説明します。核となる部分は、数学ですから、コンピュータ・ツールは使わなくても学習できますが、使うことで視覚化でき、理解もしやすくなりますし、発想の幅も広がります。ただ、なれるのには、多少の時間がかかりますので、少し、触っておくことはたいせつです。二日間で、考えられることは時間の関係で限られますが、ツールにもなれておくことで、自分で問題を作って、考えることもでき、発展性もあります。得意な人もそうでない人も、少し、世界を広げるといった気持ちで、この機会に、使ってみてはいかがでしょうか。
大きく分けて三種類のツールを紹介します。１つ目は、論理回路に関係するもの、２つ目は、グラフを描くためのもの、３つ目は、文書を書くためのものです。３つ目は、みなさんは、基本的に使いませんが、わたしがどのようにして、数式などを書いているかを知ることは、有益だと思うのと、数学やデータ・サイエンスを利用する分野で文章を書く時には、基本的なツールですので、簡単に紹介しておきます。
すべてフリーのソフトで、かつインターネット上で、オンラインで使えるものです。アカウントを作ったほうが便利なものもありますが、１つ目と２つ目に関しては、それも必要ありません。
理解を助けるツールです。たくさんありますが、二種類、紹介します。
英語のサイトですが、オンラインで使えますので、コンピュータにインストールする必要もなく、かつ直感的に使えます。入力（input）は、ON または OFF （1 または 0）と考えても構いません。論理ゲート（logic gate, logic port）を通ると、入力によって変化します。出力（output）で、実際に ON なのか、OFF なのかを確認できます。基本的にこれら３つのものを線でつないで作ります。
Logic Lab と Logic.ly で多少ことなりますが、殆ど同じ機能を持っています。（Logic Lab は、Adobe の Flash Player を使っていますので、特に、iOS すなわち、Apple 系の Tablet や、Cell Phone などでは、うまく動作しないかもしれません、そのときは、Logic.ly を使ってみてください。ただし、無償版では保存はできません。）Logic Lab は、古くからある Web Application で、わたしは、長く使っています。自分で設計した回路を保存することもできます。Logic.ly のほうが新しく、発展性もあるようですが、Online 版では保存はできません。わたしは、（8月に入ってから）30日間の無償トライアル版を使っています。Windows 版と、MacOS 版があり、30日間は、すべての機能が使えるようで、保存もできます。
数学ツアーでは、NAND ゲートだけを使って、加算器を作ることを目標としていますが、他のゲート（Logic Lab では Port と呼ばれています）もぜひ使ってみてください。
Flip-Flops も使えるようになっています。今回は、時間の関係で触れることはできないと思いますが、基本的なものですので、Flip-Flop とはどのようなもので、何に使われるのか、調べてみるのもよいでしょう。
論理ゲートや、Flip-Flop や、実際のゲートが電子的にどのような構造になっているのかなどの情報は、インターネットで調べることができます。二箇所だけ上げておきます。
関数のグラフを描画するツールです。二つ上げておきます。
Desmos は、関数のグラフの描画に特化したもので、GoeGebra は幾何にも使えるようになっています。今回は、Desmos をほんの少し使う予定ですが、殆どのことは、どちらでも可能です。機能も充実しており、学習にも、教育にも有効だと思います。
数学の文章は、数式を整えて見やすく書く必要があること、文書全体の論理構造がきっちりしていることがたいせつですが、数学者の D. Knuth が開発し、無償公開した、\(\TeX\)（テック） という組版システムが、数学関連の論文や書籍の殆どで使われています。\(\TeX\) は、本体だけでなく、フォントを作成し管理するシステムや、\(\TeX\) ブログラム自体を改善し使い易くする、マクロと呼ばれるものが最初の設計段階から整備されていたり、説明をも加えられる、web という形式で書かれたこともあり、Reproducible Research（研究の再現性）や、Literate Programming（プログラムの文書化） という、研究や、ソフトウェア開発にも欠かせない分野に大きな影響を与えました。
\(\TeX\) を使いやすくするために、やはり、数学者の L. Lamport によるマクロを付け加えた、\(\LaTeX\)（ラテック） の名前で呼ばれることもあります。
この文章は、web の考え方を発展させ、データ・サイエンスで主要なソフトとして使われている、R などとの連携を考えて開発された、Rmarkdown という形式で書かれています。この形式で書くと、ホームページなどを記述する、HTML（hypertext markup language）形式のほか、Microsoft Word や、PDF にも簡単に出力できるようになっています。Rmarkdown は、中にプログラムを書き込み、その実行結果とともに、文書を作成できるようになっており、プログラムもいろいろな言語に対応しています。プログラムを文書に加え、その結果を出力するだけでなく、そのプログラムの解説も、同時に作成することができ、データを書き換えても、グラフなども同時に書き換えることができるので、データ・サイエンスにおける、再現性（Reproducibility）にはなくてはならないものになっています。今回は、データ分析も、プログラミングも行いませんが、いろいろな形式の文書として、書き出すことができる利点を考えて、Rmarkdown で書き始めています。Rmarkdown は、テキストで文書を作成しますが、RStudio と連携させると、特に、データ分析のときには、便利です。他に似たものとしては、Python というコンピュータ言語に付随して開発された、Jupyter と呼ばれる、Python Notebook が有名です。
Cocalc は、\(\LaTeX\) も Rmarkdown も Jupiter も 使えますし、数式の計算もできるもので、最初は、SageMath の一部として開発されたものです。Cocalc は、Collaborative Calculation からとったもので、共同作業に適した環境を提供しています。最後の SageCell は、電卓のようにして使える、SageMath（商用の Mathematica や Maple などの代わりになるものとして開発されました） です。
Rmarkdown の中でも、数式は、\(\TeX\) 形式で書いています。
The Logic Lab で説明してみます。ページの下に、Logic Ports と書いてあるものがあります。それは、この[リンク] のようになっています。すべてにスイッチがついていて、白になっていれば、OFF、赤になっていれば ON です。それを動かして、AND, NOR, NOT, NAND, XOR, OR, XNOR それぞれで、入力がどうなっているときに、電気が赤くつくかを調べてみてください。案内に書いたように、NAND は、両方が、OFF のときのみ ON になっていることが確かめられると思います。他のものは、それぞれどうなっていますか。
Logic.ly の場合には、ある回路を選択すると、Truth Table（真理表）を作ってくれる機能もあります。上で書いた、ON または 1 が TRUE で、OFF または 0 が FALSE に対応しています。入力の値によって、出力がどうなるかが読み取れるようになっています。
加算器を作りたいのですが、２進演算を考えます。簡単なものから始めます。
どのように考えていったらよいのでしょうか。ひとに説明できるように、考え方も整理できるとよいですね。
平面上の二点 \((a,b)\) と \((c,d)\) を通る直線は、いつでも一本ありますね。その方程式はどうなりますか。
三点 \((a,b)\) と \((c,d)\) と \((e,f)\) のときは、どうでしょうか。二次関数をつかうと、この三点を通るものがいつでも見つけられますか。 \[ y = \alpha x^2 + \beta x + \gamma \] として、\(\alpha, \beta, \gamma\) はいつでも見つかりますか。
二次関数が見つかる条件は何でしょうか。それは、ただ一つに決まるのでしょうか。
二点を通る直線は、1次関数に関係しており、三点を通る直線は、2次関数に関係しているとすると、点の数を、4点、5点、6点とどんどん増やしていくとどうなると思いますか。
すっきりした形で記述する方法はあるでしょうか。
\(y = \alpha x^3 + \beta x^2 + \gamma x + \delta\) は、\(\alpha \neq 0\) のとき、三次関数と呼びます。三点 \((a,b)\) と \((c,d)\) と \((e,f)\) を通る、三次関数をすべて求めることはできるでしょうか。
どのように結果を整理（定理として記述）したら良いでしょうか。
\(y = \alpha x^3 + \beta x^2 + \gamma x + \delta\) は、\(\alpha \neq 0\) の左辺は、右辺の \(x\) の値によって決まりますから、\(x\) の関数とよび、\(f(x) = \alpha x^3 + \beta x^2 + \gamma x + \delta\) と書きます。\(f(x)\) は三次関数です。\(c\) を実数としたとき、 \[ f(x) = \alpha x^3 + \beta x^2 + \gamma x + \delta = (\alpha' x^2 + \beta' x + \gamma')(x-c) +r \] と書けることが知られてます（数学II）。\(\alpha' = \alpha\) と書けることはわかりますね。上のように書けている時、\(f(x)\) を \(x-c\) で割って、商が \(\alpha' x^2 + \beta' x + \gamma'\) 余りが、\(r\) であるともいいます。
上の式で、\(r = f(c)\) となっていることに注意してください。特に、\(f(c)=0\) のときは、 \[ f(x) = (\alpha' x^2 + \beta' x + \gamma')(x-c) \] と書くことができます。
Desmos で遊んでみましょう。
最初に、1.3.1 にあることから確認していきたいと思います。
答えだけ書いておきます。
10進数の 0-15 を2進数で表すと
10進数を2進数で表す方法
2進数を10進数で表す方法
2進数の足し算 例：\(101_2 + 110_2\)
\[ \begin{array}{ccccc} & & 1 & 0 & 1 \\ + & & 1 & 1 & 0 \\ \hline & 1 & 0 & 1 & 1 \end{array} \]
2進数の掛け算 例：\(101_2 \times 110_2\)
\[ \begin{array}{cccccc} & & & 1 & 0 & 1 \\ \times & & & 1 & 1 & 0\\ \hline & & 1 & 0 & 1 & \\ & 1 & 0 & 1 & & \\ \hline & 1 & 1 & 1 & 1 & 0 \end{array} \]
2進数で1より小さい小数を表す方法
２進演算で、加算器を作ることを考えましょう。単純なものから考えます。すなわち、二進一桁を一ビット（bit）と呼びますが、１ビット＋１ビットの加算器です。\(A\)と\(B\)であらわしましょう。
\(0+0=0\), \(0+1=1\), \(1+0=1\), \(1+1 = 10_2\) です。最後だけ二桁になっています。添字の2は、2進であることを示したものです。繰り上がりを Carry と言います。ですから、みな二桁だと考えて、
\(0+0=00_2\), \(0+1=01_2\), \(1+0=01_2\), \(1+1 = 10_2\) と出力を二桁にしてみましょう。
一桁目（\(2^0\) の位）を \(A\oplus B\) 繰り上がりを \(C\) であらわしましょう。すると次のようになっていることがわかります。 \[ \begin{array}{|c|c||c|c|} \hline A & B & A\oplus B & C \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1\\ \hline \end{array} \]
入力が \(A\) と \(B\) の二つ。出力が、\(A\oplus B\) と \(C\) の二つということになります。出力は一つ一つ作っていくことにしましょう。
これを、いくつかのゲート（ポート）を組み合わせて作りたいので、それぞれの、ゲートが入力に対して、どのような出力をしているか見てみましょう。
\[ \begin{array}{|c|c||c|c||c|c|c|c|c|c|c|} \hline A & B & A\oplus B & C & A \mbox{ NAND } B & A \mbox{ AND } B & A \mbox{ OR } B & \mbox{ NOT } A & A \mbox{ XOR } B & A \mbox{ NOR } B\\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ \hline \end{array} \]
\[ \begin{array}{|c|c||cc|ccc|c|} \hline A & B & \mbox{NOT} & (A \mbox{ AND } B) & \mbox{NOT}(A) & \mbox{ OR } & \mbox{NOT}(B) & A \mbox{ NAND } B \\ \hline 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]
入力が何であっても、出力が同じであるとき、同値といい、\(\equiv\)の記号を使って、次のように書きます。
複雑になると、簡単な記号を使ったほうがわかりやすいこともありますので、一般的に使われる（論理）記号を紹介しておきます。
記号をつかうと、次のように書くことができます。
二桁以上の場合も一桁ずつ計算しますが、桁上り（Carry）の部分も計算しないといけませんから、入力が \(A, B, C\) で出力が \(X, Y\) のようになっています。\(Y\) を桁上り分としましょう。
\(A = B = C = 1\) であっても、桁上りをふくめて二桁で収まることを確認しておきましょう。するとどうなるでしょうか。
\[ \begin{array}{|c|c|c||c|c|c|} \hline A & B & C & X & Y & Z\\ \hline 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1\\ \hline \end{array} \]
最後に述べた問題の 1 と 2 について考えてみたいと思います。
具体的には、次の二つの項目について話します。
注：XOR については、述べていませんが、\(A \oplus B\) の値を、\(Z\) に書いておけば、そのように、NOT, AND, OR だけで書けるのですから、心配いらないことがわかります。
Hint: \(Z\) がどんな式であっても、\(\overline{\bar{Z}} = Z\), \(A \uparrow B \equiv \overline{A \land B} \equiv \overline{A} \lor \overline{B}\)
\[ \begin{array}{|c|c|c||c|c|c|c|c|c|c|} \hline X & Y & Z & X \land Y \land Z = E_8 & X \lor Y \lor Z & S & C & E_2 & E_3 & E_5 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\ \hline \end{array} \]
原理的には、全加算器の回路ができることを示しました。
かなり複雑ですから、全加算器をNAND で簡単に書く方法を考えてください。
できれば、３桁＋３桁の計算までできる加算器を作ってください。
設計した加算器と工夫したこと、考え方などを、説明してもらおうと思います。
NAND ではなく、他の一種類のゲートだけで、書くことはできないのでしょうか。考えてみてください。
\(A\Rightarrow B\) （\(A \mbox{ IM } B\) ともかく）ゲートを下の表で定義する。空欄を埋めよ。 \[ \begin{array}{|c|c||c|c|c|c|} \hline A & B & A\Rightarrow B & \bar{A} \lor B & \overline{A \land \bar{B}} & \bar{B} \Rightarrow \bar{A} \\ \hline 0 & 0 & 1 & & & \\ 0 & 1 & 1 & & & \\ 1 & 0 & 0 & & & \\ 1 & 1 & 1 & & & \\ \hline \end{array} \] このことから、次がわかる。 \[ A\Rightarrow B \equiv \bar{A} \lor B \equiv \overline{A \land \bar{B}} \equiv \bar{B} \Rightarrow \bar{A}. \] \(\bar{B} \Rightarrow \bar{A}\) は対偶（contrapositive）と呼ばれる。
次の二つの式で表される論理回路の出力が同じではない（同値でない）ことを示せ。\[ (A\land B) \lor C, \quad A\land (B\lor C) \] （回路を作って示しても、表を書いて示しても、他の方法でも構いません。）
\(A \Rightarrow (B\lor C) \equiv A\land (\bar{B}) \Rightarrow C\) すなわち、どちらの論理回路も \((A, B, C)\) のすべての値について同じ出力となること（同値であること）を、二つの方法で示せ。
論理記号 \(\uparrow\) NAND だけを用い（NAND 回路で）次を表わせ。NOT も使ってはいけません。
\((A\land \bar{B}) \Rightarrow C\) を以下の指示にしたがって変形せよ。
\((A, B, C)\) の入力が \((0,0,0), (0,1,0), (1,0,1)\) のときだけ \(1\) でそれ以外、\(0\) を出力する回路を作成せよ。
最初に 1.3.2 に書いてあることから確認していきたいと思います。
下のプログラムと結果は、何をあらわしているのでしょうか。
# R Program
library(polynom)
x<-c(0,2,3,4)
y<-c(7,11,28,63)
poly.calc(x,y)## 7 - 2*x + x^3次の二行を copy して、SageMathCell の窓に paste して、Evaluate くだみてさい。
R = PolynomialRing(QQ, 'x')
R.lagrange_polynomial([(0,7),(2,11),(3,28),(4,63)])\((0,7),(2,11),(3,28),(4,63)\) の部分を変更するとどうなるでしょうか。
まず、\(c_0, c_1, \ldots, c_n\) を数とし、\(x\) を変数としたとき、次の式を考える。
\[
y = c_nx^n + c_{n-1}x^{n-1} + \cdots + c_1x+c_0
\] 右辺の\(x\)にある数を代入すると、\(y\) の値が決まるので、\(x\) の値によって、\(y\) の値が一つ定まることを \(y\) は \(x\) の関数（function）であるといい、\(y = f(x)\) などと書く。\(f\) は function からとっている。右辺は、\(x\) の整式ともよばれるが、ここでは、多項式（polynomial）と呼ぶことにする。高校では、一項しかないとき、単項式、複数項のとき、多項式と区別することもあるが、ここでは、すべて多項式と呼ぶことにする。ここで、\(c_n\neq 0\) であるとき、\(f(x)\) の次数（degree）は \(n\) であるといい、\(\deg f(x) = n\) と書く。右辺が \(0\) のとき、すなわち、ゼロ多項式の次数の次数もいくつか決め方があるが、ここでは、\(0\) でない多項式のときだけ、次数を考えることにする。定数たとえば、\(f(x) = c_0 = 2\) の次数は、\(0\) である。右辺が次数\(n\) の多項式の時、\(y = f(x)\) を次数\(n\)（または \(n\)次）の多項式関数という。
「1.4 数学を復習しておきたい人のために」の「直線と二次関数」の問題を眺めながら、考えてみてください。
まず、「1.4 数学を復習しておきたい人のために」の「直線と二次関数」の問題の答えを書いておきます。
\((0,-2)\) を通り、傾きが 3 の直線の方程式。
\((0,b)\) を通り、傾きが \(a\) の直線の方程式。
平面上の直線で、\(y = ax+b\) とは表せないもの。
\(ax + by + c = 0\) をみたす平面上の点 \((x,y)\) 全体が直線となる条件。
\((a,0)\) と \((0,b)\) を通る直線の方程式。
\((a,b)\) と \((c,d)\) を通る直線の方程式。
\((0,0), (1,-1), (3,3)\) を通る二次関数。
\((1,a), (2,b), (3,c)\) を通る二次関数（か、１次関数か…)。
先に進む前に、\(m=3\) すなわち、三点与えられた場合、\(n=2\) 二次関数で三点を通るものがあるかを考えておきましょう。
\((1,a), (2,b), (3,c)\) を考えましたが、今の記号を使い、
\[ (a_1, b_1), (a_2, b_2), (a_3, b_3) \] この三点を通る関数を作ってみましょう。 \[ y = b_1\cdot \frac{(x-a_2)(x-a_3)}{(a_1-a_2)(a_1-a_3)} + b_2\cdot\frac{(x-a_1)(x-a_3)}{(a_2-a_1)(a_2-a_3)} + b_3\cdot\frac{(x-a_1)(x-a_2)}{(a_3-a_1)(a_3-a_2)} \] ２次以下ではありますが、2次とは限りません。
\(r_1(x), r_2(x), \ldots, r_m(x)\) は、論理回路のときの、\(E_1, E_2, \ldots, E_8\) と似ていませんか。
次の授業では、他の表し方はないのかなど、考えてみようと思います。
\(f(x) = \alpha x^3 + \beta x^2 + \gamma x + \delta\) としたとき、実数 \(c\) について、\(f(c)=0\) ならば、 \[ f(x) = (\alpha' x^2 + \beta' x + \gamma')(x-c) \] と書くことができると書きました。これを一般化したものを考えましょう。
\(f(x) = c_nx^n + c_{n-1}x^{n-1} + \cdots + c_1x+c_0, \; c_n \neq 0\) で、次数に制限をつけず、
\[ f(a_1) = b_1, \; f(a_2) = b_2, \ldots, f(a_m) = b_m \] となるものを、すべて見つけてみましょう。
次の、次数（\(\deg\)）に関する性質成立することが背景としてあります。
多項式\(f(x), g(x)\) が\(0\) でないとすると以下が成立する。
注：\(\max\) はどちらか大きい（小さくない）方を表します。
次数が3以下の多項式 \(f(x)\) で \(f(0) = 4\), \(f(1) = 3\), \(f(2) = -6\), \(f(3) = 1\) を満たすものは何か。
次数が3以下の多項式 \(r(x)\)、\(f(x)\) で \(r(-1) = 1\), \(r(0) = r(1) = r(2) = 0\)、 および \(f(-1) = 2\), \(f(0) = -1\), \(f(1) = 3\), \(f(2) = -6\) となるものを求めよ。
多項式 \(f(x)\) は \(f(1) = 2, \;f(2) = 7, \;f(3) = 1, \;f(4) = 8\) を満たすものとする。
多項式 \(r(x)\) は \(r(-5) = r(0) = r(5) = r(10) = 0\) and \(r(15) = 1\) を満たすものとする。次数が4 のものと\(5\) のものを一つずつ求めよ。
多項式 \(f(x)\) は \(f(1) = -2, \;f(2) = 2, \;f(3) = 14, \;f(4) = 40\) を満たすものとする。
多項式、\(f(x)\) は \(f(1) = a_1\), \(f(2) = a_2\), \(f(3) = a_3\), \(f(4) = a_4\) を満たすものとする。多項式 \(g(x)\) で \(g(1) = a_1\), \(g(2) = a_2\), \(g(3) = a_3\), \(g(4) = a_4\), \(g(5) = a_5\) を満たすものを \(f(x)\) を利用して求めたい。
数学の問題を理解し、考え、英語を利用し、コンピュータ・ツールも利用し、自律的に、能動的に思考し、かつ他者から学ぶ謙虚さを持ち続けることは、どのような、分野に進んでも、世界を広げる大きな力となると思います。わたしも、みなさんと、一緒に学びを楽しみ続けたいと願っています。
\(A\Rightarrow B\) （\(A \mbox{ IM } B\) ともかく）ゲートを下の表で定義する。空欄を埋めよ。 \[ \begin{array}{|c|c||c|c|c|c|} \hline A & B & A\Rightarrow B & \bar{A} \lor B & \overline{A \land \bar{B}} & \bar{B} \Rightarrow \bar{A} \\ \hline 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \hline \end{array} \] このことから、次がわかる。 \[ A\Rightarrow B \equiv \bar{A} \lor B \equiv \overline{A \land \bar{B}} \equiv \bar{B} \Rightarrow \bar{A}. \] \(\bar{B} \Rightarrow \bar{A}\) は対偶（contrapositive）と呼ばれる。
次の二つの式で表される論理回路の出力が同じではない（同値でない）ことを示せ。\[ (A\land B) \lor C, \quad A\land (B\lor C) \] （回路を作って示しても、表を書いて示しても、他の方法でも構いません。） \[ \begin{array}{|c|c|c||c|c|} \hline A & B & C & (A\land B) \lor C & A\land (B\lor C) \\ \hline 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \hline \end{array} \] A, B が OFF（または 0）で、C が ON（または 1）のとき、\((A\land B) \lor C\) はON（または 1）になりますが、\(A\land (B\lor C)\) は、OFF（または 0）になり、等しく（同値では）ありません。Aが OFF で、B, C が ON の場合も食い違っていますが、同値ではないことを示すためには、一カ所食い違っていることをしめせば、十分であることに気をつけてください。
\(A \Rightarrow (B\lor C) \equiv A\land (\bar{B}) \Rightarrow C\) すなわち、どちらの論理回路も \((A, B, C)\) のすべての値について同じ出力となること（同値であること）を、三つの方法で示せ。
表を完成することで確認せよ。 \[ \begin{array}{|c|c|c||c|c|} \hline A & B & C & A \Rightarrow (B\lor C) & A\land (\bar{B}) \Rightarrow C \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \hline \end{array} \]
実際に、論理回路を作って確認せよ。
ヒント：\(\Rightarrow\) のゲートはありませんが、\(X\Rightarrow Y\) の形の回路は、問題1をもちいて、\(\bar{X}\lor Y\) などに置き換えれば良いことを注意しておきます。
練習問題 1 などの公式を使った変形により示せ。
\[A \Rightarrow (B\lor C) \equiv \bar{A} \lor (B\lor C) \equiv (\bar{A} \lor B) \lor C \equiv \overline{(\bar{A} \lor B)} \Rightarrow C \equiv A\land (\bar{B}) \Rightarrow C\] それぞれ、どの公式を使って変形したか確認してください。
論理記号 \(\uparrow\) NAND だけを用い（NAND 回路で）次を表わせ。NOT も使ってはいけません。
\((A\land \bar{B}) \Rightarrow C\) を以下の指示にしたがって変形せよ。
\((A, B, C)\) の入力が \((0,0,0), (0,1,0), (1,0,1)\) のときだけ \(1\) でそれ以外、\(0\) を出力する回路を作成せよ。
# R Program
library(polynom)
x<-c(0,1,2,3)
y<-c(4,3,-6,1)
poly.calc(x,y)## 4 + 11*x - 16*x^2 + 4*x^3# R Program for r(x)
library(polynom)
x<-c(-1,0,1,2)
y<-c(1,0,0,0)
poly.calc(x,y)## -0.3333333*x + 0.5*x^2 - 0.1666667*x^3# R Program for f(x)
library(polynom)
x<-c(-1,0,1,2)
y<-c(2,-1,3,-6)
poly.calc(x,y)## -1 + 3.833333*x + 3.5*x^2 - 3.333333*x^3# R Program for f(x)
library(polynom)
x<-c(1,2,3,4)
y<-c(2,7,1,8)
poly.calc(x,y)## -38 + 65.5*x - 29.5*x^2 + 4*x^3# R Program for r(x)
library(polynom)
x<-c(-5,0,5,10, 15)
y<-c(0,0,0,0,1)
poly.calc(x,y)## 0.01666667*x - 0.001666667*x^2 - 0.0006666667*x^3 + 6.666667e-05*x^4分数で書くとどうなりますか。
# R Program for g(x)
library(polynom)
x<-c(1,2,3,4)
y<-c(1,0,0,0)
poly.calc(x,y)## 4 - 4.333333*x + 1.5*x^2 - 0.1666667*x^3# R Program for f(x)
library(polynom)
x<-c(1,2,3,4)
y<-c(-2,2,14,40)
poly.calc(x,y)## -4 + 3*x - 2*x^2 + x^3条件から、\(f(1)=g(1)\), \(f(2)=g(2)\), \(f(3) = g(3)\), \(f(4)=g(4)\)。したがって、因数定理によて、\(g(x)-f(x) = h(x)(x-1)(x-2)(x-3)(x-4)\) と書ける。
\[ g(5) = f(5) + h(5)(5-1)(5-2)(5-3)(5-4) = f(5) + 24\cdot h(5) = a_5. \]
下のリンクから、Download し、Logicly から開いてください。
最初に、文書の作成ツールについても説明しましたので、文書とともに、そのソース・ファイルのリンクもつけておきます。参考になれば幸いです。Rmarkdown を compile するには、Rmarkdown 関連の R package と、ラグランジュの補間公式の計算のため、polynom package が必要です。\(\LaTeX\) の compile には、\(\TeX\) システムが必要です。説明にも書きましたが、Online で使うことも可能です。