20260423_4

20260416_4

---

論理式の展開公式

$$\begin{array}{r}X(Y+Z)=XY+YZ\\ (X+Y)(Y+Z)=X+YZ\\ (X+Y)(X^{\prime }+Z)=XZ+X^{\prime }Y\end{array}$$

排他的論理和

$X$	$Y$	$X\oplus Y$
0	0	0
0	1	1
1	0	1
1	1	0

排他的論理和

$$\begin{array}{rl}X\oplus o& =X\\ X\oplus 1& =1\\ X\oplus X& =0\\ X\oplus X^{\prime }& =1\\ X\oplus Y& =Y\oplus X\\ (X\oplus Y)\oplus Z& =X\oplus (Y\oplus Z)\end{array}$$

$X\oplus Y=X^{\prime }Y+X{Y}^{\prime }=(X+Y)(XY{)}^{\prime }$

いわゆるORを包含的論理和という場合も

一致演算

$X$	$Y$	$X\equiv Y$
0	0	1
0	1	0
1	0	0
1	1	1

$$\begin{array}{rl}X\equiv Y& =(XY+X^{\prime }{Y}^{\prime })\\ & =(X+Y^{\prime })(X^{\prime }+Y)\\ & =(X^{\prime }Y+XY)\\ & =(X\oplus Y{)}^{\prime }\end{array}$$

コンセンサスの定理

$XY+X^{\prime }Z+YZ=XY+X^{\prime }Z$

このときの$YZ$はコンセンサス項

双対

$(X+Y)(X^{\prime }Z)(Y+Z)=(X+Y)(X^{\prime }+Z)$

$X(なにか1)$と$X^{\prime }(なにか2)$があったとき、$(なにか1)(なにか2)$は消去可能

一回冗長な項を追加してからだと複数のコンセンサスを消去できる場合がある

---

式の簡単化

graph TD
A[項の併合] --> B[項の消去] --> C[リテラルの消去] --> 冗長な項の追加

項の併合

$ab{c}^{\prime }d+abcd=abd$

みたいなやつ。

$$\begin{array}{rl}a{b}^{\prime }c+abc+a^{\prime }bc& =a^{\prime }bc+abc+abc+a^{\prime }bc\\ & =ac+ac\end{array}$$

のように一度項を追加する場合も

項の消去

$a^{\prime }b+a^{\prime }bc=a^{\prime }b$

みたいなやつ

$$\begin{array}{rl}{a}^{\prime }bc+bcd+a^{\prime }bc& =a^{\prime }b{c}^{\prime }+bcd\end{array}$$

リテラルの消去

因数分解したあとその中を処理

冗長な項の追加

$$\begin{array}{rl}WX+WY+X^{\prime }{Z}^{\prime }+W{Y}^{\prime }{Z}^{\prime }& =WX+WY+X^{\prime }{Z}^{\prime }+W{Y}^{\prime }{Z}^{\prime }+W{Z}^{\prime }\\ & =WX+WY+X^{\prime }Z+W{Z}^{\prime }\\ & =WX+XY+X^{\prime }{Z}^{\prime }\end{array}$$

---

等式の妥当性の証明

1. 真理値表を書けば証明できる
2. ブール代数によって一方の式を変形してた方と同じ形になることを示す
3. 両辺に独立な式変形を施して同じ形にする
4. リバーシブルな演算(否定など)を施す(乗算はリバーシブルではない)

等式が異なることの証明(反例の示し方)

1. 両辺を積和形にしてみる
2. 片方にのみある項が冗長か検討する
3. 足りない項を追加できるか検討する
4. 余分な項を削除できるか検討する

ブール代数では簡約法則が成り立たない

• $x+y=x+z\to y=z$は通常の代数では成り立つがブール代数では成り立たない
• $xy=xz\to y=z$も通常の代数では成り立つがブール代数では成り立たない
• 逆は成り立つ

---

センテンスを論理式に変換する

文章から論理式を導く

• 文章の一部(文節)に論理変数を割り当てる
• その関数に対応する代数式を決める
• これを割り当てる

真理値表から論理回路を設計する

$A$	$B$	$C$	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

最小項展開を用いる

単に1になる条件を書き下す

$f=A^{\prime }BC+A{B}^{\prime }{C}^{\prime }+A{B}^{\prime }C+AB{C}^{\prime }+ABC$

これを簡単化する

$f=A^{\prime }BC+A{B}^{\prime }+AB=A^{\prime }BC+A=A+BC$

あるいは$f^{\prime }$からもとめてもいい(最大項展開)

$f^{\prime }=A^{\prime }{B}^{\prime }{C}^{\prime }+A^{\prime }{B}^{\prime }C+A^{\prime }BC$

これを否定

$f=(A+B+C)(A+B+C^{\prime })(A+B^{\prime }+C)$

数	$A$	$B$	$C$	$m$表記法	$M$表記法
0	0	0	0	$m_0=A^{\prime }{B}^{\prime }{C}^{\prime }$	$M_0=A+B+C$
1	0	0	1	$m_1=A^{\prime }{B}^{\prime }C$	$M_1=A+B+C^{\prime }$
2	0	1	0	$m_2=A^{\prime }B{C}^{\prime }$	$M_2=A+B^{\prime }+C$
3	0	1	1	$m_3=A^{\prime }BC$	$M_3=A+B^{\prime }+C^{\prime }$
4	1	0	0	$m_4=A{B}^{\prime }{C}^{\prime }$	$M_4=A^{\prime }+B+C$
5	1	0	1	$m_5=A{B}^{\prime }C$	$M_5=A^{\prime }+B+C^{\prime }$
6	1	1	0	$m_6=AB{C}^{\prime }$	$M_6=A^{\prime }+B^{\prime }+C$
7	1	1	1	$m_7=ABC$	$M_7=A^{\prime }+B^{\prime }+C^{\prime }$

最小項展開は$m$表記法の論理和で表した形

最大項展開は$M$表記法の論理積で表した形(論理和は$f^{\prime }$に相当するためドモルガンによって反転すると論理積になる)

最小項展開と最大項展開の一般化

$$F={\Sigma }_{i=o}^7{a}_o{m}_i$$ $$F={\Pi }_{i=0}^7(a_i+M_i)$$