ตรรกศาสตร์
ตรรกศาสตร์พื้นฐาน
1.คุณสมบัติของตรรกศาสตร์พื้นฐาน 1.1ประพจน์ (Propostion) คือ ข้อความที่เป็นจริงหรือเป็นเท็จเพียงอย่างเดียวเท่านั้น ตัวอย่างที่เป็นประพจน์ P : 15 + 5 = 20 Q : วันนี้อากาศหนาว R : สัปดาห์หนึ่งมี 8 วัน S : คนทุกคนเป็นอมตะ ตัวอย่างที่ไม่เป็นประพจน์ ช่วยเปิดไฟให้หน่อย ห้ามรบกวน การแทนประพจน์จะใช้สัญลักษณ์ p, q, r … เพื่อแทนประพจน์ที่แตกต่างกัน ข้อความที่มีกริยาเพียงตัวเดียวและเป็นประพจน์ จะเรียกว่าประพจน์เบื้องต้น 1.2. การเชื่อมประพจน์ ถ้ากำหนดให้ T แทนค่าความจริงของประพจน์ที่เป็นจริง
ประพจน์ p ฺ q เรียกว่าข้อความเลือก (disjunctive statement) เป็นข้อความที่เป็นจริงถ้า p หรือ q เป็นอย่างน้อยที่สุดหนึ่งประพจน์ แต่จะไม่เป็นจริงเมื่อทั้งสองประพจน์เป็นเท็จ ตารางค่าความจริงของ p ฺ q สามารถเขียนได้ดังนี้ ประพจน์ ~p เรียกว่านิเสธ (negation) p หมายถึงไม่เป็นจริงสำหรับ p จะเป็นจริงเมื่อ p เป็นเท็จและจะเป็นเท็จเมื่อ p เป็นจริง ตารางค่าความจริงของ ~p เป็นดังนี้ ประพจน์ p ฎ q เรียกว่าประโยคเงื่อนไขหรือข้อความแจงเหตุสู่ผล (conditional statement) ประพจน์ p เรียกว่าเหตุตัวเงื่อนและ q เป็นผลสรุป ประพจน์ p ซq เรียกว่าประโยคเงื่อนไขสองทาง (biconditional statement) คือ ประพจน์ที่มีความหมายเหมือนกับ (p ฎ q) ู (q ฎ p) เนื่องจาก (p ฎ q) และ (q ฎ p) เชื่อมด้วยคำว่า “และ” ดังนั้น p ซq จะมีค่าความจริงเป็นจริงต่อเมื่อประพจน์ p และประพจน์ q มีค่าความจริงเหมือนกัน ดังตารางต่อไปนี้ จากตารางค่าความจริงของประพจน์ที่มีตัวเชื่อมทั้ง 5จะพบว่า |
||
|
ตรรกศาสตร์ของบูล
1. คุณสมบัติของตรรกศาสตร์ของบูล
ในเครื่องคอมพิวเตอร์มีการทำงานกับข้อมูลในระดับบิท ซึ่งมีค่าได้เพียง 2 ค่า คือ 0 และ 1 ดังนั้นเราจึงสามารถใช้บิทแทนข้อมูล 2 ค่าทางตรรกได้ โดยให้ 0 แทนค่าที่เป็น เท็จ และ 1 แทนค่าที่เป็นจริง ตัวแปรใดๆที่มีค่าได้เพียงค่าใดค่าหนึ่งระหว่าง จริง หรือ เท็จ เรียกว่า boolean variable และเราสามารถแทนค่าของตัวแปรเหล่านั้นโดยใช้บิทในคอมพิวเตอร์ได้
การกระทำระดับบิทในคอมพิวเตอร์เปรียบเทียบได้กับการกระทำทางตรรก โดยอาศัยตัวเชื่อม ฺ , ู , และ ล กระทำกับบิท ใช้สัญลักษณ์ OR, AND, XOR ตามลำดับ จะได้ผลลัพธ์ดังแสดงในตารางค่าความจริงต่อไปนี้
ข้อตกลงมูลฐานของบูลีน (Boolean Postulate)
ทฤษฎีพื้นฐานของพีชคณิตบูลีน
2. การปฏิบัติการตรรกศาสตร์ของบูล
การพิสูจน์ทฤษฎี
พิสูจน์กฎของ นิจพล (Idempotent)
จงพิสูจน์ว่า
พิสูจน์
จงพิสูจน์ว่า
พิสูจน์
จงพิสูจน์ว่า
พิสูจน์
3. การนำไปใช้กับวงจรไฟฟ้า
ในชีวิตประจำวันจะพบการทำงานของสวิตซ์ไฟ ซึ่งมี 2 สถานะคือ เปิด และ ปิด สถานะเปิดของสวิตซ์มีค่าเป็น 0 สถานะปิดมีค่าเป็น 1 (สวิตซ์ปิด หมายถึง วงจรไฟฟ้าปิด นั่นก็คือ มีกระแสไฟฟ้าไหลผ่านได้ สวิตซ์เปิด หมายถึง สถานะทั้งวงจรเปิดทำให้กระแสไฟฟ้าไม่สามารถไหลผ่านได้) ดังนั้นถ้านำสวิตซ์หลายๆตัวมาต่อรวมกัน จะสามารถต่อได้ในรูปแบบอนุกรมหรือขนานก็ได้ ซึ่งการต่อกันในแต่ละรูปแบบของสวิตซ์ จะสามารถแทนการกระทำต่างๆของพีชคณิตบูลีน ได้ดังนี้
1. การกระทำแบบ AND ถ้า A และ B เป็นตัวแปร 2 ตัว การกระทำแบบ AND ของ Aและ B แทนด้วย AทB สามารถใช้สวิตซ์มาต่อกันแบบอนุกรม
ถ้า A และ B เป็นสวิตซ์ที่ต่อกันแบบอนุกรม L เป็นหลอดไฟฟ้า จะได้ว่า ถ้า A = 1 และ
B = 1 จะได้ L = 1
2. การกระทำแบบ OR ถ้า A และ B เป็นสวิตซ์ไฟ 2 ตัว การกระทำแบบ OR แทนด้วย A+B สามารถใช้สวิตซ์มาต่อกันแบบขนาน
A และ B เป็นสวิตซ์ไฟที่ต่อกันแบบขนาน L เป็นหลอดไฟ จะได้ว่า ถ้า A = 1 และ
B = 1 จะได้ L = 1 และถ้า A = 0 และ B = 0 จะได้ L = 0 จะสามารถเขียนผลเป็นตารางได้ดังนี้
3. การกระทำแบบ NOT ถ้า A เป็นสวิตซ์ไฟ 1 ตัว การกระทำแบบ NOT แทนด้วย สามารถใช้การต่อสวิตซ์ A ให้ขนานกับหลอดไฟ ถ้าเปิดสวิตซ์จะได้ว่าหลอดไฟจะติด แต่ถ้าปิดสวิตซ์ จะได้ว่าไฟดับ นั่นคือ
ถ้า A = 0 จะได้ = 1 หรือ L = 1
ถ้า A = 1 จะได้ = 0 หรือ L = 0
จะสามารถเขียนผลของการต่อสวิตซ์แบบ NOT ได้ดังตารางต่อไปนี้
4. การนำสวิตซ์มาต่อกันแบบอนุกรม แล้วมาต่อขนานกับหลอดไฟ
จะพบว่า ถ้า A หรือ B เป็น 0 จะได้ L = 1
ถ้า A หรือ B เป็น 1 จะได้ L = 0
5. การนำสวิตซ์มาต่อกันแบบขนานแล้วมาต่อขนานกับหลอดไฟ
จะพบว่า ถ้า A หรือ B เป็น 1 จะได้ L = 0
ถ้า A หรือ B เป็น 0 จะได้ L = 1
4. การนำไปใช้กับวงจรอิเล็กทรอนิกส์
พีชคณิตบูลีนถูกใช้เป็นแบบของการทำวงจรอิเล็กทรอนิกส์ ข้อมูลเข้าออกแต่ละตัวสามารถถือได้ว่าเป็นสมาชิกของเซต {0,1}
วงจรพื้นฐานที่นำมาใช้งานเรียกว่า เกต (gate) เกตแต่ละชนิดจะแทนการดำเนินการบูลีน
รูปแบบต่างๆ โดยการใช้เกต จะทำให้สามารถใช้กฎของพีชคณิตบูลีนมาออกแบบวงจรที่ทำงานได้หลายรูปแบบ วงจรที่จะศึกษาต่อไปนี้เป็นวงจรที่ไม่มีหน่วยความจำ ข้อมูลที่ได้จะขึ้นกับข้อมูลที่เข้าไปเท่านั้น
เกต AND
ข้อมูลเข้าจะเป็นค่าของตัวแปรบูลีนตั้งแต่สองตัวขึ้นไป ข้อมูลออกจะเขียนแทนได้ด้วย
x ู y และมีค่าเป็นผลคูณ (product) ของค่าที่ใส่เข้าไปหรือเขียนได้เป็น xy
เกต OR
ข้อมูลเข้าจะเป็นค่าของตัวแปรบูลีนตั้งแต่สองตัวขึ้นไป ข้อมูลออกจะเขียนแทนได้ด้วย
x ฺ y และมีค่าเป็นผลบวก (sum) ของค่าที่ใส่เข้าไปหรือเขียนได้เป็น x+y
เกต NOT
ข้อมูลเข้าจะเป็นค่าของตัวแปรบูลีนหนึ่งตัว และได้ข้อมูลออกเป็นคอมพลีเมนต์ (complement) ของค่าที่เข้าไป
การรวมวงจร AND, OR, NOT
วงจรเชิงผสมสามารถสร้างได้โดยการรวมเกต AND, Or และ NOT เมื่อมีการรวมวงจรกันบางเกตอาจมีการใช้ข้อมูลร่วมกัน และข้อมูลออกจากเกตอาจถูกใช้เป็นข้อมูลเข้าของตัวอื่น
ตัวอย่าง จงสร้างวงจรที่สามารถให้ข้อมูลออกมาเป็น (x+y)
วิธีทำ ใช้หลักการของเกตแต่ละรูปแบบจะสามารถเขียนวงจรเชิงผสมได้ดังนี้
ทั้งนี้ในเรื่องวงจรเชิงผสมยังมีวงจรอีกรูปแบบหนึ่งที่สามารถใช้เพื่อคำนวณหรือการกระทำการเพียงหนึ่งอย่างของ x1 และ x2 วงจรนี้คือ exclusive OR (XOR) เขียนแทนด้วย x1 ล x2