วันนี้จะเสนอวิธีพิสูจน์พื้นฐานอีกวิธี คือ การพิสูจน์โดยหาข้อขัดแย้ง ( Proof by contradiction ) แนวคิดก็คือ หากเราต้องการพิสูจน์ทฤษฎีหนึ่งโดยหาข้อขัดแย้ง เราจะเริ่มต้นด้วยการสมมติให้ทฤษฎีนั้นไม่เป็นจริงก่อน และแสดงว่าการสมมติแบบนี้จะนำไปสู่ข้อขัดแย้งที่ไม่เป็นจริง ดังนั้นทฤษฎีนี้จะไม่เป็นจริงไม่ได้ จึงได้ว่าทฤษฎีนี้เป็นจริง

ลองดูจากทฤษฎีต่อไปนี้ ( หวังว่าคราวนี้จะไม่ยากไปนะ )

Theorem : ไม่มีจำนวนตรรกยะใดเป็นคำตอบของสมการ $x^3+x+1=0$

Proof : สมมติให้มีจำนวนตรรกยะ $s$ เป็นคำตอบของสมการ $x^3+x+1=0$ เนื่องจาก $s$ เป็นจำนวนตรรกยะ จึงสามารถเขียนเป็นเศษส่วนได้ ให้ $s=p/q$ โดยเป็นเศษส่วนอย่างต่ำแล้ว และ $q!=0$ เราจะได้ว่า
$p^3/q^3+p/q+1=0$
เมื่อคูณทั้งสมการด้วย $q^3$ จะได้
$p^3+p*q^2+q^3=0$
เราจะแบ่งเป็นสี่กรณีที่เป็นไปได้
1. ทั้ง $p$ และ $q$ เป็นจำนวนคี่ จะได้ว่าทั้ง $p^3$, $p*q^2$, และ $q^3$ เป็นจำนวนคี่ทั้งสิ้น ดังนั้น $p^3+p*q^2+q^3$ เป็นจำนวนคี่ ซึ่งไม่เท่ากับ $0$ แน่นอน เกิดข้อขัดแย้ง
2. $p$ เป็นจำนวนคี่ และ $q$ เป็นจำนวนคู่ จะได้ $p^3$ เป็นจำนวนคี่, $p*q^2$ และ $q^3$ เป็นจำนวนคู่ เมื่อบวกกันก็เป็นจำนวนคี่ซึ่งไม่มีทางเท่ากับ $0$ ได้ เกิดข้อขัดแย้งเช่นกัน
3. $p$ เป็นจำนวนคู่ และ $q$ เป็นจำนวนคี่ จะได้ $p^3$ และ $p*q^2$ เป็นจำนวนคู่ และ $q^3$ เป็นจำนวนคี่ เมื่อบวกกันก็ได้จำนวนคี่ เกิดข้อขัดแย้งเหมือนเดิม
4. ทั้ง $p$ และ $q$ เป็นจำนวนคู่ เราจะได้ว่า $p/q$ มีตัวประกอบร่วม สามารถตัดทอนได้ ซึ่งแสดงว่าไม่เป็นเศษส่วนอย่างต่ำ ขัดแย้งอยู่ดี

ทั้งสี่กรณีสรุปได้ว่า ข้อสมมติที่เราตั้งไว้ตอนต้นนั้นไม่เป็นจริง ดังนั้น จึงไม่มีจำนวนตรรกยะใดเป็นคำตอบของสมการ $x^3+x+1=0$

( เกี่ยวกับ MathML เล็กน้อย เนื่องจาก blog นี้จะเกี่ยวกับคณิตศาสตร์ซะส่วนใหญ่ จึงจำเป็นที่จะต้องหาทางแสดงสมการที่ซับซ้อนให้ได้ วิธีการก็ได้มาจากอาจารย์มะนาวนี่เอง หากใครที่อ่านสมการไม่ได้ เห็นเป็นโค้ดแปลกๆ ลองลง MathPlayerดูก็จะอ่านได้ครับ )

วันนี้จะเริ่มเกี่ยวกับการพิสูจน์ เนื่องจากทฤษฎีทั้งหลายจะไม่ได้รับการเชื่อถือเลยหากไม่มีบทพิสูจน์ที่สนับสนุนมัน ซึ่งวิธีการพิสูจน์ก็มีอยู่หลากหลายรูปแบบ แบบแรกที่จะเสนอคือการพิสูจน์โดยการแยกกรณี ( Proof by case )

Theorem : มีจำนวนอตรรกยะ $x$,$y$ และจำนวนตรรกยะ $z$ ที่ $x^y=z$

Proof : เรามาพิจารณาจำนวนอตรรกยะที่รู้จักกันดีตัวหนึ่ง คือ $sqrt2$ หากเราให้ $x=y=sqrt2$ สิ่งที่เราควรจะรู้ก็คือ $sqrt2^sqrt2$ เป็นจำนวนตรรกยะหรือไม่? แต่เรายังไม่รู้ เพราะฉะนั้นเราก็จะแบ่งเป็นสองกรณีคือ
1. ถ้า $sqrt2^sqrt2$ เป็นจำนวนตรรกยะ เราก็จะให้ $x=y=sqrt2$ และ $z=sqrt2^sqrt2$ ก็จะได้ตามต้องการ
2. ถ้า $sqrt2^sqrt2$ เป็นจำนวนอตรรกยะ เราสามารถแทนให้ $x=sqrt2^sqrt2$,$y=sqrt2$ และ $z=(sqrt2^sqrt2)^sqrt2=sqrt2^(sqrt2*sqrt2)=sqrt2^2=2$ ซึ่งเป็นจำนวนตรรกยะ และทำให้ทฤษฎีเป็นจริงได้เช่นกัน

ดังนั้น ไม่ว่า $sqrt2^sqrt2$ จะเป็นจำนวนตรรกยะหรือไม่ เราก็ยังสามารถหาจำนวนมาแทนตัวแปรทั้งสามตามต้องการได้อยู่ดี จึงสามารถพิสูจน์ Theorem ข้างต้นได้

วันนี้ขอหยุดไว้เท่านี้ก่อน

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

สำหรับเรื่องแรกที่จะพูดถึง คือเรื่องของตรรกศาสตร์เบื้องต้น ซึ่งคิดว่าทุกคนคงได้ผ่านหูผ่านตามาบ้างพอสมควร กับตารางค่าความจริง

( T = True , F = False )
$TvvT=T$ $T^^T=T$ $T->T=T$ $TharrT=T$
$TvvF=T$$T^^F=F$ $T->F=F$ $TharrF=F$
$FvvT=T$$F^^T=F$$F->T=T$ $FharrT=F$
$FvvF=F$ $F^^F=F$$F->F=T$ $FharrF=T$

แล้วเคยสงสัยกันหรือไม่ ว่าตารางนี้ สร้างกันมาได้อย่างไร ข้อที่คิดว่าน่าจะมีคนสงสัยมากที่สุดคือ ผลของ "ถ้า...แล้ว..." ทำไม $T->F=F$ และทำไม $F->T=T$
หากนึกย้อนไปถึงที่มาของมันแล้ว ก็ไม่ยากที่จะหาเหตุผลที่น่าเชื่อถือ นี่คือความอัจฉริยะของนักคณิตศาสตร์ที่สามารถจับข้อเท็จจริง เหตุผลทั้งมวลมาสรุปเป็นตารางที่กระชับและทรงพลังยิ่งนัก

ทำไม $T->F=F$ ? ข้อนี้หากใช้เวลาคิดดูสักพัก ก็น่าจะเข้าใจได้ จริงๆแล้วมันไม่ได้ฝืนความรู้สึกมากมายเท่าไหร่

ทำไม $F->T=T$ ? คิดว่าข้อนี้น่าแปลกใจมากกว่าสำหรับหลายๆคน ทำไม "ถ้าเท็จแล้วจริง" จึงได้ค่าเป็น "จริง" ตอนแรกที่ผมเองได้พบตารางนี้ ก็สับสนกับปัญหานี้ไม่น้อยทีเดียว แต่หากลองนึกถึงโลกแห่งความเป็น "จริง" ดังตัวอย่างต่อไปนี้
สมมติให้ ( นาย ก. เป็นพี่นาย ข. ) เป็นจริง
และสมมติให้ ( วันนี้ฝนตก ) เป็นจริง เรามาพิจารณา
ถ้าวันนี้ฝนไม่ตกแล้ว นาย ก. เป็นพี่นาย ข. ....
จะเห็นว่าข้อความดังกล่าวเป็นจริงแน่นอน ถึงแม้ว่า ( วันนี้ฝนไม่ตก )จะไม่เป็นจริงก็ตาม เพราะความจริงแล้ว ไม่ว่า ฝนจะตกหรือไม่ตก นาย ก. ก็ยังคงเป็นพี่นาย ข. ไม่เปลี่ยนแปลง

ทีนี้ข้อข้องใจที่เคยมีในตารางค่าความจริงก็หมดไปจนได้