นิพจน์บูลีนและฟังก์ชัน
พีชคณิตบูลีนคือพีชคณิตของตรรกะ เกี่ยวข้องกับตัวแปรที่สามารถมีค่าไม่ต่อเนื่องได้ 2 ค่าคือ 0 (False) และ 1 (True) และการดำเนินการที่มีความสำคัญเชิงตรรกะ วิธีแรกสุดในการจัดการกับตรรกะเชิงสัญลักษณ์ถูกคิดค้นโดย George Boole และต่อมาเป็นที่รู้จักในชื่อ Boolean Algebra
พีชคณิตบูลีนได้กลายเป็นเครื่องมือที่ขาดไม่ได้ในวิทยาการคอมพิวเตอร์สำหรับการนำไปใช้ในทฤษฎีการสลับการสร้างวงจรอิเล็กทรอนิกส์พื้นฐานและการออกแบบคอมพิวเตอร์ดิจิทัล
ฟังก์ชันบูลีน
A Boolean functionเป็นฟังก์ชันทางคณิตศาสตร์ชนิดพิเศษ $ f: X ^ n \ rightarrow X $ ขององศา n โดยที่ $ X = \ lbrace {0, 1} \ rbrace $ เป็นโดเมนบูลีนและ n เป็นจำนวนเต็มที่ไม่เป็นลบ อธิบายวิธีการรับเอาต์พุตบูลีนจากอินพุตบูลีน
Example- ให้ $ F (A, B) = A'B '$. นี่คือฟังก์ชันของระดับ 2 จากชุดของตัวแปรบูลีนที่เรียงลำดับไปยังชุด $ \ lbrace {0, 1} \ rbrace $ โดยที่ $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ และ $ F (1, 1) = 0 $
นิพจน์บูลีน
A Boolean expressionสร้างค่าบูลีนเสมอ นิพจน์บูลีนประกอบด้วยการรวมกันของค่าคงที่บูลีน (จริงหรือเท็จ) ตัวแปรบูลีนและการเชื่อมต่อเชิงตรรกะ แต่ละนิพจน์บูลีนแสดงถึงฟังก์ชันบูลีน
Example - $ AB'C $ เป็นนิพจน์บูลีน
ข้อมูลประจำตัวบูลีน
กฎหมายเสริมสองชั้น
$ \ sim (\ sim A) = A $
กฎหมายประกอบ
$ A + \ sim A = 1 $ (หรือแบบฟอร์ม)
$ ก. \ sim A = 0 $ (และแบบฟอร์ม)
กฎหมาย Idempotent
$ A + A = A $ (หรือแบบฟอร์ม)
$ ก. A = A $ (และแบบฟอร์ม)
กฎหมายประจำตัว
$ A + 0 = A $ (หรือแบบฟอร์ม)
$ ก. 1 = A $ (และแบบฟอร์ม)
กฎหมายปกครอง
$ A + 1 = 1 $ (หรือแบบฟอร์ม)
$ ก. 0 = 0 $ (และแบบฟอร์ม)
กฎหมายสับเปลี่ยน
$ A + B = B + A $ (หรือแบบฟอร์ม)
$ ก. B = ข. A $ (และแบบฟอร์ม)
กฎหมายที่เกี่ยวข้อง
$ A + (B + C) = (A + B) + C $ (หรือแบบฟอร์ม)
$ ก. (B. C) = (ก. ข). C $ (และแบบฟอร์ม)
กฎหมายการดูดซึม
$ ก. (A + B) = A $
$ A + (ก. B) = A $
กฎหมายลดความซับซ้อน
$ ก. (\ sim A + B) = ก. B $
$ A + (\ sim A. B) = A + B $
กฎหมายการจัดจำหน่าย
$ A + (B. C) = (A + B) (A + C) $
$ ก. (B + C) = (ก. B) + (ก. C) $
กฎของ De-Morgan
$ \ sim (A. B) = \ sim A + \ sim B $
$ \ sim (A + B) = \ sim A \ ซิม B $
แบบฟอร์มบัญญัติ
สำหรับนิพจน์บูลีนมีรูปแบบบัญญัติสองประเภท -
- แบบฟอร์มผลรวมของ minterms (SOM)
- ผลิตภัณฑ์ของแบบฟอร์ม maxterms (POM)
แบบฟอร์ม Sum of Minterms (SOM) หรือ Sum of Products (SOP)
Minterm คือผลคูณของตัวแปรทั้งหมดที่นำมาในรูปแบบโดยตรงหรือแบบเสริม ฟังก์ชันบูลีนใด ๆ สามารถแสดงเป็นผลรวมของ 1 นาทีและค่าผกผันของฟังก์ชันสามารถแสดงเป็นผลรวมของ 0 นาที ดังนั้น
F (รายการตัวแปร) = ∑ (รายการดัชนี 1 นาที)
และ
F '(รายการตัวแปร) = ∑ (รายการดัชนี 0 นาที)
| ก | ข | ค | ระยะเวลา | Minterm |
|---|---|---|---|---|
| 0 | 0 | 0 | x'y'z ' | ม. 0 |
| 0 | 0 | 1 | x'y'z | ม. 1 |
| 0 | 1 | 0 | x'yz ' | ม. 2 |
| 0 | 1 | 1 | x'yz | ม. 3 |
| 1 | 0 | 0 | xy'z ' | ม. 4 |
| 1 | 0 | 1 | xy'z | ม. 5 |
| 1 | 1 | 0 | xyz ' | ม. 6 |
| 1 | 1 | 1 | xyz | ม. 7 |
Example
ให้$ F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz $
หรือ$ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $
ดังนั้น
$ F (x, y, z) = \ sum (0, 5, 6, 7) $
ตอนนี้เราจะพบส่วนเติมเต็มของ $ F (x, y, z) $
$ F '(x, y, z) = x' yz + x 'y' z + x 'yz' + xy 'z' $
หรือ$ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $
ดังนั้น
$ F '(x, y, z) = \ sum (3, 1, 2, 4) = \ sum (1, 2, 3, 4) $
แบบฟอร์ม Product of Maxterms (POM) หรือ Product of Sums (POS)
maxterm คือการเพิ่มตัวแปรทั้งหมดที่นำมาในรูปแบบโดยตรงหรือแบบเสริม ฟังก์ชันบูลีนใด ๆ สามารถแสดงเป็นผลคูณของ 0-maxterms และค่าผกผันของฟังก์ชันสามารถแสดงเป็นผลคูณของ 1-maxterms ได้ ดังนั้น
F (รายการตัวแปร) = $ \ pi $ (รายการดัชนี 0-maxterm)
และ
F '(รายการตัวแปร) = $ \ pi $ (รายการดัชนี 1-maxterm)
| ก | ข | ค | ระยะเวลา | Maxterm |
|---|---|---|---|---|
| 0 | 0 | 0 | x + y + z | ม0 |
| 0 | 0 | 1 | x + y + z ' | ม. 1 |
| 0 | 1 | 0 | x + y '+ z | ม. 2 |
| 0 | 1 | 1 | x + y '+ z' | ม. 3 |
| 1 | 0 | 0 | x '+ y + z | ม. 4 |
| 1 | 0 | 1 | x '+ y + z' | ม. 5 |
| 1 | 1 | 0 | x '+ y' + z | ม6 |
| 1 | 1 | 1 | x '+ y' + z ' | ม. 7 |
ตัวอย่าง
ให้$ F (x, y, z) = (x + y + z) (x + y + z ') (x + y '+ z) (x '+ y + z) $
หรือ$ F (x, y, z) = M_0 M_1 M_2 M_4 $
ดังนั้น
$ F (x, y, z) = \ pi (0, 1, 2, 4) $
$ F '' (x, y, z) = (x + y '+ z') (x '+ y + z') (x '+ y' + z) (x '+ y' + z ') $
หรือ$ F (x, y, z) = M_3 M_5. M_6. M_7 $
ดังนั้น
$ F '(x, y, z) = \ pi (3, 5, 6, 7) $
ลอจิกเกตส์
ฟังก์ชันบูลีนถูกนำไปใช้โดยใช้ลอจิกเกต ต่อไปนี้คือลอจิกเกต -
ไม่ใช่ประตู
ประตู NOT จะแปลงอินพุตบิตเดียวไปเป็นเอาต์พุตบิตเดียว
| ก | ~ ก |
|---|---|
| 0 | 1 |
| 1 | 0 |
และประตู
ประตู AND เป็นลอจิกเกตที่ให้เอาต์พุตสูงก็ต่อเมื่ออินพุตทั้งหมดสูงเท่านั้นมิฉะนั้นจะให้เอาต์พุตต่ำ จุด (.) ใช้เพื่อแสดงการดำเนินการ AND
| ก | ข | AB |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
หรือประตู
OR gate คือลอจิกเกตที่ให้เอาต์พุตสูงหากอินพุตอย่างน้อยหนึ่งอินพุตสูง เครื่องหมายบวก (+) ใช้เพื่อแสดงการทำงานของ OR
| ก | ข | A + B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
ประตู NAND
NAND gate เป็นลอจิกเกตที่ให้เอาต์พุตต่ำก็ต่อเมื่ออินพุตทั้งหมดสูงมิฉะนั้นจะให้เอาต์พุตสูง
| ก | ข | ~ (AB) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
ประตู NOR
NOR gate เป็นลอจิกเกตที่ให้เอาต์พุตสูงหากอินพุตทั้งสองต่ำมิฉะนั้นจะให้เอาต์พุตต่ำ
| ก | ข | ~ (A + B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
ประตู XOR (Exclusive OR)
XOR gate เป็นลอจิกเกตที่ให้เอาต์พุตสูงหากอินพุตต่างกันมิฉะนั้นจะให้เอาต์พุตต่ำ
| ก | ข | A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
ประตู X-NOR (พิเศษ NOR)
ประตู EX-NOR เป็นลอจิกเกตที่ให้เอาต์พุตสูงหากอินพุตเหมือนกันมิฉะนั้นจะให้เอาต์พุตต่ำ
| ก | ข | ก X-NOR B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |