นิพจน์บูลีนและฟังก์ชัน

พีชคณิตบูลีนคือพีชคณิตของตรรกะ เกี่ยวข้องกับตัวแปรที่สามารถมีค่าไม่ต่อเนื่องได้ 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