พีชคณิตบูลีน: ประวัติศาสตร์ทฤษฎีบทและสมมุติฐานตัวอย่าง - เลข - 2025

พีชคณิตแบบบูลหรือพีชคณิตแบบบูลเป็นสัญกรณ์พีชคณิตใช้สำหรับการรักษาของตัวแปรไบนารี ครอบคลุมการศึกษาตัวแปรใด ๆ ที่มีผลลัพธ์ที่เป็นไปได้เพียง 2 อย่างคือเสริมและไม่ซ้ำกัน ตัวอย่างเช่นตัวแปรที่มีความเป็นไปได้เพียงอย่างเดียวคือจริงหรือเท็จถูกต้องหรือไม่ถูกต้องเปิดหรือปิดเป็นพื้นฐานของการศึกษาพีชคณิตบูลีน

พีชคณิตบูลีนถือเป็นพื้นฐานของอุปกรณ์อิเล็กทรอนิกส์ดิจิทัลซึ่งทำให้ปัจจุบันมีอยู่มาก มันถูกควบคุมโดยแนวคิดของลอจิกเกตซึ่งการดำเนินการที่เป็นที่รู้จักในพีชคณิตแบบดั้งเดิมจะได้รับผลกระทบอย่างเห็นได้ชัด

ที่มา: pexels.com

ประวัติศาสตร์

พีชคณิตบูลีนถูกนำมาใช้ในปี 1854 โดยนักคณิตศาสตร์ชาวอังกฤษ George Boole (1815 - 1864) ซึ่งเป็นนักวิชาการที่เรียนรู้ด้วยตนเองในยุคนั้น ความกังวลของเขาเกิดจากข้อพิพาทระหว่างออกัสตัสเดอมอร์แกนและวิลเลียมแฮมิลตันเกี่ยวกับพารามิเตอร์ที่กำหนดระบบตรรกะนี้

จอร์จบูลแย้งว่าคำจำกัดความของค่าตัวเลข 0 และ 1 สอดคล้องกันในด้านตรรกะกับการตีความ Nothing และ Universe ตามลำดับ

ความตั้งใจของ George Boole คือการกำหนดผ่านคุณสมบัติของพีชคณิตนิพจน์ของตรรกะเชิงประพจน์ที่จำเป็นในการจัดการกับตัวแปรประเภทไบนารี

ในปีพ. ศ. 2397 ส่วนที่สำคัญที่สุดของพีชคณิตบูลีนได้รับการตีพิมพ์ในหนังสือ "การตรวจสอบกฎแห่งความคิดซึ่งใช้ทฤษฎีทางคณิตศาสตร์ของตรรกะและความน่าจะเป็น"

ชื่อที่น่าสงสัยนี้จะสรุปในภายหลังว่า "The law of thought" ("กฎแห่งความคิด") ชื่อนี้มีชื่อเสียงขึ้นมาจากความสนใจที่ได้รับจากชุมชนคณิตศาสตร์ในเวลานั้น

ในปีพ. ศ. 2491 Claude Shannon ได้นำไปใช้ในการออกแบบวงจรสวิตชิ่งไฟฟ้าแบบ bistable สิ่งนี้ทำหน้าที่เป็นข้อมูลเบื้องต้นเกี่ยวกับการประยุกต์ใช้พีชคณิตบูลีนภายในโครงร่างอิเล็กทรอนิกส์ - ดิจิทัลทั้งหมด

โครงสร้าง

ค่าพื้นฐานในพีชคณิตประเภทนี้คือ 0 และ 1 ซึ่งสอดคล้องกับ FALSE และ TRUE ตามลำดับ การดำเนินการพื้นฐานในพีชคณิตบูลีนคือ 3:

- และการดำเนินการหรือการเชื่อมต่อ แทนด้วยจุด (.) คำพ้องความหมายของผลิตภัณฑ์

- หรือการดำเนินการหรือ disjunction แทนด้วยกากบาท (+) คำพ้องความหมายของผลรวม

- ไม่ดำเนินการหรือปฏิเสธ แทนด้วยคำนำหน้า NOT (ไม่ใช่ A) เรียกอีกอย่างว่าส่วนเติมเต็ม

ถ้าในชุด A 2 กฎขององค์ประกอบภายในถูกกำหนดให้แสดงเป็นผลคูณและผลรวม (. +) ทริปเปิล (A. +) จะกล่าวว่าเป็นพีชคณิตบูลีนก็ต่อเมื่อกล่าวว่า triple ตรงตามเงื่อนไขของการเป็นแลตทิซเท่านั้น เกี่ยวกับการจำหน่าย

ในการกำหนดตาข่ายการกระจายต้องตรงตามเงื่อนไขการแจกจ่ายระหว่างการดำเนินการที่กำหนด:

. มีการกระจายตามผลรวม+ a (b + c) = (a. b) + (a. c)

+เป็นตัวแทนจำหน่ายที่เกี่ยวกับผลิตภัณฑ์ a + (b. c) = (a + b) (a + c)

องค์ประกอบที่ประกอบเป็นเซต A ต้องเป็นไบนารีจึงมีค่าจักรวาลหรือโมฆะ

การประยุกต์ใช้งาน

สถานการณ์จำลองแอปพลิเคชันหลักคือสาขาดิจิทัลซึ่งทำหน้าที่จัดโครงสร้างวงจรที่ประกอบขึ้นเป็นการดำเนินการเชิงตรรกะที่เกี่ยวข้อง ศิลปะของความเรียบง่ายของวงจรที่สนับสนุนกระบวนการปรับให้เหมาะสมเป็นผลมาจากการประยุกต์ใช้พีชคณิตบูลีนที่ถูกต้อง

จากการสร้างแผงไฟฟ้าอย่างละเอียดการส่งผ่านข้อมูลไปจนถึงการเขียนโปรแกรมในภาษาต่างๆเรามักจะพบพีชคณิตบูลีนในแอปพลิเคชันดิจิทัลทุกประเภท

ตัวแปรบูลีนเป็นเรื่องปกติมากในโครงสร้างของการเขียนโปรแกรม ขึ้นอยู่กับภาษาโปรแกรมที่ใช้จะมีการดำเนินการเชิงโครงสร้างในโค้ดที่ใช้ตัวแปรเหล่านี้ เงื่อนไขและอาร์กิวเมนต์ของแต่ละภาษายอมรับตัวแปรบูลีนเพื่อกำหนดกระบวนการ

สมมุติฐาน

มีทฤษฎีบทที่ควบคุมกฎเชิงตรรกะเชิงโครงสร้างของพีชคณิตบูลีน ในทำนองเดียวกันมีสมมุติฐานเพื่อให้ทราบผลลัพธ์ที่เป็นไปได้ในชุดค่าผสมของตัวแปรไบนารีที่แตกต่างกันขึ้นอยู่กับการดำเนินการ

ผลรวม (+)

ตัวดำเนินการORที่มีองค์ประกอบเชิงตรรกะคือยูเนี่ยน (U) ถูกกำหนดสำหรับตัวแปรไบนารีดังนี้:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

สินค้า (.)

ตัวดำเนินการANDที่มีองค์ประกอบเชิงตรรกะคือจุดตัด (∩) ถูกกำหนดสำหรับตัวแปรไบนารีดังนี้:

0 0 = 0

0 1 = 0

หนึ่ง. 0 = 0

หนึ่ง. 1 = 1

ตรงข้าม (ไม่ใช่)

ตัวดำเนินการNOTที่มีองค์ประกอบเชิงตรรกะคือส่วนเติมเต็ม (X) 'ถูกกำหนดสำหรับตัวแปรไบนารีดังนี้:

ไม่ใช่ 0 = 1

ไม่ใช่ 1 = 0

หลายสมมุติฐานแตกต่างจากคู่ของพวกเขาในพีชคณิตทั่วไป เนื่องจากโดเมนของตัวแปร ตัวอย่างเช่นการเพิ่มองค์ประกอบจักรวาลในพีชคณิตบูลีน (1 + 1) ไม่สามารถให้ผลลัพธ์แบบเดิมของ 2 ได้เนื่องจากไม่ได้อยู่ในองค์ประกอบของชุดไบนารี

ทฤษฎีบท

กฎของศูนย์และความสามัคคี

การดำเนินการง่ายๆใด ๆ ที่เกี่ยวข้องกับองค์ประกอบที่มีตัวแปรไบนารีถูกกำหนด:

0 + A = ก

1 + A = 1

0 A = 0

หนึ่ง. ก = ก

อำนาจที่เท่าเทียมกันหรือ idempotency

การดำเนินการระหว่างตัวแปรที่เท่ากันถูกกำหนดเป็น:

ก + ก = ก

ถึง . ก = ก

complementation

การดำเนินการใด ๆ ระหว่างตัวแปรและส่วนเสริมถูกกำหนดเป็น:

A + ไม่ใช่ A = 1

ถึง . ไม่ใช่ A = 0

การรุกรานหรือการปฏิเสธสองครั้ง

การปฏิเสธซ้อนใด ๆ จะถือเป็นตัวแปรตามธรรมชาติ

NOT (ไม่ใช่ A) = A

สับเปลี่ยน

A + B = B + A; การสับเปลี่ยนของผลรวม

ถึง . B = ข. ถึง ; การสับเปลี่ยนของผลิตภัณฑ์

ที่สมาคม

A + (B + C) = (A + B) + C = A + B + C; ความสัมพันธ์ของผลรวม

ถึง . (ข. C) = (ก. ข). C = A. บี ค; การเชื่อมโยงผลิตภัณฑ์

เกี่ยวกับการจำหน่าย

A + (B.C) = (A + B) (A + C); การกระจายของผลรวมที่เกี่ยวกับผลิตภัณฑ์

ถึง . (B + C) = (ก. B) + (A + C); การกระจายของผลิตภัณฑ์เทียบกับผลรวม

กฎของการดูดซึม

มีกฎหมายการดูดกลืนหลายฉบับในการอ้างอิงหลายฉบับบางส่วนที่รู้จักกันดี ได้แก่

ถึง . (A + B) = ก

ถึง . (ไม่ใช่ A + B) = A. B

NOT A (A + B) = ไม่ใช่ A B

(A + B) (A + NOT B) = ก

ก + ก. B = A

A + ไม่ใช่ A. B = A + B

ไม่ใช่ A + A. B = ไม่ใช่ A + B

ถึง . B + A. ไม่ใช่ B = A

ทฤษฎีบทของมอร์แกน

เป็นกฎการเปลี่ยนแปลงซึ่งจัดการคู่ของตัวแปรที่โต้ตอบระหว่างการดำเนินการที่กำหนดไว้ของพีชคณิตบูลีน (+.)

NOT (A. B) = ไม่ใช่ A + NOT B

NOT (A + B) = ไม่ใช่ A ไม่ใช่ B

A + B = ไม่ (ไม่ใช่ A + ไม่ใช่ B)

ถึง . B = ไม่ (ไม่ใช่ A. ไม่ใช่ B)

ความเป็นคู่

สมมุติฐานและทฤษฎีบททั้งหมดมีคณะแห่งความเป็นคู่ นี่หมายความว่าโดยการแลกเปลี่ยนตัวแปรและการดำเนินการข้อเสนอที่เป็นผลลัพธ์จะได้รับการตรวจสอบ นั่นคือเมื่อแลกเปลี่ยน 0 เป็น 1 และ AND สำหรับ OR หรือในทางกลับกัน นิพจน์ถูกสร้างขึ้นซึ่งจะใช้ได้อย่างสมบูรณ์

ตัวอย่างเช่นถ้าสมมุติฐานถูกนำมาใช้

หนึ่ง. 0 = 0

และใช้ความเป็นคู่

0 + 1 = 1

ได้รับสมมุติฐานที่ถูกต้องอีกประการหนึ่ง

แผนที่ Karnaugh

แผนที่ Karnaugh เป็นแผนภาพที่ใช้ในพีชคณิตบูลีนเพื่อลดความซับซ้อนของฟังก์ชันลอจิคัล ประกอบด้วยการจัดเรียงแบบสองมิติที่คล้ายกับตารางความจริงของตรรกะเชิงประพจน์ ข้อมูลจากตารางความจริงสามารถจับได้โดยตรงบนแผนที่ Karnaugh

แผนที่ Karnaugh สามารถรองรับกระบวนการได้ถึง 6 ตัวแปร สำหรับฟังก์ชันที่มีตัวแปรจำนวนมากขึ้นแนะนำให้ใช้ซอฟต์แวร์เพื่อลดความซับซ้อนของกระบวนการ

เสนอในปี 2496 โดย Maurice Karnaugh ได้รับการจัดตั้งขึ้นเป็นเครื่องมือคงที่ในสาขาพีชคณิตบูลีนเนื่องจากการใช้งานได้ประสานศักยภาพของมนุษย์กับความต้องการที่จะทำให้นิพจน์บูลีนง่ายขึ้นซึ่งเป็นประเด็นสำคัญในความลื่นไหลของกระบวนการดิจิทัล

ตัวอย่าง

พีชคณิตบูลีนใช้เพื่อลดลอจิกเกตในวงจรโดยลำดับความสำคัญคือการนำความซับซ้อนหรือระดับของวงจรไปสู่นิพจน์ที่ต่ำที่สุดเท่าที่จะเป็นไปได้ เนื่องจากความล่าช้าในการคำนวณที่แต่ละเกตรองรับ

ในตัวอย่างต่อไปนี้เราจะสังเกตความเรียบง่ายของนิพจน์เชิงตรรกะเป็นนิพจน์ขั้นต่ำโดยใช้ทฤษฎีบทและสมมุติฐานของพีชคณิตบูลีน

ไม่ (AB + A + B) ไม่ (A + ไม่ใช่ B)

ไม่. ไม่ (A + ไม่ใช่ B); การแยกตัวประกอบ A ด้วยปัจจัยร่วม

ไม่. ไม่ (A + ไม่ใช่ B); ตามทฤษฎีบท A + 1 = 1

ไม่ (A + B) ไม่ (A + ไม่ใช่ B); โดย theorem A. 1 = ก

(ไม่ใช่ A. ไม่ใช่ B) ;

ตามทฤษฎีบทของมอร์แกน NOT (A + B) = ไม่ใช่ A ไม่ใช่ B

(ไม่ใช่ A. ไม่ใช่ B) (ไม่ใช่ก. B); โดยทฤษฎีบทการปฏิเสธสองครั้ง NOT (NOT A) = A

ไม่ใช่ A. ไม่ใช่บี ไม่ใช่ A. B; การจัดกลุ่มพีชคณิต.

ไม่ใช่ A. ไม่ใช่ A. ไม่ใช่บี B; ความแปรผันของผลิตภัณฑ์ A. B = ข. ถึง

ไม่ใช่ A. ไม่ใช่บี B; โดยทฤษฎีบทก. ก = ก

ไม่ใช่ A. 0; โดยทฤษฎีบทก. ไม่ใช่ A = 0

0; โดยทฤษฎีบทก. 0 = 0

ถึง . บี C + ไม่ใช่ A + A ไม่ใช่บี ค

ถึง . ค. (B + NOT B) + ไม่ใช่ A; การแยกตัวประกอบ (A. C) ด้วยปัจจัยร่วม.

ถึง . ค. (1) + ไม่ใช่; ตามทฤษฎีบท A + NOT A = 1

ถึง . C + ไม่ใช่ A; ตามกฎของทฤษฎีบทศูนย์และเอกภาพ 1. ก = ก

ไม่ใช่ A + C ; ตามกฎหมายของ Morgan A + NOT A. B = A + B

สำหรับการแก้ปัญหานี้ต้องขยายกฎหมายของมอร์แกนเพื่อกำหนด:

ไม่ (ไม่ใช่ A) C + NOT A = ไม่ใช่ A + C

เพราะ NOT (ไม่ใช่ A) = A โดยการรุกราน

ลดความซับซ้อนของฟังก์ชันลอจิก

ไม่ใช่ A. ไม่ใช่บี ไม่ C + ไม่ใช่ A ไม่ใช่บี C + ไม่ใช่ A. ไม่ C ลงไปที่นิพจน์ต่ำสุด

ไม่ใช่ A. ไม่ใช่บี (ไม่ใช่ C + C) + ไม่ใช่ A ไม่ C; แฟคตอริ่ง (ไม่ใช่ A ไม่ใช่ B) ด้วยปัจจัยร่วม

ไม่ใช่ A. ไม่ใช่บี (1) + ไม่ใช่ A. ไม่ C; ตามทฤษฎีบท A + NOT A = 1

(ไม่ใช่ A. ไม่ใช่ B) + (ไม่ใช่ A. ไม่ใช่ C); ตามกฎของทฤษฎีบทศูนย์และเอกภาพ 1. ก = ก

ไม่ใช่ A (ไม่ใช่ B + ไม่ใช่ C); การแยกตัวประกอบไม่ใช่ A ด้วยปัจจัยทั่วไป

ไม่ใช่ A. ไม่ (B.C); ตามกฎหมายของมอร์แกน NOT (A. B) = NOT A + NOT B

ไม่ใช่ตามกฎหมายของมอร์แกน NOT (A. B) = NOT A + NOT B

ตัวเลือก 4 ตัวใด ๆ ที่เป็นตัวหนาแสดงถึงวิธีการแก้ปัญหาที่เป็นไปได้ในการลดระดับของวงจร

ลดความซับซ้อนของฟังก์ชันลอจิคัลเป็นรูปแบบที่ง่ายที่สุด

(ก. NOT B. C + A. NOT B.B. D + NOT A. NOT B) ค

(ก. NOT B. C + A 0. D + NOT A. NOT B). ค; โดยทฤษฎีบทก. ไม่ใช่ A = 0

(ก. ไม่ใช่ข. C + 0 + ไม่ใช่ก. ไม่ใช่ข). ค; โดยทฤษฎีบทก. 0 = 0

(ก. NOT B. C + NOT A. NOT B). ค; ตามทฤษฎีบท A + 0 = A

ถึง . ไม่ใช่บี ค. C + ไม่ใช่ A. ไม่ใช่บี ค; โดยการกระจายของผลิตภัณฑ์เทียบกับผลรวม

ถึง . ไม่ใช่บี C + ไม่ใช่ A. ไม่ใช่บี ค; โดยทฤษฎีบทก. ก = ก

ไม่ใช่บี C (A + ไม่ใช่ A) ; แฟคตอริ่ง (ไม่ใช่บีซี) ด้วยปัจจัยร่วม

ไม่ใช่บี ค (1); ตามทฤษฎีบท A + NOT A = 1

ไม่ใช่บี ค; ตามกฎของทฤษฎีบทศูนย์และเอกภาพ 1. ก = ก

อ้างอิง

1. พีชคณิตบูลีนและแอพพลิเคชั่น J. Eldon Whitesitt Continental Publishing Company, 1980.
2. คณิตศาสตร์และวิศวกรรมศาสตร์สาขาวิทยาการคอมพิวเตอร์. คริสโตเฟอร์เจ. แวนวิค สถาบันวิทยาศาสตร์คอมพิวเตอร์และเทคโนโลยี. สำนักงานมาตรฐานแห่งชาติ. วอชิงตัน ดี.ซี. 20234
3. คณิตศาสตร์สำหรับวิทยาการคอมพิวเตอร์. Eric Lehman Google Inc.
   F Thomson Leighton Department of Mathematics and the Computer Science and AI Laboratory, Massachussetts Institute of Technology; Akamai Technologies
4. องค์ประกอบของการวิเคราะห์บทคัดย่อ Mícheál O'Searcoid PhD. ภาควิชาคณิตศาสตร์. University College Dublin, Beldfield, Dublind
5. รู้เบื้องต้นเกี่ยวกับลอจิกและระเบียบวิธีวิทยานิรนัย Alfred Tarski จาก New York Oxford สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ด