วงจรดิจิทัล - พีชคณิตบูลีน

Boolean Algebraคือพีชคณิตซึ่งเกี่ยวข้องกับเลขฐานสองและตัวแปรไบนารี ดังนั้นจึงเรียกอีกอย่างว่า Binary Algebra หรือ Logical Algebra นักคณิตศาสตร์ชื่อ George Boole ได้พัฒนาพีชคณิตนี้ในปี 1854 ตัวแปรที่ใช้ในพีชคณิตนี้เรียกอีกอย่างว่าตัวแปรบูลีน

ช่วงของแรงดันไฟฟ้าที่สอดคล้องกับลอจิก 'สูง' จะแสดงด้วย '1' และช่วงของแรงดันไฟฟ้าที่สอดคล้องกับตรรกะ 'ต่ำ' จะแสดงด้วย '0'

สมมุติฐานและกฎพื้นฐานของพีชคณิตบูลีน

ในส่วนนี้ให้เราพูดคุยเกี่ยวกับสมมติฐานบูลีนและกฎพื้นฐานที่ใช้ในพีชคณิตบูลีน สิ่งเหล่านี้มีประโยชน์ในการลดฟังก์ชันบูลีน

สมมติฐานบูลีน

พิจารณาเลขฐานสอง 0 และ 1 ตัวแปรบูลีน (x) และส่วนเติมเต็ม (x ') ตัวแปรบูลีนหรือส่วนเติมเต็มเรียกว่าliteral. สี่ที่เป็นไปได้logical OR การดำเนินการระหว่างตัวอักษรและเลขฐานสองเหล่านี้แสดงไว้ด้านล่าง

x + 0 = x

x + 1 = 1

x + x = x

x + x '= 1

ในทำนองเดียวกันสี่เป็นไปได้ logical AND การดำเนินการระหว่างตัวอักษรและเลขฐานสองดังแสดงด้านล่าง

x.1 = x

x.0 = 0

xx = x

x.x '= 0

นี่คือสมมติฐานแบบบูลีนง่ายๆ เราสามารถตรวจสอบสมมุติฐานเหล่านี้ได้อย่างง่ายดายโดยแทนที่ตัวแปรบูลีนด้วย '0' หรือ '1'

Note- ส่วนเติมเต็มของตัวแปรบูลีนใด ๆ จะเท่ากับตัวแปรนั้นเอง กล่าวคือ (x ')' = x.

กฎพื้นฐานของพีชคณิตบูลีน

ต่อไปนี้เป็นกฎพื้นฐานสามประการของพีชคณิตบูลีน

กฎหมายสับเปลี่ยน
กฎหมายที่เกี่ยวข้อง
กฎหมายการจัดจำหน่าย

กฎหมายสับเปลี่ยน

หากการดำเนินการทางตรรกะของตัวแปรบูลีนสองตัวให้ผลลัพธ์เดียวกันโดยไม่คำนึงถึงลำดับของตัวแปรทั้งสองนั้นการดำเนินการทางตรรกะนั้นจะถูกกล่าวว่าเป็น Commutative. การดำเนินการตรรกะ OR & ตรรกะ AND ของสองตัวแปรบูลีน x & y แสดงไว้ด้านล่าง

x + y = y + x

xy = yx

สัญลักษณ์ '+' แสดงถึงการดำเนินการหรือตรรกะ ในทำนองเดียวกันสัญลักษณ์ "." บ่งชี้การดำเนินการเชิงตรรกะ AND และเป็นทางเลือกในการแสดง กฎการสับเปลี่ยนเป็นไปตามการดำเนินการทางตรรกะหรือและตรรกะ AND

กฎหมายที่เกี่ยวข้อง

หากการดำเนินการทางตรรกะของตัวแปรบูลีนสองตัวใด ๆ ถูกดำเนินการก่อนจากนั้นการดำเนินการเดียวกันจะดำเนินการกับตัวแปรที่เหลือจะให้ผลลัพธ์เหมือนกันดังนั้นการดำเนินการเชิงตรรกะนั้นจะถูกกล่าวว่าเป็น Associative. การดำเนินการตรรกะ OR & ตรรกะ AND ของตัวแปรบูลีนสามตัว x, y & z แสดงอยู่ด้านล่าง

x + (y + z) = (x + y) + z

x. (yz) = (xy) .z

กฎการเชื่อมโยงเป็นไปตามสำหรับการดำเนินการทางตรรกะหรือและตรรกะ AND

กฎหมายการจัดจำหน่าย

หากการดำเนินการทางตรรกะใด ๆ สามารถกระจายไปยังเงื่อนไขทั้งหมดที่มีอยู่ในฟังก์ชันบูลีนการดำเนินการเชิงตรรกะนั้นจะถูกกล่าวว่าเป็น Distributive. การกระจายของการดำเนินการเชิงตรรกะ OR & ตรรกะ AND ของตัวแปรบูลีนสามตัว x, y & z แสดงอยู่ด้านล่าง

x. (y + z) = xy + xz

x + (yz) = (x + y). (x + z)

กฎหมายการกระจายเป็นไปตามการดำเนินการทางตรรกะหรือตรรกะและตรรกะ AND

นี่คือกฎพื้นฐานของพีชคณิตบูลีน เราสามารถตรวจสอบกฎหมายเหล่านี้ได้อย่างง่ายดายโดยการแทนที่ตัวแปรบูลีนด้วย '0' หรือ '1'

ทฤษฎีพีชคณิตบูลีน

สองทฤษฎีต่อไปนี้ใช้ในพีชคณิตบูลีน

ทฤษฎีบทความเป็นคู่
ทฤษฎีบทของ DeMorgan

ทฤษฎีบทความเป็นคู่

ทฤษฎีบทนี้ระบุว่า dualของฟังก์ชันบูลีนได้มาจากการแลกเปลี่ยนตัวดำเนินการตรรกะ AND กับตัวดำเนินการตรรกะ OR และศูนย์กับตัวดำเนินการ สำหรับทุกฟังก์ชันบูลีนจะมีฟังก์ชัน Dual ที่สอดคล้องกัน

ให้เราสร้างสมการบูลีน (ความสัมพันธ์) ที่เรากล่าวถึงในส่วนของสมมติฐานบูลีนและกฎหมายพื้นฐานออกเป็นสองกลุ่ม ตารางต่อไปนี้แสดงสองกลุ่มนี้

กลุ่ม 1	กลุ่ม 2
x + 0 = x	x.1 = x
x + 1 = 1	x.0 = 0
x + x = x	xx = x
x + x '= 1	x.x '= 0
x + y = y + x	xy = yx
x + (y + z) = (x + y) + z	x. (yz) = (xy) .z
x. (y + z) = xy + xz	x + (yz) = (x + y). (x + z)

ในแต่ละแถวจะมีสมการบูลีนสองสมการและเป็นคู่ซึ่งกันและกัน เราสามารถตรวจสอบสมการบูลีนทั้งหมดของ Group1 และ Group2 ได้โดยใช้ทฤษฎีบทความเป็นคู่

ทฤษฎีบทของ DeMorgan

ทฤษฎีบทนี้มีประโยชน์ในการค้นหา complement of Boolean function. มันระบุว่าส่วนเติมเต็มของตรรกะ OR ของตัวแปรบูลีนอย่างน้อยสองตัวแปรเท่ากับตรรกะ AND ของตัวแปรเสริมแต่ละตัว

ทฤษฎีบทของ DeMorgan ที่มี 2 ตัวแปรบูลีน x และ y สามารถแสดงเป็น

(x + y) '= x'.y'

ฟังก์ชันบูลีนคู่ข้างต้นคือ

(xy) '= x' + y '

ดังนั้นส่วนเติมเต็มของตรรกะ AND ของตัวแปรบูลีนสองตัวจึงเท่ากับตรรกะ OR ของตัวแปรเสริมแต่ละตัว ในทำนองเดียวกันเราสามารถใช้ทฤษฎีบทของ DeMorgan สำหรับตัวแปรบูลีนมากกว่า 2 ตัวได้เช่นกัน

การลดความซับซ้อนของฟังก์ชันบูลีน

จนถึงตอนนี้เราได้พูดถึงสมมติฐานกฎหมายพื้นฐานและทฤษฎีบทของพีชคณิตบูลีน ตอนนี้ให้เราลดความซับซ้อนของฟังก์ชันบูลีนบางอย่าง

ตัวอย่าง 1

ขอให้เรา simplify ฟังก์ชันบูลีน f = p'qr + pq'r + pqr '+ pqr

เราสามารถลดความซับซ้อนของฟังก์ชันนี้ได้สองวิธี

Method 1

ให้ฟังก์ชันบูลีน f = p'qr + pq'r + pqr '+ pqr

Step 1- ในคำที่หนึ่งและสอง r เป็นเรื่องธรรมดาและในคำที่สามและสี่ pq เป็นเรื่องปกติ ดังนั้นใช้คำศัพท์ทั่วไปโดยใช้Distributive law.

⇒ฉ = (p'q + pq ') r + pq (r' + r)

Step 2- คำศัพท์ที่อยู่ในวงเล็บแรกสามารถทำให้ง่ายต่อการดำเนินการ Ex-OR คำศัพท์ที่อยู่ในวงเล็บที่สองสามารถทำให้ง่ายขึ้นเป็น '1' โดยใช้Boolean postulate

⇒ f = (p ⊕q) r + pq (1)

Step 3- คำแรกไม่สามารถทำให้ง่ายขึ้นได้อีก แต่คำที่สองสามารถทำให้ง่ายขึ้นโดยใช้ pqBoolean postulate.

⇒ f = (p ⊕q) r + pq

ดังนั้นฟังก์ชันบูลีนแบบง่ายคือ f = (p⊕q)r + pq

Method 2

ให้ฟังก์ชันบูลีน f = p'qr + pq'r + pqr '+ pqr

Step 1 - ใช้ไฟล์ Boolean postulate, x + x = x. นั่นหมายความว่าการดำเนินการ Logical OR กับตัวแปรบูลีน 'n' ครั้งใด ๆ จะเท่ากับตัวแปรเดียวกัน ดังนั้นเราสามารถเขียน pqr เทอมสุดท้ายได้อีกสองครั้ง

⇒ฉ = p'qr + pq'r + pqr '+ pqr + pqr + pqr

Step 2 - การใช้งาน Distributive law1 ^{เซนต์}และ 4 ^THแง่ 2 ^{ครั้ง}และ 5 ^THแง่ 3 ^RDและ 6 ^THเงื่อนไข

⇒ f = qr (p '+ p) + pr (q' + q) + pq (r '+ r)

Step 3 - การใช้งาน Boolean postulate, x + x '= 1 เพื่อลดความซับซ้อนของคำศัพท์ที่มีอยู่ในแต่ละวงเล็บ

⇒ f = qr (1) + pr (1) + pq (1)

Step 4 - การใช้งาน Boolean postulate, x.1 = x เพื่อลดความซับซ้อนของคำศัพท์สามคำข้างต้น

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

ดังนั้นฟังก์ชันบูลีนแบบง่ายคือ f = pq + qr + pr.

ดังนั้นเราจึงมีฟังก์ชันบูลีนสองฟังก์ชันที่แตกต่างกันหลังจากทำให้ฟังก์ชันบูลีนที่กำหนดง่ายขึ้นในแต่ละวิธี ฟังก์ชันบูลีนสองฟังก์ชันนั้นเหมือนกัน ดังนั้นตามข้อกำหนดเราสามารถเลือกหนึ่งในสองฟังก์ชันบูลีนดังกล่าวได้