ตรรกศาสตร์ของคอมพิวเตอร์(LogicinComputer)


Hack MathematicsForComputer

 ตรรกศาสตร์พื้นฐาน

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

 

คำสำคัญ (Tags): #hack#mathematicsforcomputer
หมายเลขบันทึก: 58903เขียนเมื่อ 12 พฤศจิกายน 2006 17:03 น. ()แก้ไขเมื่อ 24 มิถุนายน 2012 01:10 น. ()สัญญาอนุญาต: จำนวนที่อ่านจำนวนที่อ่าน:


ความเห็น (2)

เยี่ยมค่ะ

ความรู้เต็มหัวเลยค่ะ

พบปัญหาการใช้งานกรุณาแจ้ง LINE ID @gotoknow
ClassStart
ระบบจัดการการเรียนการสอนผ่านอินเทอร์เน็ต
ทั้งเว็บทั้งแอปใช้งานฟรี
ClassStart Books
โครงการหนังสือจากคลาสสตาร์ท