ตรรกศาสตร์พื้นฐาน
1. คุณสมบัติของตรรกศาสตร์พื้นฐาน
1.1. ประพจน์ (Propostion)
คือ ข้อความที่เป็นจริงหรือเป็นเท็จเพียงอย่างเดียวเท่านั้น
ตัวอย่างที่เป็นประพจน์
P : 15 + 5 = 20
Q : วันนี้อากาศหนาว
R : สัปดาห์หนึ่งมี 8 วัน
S : คนทุกคนเป็นอมตะ
ตัวอย่างที่ไม่เป็นประพจน์
ช่วยเปิดไฟให้หน่อย
ห้ามรบกวน
การแทนประพจน์จะใช้สัญลักษณ์ p, q, r … เพื่อแทนประพจน์ที่แตกต่างกัน
ข้อความที่มีกริยาเพียงตัวเดียวและเป็นประพจน์
จะเรียกว่าประพจน์เบื้องต้น
1.2. การเชื่อมประพจน์
โดยปกติเมื่อกล่าวถึงข้อความหรือประโยคนั้นมักจะมีกริยามากกว่าหนึ่งตัว
แสดงว่าได้นำ
ประโยคมาเชื่อมกันมากว่าหนึ่งประโยค
ดังนั้นถ้านำประพจน์มาเชื่อมกันก็จะได้ประพจน์ใหม่ซึ่งสามารถบอกได้ว่าเป็นจริงหรือเป็นเท็จ
ตัวเชื่อมประพจน์มีอยู่ 5 ตัว และตัวเชื่อมที่ใช้กันมากคือ
“และ” “หรือ” “ไม่” ที่เหลืออีกสองตัวคือ “ถ้า…แล้ว…” และ
“…ก็ต่อเมื่อ…” เมื่อนำประพจน์เชื่อมด้วยตัวเชื่อม และ ,หรือ,
ถ้า…แล้ว, …ก็ต่อเมื่อ
โดยที่ถ้า p และ q แทนประพจน์ จะเขียน
ถ้ากำหนดให้ T แทนค่าความจริงของประพจน์ที่เป็นจริง
F แทนค่าความจริงของประพจน์ที่เป็นเท็จ
และ p, q แทนประพจน์ใดๆ
ที่ยังไม่ได้ระบุข้อความหรือแทนค่าข้อความลงไป
ประพจน์ p ู q จะเรียกว่าข้อความร่วม (conjugate statement)
และจะสามารถเขียนตารางค่าความจริงของประพจน์ p ู q ได้ดังนี้
จากตารางจะพบว่า ค่าความจริงของประพจน์ p ู q
จะเป็นจริงถ้าประพจน์ทั้งสองเป็นจริงนอกนั้นจะเป็นเท็จ
ประพจน์ p ฺ q เรียกว่าข้อความเลือก
(disjunctive statement) เป็นข้อความที่เป็นจริงถ้า p หรือ q
เป็นอย่างน้อยที่สุดหนึ่งประพจน์
แต่จะไม่เป็นจริงเมื่อทั้งสองประพจน์เป็นเท็จ ตารางค่าความจริงของ p ฺ
q สามารถเขียนได้ดังนี้
ประพจน์ ~p เรียกว่านิเสธ (negation) p หมายถึงไม่เป็นจริงสำหรับ p
จะเป็นจริงเมื่อ p เป็นเท็จและจะเป็นเท็จเมื่อ p เป็นจริง
ตารางค่าความจริงของ ~p เป็นดังนี้
ประพจน์ p ฎ q เรียกว่าประโยคเงื่อนไขหรือข้อความแจงเหตุสู่ผล
(conditional statement) ประพจน์ p เรียกว่าเหตุตัวเงื่อนและ q
เป็นผลสรุป
เช่น p : นุ่นไปเที่ยวนอกบ้าน
q : คุณพ่อโทรศัพท์ตาม
ดังนั้น p ฎ q : ถ้านุ่นไปเที่ยวนอกบ้านแล้วคุณพ่อโทรศัพท์ตาม
จากการตรวจสอบเงื่อนไขนี้จะพบว่าประพจน์นี้จะเป็นเท็จกรณีเดียวคือ
นุ่นไปเที่ยวนอกบ้านแต่คุณพ่อไม่โทรศัพท์ตาม
ดังนั้นจะสามารถแสดงตารางค่าความจริงของประพจน์ p ฎ q ได้ดังนี้
ประพจน์ p ซq เรียกว่าประโยคเงื่อนไขสองทาง (biconditional statement)
คือ ประพจน์ที่มีความหมายเหมือนกับ (p ฎ q) ู (q ฎ p) เนื่องจาก (p ฎ
q) และ (q ฎ p) เชื่อมด้วยคำว่า “และ” ดังนั้น p ซq
จะมีค่าความจริงเป็นจริงต่อเมื่อประพจน์ p และประพจน์ q
มีค่าความจริงเหมือนกัน ดังตารางต่อไปนี้
จากตารางค่าความจริงของประพจน์ที่มีตัวเชื่อมทั้ง 5จะพบว่า
1. ~ p มีค่าความจริงตรงกันข้ามกับค่าความเป็นจริงของ p
2. p ู q เป็น T กรณีเดียวคือกรณีที่ทั้ง p และ q เป็น T
3. p ฺ q เป็น F กรณีเดียวคือกรณีที่ทั้ง p และ q เป็น F
4. p ฎ q เป็น F กรณีเดียวคือกรณีที่ทั้ง p เป็น T และ q เป็น F
5. p ซ q เป็น T เมื่อ p และ q มีค่าความจริงเหมือนกัน
1.3. สัจนิรันดร์ (Tautology)
หมายถึงประพจน์ผสมที่มีค่าความจริงเป็นจริงทุกกรณี
ไม่ว่าจะประกอบขึ้นจากประพจน์ย่อยที่มีค่าความจริงเป็นอย่างไร
อาทิเช่น
การทดสอบว่าประพจน์ใดเป็นสัจนิรันดร์หรือไม่ ทำได้ 2 วิธีคือ
1. ใช้ตารางค่าความจริง
เพื่อดูว่ามีค่าความจริงเป็นจริงทุกกรณีจริงหรือไม่
2. ใช้การทำ Contradiction คือการบังคับให้ประพจน์นั้นเป็นเท็จ
ถ้าสามารถทำให้ประพจน์นั้นเป็นเท็จได้สำเร็จ
แสดงว่าประพจน์นั้นไม่เป็นสัจนิรันดร์
แต่ถ้าไม่สามารถบังคับให้ประพจน์นั้นเป็นเท็จได้
ประพจน์นั้นจะเป็นสัจนิรันดร์ทันที
1.4. กฎของการแทนที่
กฎของการแทนที่เป็นกฎที่ใช้แทนที่กันได้เนื่องจากเป็นข้อความที่สมมูลกัน
มีดังต่อไปนี้
2.
การปฏิบัติการของตรรกศาสตร์พื้นฐาน
ตัวอย่าง
2.1. กำหนดให้ประพจน์ p ฎ (q ู r) มีค่าความจริงเป็น เท็จ
และ
(p ฺ q) ซ r มีค่าความจริงเป็น จริง แล้ว
พิจารณาค่าความจริงของประพจน์ต่อไปนี้
(ก) (p ซ q) ซ ~r
(ข) p ซ (q ฺ~r)
วิธีทำ เปิดหาค่าจากตารางค่าความจริง ซึ่งได้ค่าต่างๆดังนี้ p = T , q
= F , r = T
คำตอบคือ (ก) มีค่าความจริงเป็นจริง และ (ข)
มีค่าความจริงเป็นเท็จ
2.2. ประพจน์ใดที่สมมูลกับประพจน์ (p ฎ r) ู (q ฎ
r)
วิธีทำ
2.3. ถ้า p และ q เป็นประพจน์แล้ว p ฎ~(q ฎ p)
สมมูลกับประพจน์ใด
วิธีทำ
2.4. พิจารณาประพจน์ p ฎ (p ฺ q)
เป็นสัจนิรันดร์หรือไม่
วิธีทำ สมมติให้ประพจน์ดังกล่าวเป็นเท็จ แล้วดูว่าขัดแย้งหรือไม่
ถ้าขัดแย้งเป็นสัจนิรันดร์
(แต่ถ้าไม่ขัดแย้ง ตอบไม่เป็นสัจนิรันดร์)
2.5. พิจารณาประพจน์ p ฎ (p ู q)
เป็นสัจนิรันดร์หรือไม่
วิธีทำ
ตรรกศาสตร์ของมูล
2.1. คุณสมบัติของตรรกศาสตร์ของบูล
ในเครื่องคอมพิวเตอร์มีการทำงานกับข้อมูลในระดับบิท ซึ่งมีค่าได้เพียง
2 ค่า คือ 0 และ 1 ดังนั้นเราจึงสามารถใช้บิทแทนข้อมูล 2
ค่าทางตรรกได้ โดยให้ 0 แทนค่าที่เป็น เท็จ และ 1 แทนค่าที่เป็นจริง
ตัวแปรใดๆที่มีค่าได้เพียงค่าใดค่าหนึ่งระหว่าง จริง หรือ เท็จ
เรียกว่า boolean variable
และเราสามารถแทนค่าของตัวแปรเหล่านั้นโดยใช้บิทในคอมพิวเตอร์ได้
การกระทำระดับบิทในคอมพิวเตอร์เปรียบเทียบได้กับการกระทำทางตรรก
โดยอาศัยตัวเชื่อม ฺ , ู , และ ล กระทำกับบิท ใช้สัญลักษณ์ OR, AND,
XOR ตามลำดับ จะได้ผลลัพธ์ดังแสดงในตารางค่าความจริงต่อไปนี้
ข้อตกลงมูลฐานของบูลีน (Boolean Postulate)
ทฤษฎีพื้นฐานของพีชคณิตบูลีน
2.2.
การปฏิบัติการตรรกศาสตร์ของบูล
การพิสูจน์ทฤษฎี
พิสูจน์กฎของ นิจพล (Idempotent)
จงพิสูจน์ว่า
พิสูจน์
จงพิสูจน์ว่า
พิสูจน์
จงพิสูจน์ว่า
พิสูจน์
2.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
2.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
เยี่ยมค่ะ
ความรู้เต็มหัวเลยค่ะ