Các phép toán trên mệnh đề

Giới thiệu

Nội dung Logic cung cấp cho học sinh những kiến thức cơ bản về logic mệnh đề, các quy tắc suy diễn. Về hình thức, nội dung này không có trong chương trình THPT (ngoài phần đại số mệnh đề ở lớp 10), không có trong đề thi tốt nghiệp, đề thi đại học. Tuy nhiên, đây là nội dung rất quan trọng đối với học sinh:

Tư duy logic giúp học sinh biết cách lập luận chặt chẽ, biết cách loại suy, suy diễn để học một biết hai, ba. Học logic tốt sẽ thực hiện chứng minh tốt hơn. Logic cũng giúp viết văn chặt chẽ, súc tích, giúp học ngoại ngữ nhanh và nhẹ nhàng hơn. Logic cũng giúp cả trong

… thi trắc nghiệm để tăng khả năng đúng. Tư duy logic cùng với tư duy phản biện tạo thành cặp phạm trù tương hỗ quan trọng trong kỹ năng cần có của một người.

Tóm tắt nội dung: Khái niệm mệnh đề. Các phép toán trên mệnh đề. Bảng chân trị, mệnh đề tương đương. Luật logic. Vị từ và lượng từ. Quy tắc suy diễn. Lý thuyết chứng minh.

Các phương pháp và kỹ thuật chứng minh.

Tài liệu tham khảo

1. Nguyễn Hữu Anh: Toán rời rạc, Nhà xuất bản Giáo dục, 2003 2. Đỗ Đức Giáo: Toán rời rạc, NXB Đại học quốc gia Hà Nội, 2000

3. Đặng Huy Ruận: Bảy phương pháp giải các bài toán logic, NXB Khoa học và Kỹ thuật 2002.

4. Kenneth H.Rosen: Discrete Mathematics and Its applications, McGraw Hill, 2011

5. Larry Cusick, How to Write Proofs,

http://zimmer.csufresno.edu/~larryc/proofs/proofs.html

1. Khái niệm mệnh đề

Mệnh đề là phát biểu mà tính đúng sai được xác định. Ví dụ về mệnh đề và không mệnh đề.

Hà Nội là thủ đô của Việt Nam 6 > 5

12 là số nguyên tố

x > 5

Mấy giờ rồi?

Vui quá!

Các mệnh đề đơn thường được ký hiệu là p, q, r, s, t, u, v, … 2. Các phép toán trên mệnh đề

Từ các mệnh đề đơn, ta có thể tạo ra các mệnh đề phức bằng các cấu trúc (trong toán gọi là các phép nối)

Giới thiệu về các phép nối liền (hội, và) (), nối rời (tuyển, hoặc) (), kéo theo (), kéo theo hai chiều () và phép phủ định ().

p  q là mệnh đề chỉ đúng khi cả p và q cùng đúng p  q là mệnh đề chỉ sai khi cả p và q cùng sai p  q chỉ sai khi p đúng q sai.

p  q đúng khi p, q cùng chân trị

p

(p  q)  (r  p)

3. Bảng chân trị của dạng mệnh đề. Tương đương logic.

Bảng chân trị là bảng ghi tính đúng sai của dạng mệnh đề phụ thuộc theo tính đúng sai của các mệnh đề cấu thành

Ví dụ p  q = p  q.

p q r p (p  q) (r  p) (p  q)  (r  p)

0 0 0 1 0 1 1

0 0 1 1 0 1 1

0 1 0 1 0 1 1

0 1 1 1 0 1 1

…

(còn 4 dòng nữa )

p  q = p  q

p q p  q p p q

0 0 1 1 1

0 1 1 1 1

1 0 0 0 0

1 1 1 0 1

4. Các luật logic (liên quan đến 3 phép toán , , 

Luật giao hoán, luật kết hợp, luật phân phối, luật De Morgan, luật phần tử trung hòa, luật phi mâu thuẫn, luật bài trung, luật lũy đẳng, luật thống trị, luật phủ định của phủ định, luật hấp thụ.

Giao hoán: p  q = q  p

Kết hợp (p  q)  r = p  (q  r) Phân phối: (p  q)  r = (p  r)  (q  r) (p  q)  r = (p  r)  (q  r) De Morgan: (p  q) =  p  q

p  0 = p p  p = p p  1 = 1

Giải hệ {x² = y + 2, y² = x+2}  (x²-y²=y-x, x² = y+2}  {(x-y)(x+y+1) = 0, x² = y+2}

 {x-y=0, x² = y+2}  {x+y+1 = 0, x²=y+2}

Tính đối ngẫu của cặp phép toán , . (Trong các công thức, nếu hoán vị hai phép toán này thì ta thu được công thức đúng).

Luật hấp thụ là p ∧ (p ∨ q) ⟺ p

Ý nghĩa của một số luật.

Ví dụ áp dụng. Lấy phủ định của mệnh đề “Nếu trời mưa và bạn không đến đón thì tôi không đi học”.

p := trời mưa

q := bạn không đến đón

r: = tôi không đi học  [(p  q)  r] =  [ (p  q)  r]

=   (p  q)   r = (p  q)   r

= Trời mưa và bạn không đến đón mà tôi vẫn đi học.

Chân lý và mâu thuẫn Các quy tắc thay thế.

Quy tắc thay thế thứ nhất: Trong một dạng mệnh đề, nếu ta thay các thành phần bằng các dạng mệnh đề tương đương logic thì ta được dạng mệnh đề mới tương đương logic với dạng mệnh đề cũ.

Quy tắc thay thế thứ hai:

p  q = p  q (p  q)  r =  (p  q)  r (a+b)³ = a³ + b³ + 3ab(a+b)

(a+b+c)³ = a³ + b³ + c³ + 3(a+b)(b+c)(c+a) [(a+b)+c]³ = (a+b)³ + c³ + 3(a+b)c(a+b+c) 0, 1, p, q, p, q, p  q, p  q, ….

[(p  q)  p]  (q  p) p  q = p.q

p  q = p + q – pq

p = 1 – p

p  q = 1 – p + pq

[(p  q)  p]  (q  p) [(p  q)  p] = 1 – pq + pqp = 1.

p  q = p  q = (1-p) + q – (1-p)q = 1 – p + q – q + pq = 1 – p + pq

(p  q)  r = (p  r)  (q  r)

(p+q-pq)r = pr + qr – pqr = pr + qr – pr.qr = pr V qr

5. Vị từ và lượng từ

Vị từ = mệnh đề chứa biến = hàm mệnh đề p(x, y): x > y.

Phát biểu chưa phải là mệnh đề, nhưng sẽ là mệnh đề khi thay biến bằng các giá trị.

Lượng từ tồn tại và với mọi,

Mô hình minh họa, nếu X = {x1, x2} thì x, p(x) = p(x1)  p(x2), x, p(x) = p(x1)  p(x2) Định lý về x , y p(x,y) và y, x p(x, y).

x  R , y  R, x > y

y  R, x  R x > y.

Định lý: Hai lượng tự cùng tên thì giao hoán, hai lượng từ khác tên thì không giao hoán.

 (x, p(x)) = x,  p(x)

4. Định lý lớn Fermat khẳng định rằng với mọi số nguyên dương n ≥ 3, không tồn tại các số nguyên dương x, y, z sao cho xⁿ + yⁿ = zⁿ. Hãy phát biểu định lý lớn Fermat dưới dạng lượng từ và vị từ, từ đó lấy mệnh đề phủ định của nó.

Với mọi n thuộc Z+, n<3-> Tồn tại n:x^n+y^n=z^n

Với mọi n thuộc N* và n>=3, với mọi x,y,z-> không x^n+y^n=z^n n  {N*| n >= 3}, x,y,z  N* => xⁿ + yⁿ ≠ zⁿ

 n  {N*, n >= 3}, x,y,z  N* và xⁿ + yⁿ = zⁿ. với mọi n thuộc N* , n=<3 , xyz thuộc R -> x^n+y^n=z^n 5. Lấy phủ định của mệnh đề sau

 > 0, N: n, n ≥ N  |xn – a | < .

thầy họ phát biểu là mọi số lớn hơn 3 thì pt ko có ngiệm vậy thì bé hơn 3 là có ngiệm nguyên.

Tồn tại epsilon > 0 sao cho với mọi N: tồn tại n , n>=N và |xn-a| >= epsilon

Tồn tại epsilon>0 mà với mọi N tồn tại n>=N và |xn-a|>epsilon Với mọi epsilon >0 tồn tại N: tồn tại n, n>=N kéo theo |xn-a|>epsilon

 (p  q) = (p V q) = p và q

tồn tại e>0; vói mọi N:tồn tại n,n>=N và |xn-a|<e

Tồn tại epsilon dương hoặc mọi N: tồn tại n,n>=N và |xn-a|>e

 > 0, với mọi N: n, n ≥ N và |xn – a | >= .

6. Các quy tắc suy diễn

Từ các tiền đề và các quy tắc suy luận suy ra các kết luận hoặc các quy tắc mới

Quy tắc khẳng định (Modus Ponens), Quy tắc phủ định (Modus Tollens), Tam đoạn luận (Syllogism) , Tam đoạn luận rời (Disjunctive Syllogism).

Modus Ponens p  q

p q

Modus Tollens p  q

q p

Tam đoạn luận p  q

q  r p  r

Tam đoạn luận rời p v q

p q

A (chứng cứ - tiền đề) B (chứng cứ - tiền đề) C (luật

D (luật E F G

(p  q) ^ (q  r)  (p  r) = 1 1) Bảng chân trị

2) Luật logic 3) Đại số hóa

Các quy tắc rút trích, tổng hợp ...

Ứng dụng của các quy tắc suy diễn (trong cuộc sống, trong hình sự ...) 7. Lý thuyết chứng minh.

Giới thiệu về các phương pháp và kỹ thuật chứng minh.

- Phương pháp chứng minh quy nạp

 n N*, A(n)  A(1) và  n N*, A(n)  A(n+1)

 A(1), A(2) và  n N*, A(n)  A(n+2) A(1)

A(1)  A(2) A(2)  A(3)

- Phương pháp chứng minh phản chứng A = A  0

Các định lý thường có dạng A  B A  B = (A B)  0 A  B = (A và B)  0 A  B = B  A

- Nguyên lý Dirichlet - Nguyên lý cực hạn - Nguyên lý bất biến

- Nguyên lý đếm bằng hai cách

- Nguyên lý song sánh

- Nguyên lý bao hàm và loại trừ Một số ví dụ

1. Peter có 4 tấm bìa 2 mặt, một mặt ghi 1 chữ cái còn mặt kia ghi một số. Peter khẳng định rằng "Nếu 1 mặt của tấm bìa ghi chữ A thì mặt kia ghi số 1". Hiện trên bàn đặt 4 tấm bìa và mặt ngửa lên ghi lần lượt là A, 1, 2, B. Hỏi phải lật 2 tấm bìa nào để kiểm tra khẳng định của Peter là đúng hay sai.

2. Có 4 chàng trai khiêm tốn là Hùng, Huy, Hoàng và Hải. Họ tuyên bố như sau:

Hùng: “Huy là người khiêm tốn nhất”

Huy: “Hoàng là người khiêm tốn nhất”

Hoàng : “Tôi không phải là người khiêm tốn nhất”

Hải: “Tôi không phải là người khiêm tốn nhất”

Hóa ra, chỉ có một tuyên bố của bốn chàng trai khiêm tốn trên là đúng. Vậy ai là người khiêm tốn nhất?

3. Từ hai mệnh đề đơn và các phép toán mệnh đề ta có thể vô số các dạng mệnh đề.

Nhưng nếu xét theo quan hệ tương đương logic, sẽ chỉ có 16 lớp tương đương như thế.

Hãy tìm 16 đại diện đơn giản cho 16 lớp tương đương này.

4. Định lý lớn Fermat khẳng định rằng với mọi số nguyên dương n ≥ 3, không tồn tại các số nguyên dương x, y, z sao cho xⁿ + yⁿ = zⁿ. Hãy phát biểu định lý lớn Fermat dưới dạng lượng từ và vị từ, từ đó lấy mệnh đề phủ định của nó.

5. Lấy phủ định của mệnh đề sau

 > 0, N: n, n ≥ N  |xn – a | < .

6. Cho biết suy luận nào trong các suy luận sau đây là đúng và Qui tắc suy diễn nào đã được sử dụng

a) Điều kiện đủ để Hoàng Anh Gia Lai thắng trận là đối thủ đừng gỡ lại vào phút cuối

Mà Hoàng Anh Gia Lai đã thắng trận

Vậy đối thủ của Hoàng Anh Gia Lai không gỡ lại vào phút cuối.

b) Nếu Bình đi làm về muộn thì vợ anh ta sẽ rất giận dữ Nếu An thường xuyên vắng nhà thì vợ anh ta sẽ rất giận dữ

Nếu vợ Bình hay vợ An giận dữ thì cô Hà bạn họ sẽ nhận được lời than phiền Mà Hà đã không nhận được lời than phiền

Vậy Bình đi làm về sớm và An ít khi vắng nhà.

7. Có 13 bạn nhỏ ngồi quanh một bàn tròn. Họ thỏa thuận với nhau là hai bạn khác giới sẽ nói dối nhau, còn hai bạn cùng giới sẽ nói thật. Một bạn nói với bạn bên phải mình

"Đa số trong chúng ta là con trai", bạn này lại nói với bạn bên phải của mình "Đa số trong chúng ta là con gái", bạn kế tiếp lại nói với bạn bên phải của mình "Đa số trong chúng ta là con trai", bạn này lại nói với bạn bên phải mình "Đa số trong chúng ta là con gái" ...

cho đến bạn cuối cùng nói với bạn đầu tiên "Đa số trong chúng ta là con trai". Hỏi có bao nhiêu bạn trai ngồi quanh bàn?

8. a) Phát biểu mệnh đề phản đảo của mệnh đề “Nếu (p-1)!+1 chia hết cho p thì p là số nguyên tố”

Nếu p là hợp số thì (p-1)! + 1 không chia hết cho p.

b) Phát biểu mệnh đề phản đảo của mệnh đề “Nếu x  y thì f(x)  f(y)”.

9. Trong Quốc hội của nước Uất kim hương, mỗi một nghị sĩ có không quá 3 kẻ thù.

Chứng minh rằng có thể chia Quốc hội thành 2 viện, sao cho trong mỗi viện, mỗi một nghị sĩ có không quá 1 kẻ thù.

10. Xét dãy Fibonacci 1, 1, 2, 3, 5, 8, … trong đó mỗi số hạng, kể từ số hạng thứ ba bằng tổng của hai số hạng trước nó. Chứng minh rằng trong dãy số này tồn tại một số tận cùng bằng 4 chữ số 0.

11. Cho ngũ giác lồi ABCDE trên mặt phẳng toạ độ có toạ độ các đỉnh đều nguyên.

a) Chứng minh rằng tồn tại ít nhất 1 điểm nằm trong hoặc nằm trên cạnh của ngũ giác (khác với A, B, C, D, E) có toạ độ nguyên.

b) Chứng minh rằng tồn tại ít nhất 1 điểm nằm trong ngũ giác có toạ độ nguyên.

c) Các đường chéo của ngũ giác lồi cắt nhau tạo ra một ngũ giác lồi nhỏ A1B1C1D1E1 bên trong. Chứng minh rằng tồn tại ít nhất 1 điểm nằm trong hoặc trên biên ngũ giác lồi A1B1C1D1E1.

12. Ngân hàng trung ương của vương quốc Ngũ bát chỉ phát hành hai loại tiền là đồng 5 quan và đồng 8 quan. Siêu thị “Nhị thập bát and more” chỉ bán các mặt hàng có giá từ 28 quan trở lên. Chứng minh rằng khách hàng có đủ cả hai loại tiền có thể mua đúng một mặt hàng bất kỳ của cửa hàng này.

13. The hardest logic puzzle ever is a riddle by the logicians Raymond Smullyan and John McCarthy that became famous in the 1990s.

Imagine there are three oracles called True, False, and Random. True always tells the truth, False always lies and Random randomly tells the truth or lies. Your task is to find out which oracle is which by asking them some yes/no questions. But there is an additional difficulty: the oracles will reply in their mystic language, either saying "DA"

or "BAL" and you don't know which one of these words means yes and which one means no.

Surprisingly, three questions are enough to solve the riddle.

Before you start pondering this, here are three things that are important to know:

1. The random oracle will decide whether or not to lie or tell the truth by secretly tossing a coin.

2. You can ask any yes/no question to any oracle of your choice.

3. You do not have to ask all questions at once. In fact, you can make use of the previous answers to adapt your questions and choose the oracle that you ask them to.

If you are struggling to find the solution, don't despair. After all, it's called the hardest logic puzzle ever. Here is the general idea behind the solution. With the first question you identify an oracle X which is not Random. You then ask the two further questions of X.

The second question identifies whether X is True or False, and the third question identifies the other two oracles.

Tính đầy đủ của dữ liệu

Cho hai dữ kiện và một câu hỏi. Có 5 phương án trả lời (A) (1) đủ, (2) không đủ

(B) (2) đủ, (1) không đủ (C) (1) và (2) gộp lại đủ (D) (1) đủ, (2) đủ

(E) (1) và (2) gộp lại cũng không đủ.

1. Nếu x là số nguyên thì giá trị của x bằng bao nhiêu?

(1) –2(x + 5) < -1 (2) – 3x > 9

A) B) C) D) E)

2. Trong ba người An, Bình, Chi, ai là người đạt số điểm cao nhất?

(1) Chi có số điểm bằng nửa số điểm mà An và Bình đạt được.

(2) An có số điểm bằng nửa số điểm mà Bình và Chi đạt được.

A) B) C) D) E)

3. Chiến mua tem hết 16.000 đồng, một số con tem giá 2.000/con tem, số còn lại giá 1.500/con tem. Hỏi Chiến đã mua bao nhiêu con tem giá 2.000?

(1) Chiến mua đúng 9 con tem.

(2) Số con tem 2.000 Chiến mua nhiều hơn số con tem 1.500 đúng 1.

A) B) C) D) E)

4. Giá trị của x bằng bao nhiêu?

(1) 3 + x + y = 14 và 2x + y = 15 (2) 3x + 2y = 12 + 2y

A) B) C) D) E)

5. Nếu John lớn hơn Bill 4 tuổi thì John bao nhiêu tuổi?

(1) Đúng 9 năm trước đây John có tuổi gấp 5 lần tuổi Bill lúc đó.

(2) Bill lớn hơn 9 tuổi.

A) B) C) D) E)

Điều thú vị là sử dụng logic, nếu chúng ta không xử lý được trọn vẹn cả hai dữ kiện thì chúng ta vẫn có thể làm tăng xác suất đúng.

Ví dụ nếu ta kiểm tra được (1) là đủ để trả lời câu hỏi, nhưng (2) thì không biết sao. Lúc đó ta sẽ chọn các phương án nào?

Ví dụ nếu ta kiểm tra được (1) là không đủ để trả lời câu hỏi, nhưng (2) thì không biết sao. Lúc đó ta sẽ chọn các phương án nào?