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

กฎเดอมอร์แกนหรือกฎของเดอมอร์กอง(อ่านตามภาษาฝรั่งเศส) (อังกฤษ: De Morgan's laws) หรือ ทฤษฎีบทเดอมอร์แกน (อังกฤษ: De Morgan's theorem) เป็นกฎในวิชาตรรกศาสตร์ คือ ชุดของกฎในสาขาตรรกศาสตร์รูปนัยซึ่งแสดงความสัมพันธ์อย่างเป็นระบบระหว่างคู่ของตัวดำเนินการเชิงตรรกที่คู่กัน โดยแสดงในรูปนิเสธ ความสัมพันธ์เช่นนี้เรียกว่าภาวะคู่กันเดอมอร์แกน (De Morgan duality)

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

$\neg (p\wedge q)\iff (\neg p)\vee (\neg q)$

$\neg (p\vee q)\iff (\neg p)\wedge (\neg q)$

การประยุกต์

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

นิเสธของประพจน์เลือก

ในกรณีของการประยุกต์กับประพจน์เลือก (disjunction) พิจารณาข้อความอ้างต่อไปนี้

การที่ A หรือ B เป็นจริงแม้เพียงตัวเดียวนั้น เป็นเท็จ

ซึ่งเขียนได้เป็น

$\neg (A\vee B)$

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

ในทิศทางกลับกันของปัญหานี้ พิจารณาข้อความอ้างต่อไปนี้

$(\neg A)\wedge (\neg B)$

ข้อความอ้างนี้ยืนยันว่า A เป็นเท็จ และ B เป็นเท็จ (หรือทั้ง "not A" และ "not B" เป็นจริง) เมื่อรู้เช่นนี้ ประพจน์เลือกของ A กับ B ย่อมเป็นเท็จด้วย อย่างไรก็ตาม นิเสธของประพจน์เลือกดังกล่าวนี้จะนำไปสู่ผลลัพธ์เป็นจริงที่สมมูลเชิงตรรกกับข้อความอ้างเดิม

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

นิเสธของประพจน์เชื่อม

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

การที่ทั้ง A และ B จะเป็นจริงทั้งคู่ได้นั้นเป็นเท็จ

ซึ่งเขียนได้เป็น

$\neg (A\wedge B)$

ข้อความอ้างข้างต้นนี้จะเป็นจริงได้ A หรือ B ตัวใดตัวหนึ่งหรือทั้งคู่ต้องเป็นเท็จ หากทั้งคู่เป็นจริง ประพจน์เชื่อมของ A และ B ย่อมเป็นจริง ซึ่งทำให้นิเสธของประพจน์เชื่อมนี้เป็นเท็จ ฉะนั้น ข้อความอ้างข้างต้นอาจกล่าวได้เป็น "A หรือ B อย่างน้อยตัวหนึ่งเป็นเท็จ" หรือ "not A เป็นจริง หรือ not B เป็นจริง อย่างน้อยตัวใดตัวหนึ่ง"

$(\neg A)\vee (\neg B)$

หากกล่าวเป็นภาษาทั่วไป การประยุกต์นี้เป็นไปตามตรรกะที่ว่า "เมื่อการที่สิ่งสองสิ่งจะเป็นจริงทั้งคู่ได้นั้นเป็นเท็จ อย่างน้อยสิ่งหนึ่งในสองสิ่งนั้นย่อมเป็นเท็จ"

ประวัติและการสร้างสูตร

เมื่อเริ่มแรก ออกัสตัส เดอ มอร์แกน สังเกตว่า ในตรรกศาสตร์เชิงประพจน์แบบฉบับ มีความสัมพันธ์ต่อไปนี้

not (P and Q) = (not P) or (not Q)

not (P or Q) = (not P) and (not Q)

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