Giáo trình toán rời rạc -Nguyễn Thế Vinh

Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 4 CHƯƠNG I CÁC KIẾN THỨC CƠ SỞ 1.1. MỆNH ĐỀ 1.1.1. Định nghĩa mệnh đề Một mệnh đề là một câu phản ánh một điều đúng hoặc sai, chứ không thể vừa đúng vừa sai. Ví dụ: Tất cả các câu sau đều là các mệnh đề (1). 2 + 3 = 5 (2). 3 x 4 = 10 (3). Tam giác đều có 3 cạnh bằng nhau (4). Thái Nguyên là thủ đô Kháng chiến (5). Washington D.C. là thủ đô của Canada Câu xác định "2 + 3 = 5", "Tam giác đều có 3 cạnh bằng nhau" và "Thái Nguyên là thủ đô Kháng chiến" là các mệnh đề đúng. Các câu xác định "3 x 4 = 10" và "Washington D.C. là thủ đô của Canada" là các mệnh đề sai. Như vậy, một mệnh đề có thể là mệnh đề đúng hoặc mệnh đề sai. Hay nói cách khác, một mệnh đề chỉ có thể lựa chọn 1 trong 2 giá trị là đúng hoặc là sai. Một mệnh đề không thể vừa đúng vừa sai. Ví dụ: Xét các câu sau (1). Hôm nay là thứ mấy ? (2). Hãy đọc kỹ đọan văn này (3). x + 1 = 2 (4). x + y = z Câu "Hôm nay là thứ mấy ? " và " Hãy đọc kỹ đoạn văn này" không phải là mệnh đề vì chúng không phải là câu khảng định. Còn các câu "x+1=2" và "x+y=z" không phải là mệnh đề vì chúng chẳng đúng cũng chẳng sai bởi các biến trong những câu đó chưa gán cho giá trị cụ thể nào. Giá trị đúng, sai của một mệnh đề được gọi là giá trị chân lí của mệnh đề đó. Giá trị chân lí của mệnh đề đúng ký hiệu là T (true), giá trị chân lí của Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 5 mệnh đề sai ký hiệu là F (false). Bảng giá trị chân lí gọi tắt là bảng chân trị (truth table) của mệnh đề bao gồm các trường hợp đúng, sai có thể xảy ra của mệnh đề đó. Mục đích của các họat động khoa học là phân biệt các mệnh đề để xác định chân trị của nó. Sự xác định chân trị này dựa vào thực nghiệm và lý luận. Vì thế, chúng ta cần nói đến "Đại số mệnh đề". Bây giờ chúng ta xét các phương pháp tạo ra các mệnh đề mới từ các mệnh đề đã có. Các phương pháp này được nghiên cứu bởi nhà toán học người Anh Geogre Boole. Rất nhiều mệnh đề toán học được xây dựng bằng cách tổ hợp một hoặc nhiều mệnh đề, khi đó các mệnh đề mới được gọi là mệnh đề phức hợp. 1.1.2. Mệnh đề phủ định Giả sử P là một mệnh đề. Câu "không phải là P" là một mệnh đề khác được gọi là phủ định của mệnh đề P, nhận giá trị sai khi P đúng và giá trị đúng khi P sai. Kí hiệu : ¬P (hay P ). Ví dụ: P = " 2 > 0 " ¬P = " 2 ≤ 0 " Bảng chân trị P ¬P T F F T 1.1.3. Hội của hai mệnh đề Giả sử P và Q là hai mệnh đề. Mệnh đề "P và Q", được kí hiệu bởi P∧Q, là đúng khi cả P và Q đều đúng, là sai trong các trường hợp còn lại. Mệnh đề P∧Q được gọi là hội của P và Q. Ví dụ: Cho 2 mệnh đề P và Q như sau P = " 2 > 0 " là mệnh đề đúng Q = " 2 = 0 " là mệnh đề sai P ∧ Q = " 2> 0 và 2 = 0 " là mệnh đề sai. Bảng chân trị Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 6 P Q P ∧ Q T T T T F F F T F F F F 1.1.4. Tuyển của hai mệnh đề Giả sử P và Q là hai mệnh đề. Mệnh đề "P hoặc Q" được kí hiệu P∨Q, là sai khi cả P và Q đều sai, là đúng trong các trường hợp còn lại. Mệnh đề P∨Q được gọi là tuyển của P và Q Ví dụ : Cho 2 mệnh đề P và Q như sau P = " 2 > 0 " là mệnh đề đúng Q = " 2 = 0 " là mệnh đề sai P ∨ Q = " 2 > 0 hoặc 2=0" là mệnh đề đúng. Bảng chân trị P Q P ∨ Q T T T T F T F T T F F F 1.1.5. Tuyển loại của hai mệnh đề Giả sử P và Q là hai mệnh đề. Mệnh đề tuyển loại của P và Q được kí hiệu là P ⊕ Q, là đúng khi một trong hai mệnh đề P và Q là đúng, là sai trong các trường hợp còn lại. Bảng chân trị P Q P ⊕ Q T T F T F T F T T F F F Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 7 1.1.6. Mệnh đề kéo theo Giả sử P và Q là hai mệnh đề. Mệnh đề kéo theo, được kí hiệu P → Q, là sai khi P đúng và Q sai, là đúng trong các trường hợp còn lại. Trong phép kéo theo này P được gọi là giả thiết còn Q được gọi là kết luận. Trong các suy luận toán học phép kéo theo P → Q được dùng để diễn đạt “Nếu P thì Q” Ví dụ: Cho hai mệnh đề P và Q như sau P = " tam giác T là đều " Q = " tam giác T có một góc bằng 600 " P → Q = " nếu tam giác T là đều thì tam giác T có một góc bằng 600 " P Q P → Q T T T T F F F T T F F T 1.1.7. Mệnh đề tương đương Giả sử P và Q là hai mệnh đề. Mệnh đề tương đương, được kí hiệu bởi P⇔Q, là đúng khi P và Q có cùng giá trị chân lí, là sai trong các trường hợp còn lại. Mệnh đề P ⇔ Q còn được gọi là mệnh đề hai điều kiện. Trong các suy luận toán học phép tương đương P ⇔ Q được dùng để diễn đạt “P nếu và chỉ nếu Q” hay “P là cần và đủ đối với Q” P Q P ⇔ Q T T T T F F F T F F F T Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 8 1.2. CÁC PHÉP TOÁN LOGIC VÀ CÁC PHÉP TOÁN TRÊN BÍT Các máy tính dùng các bit để biểu diễn thông tin. Một bit có 2 giá trị khả dĩ là 0 và 1. Bit cũng có thể được dùng để biểu diễn chân trị, vì giá trị chân lí của một mệnh đề cũng chỉ có hai giá trị đúng hoặc sai. Thường người ta dùng bit 1 để biểu diễn chân trị đúng (True) và bit 0 để biểu diễn chân trị sai (False). Một biến được gọi là biến Boole nếu giá trị của nó hoặc đúng hoặc sai do đó cũng có thể dùng bit để biểu diễn một biến Boole Các phép toán trên bit trong máy tính tương ứng với các liên từ logic. Bằng cách thay đúng bằng 1 và sai bằng 0 trong bảng chân trị đối với các toán tử phủ định, tuyển, hội, tuyển loại ta sẽ nhận được bảng các phép toán bit tương ứng. Chúng ta sẽ dùng các kí hiêu NOT, OR, AND và XOR thay cho các toán tử trên. Thông tin thường được biển diễn bằng cách dùng các xâu bit, đó là các dãy số 0 và 1. Khi đó các phép toán trên xâu bit cũng có thể được dùng để thao tác thông tin trên đó. Định nghĩa: Một xâu bit (hoặc xâu nhị phân) là dẫy không hoặc nhiều bit. Độ dài của xâu là số các bit trong xâu đó. Ví dụ: 101011 là một xâu bit có độ dài là 6 Có thể mở rộng các phép toán trên bit tới các xâu bit. Ta định nghĩa các OR bit, AND bit và XOR bit đối với 2 xâu bit có cùng độ dài là các xâu có các bít của chúng là các OR, AND, XOR của các bit tương ứng trong 2 xâu tương ứng. (đảo bit được thực hiện bởi NOT bit) Ví dụ: Tìm OR bit, AND bit và XOR bit đối với 2 xâu sau đây 01 1011 0110 11 0001 1101 11 1011 1111 OR bit 01 0001 0100 AND bit 10 1010 1011 XOR bit Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 9 1.3. SỰ TƯƠNG ĐƯƠNG CỦA CÁC MỆNH ĐỀ Định nghĩa: Các mệnh đề P và Q được gọi là tương đương logic nếu P↔Q là hằng đúng. Kí hiệu P≡Q để chỉ P và Q là tương đương logic. Một các để xác định hai mệnh đề có tương đương logic không là lập bảng chân trị. Dựa vào bảng nếu các cột cho giá trị của chúng phù hợp với nhau, từ đó kết luận rằng các mệnh đề đó là tương đương logic. Sau đây là ví dụ minh họa Ví dụ: Chứng minh rằng P→ Q và ¬Q→ ¬P là tương đương logic P Q P→ Q ¬P ¬Q ¬Q→ ¬P T T T F F T T F F F T F F T T T F T F F T T T T Dựa vào bảng ta thấy cột 3 và cột 6 có các giá trị tương ứng phù hợp với nhau. Vậy P→ Q và ¬Q→ ¬P là tương đương logic.(đpcm) Ta nhận thấy rằng đối với một mệnh đề phức hợp việc lập bảng gặp nhiều khó khăn vì nếu có n mệnh đề phải cần ít nhất 2n hàng. Do vậy trong những trường hợp này người ta sử dụng các luật để chứng minh các tương đương logic. Các tương đương logic Tương đương Tên gọi p∧T≡p p˅F≡p Luật đồng nhất p∧F≡F p˅T≡T Luật nuốt(luật trội) p∧p≡p p˅p≡p Luật lũy đẳng ¬(¬p)≡p Luật phủ định kép Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 10 p∧q≡ q∧p p˅q≡q˅p Luật giao hoán (p˅q)˅r≡p˅(q˅r) (p∧q) ∧r≡p∧(q∧r) Luật kết hợp p˅(q ∧ r)≡ (p˅q) ∧(p˅r) p∧(q ˅ r)≡ (p∧q) ˅(p∧r) Luật phân phối ¬(p∧q)≡ ¬p˅¬p ¬(p˅q)≡ ¬p∧¬q Luật De Morgan p˅(p ∧ q) ≡p p∧(p ˅ q) ≡p Luật thu hút p˅¬p ≡T p∧¬p≡F Luật phủ định(luật xóa) Ví dụ: Chứng minh rằng ¬(p˅(¬p∧q)) và ¬p∧¬q là tương đương logic Giải: Áp dụng các luật ta có các tương đương logic sau ¬(p˅(¬p∧q)) ≡ ¬p∧¬(¬p∧q) theo luật De Morgan ≡ ¬p∧ (¬(¬p)˅¬ q) theo luật De Morgan ≡ ¬p∧ (p˅¬ q) theo luật phủ định kép ≡ (¬p∧ p)˅(¬p∧¬q) theo luật phân phối ≡ F˅(¬p∧¬q) vì (¬p∧ p) ≡ F ≡ (¬p∧¬q) ˅F theo luật giao hoán ≡ (¬p∧¬q) theo luật dồng nhất Vậy ¬p(p˅(¬p∧q)) và ¬p∧¬q là tương đương logic.(đpcm) 1.4. LƯỢNG TỪ VÀ VỊ TỪ 1.4.1. Hàm mệnh đề: Trong thực tế ta thường gặp các câu liên quan đến các biến như “ x+y= 5”; “x lớn hơn 5”; “x-y<5”. Các câu này không đúng cũng không sai chừng nào các biến còn chưa nhận những giá trị cụ thể. Câu “ x lớn hơn 5” có hai bộ phận. Bộ phận thứ nhất biến x là chủ ngữ của câu. Bộ phận thứ hai “lớn hơn 5” là vị từ nó cho biết một tính chất mà chủ ngữ có thể có. Chúng ta gọi P(x) là câu “ x lớn hơn 5” với P là kí hiệu vị từ, x Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 11 là biến. Ta nói P(x) là giá trị của hàm mệnh đề P tại x. Biến x được gán cho một giá trị cụ thể nào đó thì câu P(x) trở thành một mệnh đề và có một giá trị chân lí. Ví dụ với x=3 thì giá trị chân lí của P(3) là sai (F) Như vậy hàm mệnh đề là một câu có chứa biến (xét trong tập hợp D) và trở thành mệnh đề khi thay biến đó bằng một hằng trong D. Tập hợp D gọi là miền xác định (hay không gian thực) của hàm mệnh đề. Ví dụ: Xét câu If (x>10) then x:=x-1; Khi gặp câu này trong chương trình giá trị biến x tại thời điểm đó sẽ được đặt vào P(x)=” x lớn hơn 10”, nếu P(x) là đúng với giá trị của x thì máy tính sẽ thực hiện lệnh gán x:=x-1 tức là giá trị của x tại thời điểm đó sẽ giảm đi 1. Còn P(x) là sai thì lệnh gán sẽ không thực hiện khi đó giá trị của x không thay đổi. 1.4.2. Lượng từ Khi tất cả các biến của một hàm mệnh đề được gán cho giá trị xác định thì mệnh đề tạo thành có giá trị chân lí. Tuy nhiên có một cách quan trọng khác để biến các hàm mệnh đề thành các mệnh đề người ta gọi là sự lượng từ hóa (hay còn gọi là lượng từ), bao gồm hai loại đó là lượng từ hóa phổ quát (với mọi) và lượng từ hóa tồn tại. Mối liên hệ giữa vị từ và lượng từ gọi là phép tính vị từ Định nghĩa: Lượng từ hóa phổ quát (với mọi) của P(x) là mệnh đề “P(x) đúng, với mọi giá trị của x trong không gian thực”. Lượng từ hóa “với mọi” của P(x) được kí hiệu ∀x P(x), trong đó ∀ được gọi là lượng từ hóa phổ quát (với mọi) Ví dụ: Giả sử P(x) là câu “x+2>x”. Ta thấy P(x) là đúng mới mọi số thực x, nên lượng từ hóa ∀x P(x) là đúng. Ví dụ: Cho P(x) là câu “x>5”. Xác định giá trị chân lí của lượng từ hóa ∀x P(x), với không gian là tập hợp các số thực. Ta thấy P(x) không đúng với x=3 do đó ∀x P(x) là sai Định nghĩa: Lượng từ hóa tồn tại của P(x) là mệnh đề “Tồn tại một phần tử x trong không gian thực sao cho P(x) đúng ”. Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 12 Lượng từ hóa tồn tại của P(x) được kí hiệu ∃xP(x), trong đó ∃ được gọi là lượng từ tồn tại Ví dụ: Cho P(x) là câu “x>5”. Xác định giá trị chân lí của lượng từ hóa ∃xP(x), với không gian là tập hợp các số thực. Ta thấy P(x) đúng với x=6 do đó ∃xP(x) là đúng 1.4.3. Các biến bị ràng buộc Khi một lượng từ được dùng với biến x hoặc khi gán giá trị cho biến đó. Ta nói rằng thâm nhập của biến là bị ràng buộc. Thâm nhập của biến không bị ràng buộc gọi là biến tự do. Ví dụ: Trong câu ∃xP(x,y), biến x là bị ràng buộc bởi lượng từ ∃x, còn biến y là tự do 1.4.4. Phủ định Chúng ta lần lượt xét phép phủ định của một biểu thức chứa lượng từ. Phủ định của lượng từ phổ quát Ví dụ: Hãy xét phủ định của câu sau “Tất cả các sinh viên đã học môn toán rời rạc”. Đây là một lượng từ hóa phổ quát ∀x P(x), trong đó P(x) là câu “ x đã học môn toán rời rạc”. Phủ định của câu này là “ Không phải tất cả các sinh viên đã học môn toán rời rạc”. Điều này tương đương với “ Có một sinh viên ở lớp này chưa học môn toán rời rạc”. Đây là lượng từ tồn tại của phủ định hàm mệnh đề ban đầu P(x). ∃x¬P(x) điều này minh họa cho tương đương logic sau: ¬∀x P(x)≡ ∃x¬P(x) Phủ định của lượng từ tồn tại Ví dụ: Hãy xét phủ định của câu sau “Có một sinh viên đã học môn toán rời rạc”. Đây là lượng từ tồn tại ∃x P(x), trong đó P(x) là câu “ x đã học môn toán rời rạc”. Phủ định của câu này là “ Không có sinh viên nào đã học môn toán rời rạc”. Điều này tương đương với “ Tất cả các sinh viên chưa học môn Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 13 toán rời rạc”. Đây là lượng từ hóa phổ quát của phủ định hàm mệnh đề ban đầu P(x). ∀x¬P(x) điều này minh họa cho tương đương logic sau : ¬∃xP(x) ≡∀x ¬P(x) 1.5. CÁC PHƯƠNG PHÁP CHỨNG MINH Mỗi bài toán chứng minh thông thường đều có hai phần chính là giả thiết và kết luận do vậy các phương pháp chứng minh dựa trên bảng chân trị của mệnh đề kéo theo P→Q (chỉ sai khi P đúng Q sai) 1.5.1. Một số khái niệm Định lí là một phát biểu có thể chứng tỏ được là đúng. Việc chứng tỏ một phát biểu là đúng bằng một dãy các mệnh đề tạo thành một suy luận gọi là sự chứng minh. Những mệnh đề dùng chứng minh bao gồm tiên đề hoặc định đề là những giả thiết cơ sở, các cấu trúc toán học và những định lí đã được chứng minh từ trước. Một định lí đơn giản dùng để chứng minh một đinh lí khác gọi là bổ đề Các qui tắc suy luận là các cách rút ra các kết luận từ những điều khảng định khác. Một số dạng suy luận sai thường gặp được gọi là các ngụy biện. Mệnh đề được suy ra trực tiếp từ định lí đã được chứng minh gọi là hệ quả. Mệnh đề mà giá trị chân lí của nó chưa biết gọi là phỏng đoán. Khi tìm ra chứng minh của một phỏng đoán thì phỏng đoán đó trở thành định lí. 1.5.2. Các qui tắc suy luận Một hằng đúng “nếu P và Q thì R” (P∧Q) →R được viết theo cách sau P Q ∴R Kí hiêu ∴ có nghĩa là “vậy thì” Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 14 Các qui tắc suy luận Qui tắc Hằng đúng Tên gọi P ∴P ˅Q P→(P˅Q) Qui tắc cộng P∧Q ∴P (P∧Q)→P Qui tắc rút gọn P Q ∴P∧Q (P∧Q)→(P∧Q) Qui tắc kết hợp P P→Q ∴Q (P∧(P→Q))→Q Qui tắc Modus Ponens ¬Q P→Q ∴¬P (¬Q∧(P→Q))→¬P Qui tắc Modus Tollens P →Q Q→R ∴P→R ((P→Q)∧(Q→R))→(P→R) Qui tắc tam đoạn luận giả định P˅Q ¬P ∴Q ((P˅Q)∧¬P)→Q Qui tắc tam đoạn luận tuyển P˅Q ¬P˅R ∴Q˅R ((P˅Q)∧(¬P˅R))→(Q˅R) Qui tắc phân giải 1.5.3. Chứng minh trực tiếp Mệnh đề Q được chứng minh trực tiếp nếu Q là mệnh đề cuối cùng của dãy Q1, Q2,… Qn-1, Qn , Q Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 15 Ví dụ: Chứng minh rằng nếu n là số nguyên chẵn thì n2 cũng là số nguyên chẵn. Giải: Thật vậy vì n là số nguyên chẵn nên tồn tại số nguyên k sao cho n=2.k. Từ đó suy ra n2= (2.k)2 = 2. (2.k2) =2. K (với số nguyên K=2.k2). Vậy n2 là số nguyên chẵn 1.5.4. Chứng minh gián tiếp Để chứng minh mệnh đề Q ta chứng minh mệnh đề phản đảo của Q hoặc bác bỏ phủ định của Q Ví dụ: Chứng minh rằng “Hai đường thẳng cùng vuông góc với đường thẳng thứ ba thì song song với nhau”. Mệnh đề phải chứng minh có dạng P∧Q→R là đúng. Ta đi chứng minh phủ định của mệnh đề này có dạng P∧Q→¬R là sai. Giải: Thật vậy giả sử a và b cắt nhau tại điểm I. Qua I chỉ có thể dựng được một đường thẳng vuông góc với đường thẳng cho trước nên a và b trùng nhau mâu thuẫn với giả thiết vậy P∧Q→¬R là sai do đó P∧Q→R là đúng. 1.5.5. Chứng minh rỗng Ta thấy P→Q chỉ sai khi P đúng Q sai. Vậy để chứng minh mệnh đề này đúng ta chứng minh P sai. Phương pháp này gọi là chứng minh rỗng Ví dụ: Cho hàm mệnh đề P(x)= “Nếu x>1 thì x2>x”, chứng minh rằng P(1) là đúng Giải : Ta có P(1)= {Nếu 1>1 thì 12>1}. Ta biết 1>1 là sai vậy P(1) đúng 1.5.6. Chứng minh tầm thường Tương tự vì P→Q chỉ sai khi P đúng Q sai. Vậy để chứng minh mệnh đề này là đúng ta chứng minh Q đúng. Phương pháp này gọi là chứng minh tầm thường Ví dụ: Cho hàm mệnh đề P(n)= “Nếu x và y là hai số nguyên dương và x ≥ y thì xn ≥ yn ”. Chứng minh rằng P(0) là đúng Giải : Ta có a0=b0=1 vậy a0 ≥ b0 là đúng nên P(0) đúng Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 16 1.5.7. Chứng minh bằng phản chứng Để chứng minh mệnh đề Q là đúng. Trước hết ta giả sử ngược lại rằng Q là sai hay ¬Q là đúng. Từ đó dẫn đến một kết luận ¬Q→R mà R mâu thuẫn với P. Ví dụ: Chứng minh rằng “ 2 là số vô tỉ ”. Giải : Giả sử 2 không là số vô tỉ . Vậy 2 là số hữu tỉ. Khi đó ∃a,b∈N ; (a,b)=1 sao cho 2 = b a . Bình phương 2 vế ta được 2b2=a2 điều này chứng tỏ rằng a là số chẵn đặt a=2d suy ra b2=2d2 vậy b chẵn có nghĩa là (a,b)=2 mâu thuẫn (a,b)=1. Vậy 2 phải là số vô tỉ. 1.5.8. Chứng minh tồn tại Trong thực tế nhiều định lí được phát biểu như các mệnh đề có chứa lượng từ. Một định lí loại này là mệnh đề có dạng ∃xP(x),với P là vị từ. Chứng minh mệnh đề ∃xP(x) gọi là chứng minh tồn tại. Đôi khi chứng minh tồn tại được thực hiện bằng cách chỉ ra một phần tử a sao cho P(a) đúng. Nhưng đôi khi không thể chỉ ra dược phần tử a như vậy người ta thường sử dụng phương pháp chứng minh phản chứng để từ đó chỉ ra điều mâu thuẫn Ví dụ: Chứng minh rằng phương trình x2= y2+ z2 có nghiệm nguyên. Giải: Sau khi tính toán ta được 52=42+32 vậy phương trình đã cho có nghiệm nguyên. (đpcm) 1.5.9. Chứng minh tính duy nhất Một định lí khảng định sự tồn tại duy nhất của một phần tử có tính chất cụ thể nào đó. Như vậy chứng minh tính duy nhất có hai phần Tồn tại: Chỉ ra rằng tồn tại phần tử a có tính mong muốn Duy nhất: chứng minh rằng nếu b≠ a thì b không có tính mong muốn. Ví dụ: Chứng minh rằng mọi số nguyên dương P đều tồn tại duy nhất một số đối của nó. Giải: (tồn tại) Với số nguyên dương P ta có P+Q =0 nên số đối Q=-P (duy nhất) giả sử R≠Q và P+R=0 từ nhận xét trên ta có P+Q = P+R=0 suy ra Q=R mâu thuẫn với giả thiết R≠Q. (đpcm) Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 17 1.5.10. Những sai lầm trong chứng minh Những sai lầm trong chứng minh thường gặp biểu hiện ở các khía cạnh sau đây: a. Suy luận không hợp logic thường theo các sơ đồ sau ((P→Q)∧¬P)→¬Q ((P→Q)∧P)→P ((P˅Q)∧P)→¬Q Ví dụ: Các câu có dạng “bao giờ có P thì có Q”, ngầm hiểu “không bao giờ có Q vậy thì không bao giờ có P” b. Dựa vào tiên đề sai hoặc tiên đề chưa được chứng minh hoặc dựa vào một điều không đúng với giả thiết. Ví dụ: Tìm chỗ sai trong chứng minh sau: "Nếu x không dương thì x2 không dương". Chứng minh: Giả sử x là không dương. Vì mệnh đề kéo theo "Nếu x dương thì x2 cũng dương" là đúng nên ta kết luận rằng x2 là không dương Giải: Gọi P(x) là câu " x là dương" và Q(x) là câu "x2 là dương" mệnh đề "Nếu x dương thì x2 cũng dương" chính là mệnh đề ∀x(P(x)→ Q(x)). Từ giả thiết "x là không dương" tức là ¬P(x) đúng. Từ hai điều này ta không thể kết luận "x2 là không dương" hay ¬Q(x) là đúng. Đây là một sai lầm trong suy luận không hợp thức. Trong quá trình học tập việc mắc sai lầm trong chứng minh là không thể tránh khỏi. Song khi mắc phải một sai lầm mà có ai đó chỉ ra thì bạn hãy nên phân tích kĩ lưỡng mình đã sai ở điểm nào để đảm bảo chắc chắn rằng lần sau sẽ không mắc phải chính sai lầm đó nữa có như vậy bạn mới thành công. Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 18 BÀI TẬP CHƯƠNG I Bài tập tính toán 1.1.1. Lập bảng chân trị của mệnh đề (P˅Q)→(Q˅¬R) 1.1.2. Chứng minh các mệnh đề sau đây là hằng đúng a)(¬Q∧ ((P→Q))→(¬Q∧¬P) b) ((P˅Q)∧¬P)→Q 1.1.3. Gọi P(x) là hàm mệnh đề “ x là số chẵn” với không gian là tập các số tự nhiên. Hãy phát biểu các mệnh đề sau đây thành lời và xét giá trị chân lí của chúng : P(2) ; P(7) ; P(20) ; P(125) ; ∃xP(x) ; ∀x P(x). 1.1.4. Gọi Q(x) là hàm mệnh đề “10+ x=2”. Hãy dùng kí hiệu đó để chỉ các mệnh đề sau : “ 10+5=2”; “10-7=2 ”; “Có một x sao cho 10+x=2 ”; “Với mọi x, 10+x=2” ;“Không có x nào sao cho 10+x không bằng 2 ”. 1.1.5. Tìm chỗ sai trong chứng minh sau Chứng minh rằng nếu 2 số a và b nguyên tố cùng nhau thì a+b và a.b cũng là nguyên tố cùng nhau Chứng minh: Giả sử a+b và a.b không nguyên tố cùng nhau, tức là (a+b,a.b)=d với d≠1. Vì d là ước của a.b nên d phải là ước của a hoặc của b. Nếu d là ước của a thì do d là ước a+b nên d cũng là ước của b. Cũng vì lí do đó nếu d là ước của b thì d cũng là ước của a. Như vậy (a, b)=d mà d≠1. Điều này trái với giả thiết là a, b nguyên tố cùng nhau 1.1.6. Cho vị từ P(x,y) = {x đã học môn y} với không gian của x là tập hợp tất cả các sinh viên lớp bạn và không gian của y là tập hợp tất cả các môn tin học của học kỳmà bạn đang học. Hãy diễn đạt các lượng từ sau thành các câu thông thường: a) ∃x ∃y P(x,y) b) ∃x ∀y P(x,y) c) ∀x ∃y P(x,y) d) ∃y ∀x P(x,y) e) ∀y ∃x P(x,y) f) ∀x ∀y P(x,y) 1.1.7. Cho vị từ: P(x) = {x nói được tiếng Anh} Q(x) = {x biết ngôn ngữ C++} Cho không gian là tập hợp các sinh viên lớp bạn. Hãy diễn đạt các câu sau bằng cách dùng P(x), Q(x), các lượng từ và các phép toán logic. a) Có một sinh viên ở lớp bạn nói được tiếng Anh và biết C++ b) Có một sinh viên ở lớp bạn nói được tiếng Anh nhưng không biết C++ c) Mọi sinh viên ở lớp bạn đều nói được tiếng Anh hoặc biết C++ d) Không có một sinh viên nào ở lớp bạn nói được tiếng Anh hoặc biết C++ Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH 19 1.1.8. Một giải bóng đá có n đội tham dự. Các đội thi đấu vòng tròn một lượt. Trong mỗi trận đội thắng được 2 điểm hòa được 1 điểm và thua được 0 điểm. Các đội có cùng số điểm sẽ được xếp hạng theo các chỉ số phụ nào đó. Khi kết thúc giải đội vô địch được 8 điểm, đội xếp thứ nhì được 6 điểm và đội xếp thứ ba được 5 điểm. Các đội còn lại có số điểm khác nhau. Hãy cho biết số đội đã tham dự giải và điểm của các đội còn lại. 1.1.9. Một vận động viên thi bắn súng. Vận động viên đã bắn hơn 11 viên và đều bắn trúng vào các vòng 8,9,10 điểm. Kết quả tổng số điểm là 100. Hỏi vận động viên đó bắn bao nhiêu viên và kết quả bắn vào các vòng ra sao? 1.1.10. Cho a và b là hai số nguyên dương. Biết rằng, trong 4 mệnh đề sau đây có 3 mệnh đề đúng và 1 mệnh đề sai. Hãy tìm mọi cặp số (a, b) có thể có. 1/ a+1 chia hết cho b 2/ a = 2b + 5 3/ a+b chia hết cho 3 4/ a+7b là số nguyên tố Bài tập trên máy tính 1.2.1. Cho n bit dữ liệu. Hãy lập trình cho biết cần bao nhiêu byte để mã hóa n bit dữ liệu trên 1.2.2. Chỉ sử dụng các câu trả lời có hoặc không. Lập trình đoán số tuổi của một người với số lần trả lời là ít nhất (quy định tuổi tối đa là 120) 1.2.3. Cho hai xâu bít có độ dài n. Lập trình tìm AND bit, OR bít và XOR của hai xâu bít đó (mở rông bài toán cho k xâu bit cùng độ dài n) 1.2.4. Liệt kê tất cả các xâu bít với độ dài n 1.2.5. Biết rằng trong 25 ngày được chọn thì ít nhất có 3 ngày cùng rơi vào một tháng trong năm. Lập trình chỉ ra đó là những ngày nào? Viết tiểu luận 1.3.1. Logic mờ là gì ? Hãy tham khảo logic mờ được áp dụng như thế nào trong những ứng dụng thực tế. 1.3.2. Khái niệm hàm lần đầu tiên xuất hiện ở đâu và mô tả xem khái niệm này lần đầu tiên được dùng như thế nào ? 1.3.3. Hãy sưu tầm các câu đố logic. 1.3.4. Hãy sưu tầm các bài toán ngụy biện 1.3.5. Tìm các số nguyên dương không là tổng các lập phương của chín số nguyên dương khác nhau.