---
tags: Fundamentals of Logic Design
---
# Boolean Algebra

## Basic Operations and Truth Table

L, H: 高電位，低電位
F, T: false, true
complement(補數)： 把零變一之類的
圈圈代表一個 inverter。之後寫得簡潔一點就會把前面的三角形拿掉

And gate
OR gate
沒有特別強調就是 inclusive or
inclusive or: 可以兩個都是1 或 0

布林公式，可以試著推推看

這是所謂的真值表，左邊是 input 右邊是最後的結果
加法：OR
乘法：AND


左邊是 or 右邊是 and
下面那題，後面一個加一，前面都不用看，就是等於一。

## Basic & Advanced Theorems
:arrow_up: 上圖的下面定理，電路化簡會用到。

這裡很重要
or＝並聯。 and＝串連


or＝並聯。 and＝串連


串連一個 x+x' = 1，不影響結果
最後並聯一個 xy，不影響結果

分配律的寫法
也可以由串連並聯的寫法來解釋


重點：需要假設好幾個 group 來簡化電路

## Multiplying Out and Factoring
Multiplying Out: 把式子乘開

* SOP

sum term = A+B, A
product term = AB, A

SOP: (AND) OR (AND) OR (AND)
括號內不能有 OR


* POS

第三題要用 group 的概念會比較好理解

不算 inverter 只算 and, or 只會有兩層

## DeMorgan's Law and Duality

* DeMorgan's Law
為什麼要學DeMorgan's Law ： 這裡是使用正邏輯來判斷什麼時候 f = 0，對 f 取 complement(補數)，原本 x+y = 0 會變成 1 ，再由正邏輯來判斷就可以得知何時 f = 0 。

DeMorgan's Law -> 如何快速得到函數的補數
法則就是，把補數的符號分配給函數內部的變數，並且轉換裡面的 operators(AND->OR)

* Duality(對偶)

變數不需要補數，可以降低簡化難度

回過頭看，這兩個表格個別是彼此的對偶。

## More Multiplying Out and Factoring

x(y+z) = xy + xz (背)
x+ yz = (x+y)(x+z) (背)
(x+y)(x'+z) = xz + yx' (背)
example 第二題: ABC 可以再拿掉

:arrow_up:(c)證明 : and 一個 (x+x')=1
ab + abc -> 其中 abc 可以直接拿掉
因為 ab(1+c) = ab.
1+c = 1


## Exclusive-OR and Equivalence Operations

* Exclusive-OR
Exclusive-OR: 排他，我有你就不能有。兩個一樣不行
X (EOR) Y = xy' + x'y -> 下面板書有解釋如何得到
要對 (EOR) DeMorgan's Law 時，要先轉換成 AND, OR
* Exclusive-OR用越多，電路面積就越省

* Equivalence Operations
式子裡面如果有 (EOR), Equivalence Operations 可以先用上面的式子做替換

如何由真值表求得 F
把所有的1 OR 起來
然後對照個別的 x, y 。遇到零的給他補數
例如 x=0, y=1 -> x'y
x=1, y=0 -> xy'
x=1, y=1 -> xy
F = x'y + xy' + xy
-> xy' + y
-> x + y


## The Consensus Theorem

Consensus （共識）

此處的證明之前講過了，練習一很重要需要運用 dual form

## Simplification of Switching Expression - Techniques

第二個例子說明，可以加一個一樣的邏輯閘幫助化簡。


xy + x'z add yz
x add xy
(x+x')

Example: 可以發現 x, x' 使用 The Consensus Theorem
加 wz' 是為了刪掉 wy'z'

## Simplification of Switching Expression - Combining All

這個題型用很多 The Consensus Theorem

(A+C)(A+B+C) = (A+C) (背)

## Proving the Validity of Equation