พีชคณิตบูลีน
พีชคณิตบูลีน (Boolean Algebra) เป็นส่วนหนึ่งในเรื่องทางคณิตศาสตร์ที่ใช้วิเคราะห์ปัญหาทางตรรก ถูกคิคค้นพัฒนาโดยนักคณิตศาสตร์ชาวอังกฤษ ชื่อ จอร์จ บูล (George Boole) ต่อมามีผู้พัฒนาให้สมบูรณ์ขึ้นอีกหลายคน ปัจจุบันเราใช้พีชคณิตบูลีนในการออกบบวงจรลอจิก ซึ่งตัวแปรแต่ละตัวจะแทนสภาวะเพียงสองอย่าง คือ 0 หรือ 1 เท่านั้น ซึ่งการนำทฤษฎีบูลีนมาใช้จะทำให้ลดความยุ่งยากของวงจรลอจิกลง ทำให้ประหยัดในการสร้าง และลดความผิดพลาดในการประกอบวงจรได้ นอกจากนี้พีชคณิตบูลีนยังเป็นพื้นฐานในการคิดค้นวิธีการลดรูปของสมการลอจิกให้สั้นลงอีกหลายวิธี ทำให้เราสามารถทำงานได้ถูกต้อง แม่นยำ และง่ายยิ่งขึ้น
หลักการเบื้องต้นของพีชคณิตบูลีน
ถ้า A ¹ 0 แสดงว่าค่า A เป็น 1
ถ้า A ¹ 1 แสดงว่าค่า A เป็น 0
ซึ่งค่าดังกล่าวนี้จะเรียกว่า “ค่าความจริง” ของตัวแปร A หรือเรียกสั้น ๆ ว่า “ค่าของ A”
1. AND ใช้สัญลักษณ์คือ จุด ( × ) หรืออาจไม่มีจุดก็ได้ เมื่อตัวคงที่ 2 ตัว AND กัน ผลของการกระทำ AND จะเป็น 1 ได้ก็ต่อเมื่อตัวคงที่ทั้งสองต้องเป็น 1 นั่นคือ
0 × 0 = 0
0 × 1 = 0
1 × 0 = 0
1 × 1 = 1
2. OR ใช้สัญลักษณ์คือ บวก ( + ) เมื่อตัวคงที่ 2 ตัว OR กัน ผลของการกระทำ OR จะเป็น 1 ได้ก็ต่อเมื่อตัวคงที่ตัวใดตัวหนึ่งเป็น 1 หรือทั้งสองตัวเป็น 1 นั่นคือ
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
1 หรือ 1¢ = 0
0 หรือ 0¢ = 1
นิพจน์ (Expression) หมายถึง กลุ่มเทอมที่ถูกกระทำกันด้วยตัวกระทำ เช่น
A × B + C × D เป็นต้น ปกติเรามักจะเรียกว่า Logic Expression หรือ Boolean Expression โดยมีหลักการตีค่าของลำดับความสำคัญของการกระทำในนิพจน์ (Expression) ต่าง ๆ ดังนี้
1. ถ้าไม่มีวงเล็บให้ถือการกระทำของ “AND” ก่อน “OR” เช่น
A × B + C × D
อันดับแรกให้ทำ A × B และ C × D ก่อน
อันดับที่สอง ให้เอาผลของ (A × B) มา OR กับ ผลของ (C × D)
2. ถ้ามีวงเล็บ ให้กระทำในวงเล็บก่อน โดยถ้ามีวงเล็บซ้อนกันหลาย ๆ ชั้น ให้กระทำในวงเล็บชั้นในที่สุดก่อนตามลำดับออกมา เช่น
(A + B) ×{A×(B+C)+D}
อันดับแรก ให้ทำ (B+C) ก่อน แล้วมา AND กับ A ผลลัพธ์ที่ได้จึงมา OR กับ D
อันดับที่สอง ให้ทำ (A+B) แล้วจึงนำผลลัพธ์ มา AND กับผลลัพธ์ของวงเล็บปีกกา
3. ตัวแปรหรือสัญลักษณ์ตัวอักษรที่อยู่ในแต่ละเทอมของ Expression ที่เหมือนกัน จะถือว่าเป็นตัวแปรตัวเดียวกัน โดยจะคิดให้เหลือเพียงตัวแปร 1 ตัวเท่านั้น
4. สำหรับตัวกระทำ “NOT” จะกระทำก่อนหรือหลัง “AND” และ “OR” นั้น ขึ้นอยู่กับ ความยาวของ Bar ว่าครอบคลุมเพียงตัวแปรเดียวหรือทั้งหมด เช่น
A × B หรือ A × B¢ ให้ NOT B ก่อน แล้วจึง AND กับ A
ฟังค์ชัน (Function) หมายถึง สมการที่แสดงให้ทราบถึงผลการถูกกระทำกันของเทอมและนิพจน์ต่าง ๆ ปกติ เรียกว่า Logic Function หรือ Boolean Function เช่น
f(X,Y,Z) = X × Y + X¢× Z
ฝั่งทางด้านซ้ายมือ เป็นผลลัพธ์ที่ได้ เรียกว่า Output or Logic output
ฝั่งทางด้านขวามือ เป็นกลุ่มของตัวแปรที่ประกอบด้วย Term หรือ Expression เป็นตัวถูกกระทำ เรียกว่า Input หรือ Logic input
ตารางความจริง (Truth Table) หมายถึง ตารางที่แสดงผลของค่าความจริงของนิพจน์หรือ Logic output เมื่อค่าตัวแปรต่าง ๆใน Function มีค่าเปลี่ยนแปลงไปต่าง ๆ กัน เช่น
|
B
|
A×B
|
A
|
B
|
A+B
|
A
|
A
| ||
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
| ||
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
| ||
1
|
0
|
0
|
1
|
0
|
1
| ||||
1
|
1
|
1
|
1
|
1
|
1
|
Y
|
Z
|
X×Y
|
X
|
X × Z
|
F
| |
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
สูตรและกฎของพีชคณิตบูลีน
ทฤษฎีบทที่ 1 กฎการสลับที่ (Commutative law)
a) A + B = B + A
b) A × B = B ×A
ทฤษฎีบทที่ 2 กฎการจัดหมู่ (Associative law)
a) (A + B) + C = A + (B + C)
b) (A × B) × C = A × (B × C)
ทฤษฎีบทที่ 3 กฎการกระจาย (Distributive law)
a) A × (B + C) = A × B + A × C
b) A + (B × C) = (A + B) × (A + C)
ทฤษฎีบทที่ 4 กฎเอกลักษณ์ (Identity law)
a) A + A = A
b) A × A = A
ทฤษฎีบทที่ 5 กฎการนิเสธ (Negation law)
ทฤษฎีบทที่ 6 กฎการลดรูปเยิ่นเย้อหรือการดูดกลืน (Redundance law or Absorption law)
a) A + A×B = A
ทฤษฎีบทที่ 7 คุณสมบัติเกี่ยวกับการกระทำระหว่างตัวคงที่กับตัวแปรใด ๆ
a) 0 + A = A
ทฤษฎีบทที่ 8
a) A + A = 1
ทฤษฎีบทที่ 9
ทฤษฎีบทที่ 10 ทฤษฎีของเดอมอร์แกน (De Morgan’s Theorem)
ทฤษฎีบทเพิ่มเติม คุณสมบัติการกลืนหายหรือความสอดคล้องกัน (Consensus law)
a) A ×B + A × C + B × C = A × B + A × C
การพิสูจน์ทฤษฎีบทของพีชคณิตบูลีนนั้น เราสามารถพิสูจน์ได้หลายวิธี แต่มีวิธีหนึ่งที่ง่ายและเห็นได้ชัดเจนที่สุด คือการใช้ตารางความจริงในการพิสูจน์
ตัวอย่างที่ 4.2 จงพิสูจน์ว่าทฤษฎีของเดอมอร์แกนเป็นความจริง
พิสูจน์ โดยใช้ตารางความจริง
B
|
A + B
|
A + B
|
A
|
B
|
A× B
| |
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
B
|
A × B
|
A × B
|
A
|
B
|
A+ B
| |
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
การพิสูจน์ทฤษฎีบทของพีชคณิตบูลีนอีกวิธีหนึ่งนั้น เป็นการนำเอาทฤษฎีบทอื่น ๆ ที่เรายอมรับแล้วมาใช้ในการพิสูจน์
ตัวอย่างที่ 4.3 จงพิสูจน์ว่าคุณสมบัติการกลืนหายเป็นความจริง
a) A ×B + A × C + B × C = A × B + A × C
พิสูจน์ โดยใช้ทฤษฎีบทอื่น ๆ
= A × B + A × C + B × C × (A + A) (บท 8a)
= A × B + A × C + A ×B × C + A ×B × C (บท 3a)
= A×B×(1 + C) + A ×C × (1 + B) (บท 3a)
การใช้ทฤษฎี Boolean ลดทอน Switching Function
พีชคณิตบูลีนจะช่วยให้เราลดรูป Switching Function ให้สั้นลง ซึ่งเป็นผลให้ได้ Logic Diagram ที่เล็ก ใช้เกทน้อย ทำให้เกิดความประหยัด สะดวกและง่ายในการประกอบวงจร และข้อสำคัญอีกประการหนึ่งคือจะลดเวลาหน่วง (Delay Time) ให้น้อยลง
ตัวอย่างที่ 4.4 จงลดรูป Switching Function ต่อไปนี้ ให้สั้นที่สุด
ง) f(A,B,C,D) = A×B + C×D + (A×B)×(C+D)
วิธีทำ
= C× (1 + B)
= C
ข) Y = A×B + A×(B+C) + B×(B+C)
= A×B + A×B + A×C + B×B+ B×C
= A×B + A×C + B + B×C
= A×B + A×C + B×(1 + C)
= A×B + A×C + B×1
= A×B + A×C + B
= B×(A + 1) + A×C
= B× 1 + A×C
= (X+X) + Y×Z + X ×Y
= X + Y×Z + X ×Y
= X + Y + Y×Z
= X + Y×(1+ Z)
= X + Y
ง) f(A,B,C,D) = A×B + C×D + (A×B)×(C+D)
= A×B + C×D + A×B×C + A×B×D
= A×B× (1+ C+D)+ C×D
= A×B + C×D