กฎเดอมอร์แกน

💡 กฎของเดอมอร์แกน (De Morgan's Laws) 📖✨

กฎของเดอมอร์แกน คือ ชุดของกฎเกณฑ์สองข้อในวิชาตรรกศาสตร์และพีชคณิตแบบบูลีน (Boolean Algebra) ซึ่งอธิบายความสัมพันธ์ระหว่างตัวดำเนินการตรรกะ "และ" (AND), "หรือ" (OR) กับ "นิเสธ" (NOT) 🔄 กฎเหล่านี้มีประโยชน์อย่างยิ่งในการจัดรูปนิพจน์ตรรกะให้ง่ายขึ้น หรือแปลงจากรูปแบบหนึ่งไปอีกรูปแบบหนึ่ง

ชื่อของกฎนี้ตั้งตามนักคณิตศาสตร์ชาวอังกฤษชื่อ ออกัสตัส เดอ มอร์แกน (Augustus De Morgan) ผู้ที่มีบทบาทสำคัญในการพัฒนาระบบตรรกศาสตร์เชิงสัญลักษณ์ครับ 🧔🏻‍♂️🇬🇧

📜 กฎทั้งสองข้อของเดอมอร์แกน

กฎของเดอมอร์แกนมีอยู่ 2 ข้อหลักๆ ดังนี้ครับ:

1. นิเสธของคอนจังก์ชัน (Negation of a Conjunction):

   • หลักการ: "นิเสธของ (A และ B)" จะสมมูลกับ "(นิเสธของ A) หรือ (นิเสธของ B)"
   • สัญลักษณ์ทางตรรกศาสตร์: $$\neg (P\wedge Q)\iff (\neg P)\vee (\neg Q)$$
   • ความหมายง่ายๆ: 🤏 การบอกว่า "ไม่จริงที่ทั้ง P และ Q เป็นจริง" (เช่น ไม่จริงที่ "วันนี้แดดออก และ ฝนตก") ก็เหมือนกับการบอกว่า "P ไม่จริง หรือ Q ไม่จริง (หรือทั้งสองอย่างไม่จริง)" (เช่น "วันนี้แดดไม่ออก หรือ ฝนไม่ตก")

2. นิเสธของดิสจังก์ชัน (Negation of a Disjunction):

   • หลักการ: "นิเสธของ (A หรือ B)" จะสมมูลกับ "(นิเสธของ A) และ (นิเสธของ B)"
   • สัญลักษณ์ทางตรรกศาสตร์: $$\neg (P\vee Q)\iff (\neg P)\wedge (\neg Q)$$
   • ความหมายง่ายๆ: 🤏 การบอกว่า "ไม่จริงที่ P หรือ Q เป็นจริง (หรือทั้งคู่เป็นจริง)" (เช่น ไม่จริงที่ "ฉันจะกินเค้ก หรือ ไอศกรีม") ก็เหมือนกับการบอกว่า "P ไม่จริง และ Q ก็ไม่จริงด้วย" (เช่น "ฉันจะไม่กินเค้ก และ ฉันจะไม่กินไอศกรีม")

🔄 การเทียบเคียงกับทฤษฎีเซต (Set Theory)

กฎของเดอมอร์แกนยังสามารถนำไปประยุกต์ใช้กับทฤษฎีเซตได้ด้วยครับ โดยมีความคล้ายคลึงกันมาก:

1. คอมพลีเมนต์ของอินเตอร์เซกชัน: $(A\cap B{)}^{\prime }=A^{\prime }\cup B^{\prime }$
2. คอมพลีเมนต์ของยูเนียน: $(A\cup B{)}^{\prime }=A^{\prime }\cap B^{\prime }$

โดยที่ A′ หมายถึงคอมพลีเมนต์ของเซต A ครับ

🌟 ความสำคัญและการนำไปใช้

กฎของเดอมอร์แกนมีประโยชน์อย่างมากในหลายๆ ด้าน โดยเฉพาะอย่างยิ่ง:

• ตรรกศาสตร์และคณิตศาสตร์: ➕➖
  • ช่วยในการ จัดรูปและลดความซับซ้อนของนิพจน์ตรรกะ ทำให้เข้าใจและพิสูจน์ได้ง่ายขึ้น
• วิทยาการคอมพิวเตอร์และวิศวกรรมไฟฟ้า: 💻🔌 (น่าจะตรงกับที่คุณทอยเรียนมาเลยนะครับ! 🎓)
  • การออกแบบวงจรดิจิทัล (Digital Circuit Design): สามารถใช้ในการแปลงรูปแบบของเกตตรรกะ (Logic Gates) เช่น การแปลงวงจรที่ใช้ AND gate และ OR gate ไปเป็นวงจรที่ใช้ NAND gate หรือ NOR gate อย่างเดียว ซึ่งช่วยลดต้นทุนและความซับซ้อนของวงจรได้
  • การเขียนโปรแกรม (Programming): ช่วยในการเขียนเงื่อนไขที่ซับซ้อนให้เข้าใจง่ายขึ้น เช่น if (!(x > 5 && y < 10)) สามารถเขียนใหม่เป็น if (x <= 5 || y >= 10) ซึ่งอาจจะอ่านและทำความเข้าใจได้ง่ายกว่าในบางบริบท
  • การออกแบบฐานข้อมูล (Database Design): ใช้ในการปรับแต่งเงื่อนไขการค้นหา (Query Optimization)

แบบทดสอบตรรกศาสตร์

จงพิจารณาว่าประโยคหรือข้อความต่อไปนี้เป็นประพจน์หรือไม่ ถ้าเป็นประพจน์เป็นประพจน์ที่มีค่าความจริงเป็น “จริง”หรือ”เท็จ” ถ้าเป็นประพจน์เป็นข้อความประเภทใด

ประโยค	เป็น/ไม่เป็น	ค่าประพจน์/ประเภท
กรุงเทพเป็นเมืองหลวงของประเทศไทย นกไม่มีปีก ธนาคารมีการบันทึกและจัดเก็บข้อมูลลูกค้าไว้ในคอมพิวเตอร์ 4+5มีค่าเท่ากับ 9 ว้าย! น่ากลัวจัง จังหวัดอุดรธานีไม่ได้อยู่ในภาคอีสาน 2 + 3  =  3  -  1 โลกเป็นดาวเคราะห์ กรุณาปิดไฟทุกครั้งก่อนออกจากห้อง 17 + 8 = 30 เซตว่างไม่เป็นสับเซตของทุกเซต ปลาและนกเป็นสัตว์บก 50 คูณด้วย 40 มีค่าเท่ากับเท่าไร หยุดเดี๋ยวนี้นะ อย่าส่งเสียงดังในเวลาทำงาน ได้โปรดเถอะนะถือว่าสงสารฉันหน่อย ว้าย! ตะเถรตกกระโถน บรรยากาศสำหรับเราสองคนอยากให้เป็นเช่นนี้จังเลย อย่าคุยเวลาทำงาน อยากดูหนังมากเลย เลขคู่ทุกจำนวนหารด้วยสองลงตัว	เ      ป็น เป็      น เป็       น เป็       น เป็       น ไม่    เป็น เ       ป็น เป็       น ไ     ม่เป็น เ         ป็น เป็        น เป็        น ไม่เ       ป็น ไม่เป็     น ไม่     เป็น ไม่เป็      น ไม่เป็     น ไม่เป็    น ไม่     เป็น ไม่เป็    น  เป็      น	จริ      ง เ      ท็จ จ      ริง จ       ริง อุท     าน เ        ท็จ เ        ท็จ จริ       ง อ้อนวอ น เท็        จ เ        ท็จ เท็        จ คำถา    ม คำสั่      ง ห้า      ม ขอร้อ   ง อุทา     น ปรารถ นา ห้า        ม ปรารถ  นา จริ       ง

จงใช้แผนภาพแสดงการตรวจสอบการให้เหตุผลต่อไปนี้ว่าสมเหตุสมผลหรือไม่

1.              เหตุ  1    :   นักกีฬาทุกคนเป็นคนแข็งแรง

                   เหตุ  2    :   นักกีฬาบางคนเป็นคนขยัน

                   ผลสรุป   :   คนแข็งแรงบางคนเป็นคนขยัน

2.               เหตุ  1    :   ขวดเป็นสิ่งมีชีวิต

                   เหตุ  2    :   สิ่งมีชีวิตย่อมเจริญเติบโต

                   ผลสรุป   :   ขวดเจริญเติบโต

3.               เหตุ  1    :   ไม่มีคนคิดมากคนใดมีความสุข

                   เหตุ  2    :   สิตาไม่มีความสุข

                   ผลสรุป   :   สิตาเป็นคนคิดมาก

4.               เหตุ  1    :   สัตว์น้ำบางชนิดเลี้ยงลูกด้วยนม

                   เหตุ  2    :   สัตว์เลี้ยงลูกด้วยนมทุกชนิดเป็นสัตว์เลือดอุ่น

                   ผลสรุป   :   สัตว์น้ำบางชนิดไม่เป็นสัตว์เลือดอุ่น

5.               เหตุ  1    :   ไม่ว่าใครที่กินนมเป็นประจำ  จะมีรูปร่างสูงใหญ่

                   เหตุ  2    :   ปานทิพย์มีรูปร่างสูงใหญ่

                   ผลสรุป   :   ปานทิพย์กินนมเป็นประจำ

ค่าความจริงของประพจน์และตัวเชื่อม Truth Table

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

ตารางความจริง คือ ตารางที่สร้างขึ้นเพื่อใช้หาค่าความจริงของประพจน์

ตัวอย่าง                ถ้ามีตัวแปร 2 ตัว จะมีจำนวนแถว =22 = 4

ถ้ามีตัวแปร 3 ตัว จะมีจำนวนแถว = 23 = 8

การสร้างตารางความจริง

1. ตีตารางที่มีจำนวนช่องเท่ากับจำนวนตัวแปรรวมกับจำนวนตัวเชื่อม

2. เขียนค่าความจริงของตัวแปรก่อน (p,q,...)

3. เริ่มเขียนค่าความจริงของประพจน์ย่อยที่เล็กที่สุดก่อน แล้วจึงเขียนประพจน์ที่ใหญ่ขึ้นตามลำดับ

หลักในการหาค่าความจริง

1. เขียนค่าความจริงของประพจน์ย่อย หรือตัวแปรแต่ละตัวก่อน เช่น p,q,r,...

2. หาค่าความจริงที่เป็นนิเสธของตัวแปร ถ้ามี ~p,~q,...

3. หาค่าความจริงของประพจน์ที่เชื่อมด้วยตัวเชื่อมที่กินความน้อยที่สุด

4. หาค่าความจริงของประพจน์ที่เชื่อมด้วยตัวเชื่อมที่กินความมากขึ้นตามลำดับ

5. ถ้าตัวเชื่อมกินความเท่ากัน ให้ทำจากซ้ายไปขวา

6. ถ้ามีวงเล็บควรทำในวงเล็บก่อน

ตัวเชื่อมที่กินความน้อยที่สุด ไปหามากที่สุด เรียงตามลำดับดังนี้

1. ~

2. ^

3. v

4. →

5. ↔

ตารางเรียงลำดับคุมความของลักษณ์จากมากไปหาน้อย

สัญลักษณ์	ความหมาย	ขยายความหมาย
↔	ก็ต่อเมื่อ	มีค่าความจริงเป็นจริง เมื่อประพจน์ที่เชื่อมกันมีค่าความจริงเหมือนกัน
→	ถ้า...แล้ว	มีค่าความจริงเป็นเท็จเมื่อประพจน์หน้าเป็นจริงและหลังเป็นเท็จ
^	และ	มีค่าความจริงเป็นจริง เมื่อทุกประพจน์เป็นจริงทั้งหมด
v	หรือ	มีค่าความเป็นจริง เมื่อมีประพจน์ใดประพจน์หนึ่งเป็นจริง
~	ไม่	มีค่าความตรงข้าว เช่นเปลี่ยนจากเป็นเท็จ หรือเปลี่ยนจากเท็จเป็นจริง

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

p	q	~q	pvq	p^~q	pvq→p^~q
T T F F	T F T F	F T F T	T T T F	F T F F	F T F T

ตัวอย่าง จงหาตารางความจริงของประพจน์ pvq→p^~q

วิธีทำ     1. เขียนค่าของ p, q ก่อน

2. หาค่า ~q ก่อน

3. หาค่า pvq และ p^~q

4. หาค่า pvq→p^~q

ในกรณีที่ทราบค่าแน่นอนของตัวแปร (หรือประพจน์ย่อย) เราสามารถหาค่าความจริงของประพจน์รวมได้ทันทีโดยเขียนตารางเพียงแถวเดียว

ตัวอย่าง                จงหาค่าความจริงของ (p→q)v(r^s)

เมื่อให้ p เป็นเท็จ q เป็นเท็จ r เป็นเท็จ s เป็นเท็จ

วิธีทำ                     P(p,q,r,s) = (p→q)v(r^s)

P(F,F,F,F) = T

ตัวอย่าง                "ถ้า 1+1 = 3 หรือ 2+2 = 5 แล้ว 1+2 = 4"

วิธีทำ                     ให้ p คือ 1+1 = 3 เป็น F

q คือ 2+2 = 5 เป็น F

r คือ 1+2 = 4 เป็น F

ประโยคข้างต้นสามารถเขียนแทนด้วย p^q→r

pvq = FvF = F

pvq→r = F→F = T

ตัวอย่าง จงเขียนประโยคที่กำหนดให้ในรูปสัญลักษณ์

(1)          ถ้า 4 เป็นเลขคี่แล้ว 5 เป็นเลขคู่

p แทน 4 เป็นเลขคี่

q แทน 5 เป็นเลขคู่

   ดังนั้นเขียนแทนด้วย p→q

(2)          2 เท่ากับหรือมากกว่า 3

p แทน 2 เท่ากับ 3

q แทน 2 มากกว่า 3

   ดังนั้นเขียนแทนด้วย pvq

(3)          6 หาร 3 ได้ลงตัวก็ต่อเมื่อ 3 บวก 3 เท่ากับ 7

p แทน 6 หาร 3 ลงตัว

q แทน 3 บวก 3 เท่ากับ 7

    ดังนั้นเขียนแทนด้วย p↔q

(4)          ดอกกุหลาบมีสีแดงและดอกมะลิมีสีฟ้า

p แทนดอกกุหลาบมีสีแดง

q แทนดอกมะลิมีสีฟ้า

    ดังนั้นเขียนแทนด้วย p^q

การวิเคราะห์ค่าความจริงของประพจน์

ในการวิเคราะห์ค่าความจริงของประพจน์นั้น สามารถทำการวิเคราะห์ได้ด้วยวิธีการดังนี้

1. การวิเคราะห์ด้วยตารางค่าความจริง

การวิเคราะห์ด้วยตารางค่าความจริง สามารถทำการวิเคราะห์ได้ดังนี้ตัวอย่างต่อไปนี้

ตัวอย่าง จงวิเคราะห์ค่าความจริงของประพจน์ p v q   →     p ด้วยตารางค่าความจริง

นำพจน์ข้างบนมาเขียนเป็นตารางค่าความจริงได้ดังตารางต่อไปนี้                   

ตารางค่าความจริงของประพจน์ p v q →  p

p	q	p v q	p v q  →    p
T	T	T	T
T	F	T	T
F	T	T	F
F	F	F	T

วิธีทำ     1. เขียนค่าของ p, q ก่อน

2. หาค่า pvq  ก่อน

3. หาค่า pvq→p^~q

ตัวอย่าง จงวิเคราะห์ค่าความจริงของประพจน์ (p v q) ^~ r ด้วยตารางค่าความจริง

นำพจน์ข้างบนมาเขียนเป็นตารางค่าความจริงได้ดังตารางต่อไปนี้                   

ตารางค่าความจริงของประพจน์ (p v q) ^~ r

วิธีทำ     1. เขียนค่าของ p, q,  r ก่อน

p	q	r	~ r	p v q	(p v q) ^~ r
T	T	T	F	T	F
T	T	F	T	T	T
T	F	T	F	T	F
T	F	F	T	T	T
F	T	T	F	T	F
F	T	F	T	T	T
F	F	T	F	F	F
F	F	F	T	F	T

2. หาค่า ~ r   ก่อน

3. หาค่า pvq

4. หาค่า (p v q) ^~ r

การสมมูลเชิงตรรกะ (Logical Equivalence)

ประพจน์ที่สมมูลกัน

ประพจน์ที่สมมูลกัน  หมายถึง  ค่าความจริงที่ของประพจน์  2  ประพจน์  ถ้ามีค่าความจริงเหมือนกัน  กรณีต่อกรณี  แล้วสามารถนำไปใช้แทนกันได้  จะเรียกประพจน์นั้นว่า  เป็นรูปแบบที่สมมูลกันเช่น  p → q กับ ~p v q   ถือว่าเป็นรูปแบบที่สมมูลกันและจะใช้

สัญลักษณ์ “≡” แทนการสมมูลและใช้

สัญลักษณ์ “” แทนการไม่สมมูล

ตัวอย่าง ประพจน์ที่สมมูลกัน

ประพจน์กรณีที่  1	สมมูลกับ	ประพจน์กรณีที่2
~p	≡	p →~p
~q v q	≡	~p v p
~(p→q)	≡	p ^ ~q
~(p ^ q)	≡	~p v ~q
p→q	≡	~q →~p
~p v~q	≡	~(p ^ q)
~p v q	≡	p→q

จงพิจารณาว่าประพจน์ ~(p ^ q) สมมูลกับประพจน์ ~p v ~q

นำประพจน์ทั้งสองมาเขียนเป็นตารางค่าความจริง

ตารางค่าความจริงของประพจน์ ~(p ^ q) สมมูลกับประพจน์ ~p v ~q

p	q	~p	~q	p ^ q	~(p ^ q)	~p v ~q
T	T	F	F	T	F	F
T	F	F	T	F	T	T
F	T	T	F	F	T	T
F	F	T	T	F	T	T

จะเห็นว่าผลของความจริงของทั้ง 2 ประพจน์ พบว่าสมสมมูลกัน