20260416_4

20260409_4

---

• 論理回路では同じ答えでもいろいろな表し方ができる

• ブール代数ではすべての変数が2つの値あるいは1つの値をとる

  • 数値というよりは回路の状態に相当
    • 回路なら0が低電圧で1が高電圧

---

• NO端子(通常は開いているスイッチ)
• NC端子(通常は閉じているスイッチ)
• スイッチを同時に動かしたときNOとNCは常に逆になる
• NO=$X$とすると$X^{\prime }$=NC
• 0’=1, 1’=0

---

• 否定=インバーターは電子回路ではXの反転としてはたらく

X	X’
0	1
1	0

---

• 論理積=両方が1のときだけ1

A	B	C=A$\cdot$B
1	1	1
0	1	0
1	0	0
0	0	0

直列にAとBのスイッチを並べた状態に対応

graph LR

A-->B
B-->C

---

• 論理和=どちらかが1なら1

A	B	C=A+B
1	1	1
0	1	1
1	0	1
0	0	0

並列にAとBのスイッチを並べた状態に対応

graph LR
A --> C
B --> C

---

論理式$A{B}^{\prime }+C$

graph LR

A --> D[(AND)]
B --> E{NOT}
E --> D
C --> F[/OR/]
D --> F
F --> G(OUTPUT)

論理式$A^{\prime }+B$

A	B	A’	F=A’+B
0	1	1	1
0	0	1	1
1	1	0	1
1	0	0	0

リテラル: 論理式何に現れる各変数と変数の否定値
$a{b}^{\prime }c+c^{\prime }b+a^{\prime }b{c}^{\prime }+b^{\prime }c$ならリテラルは10個
式が等しい場合は二式はイコールで結んでよい ex: $A{B}^{\prime }+C=(A+C)(B^{\prime }+C)$
式が等しい→すべての入力$2^{入力の個数}$通りに対して出力が等しい(真理値表で確認)
等しい式であれば式変形が可能

---

ブール代数の基本定理

$X+0=X$

$X+1=1$

$X\cdot 1=1$

$X\cdot 0=0$

$X+X=X$

$X\cdot X=X$

$(X^{\prime }{)}^{\prime }=X$

$X+X^{\prime }=1$

$X\cdot X^{\prime }=0$

これらから

• $A$に置き換え可能なのは
  • $A\cdot A$
  • $A+A$
  • $A+0$
• $A+1$は$1$に置き換え可能
• $A+A^{\prime }$は$1$に置き換え可能
• $A\cdot A^{\prime }$は$0$に置き換え可能

---

交換則・結合則

$XY=YX$

$X+Y=Y+X$

$(XY)Z=X(YZ)=XYZ$

$(X+Y)+Z=X+(Y+Z)$

全部直列、全部並列のスイッチを想像するといい

分配則

$X(Y+Z)=XY+XZ$

$X+YZ=(X+Y)(X+Z)$

$$(X+Y)(X+Z)=X(X+Z)+Y(X+Z)=XX+XZ+YX+YZ=X+XZ+XY+YZ=X\cdot 1+XZ+YX+YZ=X(1+Z+Y)+YZ=X\cdot 1+YZ=X+YZ$$

ド・モルガンの法則

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

あるブール代数式に対する双対は定数0と1を交換し、AND演算とOR演算を交換することで作ることができる

---

簡単化

簡単化の処理

併合

$XY+X{Y}^{\prime }=X$

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

→式の決定にはXしか使わない

吸収

$X+XY=X$ → $(X+1)+XY=X$

$X(X+Y)=X$(双対)

消去

$X+X^{\prime }Y=X+Y$

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

→$X^{\prime }$が関与しない

コンセンサス

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

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

---

式の展開/因数分解

積項: リテラルの論理積で表した項
積和形: 積項の論理和で表した式$A+B^{\prime }CD$など

graph LR
A[和積形] --展開--> B[積和形]
B --因数分解--> A

ドモルガンの法則

和項の否定

$(X_1+X_2+\cdots +X_n{)}^{\prime }=X_1^{\prime }+X_2^{\prime }+\cdots +X_n^{\prime }$

積項の否定

$(X_1{X}_2\cdots X_n{)}^{\prime }=X_1^{\prime }+X_2^{\prime }+\cdots X_n^{\prime }$

繰り返し2変数のドモルガンを適用するとよい

$(A^{\prime }+B)C^{\prime }$の否定

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

---

展開の時(和積→積和)は分配則を用いる

1. $(X+Y)(X^{\prime }Z)=ZX+X^{\prime }Y$や$(X+Y+X+Z)=X+YZ$
2. $X(Y+Z)=XY+XZ$
   の順に行う