Discrete Ma Thematic Key2-6

discrete mathematic key : methods of proof

ฝายวิชาการ # cstu20 1.

ไมเฉลยนะครับ เพราะมันงาย ใชไดทั้ง direct และ indirect proof ครับ

2. direct proof

จากสมมติฐาน

d

e

d = max d1 ,d2 V x ≥ d Q x ≥d1 V x ≥d2

$ d = max d1 ,d2 b

# d ≥d1 V d ≥d2

c

b

c

b

c

x≥d # x ≥d1 V x ≥d2

ดังนั้นสมมติฐาน

d

e

d = max d1 ,d2 V x ≥ d Q x ≥d1 V x ≥d2 b

c

b

c

เปนจริง

ขอสองก็แนวคิดธรรมดานะครับ เราตีความจากfunction max()ที่จะคืนคาที่มากสุดออกมา ดังนั้นคา d จึงไมมี ทางนอยกวา d1 ,d2 แนๆ ทีนี้พอเราบอกวาคา x ไมนอยกวา d ก็แสดงวา x จะตองไมนอยกวา d1 ,d2 ดวย 3. contradiction prove by contradiction:

ลูกบอล 100 ลูกแบงใสกลอง 9 กลอง จะไมมีกลองใดเลยที่มีลูกบอล

มากกวา 11 ลูก(contradiction) ไมมีกลองใดมีลูกบอลเกิน 9 ลูก ดังนั้นจํานวนลูกบอลที่มากที่สุดที่จะเปนไปไดคือ 9B11 = 99 ลูก <100 เกิดขอขัดแยง ดังนั้น สมมติฐานลูกบอล 100 ลูกแบงใสกลอง 9 กลอง จะทีอยางนอยหนึ่งกลองที่มีลูกบอลมากกวา 11 ลูก – เปนจริง ขอนี้เปน contradiction แบบ basic นะครับ เมื่อหาขอขัดแยงเจอเราสามารถสรุปในทิศทางตรงกันขามไดทันที อยาลืมแจงลวงหนากอนวาจะใช contradiction นะครับ 4. contradiction prove by contradiction:

แบงเหรียญ 40 เหรียญ ใสถุง 9 ถุง แตละถุงมีเหรียญอยางนอยหนึ่งเหรียญ

จะไมมีถุงใดเลยมีจํานวนเหรียญเทากัน ถาไมมีถุงใดเลยที่มีจํานวนเหรียญเทากัน และแตละถุงมีอยางนอยหนึ่งเหรียญ จํานวนเหรียญทั้งหมดที่นอยที่สุดที่จะเปนไปไดเทากับ 1+2+3+4+5+6+7+8+9 = 45 เหรียญ ซึ่งขัดแยงกับสมมติฐาน ดังนั้น สมมติฐาน แบงเหรียญ 40 เหรียญ ใสถุง 9 ถุง แตละถุงมีเหรียญอยางนอยหนึ่งเหรียญ จะมีอยาง นอยสองถุงมีจํานวนเหรียญเทากัน – เปนจริง

5. prove by cases case 1 : x ≥ 0,y ≥ 0 x ≥ 0 # |x| = x y ≥ 0 # |y| = y xy ≥ 0 # |xy| = xy # |xy| = xy = |x||y|

case 2 :

x<0,y ≥ 0 x<0 # |x| =@ x y ≥ 0 # |y| = y xy<0 # |xy| =@ xy # |xy| =@ xy = @ x y = |x||y| `

case 3 :

a

x ≥ 0,y<0 x ≥ 0 # |x| = x y ≤ 0 # |y| =@ y xy ≤ 0 # |xy| =@ xy # |xy| =@ xy = x @ y = |x||y| `

case 4 :

a

x ≤ 0,y ≤ 0 x ≤ 0 # |x| =@ x y ≤ 0 # |y| =@ y xy ≥ 0 # |xy| = xy # |xy| = xy = @ x @ y = |x||y| `

a`

a

ดังนั้น สมมติฐาน x,y 2 R Q |xy| = |x||y| เปนจริง ขอนี้เกี่ยวกับเรื่องคาสมบูรณ ซึ่งนิยามของคาสมบูรณเนี่ย จะเกี่ยวกับความมากกวาและนอยกวาศูนยครับ เพราะฉะนั้น เราก็ตองแบงออกเปนเคสที่ตัวแปรมากกวากับนอยกวาศูนย แตเนื่องจากมีตัวแปรสองตัว ก็เลยกลายเปน 4 เคส 6.

เหมือนขอ 5 เลยครับ