論理関数とその応用第二部


論理関数とその応用
第二部















この教科書はBookletを利用して作成している。
本書の見方
ページをめくる
左(右)ページの左(右)端クリックまたはドラッグする
左(右)矢印キーを押す
１ページ分の移動
左右上端にある[Next]、[Previous]タブをクリックする
章の頭に移動
右上の【章の移動】タブをクリックし、現れた章を選ぶ
ページのジャンプ
右上のページ番号表示タブをクリックし、現れたページを選ぶ
画像の拡大およびリンク先への移動
画像やリンク先をクリックすれば、別ウィンドウ(タブ)で表示される

目　次

第二部
　３章　論理関数
論理関数の定義
排他的論理和に関する公式
標準形
標準形の求め方
論理式の簡単化
　４章　順序回路
順序回路とは
順序回路の能力
状態の符号化
　５章　論理関数族の理論
閉関数族
完全性

第一部
　０章　学習の指針
　１章　論理と集合
集合の記法
命題論理とその記法
１変数述語と集合
基本等式
基本不等式
双対原理
公式の証明
　２章　論理回路
AND、OR、NOT素子
論理式（回路）の設計
加算器
集積回路の原理


第３章　論理関数

【この章のポイント】

　第２章では、$\wedge,\ \vee,\ \neg$ から構成される論理式を $\mathbb{B}=\{0,1\}$ 上の関数と見做して、論理回路への応用を見てきた。
　この章では、より一般的に、論理関数と呼ばれる $\mathbb{B}=\{0,1\}$ 上の関数について、議論する。

【この章の目標】 学習後、以下のことが身についたかチェックしよう。

  1. 2進和演算$\oplus$に関する公式を理解する
  2. 積和標準形、和積標準形、ガロア標準形を求めることができる
  3. カルノー図を描くことができる
  4. 簡単な論理式について、項和式の範囲内での簡単化ができる
  5. 冗長入力を持つ場合の簡単化ができる

【この章の構成】

  1. 論理関数の定義
  2. ２進和に関する公式
  3. 標準形
  4. 論理式の簡単化

３.１節　関数の定義

　関数を定義するには、その定義域、値域、および定義（計算式あるいは計算方法）を示す必要があり、一般的には
　　　$関数名:変数リスト\in 定義域 \mapsto 定義 \in 値域$
という形をしている。例えば実数 $\mathbb{R}$ 上の２次関数 $f(x)=x^2$ であれば、$f:x \in \mathbb{R} \mapsto x^2 \in \mathbb{R}$ のように記述する。
　とくに定義域と値域を問題にしたい時は、例えば $f:\mathbb{R}\to\mathbb{R}$ のように、
　　　$関数名:定義域 \to 値域$
と書き、定義域と値域が明らかな時はそれらを省略して $f:x\mapsto x^2$ のように
　　　$関数名:変数リスト \mapsto 定義式$
あるいは $f(x):=x^2$ のように
　　　$関数名(変数リスト):=定義式$
と書く。
　変数名は定義式の記述に使う便宜的なものであり、例えば $f(x):=x^2$ と $f(y):=y^2$、$(x,y)\mapsto x$ と $(y,x)\mapsto y$ は同じ関数を定義する。ただし、変数リスト中の位置（現れる順番）は意味を持ち、$(x,y)\mapsto x$ と $(x,y)\mapsto y$ は異なる関数である。また、関数は、それが形式的に何変数関数であるかで、区別される。例えば、2変数関数 $f:(x,y)\mapsto x$ と1変数(恒等)関数 $I:x\mapsto x$ とは異なる。

問．各変数の動く範囲は実数とする。次の関数の内、互いに等しいものをあげよ。
$f_1:x\mapsto x,\ f_2:x\mapsto x^2/x,\ f_3:y\mapsto y,\ f_4:(x,y)\mapsto x,\ f_5:(x,y)\mapsto y,\ f_6:(y,x)\mapsto y$
　$\mathbb{B}=\{0,1\}$上の（多変数）関数を論理関数という。$n$変数論理関数 $f:\mathbb{B}^n\to \mathbb{B}$ は全部で$|\mathbb{B}|^{|\mathbb{B}^n|}=2^{2^n}$ 通りある。（注．$2^{2^n}=2^{(2^n)}\ne (2^2)^n=2^{2n}$）
　$n$変数論理関数の全体を $\mathcal{B}_n:=\{f\;|\;f:\mathbb{B}^n\to\mathbb{B}\}$、論理関数の全体を $\displaystyle \mathcal{B}:=\bigcup_{n=0}^\infty \mathcal{B}_n$ と書く。以下は1変数論理関数(4通り)と2変数論理関数(16通り)の一覧表で、よく使うものについては関数名(演算記号)を表記する。

$\mathcal{B}_1$$0$$1$$2$$3$
$x$$\bf 0$$I$$\,^-$$\bf 1$
$0$$0$$0$$1$$1$
$1$$0$$1$$0$$1$
$\mathcal{B}_2$$0$$1$$2$$3$$4$$5$$6$$7$ $8$$9$$10$$11$$12$$13$$14$$15$
$(x,y)$ $\bf 0$$\cdot$$x\bar{y}$$x$$\bar{x}y$$y$$\oplus$$+$ $\downarrow$$\leftrightarrow$$\bar{y}$$\leftarrow$$\bar{x}$$\to$$|$$\bf 1$
$(0,0)$ $0$$0$$0$$0$$0$$0$$0$$0$ $1$$1$$1$$1$$1$$1$$1$$1$
$(0,1)$ $0$$0$$0$$0$$1$$1$$1$$1$ $0$$0$$0$$0$$1$$1$$1$$1$
$(1,0)$ $0$$0$$1$$1$$0$$0$$1$$1$ $0$$0$$1$$1$$0$$0$$1$$1$
$(1,1)$ $0$$1$$0$$1$$0$$1$$0$$1$ $0$$1$$0$$1$$0$$1$$0$$1$

【注】
  1. $\,^-$　反転。論理演算の$\neg$に対応。数としては、$\bar{x}=1-x$である
  2. $2$ 変数関数では、関数名と演算記号を混用する。即ち、上欄が演算記号の場合、例えば、$+:(x,y)\mapsto x+y$ である
  3. 上欄が式の場合、例えば $x\bar{y}$ は(無名の)関数 $(x,y)\mapsto x\bar{y}$ を意味する
  4. $\cdot$　積。論理演算の$\wedge$に対応。数としての積にも一致しており、$x\cdot y$を単に$xy$と略記する
  5. $+$　和。論理演算の$\vee$に対応。数としての和とは、$1+1=1$である点が異なる
  6. $\leftrightarrow$　同値。$x\leftrightarrow y=1 \Leftrightarrow x=y$
  7. $\oplus$　２進和。数としての和を2で割った余りで、$+$ とは $1+1=0$ である点が異なる
  8. $\downarrow:(x,y)\mapsto \bar{x+y}$　NOR
  9. $|:(x,y)\mapsto \bar{xy}$　NAND
  10. $\to:(x,y)\mapsto \bar{x}+y$
  11. $\leftarrow:(x,y)\mapsto x+\bar{y}$
  12. 定数関数 ${\bf 0}:(x_1,\cdots,x_n)\mapsto 0$ は（${\bf 1}$ も）本来は $n$ の値で区別すべきである

$\mathbb{B}=\{0,1\}$ 上の変数 $x,y,z,\dots$ から上記の関数(演算記号)を用いて表される式も論理式といい、演算記号として特に 和($$)、積($\cdot$)、反転($\,^-$) のみを許したものを論理多項式という。これ以降、特に断らない限り、論理式は（第１章の定義ではなく）ここで定義したものを意味する。

３.２節　２進和$\oplus$に関する公式

２進和$\oplus$は、和（$+$）と $1\oplus 1=0$ となるところ(だけ)が異なる。この後の議論でも、重要な働きをするので、基本的な公式をまとめておこう。

名称公式
結合則$(x\oplus y)\oplus z=x\oplus (y\oplus z)$
交換則$x\oplus y=y\oplus x$
分配則$x(y\oplus z)=xy\oplus xz$
単位元$x\oplus 0=x$
$x\oplus 1=\bar{x}$
$x\oplus x=0$
$x+y=x\oplus y\oplus xy$

問．２進和 $\oplus$ に関する以下の式を示せ
  1. $x\oplus y=\bar{x}y+x\bar{y}$
  2. 分配則：$x(y\oplus z)=xy\oplus xz$
  3. $x\oplus y=\bar{x\leftrightarrow y}$
  4. $\bar{x}\,\bar{y}=1\oplus x\oplus y\oplus xy$
  5. $x\oplus y=x+y \Leftrightarrow xy=0$

３．３節　標準形

　論理式の間には様々な関係が成立つ(１．４節、１．５節)から、論理関数を表す論理式も一通りには定まらない。この節では、関数の表現形式を制限して、一通りに表す方法（標準形）を学ぶ。
　論理関数 $f:\mathbb{B}^n\to\mathbb{B}$ の値を $b\in\mathbb{B}$ にするような変数値(の組)の集合を $f^{-1}(b):=\{(a_1,a_2,\cdots,a_n)\;|\;f(a_1,a_2,\cdots,a_n)=b\}\subseteq\mathbb{B}^n$ で定義する。$f,g:\mathbb{B}^n\to\mathbb{B}$ に対し
  1. $f\cdot g:(x_1,x_2,\cdots,x_n)\mapsto f(x_1,x_2,\cdots,x_n)\cdot g(x_1,x_2,\cdots,x_n)$
  2. $f+g:(x_1,x_2,\cdots,x_n)\mapsto f(x_1,x_2,\cdots,x_n)+g(x_1,x_2,\cdots,x_n)$
  3. $\bar{f}:(x_1,x_2,\cdots,x_n)\mapsto \overline{f(x_1,x_2,\cdots,x_n)}$
と定義すれば、明らかに以下が成立つ。
  1. $f=g \iff f^{-1}(1)=g^{-1}(1) \iff f^{-1}(0)=g^{-1}(0)$
  2. $(f\cdot g)^{-1}(1)=f^{-1}(1)\cap g^{-1}(1)　　(f\cdot g)^{-1}(0)=f^{-1}(0)\cup g^{-1}(0)$
  3. $(f+g)^{-1}(1)=f^{-1}(1)\cup g^{-1}(1)　　(f+g)^{-1}(0)=f^{-1}(0)\cap g^{-1}(0)$
  4. $(\bar{f})^{-1}(1)=f^{-1}(0)=\mathbb{B}^n-f^{-1}(1)　　(\bar{f})^{-1}(0)=f^{-1}(1)=\mathbb{B}^n-f^{-1}(0)$
$f^{-1}(1)$ を $f$ の充足集合と言う。
　また、$f:\mathbb{B}^n\to\mathbb{B}$ が $x_1,x_2,\dots,x_n$ 上の論理式 $\alpha$ で $f(x_1,x_2,\dots,x_n)=\alpha$ と書けるとき、$f^{-1}(b)$ を $\alpha^{-1}(b)$ と書くこととする。
定理． $f(x_1,x_2,\cdots,x_n)= \begin{cases} \displaystyle \sum_{f(a_1,a_2,\cdots,a_n)=1}\left(\prod_{k=1}^n(x_k\leftrightarrow a_k)\right) & (1)\\ \displaystyle \prod_{f(a_1,a_2,\cdots,a_n)=0}\left(\sum_{k=1}^n(x_k\oplus a_k)\right) & (2) \end{cases}$
証明．$\displaystyle \left(\prod_{k=1}^n(x_k\leftrightarrow a_k)\right)^{-1}(1) =\left((x_1\leftrightarrow a_1)\cdot(x_2\leftrightarrow a_2)\cdots(x_n\leftrightarrow a_n)\right)^{-1}(1)$
$=\{(x_1,x_2,\cdots,x_n)\;|\;x_1\leftrightarrow a_1=1,x_2\leftrightarrow a_2=1,\cdots,x_n\leftrightarrow a_n=1\}$
$=\{(x_1,x_2,\cdots,x_n)\;|\;x_1=a_1,x_2=a_2,\cdots,x_n=a_n\}=\{(a_1,a_2,\cdots,a_n)\}$ だから、 $\displaystyle \left(\sum_{f(a_1,a_2,\cdots,a_n)=1}\left(\prod_{k=1}^n(x_k\leftrightarrow a_k)\right)\right)^{-1}(1)=\bigcup_{f(a_1,a_2,\cdots,a_n)=1}\{(a_1,a_2,\cdots,a_n)\}=f^{-1}(1)$
同様に
$\displaystyle \left(\sum_{k=1}^n(x_k\oplus a_k)\right)^{-1}(0) =\{(x_1,x_2,\cdots,x_n)\;|\;x_1\oplus a_1=0,x_2\oplus a_2=0,\cdots,x_n\oplus a_n=0\}$
$=\{(x_1,x_2,\cdots,x_n)\;|\;x_1=a_1,x_2=a_2,\cdots,x_n=a_n\}=\{(a_1,a_2,\cdots,a_n)\}$ だから、 $\displaystyle \left(\prod_{f(a_1,a_2,\cdots,a_n)=0}\left(\sum_{k=1}^n(x_k\oplus a_k)\right)\right)^{-1}(0)=\bigcup_{f(a_1,a_2,\cdots,a_n)=0}\{(a_1,a_2,\cdots,a_n)\}=f^{-1}(0)$ □

問．定理の(2)式の別証
定理の(1)式とド・モルガンの定理を使って、以下の式を証明せよ
$\displaystyle \left(\bar{\prod_{f(a_1,a_2,\cdots,a_n)=0}\left(\sum_{k=1}^n(x_k\oplus a_k)\right)}\right)^{-1}(1)=\left(\bar{f(x_1,x_2,\cdots,x_n)}\right)^{-1}(1)$

　$x\leftrightarrow a=\begin{cases} x & a=1\\ \bar{x} & a=0 \end{cases}$であるから、$(1)$式の $x\leftrightarrow a$ を $a$ の $1,\ 0$ に応じてそれぞれ $x,\ \bar{x}$ で置き換えた論理式を、$f(x_1,x_2,\cdots,x_n)$ の積和標準形という。すなわち、積和標準形は、各変数 $x_i$ に対し、そのリテラル（$x_i$ または $\bar{x_i}$）の積をとった項のいくつかの和をとった形をしている。このような積和標準形が、関数に対して一意に定まることはあきらかだろう。またその求め方については、すでに第２章で2変数や3変数の簡単な場合について議論している。
　$x\oplus a=\begin{cases} \bar{x} & a=1\\ x & a=0 \end{cases}$であるから、$(2)$式の $x\oplus a$ を $a$ の $1,\ 0$ に応じてそれぞれ $\bar{x},\ x$ で置き換えた論理多項式を、$f(x_1,x_2,\cdots,x_n)$ の和積標準形という。すなわち、和積標準形は、各変数のリテラルの和をとった式のいくつかの積をとった形をしている。和積標準形は積和標準形の双対形であり、一意に定まることや、求め方は基本的に積和標準形と同様である。

　積和標準形や和積標準形からわかるように、任意の論理関数は、和、積、反転の３演算（関数）を使って構成できる。このように、関数の集合は、それを組み合わせて任意の論理関数が合成できるとき完全であるという。

定理．$\{\cdot,\ +,\ ^-\}$ は完全である。

系．$\{\cdot,\ ^-\},\ \{+,\ ^-\}$ は完全である。
証明．ド・モルガンの定理から、$x+y=\overline{\bar{x}\cdot\bar{y}},\ xy=\overline{\bar{x}+\bar{y}}$ であるから、$+$（$\cdot$）は $\{\cdot,\ ^-\}$（$\{+,\ ^-\}$）から合成できる。

ガロア（リード･マラー）標準形

　論理関数を２進和($\oplus$)と積と $1$ で表すことを考えてみよう。$\bar{x}=x\oplus 1$ と $x\cdot y=0 \Leftrightarrow x+y=x\oplus y$ とに注意すれば、積和標準形で、和($+$)を排他的論理和($\oplus$)に、$\bar{x}$ を $x\oplus 1$ に置き換えた論理式は、任意の論理関数を２進和($\oplus$)と積と $1$ 使って表している。

定理．$\{\cdot,\ \oplus,\ {\bf 1}\}$ は完全である。

　ここで、変数の積または $1$ の２進和をガロア標準形という。ガロア標準形は、上に述べた論理式を展開して整理すれば得られる。以下、一般式を求めるために、展開の際にどのような計算が行われるか見てみよう。
　例えば $(x\leftrightarrow 0)(y\leftrightarrow 0)(z\leftrightarrow 1)=\bar{x}\bar{y}z=(x\oplus 1)(y\oplus 1)z=xyz\oplus xz\oplus yz\oplus z$ の最後の式の各項の特性ベクトル（出現する変数の位置を$1$他を$0$としたベクトル）はそれぞれ $(1,1,1),\ (1,0,1),\ (0,1,1),\ (0,0,1)$ となり、最初の式を定めるベクトル $(0,0,1)$ の $0$ を $1$ に置き換えたものになっている。
　そこで、$(a_1,\cdots,a_n),\ (b_1,\cdots,b_n)\in\mathbb{B}^n$ に対し、$(a_1,\cdots,a_n)\leqq(b_1,\cdots,b_n)$ を $a_1\leqq b_1,\ \cdots,\ a_n\leqq b_n$ で定義する。$n=3$ の場合の関係 $\leqq$ を表したハッセ図は右上図のようになる。

問．以下を示せ
$(a_1,\cdots,a_n)\leqq(b_1,\cdots,b_n) \iff \{i\;|\;a_i=1\}\subseteq\{i\;|\;b_i=1\}$

　記法$\leqq$を使えば、例にあげた式は $\displaystyle (x\leftrightarrow 0)(y\leftrightarrow 0)(z\leftrightarrow 1) =xyz\oplus xz\oplus yz\oplus z =\bigoplus_{(a_1,a_2,a_3)\geqq (0,0,1)}\left(\prod_{a_i=1}x_i\right)$ と書け、一般に次の補題が成立つ。
補題．$\displaystyle \prod_{k=1}^n(x_k\leftrightarrow b_k) =\bigoplus_{(a_1,\cdots,a_n)\geqq (b_1,\cdots,b_n)}\left(\prod_{a_i=1}x_i\right)$
証明．$n$ に関する帰納法で証明する。
$n=1$ のとき、$x\leftrightarrow b=\begin{cases} x & b=1 のとき\\ x\oplus 1 & b=0 のとき \end{cases}$ 　　　　より成り立つ。
$n-1$ で成り立つと仮定する。$b_n=1$ のとき、$a_n\geqq b_n$ をみたす $a_n$ は $1$ のみなので
$\displaystyle \prod_{k=1}^n(x_k\leftrightarrow b_k) =\left(\prod_{k=1}^{n-1}(x_k\leftrightarrow b_k)\right)x_n =\bigoplus_{(a_1,\cdots,a_{n-1})\geqq (b_1,\cdots,b_{n-1})} \left(x_n\prod_{a_i=1}x_i\right) =\bigoplus_{(a_1,\cdots,a_n)\geqq (b_1,\cdots,b_n)}\left(\prod_{a_i=1}x_i\right)$
$b_n=0$ のとき、$a_n\geqq b_n$ をみたす $a_n$ は $1,\ 0$ なので
$\displaystyle \prod_{k=1}^n(x_k\leftrightarrow b_k) =\left(\prod_{k=1}^{n-1}(x_k\leftrightarrow b_k)\right)(x_n\oplus 1) =\bigoplus_{(a_1,\cdots,a_{n-1})\geqq (b_1,\cdots,b_{n-1})} \left((x_n\oplus 1)\prod_{a_i=1}x_i\right)$
$\displaystyle =\bigoplus_{(a_1,\cdots,a_{n-1})\geqq (b_1,\cdots,b_{n-1})} \left(x_n\prod_{a_i=1}x_i\oplus \prod_{a_i=1}x_i\right) =\bigoplus_{(a_1,\cdots,a_n)\geqq (b_1,\cdots,b_n)}\left(\prod_{a_i=1}x_i\right)$ □

　展開後の式を整理する際には、$x\oplus x=0$ が用いられるので、次の記法を用意しておこう。
$n\in\mathbb{N}$ に対し、$n$ を $2$ で割った余り（$\in \mathbb{B}$）を $n_\text{mod2}$ と書く。したがって、集合 $A$ に対し、$|A|_\text{mod2}=\begin{cases} 0 & A の要素数が偶数のとき\\ 1 & A の要素数が奇数のとき \end{cases}$ 　　　　　である。
定理． $\displaystyle f(x_1,\cdots,x_n) =\bigoplus_{(a_1,\cdots,a_n)\in\mathbb{B}^n}\left(\left|\{(b_1,\cdots,b_n)\leqq(a_1,\cdots,a_n) \;|\;f(b_1,\cdots,b_n)=1\}\right|_\text{mod2}\prod_{a_i=1}x_i\right)$
証明．$\displaystyle (a_1,\cdots,a_n)\ne(b_1,\cdots,b_n) \Longrightarrow \prod_{k=1}^n(x_k\leftrightarrow a_k)\prod_{k=1}^n(x_k\leftrightarrow b_k)=0$
$\displaystyle \Longrightarrow \prod_{k=1}^n(x_k\leftrightarrow a_k)+\prod_{k=1}^n(x_k\leftrightarrow b_k) =\prod_{k=1}^n(x_k\leftrightarrow a_k)\oplus\prod_{k=1}^n(x_k\leftrightarrow b_k)$
であることに注意すれば、積和標準形の和$+$は、２進和$\oplus$に置き換えてよい。
　　$\displaystyle f(x_1,\cdots,x_n)=\sum_{f(b_1,\cdots,b_n)=1} \left(\prod_{k=1}^n(x_k\leftrightarrow b_k)\right) =\bigoplus_{f(b_1,\cdots,b_n)=1}\left(\prod_{k=1}^n(x_k\leftrightarrow b_k)\right)$
　上の補題を用い、さらに同じ項でまとめると
$\displaystyle f(x_1,\cdots,x_n)=\bigoplus_{f(b_1,\cdots,b_n)=1}\left(\bigoplus_{(a_1,\cdots,a_n)\geqq (b_1,\cdots,b_n)} \prod_{a_i=1}x_i\right) =\bigoplus_{(a_1,\cdots,a_n)\in\mathbb{B}^n}\left(\bigoplus_{k=1}^{|\{(b_1,\cdots,b_n)\leqq(a_1,\cdots,a_n) \;|\;f(b_1,\cdots,b_n)=1\}|}\prod_{a_i=1}x_i\right)$

が成立つ。$x\oplus x=0$ を使って整理すれば、奇数回出現する項のみが残るので、定理の式が得られる。 □

【注】$(a_1,\cdots,a_n)=(0,\cdots,0)$ のとき、$\displaystyle \prod_{a_i=1}x_i=1$ である。

　$n$ 変数ガロア標準形の個数は、変数の積が(0個の積である定数$1$を含めて) $2^n$ 通りで、それらの２進和の個数 $2^{2^n}$ であるから、$n$ 変数論理関数の個数に等しい。よって、ガロア標準形は一意である。

問．
$f:A\to B,\ |A|=|B|<\infty$ のとき、$f\ が全射 \iff f\ が単射 \iff f\ が全単射$ であることを示せ
　実際にガロア標準形を求めるには、最初に説明したように
  1. 積和標準形を求め
  2. 和($+$)を排他的論理和($\oplus$)に、$\bar{x}$ を $x\oplus 1$ に置き換え
  3. 分配法則等使って展開し、$x\oplus x=0$ を使って整理
すればよい。

$x\ y\ z$$F(x,y,z)$
$0\ \ 0\ \ 0$$0$
$0\ \ 0\ \ 1$$1$
$0\ \ 1\ \ 0$$1$
$0\ \ 1\ \ 1$$0$
$1\ \ 0\ \ 0$$1$
$1\ \ 0\ \ 1$$0$
$1\ \ 1\ \ 0$$0$
$1\ \ 1\ \ 1$$1$
　右の表の値を持つ関数の標準形を求めてみよう。
  1. 積和標準形：$F(x,y,z)\\ =(x\leftrightarrow 0)(y\leftrightarrow 0)(z\leftrightarrow 1) +(x\leftrightarrow 0)(y\leftrightarrow 1)(z\leftrightarrow 0)\\ +(x\leftrightarrow 1)(y\leftrightarrow 0)(z\leftrightarrow 0) +(x\leftrightarrow 1)(y\leftrightarrow 1)(z\leftrightarrow 1)\\ =\bar{x}\bar{y}z+\bar{x}y\bar{z}+x\bar{y}\bar{z}+xyz$
  2. 和積標準形:$F(x,y,z)\\ =((x\oplus 0)+(y\oplus 0)+(z\oplus 0)) ((x\oplus 0)+(y\oplus 1)+(z\oplus 1))\\ ((x\oplus 1)+(y\oplus 0)+(z\oplus 1)) ((x\oplus 1)+(y\oplus 1)+(z\oplus 0))\\ =(x+y+z)(x+\bar{y}+\bar{z})(\bar{x}+y+\bar{z})(\bar{x}+\bar{y}+z)$
  3. ガロア標準形：$F(x,y,z)=\bar{x}\bar{y}z+\bar{x}y\bar{z}+x\bar{y}\bar{z}+xyz\\ =(x\oplus 1)(y\oplus 1)z\oplus(x\oplus 1)y(z\oplus 1) \oplus x(y\oplus 1)(z\oplus 1)\oplus xyz\\ =(xyz\oplus xz\oplus yz\oplus z)\oplus (xyz\oplus xy\oplus yz\oplus y)\oplus (xyz\oplus xy\oplus xz\oplus x)\oplus xyz\\ =x\oplus y\oplus z$

問．下の値を持つ論理関数の標準形を求めよ。
$x\ y\ z$$F(x,y,z)$
$0\ \ 0\ \ 0$$0$
$0\ \ 0\ \ 1$$0$
$0\ \ 1\ \ 0$$0$
$0\ \ 1\ \ 1$$1$
$1\ \ 0\ \ 0$$0$
$1\ \ 0\ \ 1$$1$
$1\ \ 1\ \ 0$$1$
$1\ \ 1\ \ 1$$1$
  1. 積和標準形を求めよ
  2. 和積標準形を求めよ
  3. ガロア標準形を求めよ

３．４節　単独で完全な論理関数

　単独で完全な（すべての論理関数が合成できる）$2$ 変数論理関数として $x|y=\bar{xy}$（NAND）と $x\downarrow y=\bar{x+y}$（NOR）が知られている。本節ではそれらについて調べてみよう。まず次の定理が成立つ。

定理．$\{|\},\ \{\downarrow\}$ は完全である。
証明．$x|y=\bar{xy}$ であることに注意すると、$\bar{x}=x|x,\ xy=(x|y)|(x|y)$ である。
　$\{\downarrow\}$ が完全であることも同様に証明できる。□

問．
  1. $|$ を使って $x+y$ を表せ
  2. $\{\downarrow\}$ が完全であることを証明せよ

$0$$1$$2$$3$$4$$5$$6$$7$ $8$$9$$10$$11$$12$$13$$14$$15$
$(x,y)$ $\bf 0$$\cdot$$x\bar{y}$$x$$\bar{x}y$$y$$\oplus$$+$ $\downarrow$$\leftrightarrow$$\bar{y}$$\leftarrow$$\bar{x}$$\to$$|$$\bf 1$
$(0,0)$ $0$$0$$0$$0$$0$$0$$0$$0$ $1$$1$$1$$1$$1$$1$$1$$1$
$(0,1)$ $0$$0$$0$$0$$1$$1$$1$$1$ $0$$0$$0$$0$$1$$1$$1$$1$
$(1,0)$ $0$$0$$1$$1$$0$$0$$1$$1$ $0$$0$$1$$1$$0$$0$$1$$1$
$(1,1)$ $0$$1$$0$$1$$0$$1$$0$$1$ $0$$1$$0$$1$$0$$1$$0$$1$
　では、単独で完全になる $2$ 変数関数は、$|$（$14$番）と $\downarrow$（$8$番）の２つだけだろうか。実は、次の事に注意すれば、右の表からそのことが言える。

  1. 定数関数（$0,\ 15$番）からは定数関数しか合成できない
  2. 本質的 $1$ 変数関数（$3,\ 5,\ 10,\ 12$番）からは本質的 $1$ 変数関数しか合成できない
  3. $f(0,0)=0$ である関数（$0～7$番）からは、$g(0,\cdots,0)=0$ となる関数しか合成できない
  4. $f(1,1)=1$ である関数（奇数番）からは、$g(1,\cdots,1)=1$ となる関数しか合成できない

問．
  1. 単独で完全になる $2$ 変数関数は、$|$ と $\downarrow$ の２つだけであることを示せ
  2. ２.４節では、スイッチ素子 $S:(x,y)\mapsto \bar{x}y$（$4$番）から任意の回路が合成できた。しかし、$S(0,0)=0$ だから、論理関数 $S$ だけでは、すべての論理関数は合成できない。この違いの原因はどこにあるか。

３．５節　論理式の簡単化

{"width":330, "height":130, "showToolbox":false, "toolbox":[{"type":"NOT"},{"type":"AND"},{"type":"OR"},{"type":"DC"},{"type":"LED"},{"type":"Toggle"}], "devices":[ {"type":"DC","id":"dev0","x":16,"y":48,"label":"DC"}, {"type":"Toggle","id":"dev1","x":64,"y":16,"label":"x","state":{"on":false}}, {"type":"Toggle","id":"dev2","x":64,"y":72,"label":"y","state":{"on":false}}, {"type":"NOT","id":"dev3","x":128,"y":8,"label":"NOT"}, {"type":"AND","id":"dev4","x":184,"y":24,"label":"AND"}, {"type":"AND","id":"dev5","x":184,"y":72,"label":"AND"}, {"type":"OR","id":"dev6","x":240,"y":48,"label":"OR"}, {"type":"LED","id":"dev7","x":288,"y":48,"label":"f(x,y)"}, {"type":"NOT","id":"dev8","x":128,"y":80,"label":"NOT"} ], "connectors":[ {"from":"dev1.in0","to":"dev0.out0"}, {"from":"dev2.in0","to":"dev0.out0"}, {"from":"dev3.in0","to":"dev1.out0"}, {"from":"dev4.in0","to":"dev3.out0"}, {"from":"dev4.in1","to":"dev2.out0"}, {"from":"dev5.in0","to":"dev1.out0"}, {"from":"dev5.in1","to":"dev8.out0"}, {"from":"dev6.in0","to":"dev4.out0"}, {"from":"dev6.in1","to":"dev5.out0"}, {"from":"dev7.in0","to":"dev6.out0"}, {"from":"dev8.in0","to":"dev2.out0"} ] }
　論理関数を表す式のできるだけ簡単な表現を求めることは、論理回路の簡単化につながり応用上重要であるが、一般には難しい。論理式、というより論理回路の複雑さの指標には２種類ある。論理式を回路にしたときの、段数（変数から出力にいたる路にある素子数の最大値）と素子数である。例えば、$f(x,y)=\bar{x}y+x\bar{y}\ [=(\neg x\wedge y)\vee (x\wedge \neg y)]$ は素子数 $5$、段数 $3$ (右上の図)である。当然、論理関数(を表す式)の複雑さは、選択する基本演算（基本素子）によって異なり、$f(x,y)=x\oplus y$ だから、基本演算(基本素子)に $\oplus$ があれば、$f$ は素子数 $1$、段数 $1$ で実現できる。
　ここでは論理多項式、とくに以下で定義する項和式の範囲内で議論しよう。変数(定数)およびその反転をリテラル、リテラルの積($\cdot$)を項、項の和($+$)を項和式と呼ぶ。積和標準形は項和式である。以下、基本演算（素子）は、積（AND）、和（OR）、反転（NOT）とする。
　$n$ 変数論理関数 $f,g:\mathbb{B}^n\to \mathbb{B}$ に対し、$f\leqq g$ を、充足集合の包含関係 $f^{-1}(1)\subseteq g^{-1}(1)$ で定義し、$g$ は $f$ を覆うという。この関係を、$x_1,\cdots,x_n$ 上の式にまで拡大し $\alpha\leqq \beta$ をそれらが表す関数の大小関係 $((x_1,\cdots,x_n)\mapsto\alpha)\leqq((x_1,\cdots,x_n)\mapsto\beta)$ で定義する。さらに、$f\leqq\beta,\ \alpha\leqq g$ も同様に定義する。

問．
  1. 論理式 $\alpha,\beta$ に対し、$\alpha \leqq \alpha+\beta$ であることを示せ。
  2. $((x,y,z)\mapsto x\bar{y}z)^{-1}(1)$ を求めよ
  3. $((x,y,z)\mapsto x\bar{y})^{-1}(1)$ を求めよ
  4. $((x,y,z)\mapsto x)^{-1}(1)$ を求めよ

　さて、項 $E$ が論理関数 $f$ の項和式に現れれば $E \leqq f$ である。$E \leqq f$ で、$E \lt E' \leqq f$ となる項 $E'$ が存在しない項 $E$ を $f$ の極大項といい、${\bf 0}\lt E \leqq f$ で、${\bf 0}\lt E' \lt E$ となる項 $E'$ が存在しない項 $E$ を $f$ の極小項という。
　明らかに、$f$ の積和標準形は $f$ の極小項の和である。この節の目的であるもっとも簡単な項和式を求めるには、$f$ の極大項を（極小項の集まりから）求め、その中からいくつかを選んで、和が $f$ と等しくなるようにすればよい。

最も簡単な項和式を求めるQuineの方法

  1. 与えられた $n$変数関数 $f(x_1,x_2,\cdots,x_n)$ を積和標準形で表し、その各項（$f$ の極小項）を縦に並べる。ただし項中のリテラルは変数番号の順に並べておく。（これを第1列とする）
  2. $t=1$ とおく
  3. 第 $t$ 列の項の各対に対し
    　$XxY,\ X\bar{x}Y$ の形であれば、
    　　それらに✓を付け、項 $XY$ を第 $t+1$ 列に、なければ追加する
  4. 第 $t+1$ 列に$2$項以上あれば、$t:=t+1$ として、3 へ
  5. 表中の✓が付いていない項が、$f$ の（すべての）極大項である
  6. 得られた極大項ごとに、それが覆う極小項に✓を付けた表を作る（Quineの表）
  7. すべての極小項を覆うように、極大項を(できるだけ少ない個数で)選ぶ

例１．$f(x,y,z)=\bar{x}\,\bar{y}\,\bar{z}+x\bar{y}\,\bar{z}+xy\bar{z}+x\bar{y}z+\bar{x}yz+xyz$
第1列愛2列第3列$x$$\bar{y}\,\bar{z}$$yz$
✓$\bar{x}\,\bar{y}\,\bar{z}$　$\bar{y}\,\bar{z}$　$x$✓
✓$x\bar{y}\,\bar{z}$✓$x\bar{z}$✓✓
✓$xy\bar{z}$✓$x\bar{y}$✓
✓$x\bar{y}z$✓$xy$✓
✓$\bar{x}yz$✓$xz$✓✓
✓$xyz$　$yz$✓
$f$ の極大項：$x,\ \bar{y}\,\bar{z},\ yz$$f=x+\bar{y}\,\bar{z}+yz$
例２．$f(x,y,z)=\bar{x}\,\bar{y}\,\bar{z}+x\bar{y}\,\bar{z}+\bar{x}y\bar{z}+x\bar{y}z+\bar{x}yz+xyz$
第1列愛2列第3列$\bar{y}\,\bar{z}$$\bar{ x}\,\bar{z}$$x\bar{y}$$\bar{x}y$$xz$$yz$
✓$\bar{x}\,\bar{y}\,\bar{z}$　$\bar{y}\,\bar{z}$✓✓
✓$x\bar{y}\,\bar{z}$　$\bar{x}\bar{z}$✓✓
✓$\bar{x}y\bar{z}$　$x\bar{y}$✓✓
✓$x\bar{y}z$　$\bar{x}y$✓✓
✓$\bar{x}yz$　$xz$✓✓
✓$xyz$　$yz$✓✓
$f$ の極大項：$\bar{y}\,\bar{z},\ \bar{x}\,\bar{z},\ x\bar{y},\ \bar{x}y,\ xz,\ yz$$f=\bar{y}\,\bar{z}+\bar{x}y+xz=\bar{x}\,\bar{z}+x\bar{y}+yz$

問．Quineの方法により、次の論理関数を簡単化せよ。
$f(x,y,z)=\bar{x}\,\bar{y}\,\bar{z}+x\bar{y}\,\bar{z}+\bar{x}y\bar{z}+\bar{x}\,\bar{y}z+xy\bar{z}+\bar{x}yz$

発見的方法：カルノー図

　前頁例１．の関数 $f(x,y,z)=\bar{x}\,\bar{y}\,\bar{z}+x\bar{y}\,\bar{z}+xy\bar{z}+x\bar{y}z+\bar{x}yz+xyz$ の真理値表を右図のように書いてみよう。この関数の極大項 $x,\ yz,\ \bar{y}\bar{z}$ の充足集合（覆う領域）は、それぞれ赤、青、緑の曲線で囲まれた部分になる。ここで、$y\,z$ の値の並び順(隣同士が1ヶ所しか違わない)に注意しよう。論理関数の値のこのような配置の表を３変数のカルノー図という。

問．３変数カルノー図で、次の関数の充足集合（覆う領域）を求めよ
$x＼yz$$0\ 0$$0\ 1$$1\ 1$$1\ 0$
$0$
$1$
  1. $f_1(z,y,z)=\bar{y}$
  2. $f_2(z,y,z)=z$
  3. $f_3(z,y,z)=\bar{z}$
  4. $f_4(z,y,z)=x\bar{y}$
  5. $f_5(z,y,z)=\bar{x}\bar{z}$

問．
$x＼yz$$0\ 0$$0\ 1$$1\ 1$$1\ 0$
$0$$1$$0$$1$$1$
$1$$1$$1$$1$$0$
前頁例２．の関数 $f(x,y,z)=\bar{x}\bar{y}\bar{z}+x\bar{y}\bar{z}+x\bar{y}z+xyz+\bar{x}yz+\bar{x}y\bar{z}$ のカルノー図は右図のようになる。これを表す最も簡単な以下の項和式について、それぞれの項が表す領域を楕円で囲め。
  1. $f(x,y,z)=\bar{y}\bar{z}+xz+\bar{x}y$
  2. $f(x,y,z)=\bar{x}\bar{z}+x\bar{y}+yz$

　これらからもわかるように、カルノー図を用いて最簡項和式を求める手順は次のようになる。
  1. 極大項を求める際は、１のますからなるできるだけ大きな領域を覆う項を探す
  2. 極大項の組み合わせを選ぶ段階では、全体を覆うできるだけ簡単な組み合わせを選ぶ

　一般に、最簡項和式が、一番簡単な多項式（$\cdot,\ +,\ ^-$ を使った式）になるわけではない。実際 $f(x,y,z)=\bar{x}y+\bar{x}z=\bar{x}(y+z)$ において、$\bar{x}y+\bar{x}z$ より $\bar{x}(y+z)$ のほうが素子数や段数が少なく簡単である。

問．以下の論理関数式を回路で実現したときの素子数と段数を求めよ
  1. $\bar{x}y+\bar{x}z$
  2. $\bar{x}(y+z)$

冗長入力回路の簡単化

冗長な(禁止あるいは無視できる)入力(値の組)を持つ関数(回路)では、そのような入力(値の組)に対して、0,1のどちらの出力を割り当ててもよい。そのような冗長入力を持つ場合の最簡項和式を求める手順は次のようになる。
  1. 冗長(禁止・無視)入力に対する出力は $*$ とする
  2. 極大項を求める段階では $*$ を $1$ と見なして、できるだけ大きな極大項を探す
  3. 極大項の組み合わせを選ぶ段階では、$*$ を $0$ と見なして、できるだけ簡単な組み合わせを選ぶ

問．
$wx＼yz$$0\ 0$$0\ 1$$1\ 1$$1\ 0$
$0\ 0$$1$$0$$1$$0$
$0\ 1$$0$$0$$0$$1$
$1\ 1$$*$$*$$*$$*$
$1\ 0$$0$$1$$*$$*$
右図の４変数カルノー図を実現する項和式 $\bar{w}\bar{x}\bar{y}\bar{z}+\bar{x}yz+xy\bar{z}+wz$ の各項が覆う領域を楕円で囲め。

問．次の表で与えられる論理関数を表す最簡項和式をそれぞれ求めよ。
(1)
$x＼yz$$0\ 0$$0\ 1$$1\ 1$$1\ 0$
$0$$0$$0$$1$$0$
$1$$0$$1$$1$$1$
(2)
$x＼yz$$0\ 0$$0\ 1$$1\ 1$$1\ 0$
$0$$1$$0$$*$$1$
$1$$*$$1$$1$$1$
(3)
$wx＼yz$$0\ 0$$0\ 1$$1\ 1$$1\ 0$
$0\ 0$$0$$1$$0$$1$
$0\ 1$$0$$1$$0$$1$
$1\ 1$$1$$1$$1$$1$
$1\ 0$$1$$1$$1$$1$

多出力回路の簡単化

$x＼yz$$0\ 0$$0\ 1$$1\ 1$$1\ 0$
$0$$1\ \color{red}{1}$$0\ \color{red}{0}$$1\ \color{red}{1}$$1\ \color{red}{1}$
$1$$1\ \color{red}{1}$$1\ \color{red}{1}$$1\ \color{red}{0}$$0\ \color{red}{0}$
　個別の回路を簡単化することが、必ずしも全体を簡単化するとは限らない。右のカルノー図は、$f(x,y,z)$ の値（左側・黒字）と $g(x,y,z)$ の値（右側・赤字）を一緒に表にしたものである。$f(x,y,z)$ と $g(x,y,z)$ を別個に簡単化すれば、例えば $\begin{cases} f(x,y,z)=\bar{y}\bar{z}+xz+\bar{x}y\\ g(x,y,z)=x\bar{y}+\bar{x}y+\bar{x}\bar{z} \end{cases}$ を得るが、$\begin{cases} f(x,y,z)=g(x,y,z)+yz\\ g(x,y,z)=x\bar{y}+\bar{x}y+\bar{y}\bar{z}\\ \end{cases}$ とした方が簡単になる。

問．以下のシミュレータで、$\begin{cases} f(x,y,z)=g(x,y,z)+yz\\ g(x,y,z)=x\bar{y}+\bar{x}y+\bar{y}\bar{z}\\ \end{cases}$ の回路を構成せよ。
{ "width":650, "height":300, "showToolbox":true, "toolbox":[ {"type":"DC"}, {"type":"LED"}, {"type":"Toggle"}, {"type":"NOT"}, {"type":"AND"}, {"type":"OR"} ], "devices":[ {"type":"DC","id":"dev0","x":0,"y":120,"label":"DC"}, {"type":"Toggle","id":"dev1","x":56,"y":40,"label":"x","state":{"on":false}}, {"type":"Toggle","id":"dev2","x":56,"y":120,"label":"y","state":{"on":false}}, {"type":"Toggle","id":"dev3","x":56,"y":208,"label":"z","state":{"on":false}}, {"type":"LED","id":"dev4","x":488,"y":48,"label":"f(x,y,z)"}, {"type":"LED","id":"dev5","x":488,"y":216,"label":"g(x,y,z)"} ], "connectors":[ {"from":"dev1.in0","to":"dev0.out0"}, {"from":"dev2.in0","to":"dev0.out0"}, {"from":"dev3.in0","to":"dev0.out0"} ] }

第４章　順序回路

{"width":400, "height":300, "showToolbox":true, "toolbox":[{"type":"DC"},{"type":"OSC"},{"type":"LED","label":"出力"},{"type":"PushOn"},{"type":"Toggle"}, {"type":"NOT"},{"type":"AND"},{"type":"OR"},{"type":"D-FF", "label":"Delay"},{"type":"RS-FF"}, {"type":"JK-FF"},{"type":"8bitCounter"}, {"type":"4bit7seg"}], "devices":[ {"type":"PushOn","id":"dev0","x":56,"y":88,"label":"PushOn"}, {"type":"4bit7seg","id":"dev1","x":200,"y":8,"label":"4bit7seg"}, {"type":"8bitCounter","id":"dev2","x":104,"y":16,"label":"8bitCounter"}, {"type":"4bit7seg","id":"dev3","x":200,"y":88,"label":"4bit7seg"}, {"type":"Toggle","id":"dev4","x":56,"y":32,"label":"Toggle","state":{"on":false}}, {"type":"DC","id":"dev5","x":0,"y":64,"label":"DC"}, {"type":"DC","id":"dev6","x":0,"y":192,"label":"DC"}, {"type":"Toggle","id":"dev7","x":56,"y":168,"label":"X","state":{"on":false}}, {"type":"PushOn","id":"dev8","x":56,"y":216,"label":"Clock"}, {"type":"LED","id":"dev9","x":200,"y":184,"label":"出力"}, {"type":"D-FF","id":"dev10","x":112,"y":192,"label":"Delay"} ], "connectors":[ {"from":"dev0.in0","to":"dev5.out0"}, {"from":"dev1.in0","to":"dev2.out0"}, {"from":"dev1.in1","to":"dev2.out1"}, {"from":"dev1.in2","to":"dev2.out2"}, {"from":"dev1.in3","to":"dev2.out3"}, {"from":"dev2.in0","to":"dev4.out0"}, {"from":"dev2.in1","to":"dev0.out0"}, {"from":"dev3.in0","to":"dev2.out4"}, {"from":"dev3.in1","to":"dev2.out5"}, {"from":"dev3.in2","to":"dev2.out6"}, {"from":"dev3.in3","to":"dev2.out7"}, {"from":"dev4.in0","to":"dev5.out0"}, {"from":"dev7.in0","to":"dev6.out0"}, {"from":"dev8.in0","to":"dev6.out0"}, {"from":"dev9.in0","to":"dev10.out0"}, {"from":"dev10.in0","to":"dev7.out0"}, {"from":"dev10.in1","to":"dev8.out0"} ] }

４．１節　順序回路とは

　第２章で扱った論理回路は、$0,1$ の入力(列)から $0,1$ の出力(列)を出すものであった。一般にコンピュータには、状態があり(記憶装置を持ち)、その時の状態と入力によって出力が定まる。このような特徴を持つ論理回路を順序回路という。これに対し２章で扱った論理回路を組合せ回路という。
　順序回路の簡単な例はカウンタだろう。右の16進カウンタで、Toggle(ON/OFF切替)ボタンを ON にして PushOn ボタンをクリックすると、その回数がカウントされる。カウンタでは、同じ入力(PushOn ボタンのクリック)に対し、その時の状態(覚えているクリック回数)によって、出力が異なる。
　記憶素子には、RS-FF、JK-FF 等いくつかの種類があるが、以下直前の入力を出力する記憶素子 Delay があるものとしよう。

実習．右上のシミュレータで、Delay の働きを確認してみよう
  1. 入力ボタン X をクリックしても、出力が変化しないことを確認せよ
  2. Clock ボタンをクリックすると、そのときの入力 X (ボタンの状態・ON/OFF)が出力に反映されることを確認せよ
  3. Delay（およびその内部の RS-FF ）をダブルクリックして、その内部構造を調べよ
  4. RS-FF（Reset-Set Flip Flop）の内部構造には、組合せ回路には見られない配線上の特徴がある。それは何か
例．同期式加算回路
　時刻 $1,\cdots,n$ に入力 $(x_1,y_1),\cdots,(x_n,y_n)$ が与えられたとき、２進数としての和 $x_n\cdots x_1+y_n\cdots y_1=[z_{n+1}]z_n\cdots z_1$ を与える順序回路を考える。時刻 $n$（$n$ 桁目）における桁上がりを $c_n\ (c_1=0)$ とおくと、論理関数の表は左下のようになる。ここで、桁上がり $c_n$ を状態 $q_{c_n}$ で記憶しておくことにすると、以下の(出力,状態)遷移表が得られる。正確には第５章で定義するが、出力・状態遷移図では、状態を$\circled{　}$で、最初の状態に$\Large\rhd$を付け、遷移表の内容を状態間のラベル付き矢印で $\transition{状態}{入力;出力}\circled{次状態}$ のように表す。
論理関数値表
$c_n$$x_n\ y_n$$c_{n+1}$$z_n$
$0$$0\ 0$$0$$0$
$0$$0\ 1$$0$$1$
$0$$1\ 0$$0$$1$
$0$$1\ 1$$1$$0$
$1$$0\ 0$$0$$1$
$1$$0\ 1$$1$$0$
$1$$1\ 0$$1$$0$
$1$$1\ 1$$1$$1$
出力・状態遷移表　　　　　　　　出力・状態遷移図
状態入力 $x\ y$
$0\ 0$$0\ 1$$1\ 0$$1\ 1$
$q_0$$0,q_0$$1,q_0$$1,q_0$$0,q_1$
$q_1$$1,q_0$$0,q_1$$0,q_1$$1,q_1$
順序回路：最初に Clock をクリックして初期化
{"width":400, "height":200, "showToolbox":true, "toolbox":[{"type":"DC"},{"type":"LED","label":"出力"},{"type":"LED","label":"状態","color":"#ffff80"},{"type":"PushOn"},{"type":"Toggle"},{"type":"NOT"},{"type":"AND"},{"type":"OR"},{"type":"D-FF", "label":"Delay"},{"type":"HalfAdder"},{"type":"FullAdder"}], "devices":[ {"type":"Toggle","id":"dev0","x":56,"y":16,"label":"X","state":{"on":false}}, {"type":"FullAdder","id":"dev1","x":120,"y":24,"label":"FullAdder"}, {"type":"DC","id":"dev2","x":0,"y":40,"label":"DC"}, {"type":"Toggle","id":"dev3","x":56,"y":72,"label":"Y","state":{"on":false}}, {"type":"D-FF","id":"dev4","x":120,"y":136,"label":"Delay"}, {"type":"PushOn","id":"dev5","x":56,"y":128,"label":"Clock"}, {"type":"LED","id":"dev6","x":216,"y":128,"label":"状態","color":"#ffff80"}, {"type":"LED","id":"dev7","x":248,"y":24,"label":"出力"} ], "connectors":[ {"from":"dev0.in0","to":"dev2.out0"}, {"from":"dev1.in0","to":"dev4.out0"}, {"from":"dev1.in1","to":"dev0.out0"}, {"from":"dev1.in2","to":"dev3.out0"}, {"from":"dev3.in0","to":"dev2.out0"}, {"from":"dev4.in0","to":"dev1.out1"}, {"from":"dev4.in1","to":"dev5.out0"}, {"from":"dev5.in0","to":"dev2.out0"}, {"from":"dev6.in0","to":"dev4.out0"}, {"from":"dev7.in0","to":"dev1.out0"} ] }

実習．以下の手順にしたがい、右上のシミュレータで $1010+0111$ を求めてみよう
  1. $t:=1$ とし、Clock をクリックしてリセットする
  2. $t$ 桁目の $x,\ y$ の値を入力し、$t$ 桁目の値を出力させる
  3. Clock をクリックし、$t:=t+1$ とし、2. に戻る
【注】桁上がり（Cout）は Clock をクリック後に「状態」として表示される

４．２節　状態の符号化

　前節では、順序回路を直感的に捉えるために、出力・状態遷移図を紹介した。本節では、与えられた出力・状態遷移図を順序回路で実現する際に必要となる $0,\ 1$ 符号化の考え方を紹介する。出力・状態遷移図の理論的な取り扱いについては、次章で論じる。

　次の出力・状態遷移図を考えよう。状態数は $5$ なので、$3$ ビットで符号化できる。状態符号の各ビットを $x,\ y,\ z$ で表し、それらの値（状態）を Delay で記憶するようにすれば、入出力は各 $1$ ビットなので、順序回路（の枠組み）は、右下のようになる。問題は、組合せ回路 MyDevice を、どのように設計（構成）すればよいかである。（シミュレータ中の MyDevice は空（未完成）なので、何も反応しない。）

{ "width":400, "height":300, "showToolbox":true, "toolbox":[ {"type":"DC"}, {"type":"LED","label":"出力"}, {"type":"LED","label":"状態","color":"#ffff80"}, {"type":"PushOn"}, {"type":"Toggle"}, {"type":"NOT"}, {"type":"AND"}, {"type":"OR"}, {"type":"D-FF","label":"Delay"}, {"type":"MyDevice"} ], "devices":[ {"type":"DC","id":"dev0","x":0,"y":40,"label":"DC"}, {"type":"Toggle","id":"dev1","x":56,"y":24,"label":"i","state":{"on":false}}, {"type":"MyDevice","id":"dev2","x":120,"y":32,"label":"MyDevice"}, {"type":"LED","id":"dev3","x":248,"y":24,"label":"出力"}, {"type":"D-FF","label":"Delay x","id":"dev4","x":128,"y":144}, {"type":"D-FF","label":"Delay y","id":"dev5","x":128,"y":192}, {"type":"LED","label":"状態 x","color":"#ffff80","id":"dev6","x":216,"y":136}, {"type":"LED","label":"状態 y","color":"#ffff80","id":"dev7","x":216,"y":184}, {"type":"D-FF","id":"dev8","x":128,"y":248,"label":"Delay z"}, {"type":"PushOn","id":"dev9","x":48,"y":192,"label":"Clock"}, {"type":"LED","id":"dev10","x":216,"y":240,"label":"状態 z","color":"#ffff80"} ], "connectors":[ {"from":"dev1.in0","to":"dev0.out0"}, {"from":"dev2.in0","to":"dev1.out0"}, {"from":"dev2.in1","to":"dev4.out0"}, {"from":"dev2.in2","to":"dev5.out0"}, {"from":"dev2.in3","to":"dev8.out0"}, {"from":"dev3.in0","to":"dev2.out0"}, {"from":"dev4.in0","to":"dev2.out1"}, {"from":"dev4.in1","to":"dev9.out0"}, {"from":"dev5.in0","to":"dev2.out2"}, {"from":"dev5.in1","to":"dev9.out0"}, {"from":"dev6.in0","to":"dev4.out0"}, {"from":"dev7.in0","to":"dev5.out0"}, {"from":"dev8.in0","to":"dev2.out3"}, {"from":"dev8.in1","to":"dev9.out0"}, {"from":"dev9.in0","to":"dev0.out0"}, {"from":"dev10.in0","to":"dev8.out0"} ] }

　当然、MyDevice内の回路は、状態の符号化(状態を表す符号の割り当て)によって異なる。以下のその事を見てゆこう。

符号化１

$q_0$$q_1$$q_2$$q_3$$q_4$
$x\ y\ z$$0\ 0\ 0$$0\ 0\ 1$$0\ 1\ 0$$0\ 1\ 1$$1\ 0\ 0$
　素朴に状態 $q_k$ を $k$ の $3$ ビット２進数$x\,y\,z$で表す(右表)と、状態遷移表を実現する真理値表は左下のようになる。状態に割り振られていないビットパターンがあるので、冗長入力回路の設計で議論したように、右下のカルノー図が得られ、実現する項和式はその下のようになる。

$(状態,入力)\to (次状態,出力)$ の表
状態入力次状態出力
$x$$y$$z$$i$$x'$$y'$$z'$$o$
$q_0$$0$$0$$0$$0$ $0$$1$$1$$0$
$0$$0$$0$$1$ $0$$0$$0$$1$
$q_1$$0$$0$$1$$0$ $1$$0$$0$$0$
$0$$0$$1$$1$ $0$$0$$1$$0$
$q_2$$0$$1$$0$$0$ $0$$0$$1$$1$
$0$$1$$0$$1$ $1$$0$$0$$1$
$q_3$$0$$1$$1$$0$ $0$$0$$0$$0$
$0$$1$$1$$1$ $0$$1$$1$$1$
$q_4$$1$$0$$0$$0$ $0$$0$$1$$0$
$1$$0$$0$$1$ $0$$1$$0$$0$
$x'\ y'\ z'\ o$ のカルノー図
xy＼zi$0\ 0$$0\ 1$$1\ 1$$1\ 0$
$0\ 0$$0\ 1\ 1\ 0$$0\ 0\ 0\ 1$$0\ 0\ 1\ 0$$1\ 0\ 0\ 0$
$0\ 1$$0\ 0\ 1\ 1$$1\ 0\ 0\ 1$$0\ 1\ 1\ 1$$0\ 0\ 0\ 0$
$1\ 1$$*$$*$$*$$*$
$1\ 0$$0\ 0\ 1\ 0$$0\ 1\ 0\ 0$$*$$*$

　実現する項和式は、 $\begin{cases} x' =\bar{x}\bar{y}z\bar{i}+\bar{x}y\bar{z}i & \Rightarrow \bar{y}z\bar{i}+y\bar{z}i\\ y' =\bar{x}\bar{y}\bar{z}\bar{i}+\bar{x}yzi+x\bar{y}\bar{z}i & \Rightarrow \bar{x}\bar{y}\bar{z}\bar{i}+yzi+xi\\ z' =\bar{x}\bar{y}\bar{z}\bar{i}+\bar{x}\bar{y}zi+\bar{x}y\bar{z}\bar{i}+\bar{x}yzi+x\bar{y}\bar{z}\bar{i} & \Rightarrow \bar{z}\bar{i}+\bar{x}zi\\ o =\bar{x}\bar{y}\bar{z}i+\bar{x}y\bar{z}\bar{i}+\bar{x}y\bar{z}i+\bar{x}yzi & \Rightarrow \bar{x}\bar{z}i+y\bar{z}\bar{i}+yzi \end{cases}$

符号化２

$q_0$$q_1$$q_2$$q_3$$q_4$
$x\ y\ z$$0\ 0\ 0$$0\ 1\ 0$$1\ 0\ 1$$1\ 1\ 0$$1\ 0\ 0$
　別の符号化で試してみよう。元の状態遷移図の状態を $q_0,\ q_1$ と $q_2,\ q_3,\ q_4$ の２グループに分けて、状態遷移のみを書き直してみると、右図のようになる。詳しい議論は省略するが、このことに着目して符号化の $x$ の値を分け、例えば右表のように割り当ててみよう。この結果、$x'$ を与える項和式は $x$（と入力 $i$)のみに依存するようになる。
$(状態,入力)\to (次状態,出力)$ の表
状態入力次状態出力
$x$$y$$z$$i$$x'$$y'$$z'$$o$
$q_0$$0$$0$$0$$0$ $1$$1$$0$$0$
$0$$0$$0$$1$ $0$$0$$0$$1$
$q_1$$0$$1$$0$$0$ $1$$0$$0$$0$
$0$$1$$0$$1$ $0$$1$$0$$0$
$q_2$$1$$0$$1$$0$ $0$$1$$0$$1$
$1$$0$$1$$1$ $1$$0$$0$$1$
$q_3$$1$$1$$0$$0$ $0$$0$$0$$0$
$1$$1$$0$$1$ $1$$1$$0$$1$
$q_4$$1$$0$$0$$0$ $0$$1$$0$$0$
$1$$0$$0$$1$ $1$$0$$1$$0$
$x'\ y'\ z'\ o$ のカルノー図
xy＼zi$0\ 0$$0\ 1$$1\ 1$$1\ 0$
$0\ 0$$1\ 1\ 0\ 0$$0\ 0\ 0\ 1$$*$$*$
$0\ 1$$1\ 0\ 0\ 0$$0\ 1\ 0\ 0$$*$$*$
$1\ 1$$0\ 0\ 0\ 0$$1\ 1\ 0\ 1$$*$$*$
$1\ 0$$0\ 1\ 0\ 0$$1\ 0\ 1\ 0$$1\ 0\ 0\ 1$$0\ 1\ 0\ 1$

　実現する項和式は $\begin{cases} x' =\bar{x}\bar{y}\bar{z}\bar{i}+\bar{x}y\bar{z}\bar{i}+xy\bar{z}i+x\bar{y}\bar{z}i+x\bar{y}zi & \Rightarrow \bar{x}\bar{i}+xi\\ y' =\bar{x}\bar{y}\bar{z}\bar{i}+x\bar{y}\bar{z}\bar{i}+\bar{x}y\bar{z}i+xy\bar{z}i & \Rightarrow \bar{y}\bar{i}+yi\\ z' =x\bar{y}\bar{z}i & \Rightarrow x\bar{y}\bar{z}i\\ o =\bar{x}\bar{y}\bar{z}i+xy\bar{z}i+x\bar{y}zi+x\bar{y}z\bar{i} & \Rightarrow z+\bar{x}\bar{y}i+xyi \end{cases}$

　明らかに、こちらの方が簡単な順序回路になる。

問．
  1. 符号化２で、$y'$ の値が $y$ と入力 $i$ のみで定まる理由を説明せよ
  2. $q_0$$q_1$$q_2$$q_3$$q_4$
    $x\ y\ z$$0\ 0\ 0$$0\ 1\ 1$$1\ 0\ 1$$1\ 1\ 0$$1\ 1\ 1$
    右の符号化の下で、本節の状態遷移図を実現する出来るだけ簡単な項和式を求めよ。