Chứng minh bằng cách phân chia trường hợp

C h ứ n g m i n h b ằ n g cá c h ph â n c h ia t r ư ờ n g h ợ p

Để chứng minh mệnh đề có dạng :

(P1 v P2v...v Pn) → Q Chúng ta có thể sử dụng hằng đúng sau :

((P1v P2v..v Pn) →Q) ↔ ((P1→Q) v (P2→Q) v....v(Pn→Q)) Cách

chứng minh này gọi là chứng minh bằng cách phân chia trường hợp.

Vídụ8:Chứng minh rằng:

" Nếu n không chia hết cho 3 thì n2 không chia hết cho 3".

Giải : Gọi P là mệnh đề "n không chia hết cho 3" và Q là mệnh đề "n2

không chia hết cho 3". Khi đó, P tương đương với P1 v P2. Trong đó:

P1 = " n mod 3 =1" P2 = " n mod 3 =2"

Vậy, để chứng minh P → Q là đúng, có thể chứng minh rằng:

(P1 v P2) → Q hay là (P1 → Q ) v ( P2→ Q) Giả sử P1 là đúng. Ta có, n mod 3 = 1. Đặt n = 3k + 1 ( k là số nguyên nào đó). Suy ra

n2 = ( 3k+1)2 = 9k2 + 6k + 1 = 3(3k2 + 2k) + 1 không chia chẳn cho 3. Do đó, P1

→ Q là đúng.

Tương tự, giả sử P2 là đúng. Ta có, n mod 3 = 2. Đặt n = 3k + 2 ( k là số nguyên

nào đó).

Suy ra n2 = ( 3k+2)2 = 9k2 + 12k + 4 = 3(3k2 + 4k + 1) + 1 không chia chẳn cho

3.

Do đó, P2 → Q là đúng.

Do P1 → Q là đúng và P2 → Q là đúng, hay là (P1 → Q ) v ( P2→ Q). Vậy (P1

v P2) → Q.

Chúng ta hãy trở lại một bài toán về số nguyên đã được trình bày trong phần trước

về các ví dụ áp dụng của logic trong việc lập luận và chứng minh.

Để chứng minh một biểu thức tương đương dạng p  q, trong đó p và q là các

mệnh đề. Chúng ta có thể sử dụng hằng đúng sau:

( p q)  [( p→ q) ∧ (q→ p)]

Đôi khi chúng ta muốn chứng minh một vài mệnh đề tương đương nhau ví dụ:

p1  p2  p3  ... pn, ta có thể sử dụng hằng đúng.

[ p1  p2  p3  ... pn]  [( p1 → p2 ) ∧ ( p2 → p3 ) ∧ ... ∧ ( pn → p1 )]

Vídụ9:Hãy áp dụng để chứng minh rằng 3 khẳng định sau là tương đương với n là số tự nhiên:

p1: n mod 3= 1 hoăc n mod 3= 2

p2: n không chia hết cho 3

p3: n2 -1 chia hết cho 3