Toan roi rac

TRƯỜNG ĐẠI HỌC KINH TẾ
Giáo trình

TOÁN RỜI RẠC


TS. TRẦN MINH THUYẾT

Chương 1 - Cơ sở logic
Chương này dành trình bày các khái niệm cơ bản của logic mệnh đề, logic vị từ; các luật logic cơ bản, các quy tắc suy luận, phép chứng minh, nguyên lý quy nạp và định nghĩa đệ quy.
Các luật logic cơ bản giúp chúng ta hiểu được ý nghĩa chính xác của các phát biểu phức tạp. Các qui tắc suy luận cho phép chúng ta phân biệt được các lập luận đúng với các lập luận sai. Chúng cũng cho phép chúng ta hiểu được/xây dựng được những lập luận toán học đúng đắn.
Đặc trưng của toán học là tiến hành các chứng minh, nghĩa là đưa ra các kết luận mới từ những kết luận đã có mà tính đúng đắn của chúng đã được xác nhận hoặc đã được công nhận.
Các chứng minh được thực hiện thông qua các suy luận toán học. Một trong những nhiệm vụ trọng tâm của logic toán là xây dựng cơ sở cho các suy luận toán học, thiết lập các quy chuẩn về sự đúng đắn của các suy luận này.
Ví dụ

Hãy phủ định các câu nói sau đây:
1) Nếu không học bài thì A sẽ không qua được kỳ thi này.
2) Nếu làm hết các bài tập mà thầy đã cho thì A sẽ đậu điểm cao.
3) A tuy giỏi môn toán nhưng lại kém ngoại ngữ.

Ví dụ

Hãy phủ định các câu nói sau đây:
1) A vừa giỏi toán vừa giỏi tin học.
2) Mọi người trong lớp đều đã làm xong bài tập của mình.
3) Không ai trong lớp này có thể giải hết các bài tập mà thầy đã ra.
Ví dụ

Các sinh viên A, B và C đi thi. Hãy phủ định các câu nói sau đây:
1) A thi đậu còn B thi rớt.
2) Cả ba người đều thi đậu.
3) Không ai thi đậu.
Ví dụ
Lập luận nào sau đây là đúng ?
1) Nếu giải được tất cả các bài toán trong sách thì bạn sẽ thi đậu. Mà bạn đã thi đậu, vậy bạn đã giải được tất cả các bài toán trong sách.
2) Nếu giải được tất cả các bài toán trong sách thì bạn sẽ thi đậu. Mà bạn đã không giải hết các bài tập này vậy bạn không thi đậu.

Ví dụ
Lập luận nào sau đây là đúng ?
3) Nếu giải được tất cả các bài toán trong sách thì bạn sẽ thi đậu. Mà bạn đã giải hết các bài tập này vậy bạn thi đậu.
4) Nếu giải được tất cả các bài toán trong sách thì bạn sẽ thi đậu. Mà bạn đã không thi đậu vậy đã không giải hết các bài tập này.
Ví dụ
Lập luận nào sau đây là đúng ?
1) Nếu trời mưa thì đường sẽ bị ướt. Mà đường đang ướt vậy trời đã mưa.
2) Nếu trời mưa thì đường sẽ bị ướt. Mà trời không mưa vậy đường không bị ướt.
3) Nếu trời mưa thì đường sẽ bị ướt. Mà trời mưa vậy đường bị ướt.
4) Nếu trời mưa thì đường sẽ bị ướt. Mà đường không bị ướt vậy trời không mưa.
Ví dụ
Lập luận sai?
Mọi kim loại đều dẫn điện, mà đồng dẫn điện do đó đồng là kim loại.

Ví dụ
Lập luận sai?
Là người ai cũng phải ăn. Mèo cũng phải ăn. Vậy mèo là người.
Xét các ví dụ sau của Lewis Carroll. Lập luận nào trong các lập luận sau là đúng?
* Tất cả sư tử đều hung dữ.
* Một số sư tử không uống cà phê.
Vậy: Có một số sinh vật hung dữ không uống cà phê.
* Tất cả chim ruồi đều có màu sặc sỡ.
* Không có con chim lớn nào sống bằng mật ong.
* Các con chim không sống bằng mật ong đều có lông màu xám.
Vậy: Chim ruồi là nhỏ.
* Không có con vịt nào sẵn lòng khiêu vũ.
* Không có viên sĩ quan nào từ chối khiêu vũ.
* Toàn bộ gia cầm đều là vịt.
Vậy: Gia cầm không phải là các sĩ quan.
* Những đứa bé thì không logic.
* Không ai bị coi thường nếu cai quản được cá sấu.
* Những người không logic đều bị coi thường.
Vậy: Những đứa bé không cai quản được cá sấu.
Các quy tắc trong logic toán còn được dùng để thiết kế các mạng máy tính, xây dựng các chương trình máy tính và kiểm tra tính đúng đắn của các chương trình này.
1. Logic mệnh đề
Đối tượng chính của logic mệnh đề là mệnh đề.

Một câu nói khẳng định thông thường mà ta xác định được tính đúng/sai của nó được gọi là một mệnh đề.
Chú ý
1) Một mệnh đề phải hoặc đúng, hoặc sai.
2) Một mệnh đề không thể vừa đúng, vừa sai.
Giá trị chân lý đúng (True) của mệnh đề ký hiệu là 1 hoặc Yes.

Giá trị chân lý sai (False) của mệnh đề ký hiệu là 0 hoặc No.
Mệnh đề ký hiệu là P, Q, R, .
Biến mệnh đề ký hiệu là p, q, r,.
Biến mệnh đề, đó là các biến chỉ nhận một trong hai giá trị là 0/1.
Để nói P đúng, Q sai chúng ta viết
P = 1, Q = 0.
Ví dụ
p: Tồn tại ít nhất 1 số nguyên lớn hơn 100 là lũy thừa của 2.
q: Matxcơva là thủ đô của Hoa Kỳ.
r: Toronto là thủ đô của Canada.
s: 1 cộng 1 là 2 .
t: x cộng 1 là 2.
Mệnh đề phức hợp là một mệnh đề được tạo ra từ một số mệnh đề đơn giản ban đầu, bằng cách sử dụng các liên từ AND, OR, IF ... THEN hoặc trạng từ NOT.
Ví dụ (cách sử dụng liên từ hoặc)
1) Các sinh viên đã học giải tích hoặc tin học có thể theo lớp này (có thể cả 2)

2) Món khai vị: Súp hoặc xalat ( chỉ 1 trong 2, có ý loại trừ )

Chúng ta sẽ sử dụng liên từ hoặc theo nghĩa như trong câu nói thứ nhất của ví dụ trên.
Ví dụ
Nếu trời mưa thì Minh ở nhà.
Số 4 không phải là số nguyên tố.
Minh giỏi toán và tin học.
Các phép toán mệnh đề
Phủ định ? NOT
Hội ? AND
Tuyển ? OR
Tuyển loại ? XOR (eXclusive OR)
Kéo theo ? IMP
Tương đương ? EQU
Các phép toán này, được gọi chung là các phép toán logic hoặc các phép toán mệnh đề
Ví dụ
Câu nào dưới đây là mệnh đề đúng ? Giải thích.
1) 0 > 0 2) 0 ? 0
3) 1 > 0 4) 1 ? 0 5) x2 > 0
6) Nếu 3 < 4 thì 4 < 3
7) Nếu 4 < 3 thì 3 < 4
Ví dụ
X là năm nhuận nếu X chia hết cho 4 và X không chia hết cho 100, hoặc là X chia hết cho 400.

P: X chia hết cho 4,
Q: X chia hết cho 100,
R: X chia hết cho 400

Hãy biểu diễn điều kiện năm nhuận qua P, Q và R. Năm 2002 có nhuận hay không ? Tại sao ?
Ví dụ
Cho P: A thi đậu, Q: B thi đậu, R: C thi đậu.
Hãy biểu diễn qua P, Q và R các mệnh đề:
1) A đậu còn B rớt.
2) Cả 3 đều đậu.
3) Cả 3 đều rớt.
4) Chỉ có một mình A đậu.
5) Có ít nhất một người thi đậu.
* Mệnh đề phức hợp P ? Q, tương ứng với cấu trúc IF P THEN Q, được gọi là mệnh đề "Nếu P thì Q".

* Mệnh đề này sai khi P đúng và Q sai, và đúng trong mọi trường hợp còn lại.
* Mệnh đề P ? Q còn được gọi là mệnh đề nhân quả. P là nguyên nhân (hoặc: tiền đề, giả thiết), Q là hậu quả (hoặc: kết quả, kết luận).

* Đôi khi P còn du?c gọi là điều kiện đủ của Q và Q đu?c gọi là điều kiện cần của P.

Mệnh đề phức hợp P ? Q đóng vai trò rất quan trọng trong các lập luận nói chung và được phát biểu theo nhiều cách khác nhau như sau

Nếu P thì Q if P then Q
Q nếu P Q if P
Q khi P Q when P
P chỉ khi ( nếu ) Q P only if Q
P suy ra Q P implies Q
Q suy ra từ P Q follows from P
P là điều kiện đủ đối với Q P is sufficient for Q
Q là điều kiện cần đối với P Q is necessary for P
Ví dụ
P: Cảm sốt
Q: Nhức đầu
R: Nếu cảm sốt thì nhức đầu
Ta có R chính là P ?� Q, Q là điều kiện cần (triệu chứng) của P.
R còn là câu nói "nhức đầu khi cảm sốt".
Nhưng chúng ta không nói rằng "cảm sốt chỉ khi nhức đầu"!
Ví dụ
Những câu nói nào sau đây là đồng nghĩa ?
1) Nếu Minh không học bài thì Minh thi rớt.
2) Minh thi rớt nếu Minh không học bài.
3) Minh chỉ thi rớt khi Minh không học bài. 4) Nếu Minh học bài thì Minh thi đậu.
Chú thích
Ví dụ

Xét câu nói:
"Chỉ cần 7 điểm môn toán là đủ trúng tuyển".

Ở đây điều kiện đủ là gì ?
Ví dụ
Cho các mệnh đề:
P: Minh giỏi toán.
Q: Minh yếu tiếng Anh.
Biểu diễn các mệnh đề sau đây qua P và Q:

a) Minh giỏi toán nhưng yếu tiếng Anh.
b) Minh yếu cả toán lẫn tiếng Anh.
c) Minh chỉ giỏi môn Toán.
d) Nếu Minh giỏi Toán thì Minh cũng giỏi tiếng Anh.
e) Minh giỏi ít nhất một môn.
Ví dụ
Cho các mệnh đề
P: Nhiệt độ dưới 0o.
Q: Tuyết rơi.
Hãy biểu diễn các mệnh đề sau qua P và Q:
a) A: Nhiệt độ dưới 0o và tuyết rơi.
b) B: Nhiệt độ dưới 0o nhưng không có tuyết rơi.
c) C: Nhiệt độ không dưới 0o và không có tuyết rơi.
(Tiếp theo)
Ví dụ
Các phép toán bit: NOT, AND, OR, XOR
Suy ra:

x 1 = x , x  0 = 0
x  1 = 1 , x  0 = x
Ví dụ
1) Bật lên bằng 1 các bit chẵn và giữ nguyên các bit lẻ của xâu 4 bit xyzt bằng cách nào ?

2) Xóa về 0 các bit 1, 4 và giữ nguyên các bit khác của xâu 4 bit xyzt bằng cách nào ?
Ví dụ
1) Đảo (0 thành 1 và 1 thành 0) các bit lẻ và giữ nguyên các bit khác của xâu 4 bit xyzt.

2) Lấy giá trị của bit thứ 2 của xâu 4 bit xyzt.
Biểu diễn nhị phân của một số nguyên
Biểu diễn nhị phân của số 5 là xâu bit 0101, bởi vì:

0.23 + 1.22 + 0.21 + 1.20 = 5
Biểu diễn nhị phân của số 7 và số 10 lần lượt là 0111 và 1010, bởi vì:

0.23 + 1.22 + 1.21 + 1.20 = 7
1.23 + 0.22 + 1.21 + 0.20 = 10
Để thu được biểu diễn nhị phân của một số nguyên dương (nhỏ), chúng ta "đọc" từng bit của số nguyên này từ trái qua phải bằng cách sử dụng phép toán bit AND, như sau
0111 AND 1000 = 0000  0

0111 AND 0100 = 0100  1

0111 AND 0010 = 0010  1

0111 AND 0001 = 0001  1
Hãy viết một đoạn chương trình để dịch một số nguyên dương n bất kỳ ra thành xâu bit biểu diễn nhị phân của nó bằng cách dùng các phép toán bit thích hợp.
2. Biểu thức mệnh đề
Biểu thức bao gồm các biến mệnh đề p, q, r và các phép toán mệnh đề (phép toán logic) được gọi là biểu thức mệnh đề (hoặc: Dạng mệnh đề).
Nếu F và G là các biểu thức mệnh đề thì F? G, F? G, F? G, F? G cũng là các biểu thức mệnh đề.
Hãy lập bảng giá trị chân lý cho các biểu thức mệnh đề sau
Cách ký hiệu
Phép toán ? đôi khi được ký hiệu giống như phép toán nhân, như sau:

p ? q hoặc p.q hoặc pq

Ký hiệu p ? qr thay cho p ? (q ? r)
Tuy nhiên nên ký hiệu đầy đủ để tránh hiểu lầm!
Ví dụ
X là năm nhuận nếu:

(((X mod 4) = 0) AND ((X mod 100) <> 0)) OR ((X mod 400) = 0)
Một biểu thức mệnh đề F được gọi là một hằng đúng (tautology) nếu F luôn luôn đúng với mọi giá trị của các biến mệnh đề.

Ký hiệu:
F ? 1 hoặc F ? 1 hoặc F = 1.
Một biểu thức mệnh đề F được gọi là một hằng sai (mâu thuẫn, nghịch lý) nếu F luôn luôn sai với mọi giá trị của các biến mệnh đề.

Ký hiệu:
F ? 0 hoặc F ? 0 hoặc F = 0.
Biểu thức mệnh đề G được gọi là hệ quả logic của biểu thức mệnh đề F nếu biểu thức F ? G là một hằng đúng. Ký hiệu F ? G.

Khi đó, nếu F đúng thì G đúng.
Nếu F ? G và G ? F thì nói rằng F và G tương đương logic, ký hiệu F ? G.
Chúng ta có F ? G khi và chỉ khi F ? G là một hằng đúng.
Ký hiệu F ? G hoặc F ? G hoặc F = G.

Khi đó, F và G cùng đúng hoặc cùng sai.


Các luật logic cơ bản
Ví dụ
Quy tắc thay thế thứ nhất

Trong biểu thức E nếu ta thay biểu thức con F của nó bởi biểu thức F1 tương đương logic với F thì biểu thức E1 mới nhận được tương đương logic với E.
Quy tắc thay thế thứ hai

Giả sử E(p, .) là một hằng đúng. Khi đó nếu thay biến mệnh đề p bởi biểu thức P thì biểu thức mới nhận được vẫn là hằng đúng.
Ví dụ
Hãy chỉ ra các hằng đúng:
a) (p ? q) ? (p ? q)
b) (p ? q) ? (p ? q)
c) p ? (?q ? p)
d) p ? (p ? q)
e) p ? (p ? p)
f) (p ? q) ? [(q ? r) ? (p ? r)]
Ví dụ
Hãy chỉ ra các khẳng định đúng:
a) q ? p ? q
b) ?(p ? q) ? p
c) (p ? q) ? r ? p ? (q ? r)
d) (p ? q) ? (q ? r) ? p ? (q ? r)
Tiếp theo
e) p ? (q ? r) ? p ? r
f) p ? (q ? r) ? p ? q
g) (p ? q) ? r ? (p ? r) ? (q ? r)
h) p ? (q ? r) ? (p ? q) ? (p ? r)
i) (?p ? q) ? (p ? ?q) ? p ? q
Ví dụ
Hãy chỉ ra các khẳng định đúng:
a) p ? (p ? q) ? p ? q
b) p ? q ? ?p ? (p ? q)
c) p ? q ? ?p ? ?q
d) ?p ? ?(p ? q) ? (?p ? q)
e) [(p ? q) ? (q ? r) ? (r ? p)
? [(p ? q) ? (q ? r) ? (r ? p)]
f) (p ? q) ? (q ? r) ? (r ? p)
? (p ? q) ? (q ? r) ? (r ? p)

Ví dụ
Kiểm tra các biểu thức mệnh đề sau là hằng đúng:
a) [(p ? q) ? r] ? [?r ? ?(p ? q)]
b) [[(p ? q) ? r] ? (s ? t)] ?
[[[(p ? q) ? r] ? s] ? [[(p ? q) ? r] ? t]]

Ví dụ
Đơn giản biểu thức mệnh đề sau:

[[[(p ? q) ? r] ? [(p ? r) ? ?r]] ? ?q] ? s
Ví dụ
Lấy phủ định rồi đơn giản các biểu thức mệnh đề sau:
a) p ? (q ? r) ? (?p ? ?q ? r)
b) (p ? q) ? r
c) p ? (?q ? r)
d) p ? q ? (?p ? ?q ? r)

Ví dụ
Phủ định các mệnh đề sau:
a) Ngày mai nếu trời mưa hay trời lạnh thì tôi sẽ không ra ngoài.
b) Số 15 chia hết cho 3 nhưng không chia hết cho 4.
c) Tứ giác này không phải là hình chữ nhật mà cũng không phải là hình thoi.
d) Nếu An không đi làm ngày mai thì An sẽ bị đuổi việc.
Ví dụ
Hãy phủ định câu nói sau:

"Bạn không được phép lái xe nếu bạn cao dưới 1m5, trừ phi bạn trên 18 tuổi"
Tiếp theo
Xét các mệnh đề:

P:"Bạn được phép lái xe"
Q:"Bạn cao dưới 1m5"
R:"Bạn trên 18 tuổi"
Tiếp theo
Trừ phi ở đây được hiểu là nếu không (if not), do đó câu nói ở trên trở thành:

Không P nếu Q, trừ phi R
Không P nếu Q, nếu không R
?P nếu Q, nếu ?R
(?P nếu Q) nếu ?R
?R ? (?P nếu Q)
?R ? (Q ? ?P)
Tiếp theo
Suy ra câu phủ định là:

mặc dù cao dưới 1m5 và không đủ 18 tuổi nhưng bạn vẫn được phép lái xe.
Ví dụ
Phủ định câu nói sau:

"Bạn sẽ thi rớt môn toán trừ phi bạn học hành chăm chỉ"
Thuật ngữ
Từ đây về sau, nếu không nói gì thêm thì thuật ngữ mệnh đề được dùng để chỉ một mệnh đề đúng.
Định lý là các mệnh đề quan trọng. Bổ đề là mệnh đề được dùng riêng để chứng minh một định lý. Hệ quả là một mệnh đề có tính ứng dụng cao, được suy ra trực tiếp từ một định lý.
Tiếp theo
* Tiên đề (axiom) là các phát biểu được mọi người công nhận là đúng (không chứng minh) , chẳng hạn: Tiên đề Euclide, Tiên đề Kolmogorov,.

* Tiên đề còn gọi là nguyên lý, như nguyên lý quy nạp.
Tiếp theo
* Định lý (suy luận) thường là một hằng đúng có dạng

P ? Q

trong đó P, Q là các biểu thức mệnh đề. P là giả thiết và Q là kết luận của định lý.
Ví dụ
Xét xem suy luận sau đúng hay sai ?
Nếu An chăm học thì An thi đậu
Nếu An không đi chơi thì An chăm học
An thi trượt
------------------------------------------------
Vậy: An hay đi chơi
Ví dụ
Chứng minh biểu thức mệnh đề sau là một hằng đúng
Chúng ta có thể chứng minh điều này bằng cách lập bảng giá trị chân lý hoặc sử dụng các luật logic thích hợp để biến đổi biểu thức trên về hằng đúng.

Tuy nhiên chúng ta sẽ dùng các quy tắc suy diễn sau đây, mỗi quy tắc này về thực chất là một hằng đúng!
Ví dụ
Nếu Minh chăm học thì Minh thi đậu
Minh chăm học
----------------------------------------------
Vậy: Minh thi đậu
Ví dụ
Nếu Minh chăm học thì Minh thi đậu
Minh thi rớt
----------------------------------------------
Vậy: Minh không chăm học
Ví dụ
Nếu Bình thích đi chơi thì Bình không làm hết bài tập
Nếu Bình không làm hết bài tập thì Bình thi lại
---------------------------------------------------------
Vậy: Nếu Bình thích đi chơi thì Bình thi lại!
Ví dụ
* Chứng minh n3 + 2n luôn luôn chia hết cho 3, với mọi số nguyên n.

Xét 3 trường hợp sau đây:
n chia hết cho 3,
n chia cho 3 dư 1,
n chia cho 3 dư 2.
Ví dụ
Suy luận sau đúng hay sai ?
Nếu nghệ sĩ Văn Ba không diễn hay số vé bán ra quá ít thì đêm diễn sẽ bị hủy bỏ.
Nếu đêm diễn bị hủy bỏ thì phải trả lại tiền vé cho người xem.
Nhưng tiền vé đã không trả lại cho người xem.
---------------------------------------------------------
Vậy: Nghệ sĩ Văn Ba đã trình diễn.
Một lập luận không dựa vào một hằng đúng nào cả gọi là một ngụy biện. Ngụy biện tất nhiên là một lập luận sai!
Ví dụ
Nếu giải được tất cả các bài toán trong sách thì bạn sẽ thi đậu. Mà bạn đã thi đậu, vậy bạn đã giải được tất cả các bài toán trong sách.
Ví dụ
Nếu trời mưa thì đường sẽ bị ướt. Mà đường đang ướt vậy trời đã mưa.
Ví dụ
Nếu trời mưa thì đường sẽ bị ướt. Mà trời không mưa vậy đường không bị ướt.
Một số phép chứng minh
Chứng minh rỗng


Để chứng minh p ? q đúng chúng ta có thể chứng minh rằng p sai, bởi vì khi p sai thì hiển nhiên p ? q đúng.
Chứng minh trực tiếp là phép chứng minh xuất phát từ việc giả sử rằng p đúng, chúng ta sử dụng các quy tắc suy diễn và các kết quả đã có để chứng tỏ rằng q đúng.

Đây là phép chứng minh đi thẳng từ giả thiết đến kết luận.
Chứng minh: n lẻ ? n2 lẻ
Chứng minh gián tiếp
Cơ sở của phép chứng minh này là tương đương logic sau đây

(p ? q) ? (?q ? ?p)

Khi đó thay vì chứng minh chúng ta chứng minh (?q ? ?p).
Chứng minh: 3n + 2 lẻ ? n lẻ.
Chứng minh phản chứng
Cơ sở của phép chứng minh này là quy tắc mâu thuẫn đã nói ở trên hoặc là hằng đúng sau đây

q ? ?q ? 0

Do đó để chứng minh một mệnh đề q là đúng chúng ta xuất phát từ ?q , nếu tìm thấy mâu thuẫn 0 thì có nghĩa là q đúng.
Chứng minh theo trường hợp
Để chứng minh, chúng ta chia bài toán ra thành nhiều trường hợp. Sau đó chứng minh trong các trường hợp này bài toán luôn luôn đúng, từ đó suy ra đpcm. Cơ sở của phép chứng minh này là quy tắc chứng minh theo trường hợp.
Chứng minh: n không chia hết cho 3 ? n2?1(mod 3)

Chứng minh: Với mọi n, n3 + 2n chia hết cho 3
Chứng minh qui nạp

Xem phần nguyên lý quy nạp.
Định lý cần và đủ là mệnh đề có dạng p ? q.
Định lý này được gọi là:

Điều kiện cần và đủ để có p là có q.
Có p khi và chỉ khi có q.
Có p nếu và chỉ nếu có q.
Để chứng minh p ? q chúng ta chia làm hai bước:
1) Chứng minh p ? q,
2) Chứng minh q ? p.
4.Logic vị từ
Vị từ 1 biến
Cho X là tập bất kỳ và p là ánh xạ trên X, biến mỗi x?X thành một mệnh đề p(x).
Khi đó p(x) được gọi là vị từ 1 biến trên X. Tập X được gọi là tập xác định của vị từ.
Ví dụ: X là tập các sinh viên trong lớp, với mỗi x?X, p(x) là "x thi đậu môn toán rời rạc". Ta có p(x) là vị từ biến x.
Vị từ n biến
Vị từ còn gọi là hàm mệnh đề. Khi không sợ nhầm lẫn, chúng ta không cần chỉ rõ tập xác định của các biến vị từ.

Mệnh đề được coi là vị từ 0 biến. Một vị từ n biến, với n ? 1, không phải là một mệnh đề do đó không thể nói về tính đúng sai của nó.
Vị từ 2 biến x,y, q(x,y) = "x ? y+3" , x,y?R,
Ta có q(1,2) đúng và q(4,0) sai.
Tuy nhiên q(1,y) = "1 ? y+3" không phải là mệnh đề, nó là vị từ 1 biến y.
Lượng từ ph? d?ng ?
A�p dụng n lần các lượng từ ?, ? lên vị từ n biến p(x1,., xn) chúng ta biến vị từ này thành một mệnh đề. Mệnh đề này được gọi là mệnh đề lượng từ hóa của vị từ p(x1,., xn).
Chẳng hạn với vị từ 2 biến p(x,y) chúng ta có cả thảy 8 mệnh đề như sau:
?x, ?y, p(x,y) ?y, ?x, p(x,y)
?x, ?y, p(x,y) ?y, ?x, p(x,y)
?x, ?y, p(x,y) ?y, ?x, p(x,y)
?x, ?y, p(x,y) ?y, ?x, p(x,y)
* Một số trong các mệnh đề này trùng nhau!
Cho vị từ 2 biến p(x,y) = "x2 + y2 ? 1", x?R, y?R. Ta có:

q = "?x, ?y, p(x,y)" sai,
r = "?x, ?y, p(x,y)" đúng.
Xét vị từ p(x) = "x2 - 3x + 2 ? 0". Mệnh đề nào đúng ?
1) ?x, p(x)
2) ?x, p(x)
Cho các vị từ biến x
p(x) = "x2 - 5x + 6 = 0"
q(x) = "x2 - 4x - 5 = 0"
r(x) = "x > 0"
Hãy xác định giá trị chân lý của các mệnh đề sau
1)?x, p(x) ? r(x) 2)?x, q(x) ? ?r(x)
3)?x, q(x) ? r(x) 4)?x, p(x) ??r(x)

* Các phủ định dưới đây có đúng không ? Nếu không đúng, hãy thay bằng phủ định đúng. Xác định giá trị chân lý của các mệnh đề này.
1) Với mọi số thực x, y, nếu x2 > y2 thì x > y.
Phủ định: Tồn tại các số thực x, y sao cho x2 > y2 nhưng x ?? y.

2) Với mọi số thực x, nếu x ? 0 thì x có nghịch đảo.
Phủ định: Tồn tại số thực x khác 0 mà không có nghịch đảo.
3) Tồn tại hai số nguyên lẻ có tích là số lẻ.
Phủ định: Tích của hai số lẻ bất kỳ là số lẻ.

4) Bình phương của mọi số hữu tỷ là số hữu tỷ.
Phủ định: Tồn tại số thực x sao cho nếu x vô tỷ thì x2 vô tỷ.
Mệnh đề nào sau đây đúng ?
1) ?x, ?y, xy = 1
2) ?x, ?y, xy = 1
3) ?x, ?y, xy = 1
4) ?x, ?y, sin2x + cos2x = sin2y + cos2y
5) ?x, ?y, (2x + y = 5)?(x - 3y = - 8)
Giả sử X = {x1, ., xn}, khi đó ta có

?x, p(x) ? p(x1) ? . ? p(xn)
?x, p(x) ? p(x1) ? . ? p(xn)
?x, p(x) ? ?x, p(x)
Từ đó suy ra quy tắc phủ định


Xem phát biểu bên phải nào tương ứng với các phát biểu 1), 2), 3), 4) bên trái ?
1) (?x, p(x)) đúng a) Với mọi x, p(x) sai.
2) (?x, p(x)) sai b) Với mọi x, p(x) đúng.
3) (?x, p(x)) đúng c) Có ít nhất một x sao
cho p(x) sai.
4) (?x, p(x)) sai d) Có ít nhất một x sao
cho p(x) đúng.
Dãy (xn) được gọi là hội tụ nếu ?a?R sao cho xn ? a. Hãy phát biểu điều kiện để dãy (xn) không hội tụ.
Hàm số y = f(x) gọi là tăng (không ngặt) trên tập A nếu

??x?A, ?y?A, (x ? y) ? (f(x) ? f(y))

Hãy phát biểu điều kiện của hàm y = f(x) không tăng trên tập A.
Giả sử f: A ? B là ánh xạ từ tập A vào tập B.
1) f gọi là đơn ánh nếu
?x?A, ?y?A, (x ? y) ? (f(x) ? f(y))
2) f gọi là toàn ánh nếu
?y?B, ?x?A, y = f(x)
3) f gọi là song ánh nếu f toàn ánh và f đơn ánh.

Hãy phát biểu điều kiện để hàm f không song ánh.
Cho P = "Mọi người trong lớp đều đã làm hết các bài tập mà thầy đã cho". Hãy phủ định mệnh đề này.
Cho Q = "Chưa ai làm xong công việc của mình". Hãy phủ định mệnh đề này!
Phủ định các mệnh đề sau:
1)Với mọi số nguyên n, nếu n không chia hết cho 2 thì n là số lẻ.
2)Nếu bình phương của một số nguyên là lẻ thì số nguyên đó là số lẻ.
3)Nếu k, m, n là các số nguyên sao cho k - m và m - n là số lẻ thì k - n là số chẵn.
Phủ định các mệnh đề sau:

1) Nếu x là một số thực sao cho x2 > 16 thì
x < -4 hoặc x > 4.

2) Với mọi số thực x, nếu (x - 3)2 < 49 thì
- 4 < x < 10.
Định lý về sự hoán vị thứ tự các lượng từ

1) ?x, ?y, p(x,y) ? ?x, ?y, p(x,y)
2) ?x , ?y, p(x,y) ? ?x , ?y , p(x,y)

Mọi người đều chết.
Socrate là người
--------------------------
Do đó Socrate sẽ chết.
Quy tắc tổng quát hóa phổ dụng
* Quy tắc này được sử dụng để chứng minh mệnh đề "?x, p(x)" đúng, trong đó p(x) là vị từ 1 biến x.

* Triết lý của quy tắc này là: Để chứng minh mệnh đề "?x, p(x)" đúng, chúng ta chỉ cần chứng minh mệnh đề p(a) đúng với a được chọn bất kỳ trong tập xác định của biến x.
Chẳng hạn để chứng minh

?x, x2 + 1 ? 1

Chúng ta lập luận như sau:
Với a bất kỳ, ta có a2 ? 0 suy ra a2 + 1 ? 1. Do đó ?x, x2 + 1 ? 1.

Từ quy tắc này suy ra quy tắc tam đoạn luận "phiên bản" của vị từ như sau
Những đứa bé thì không logic.
Không ai bị coi thường nếu cai quản được cá sấu.
Những người không logic đều bị coi thường.
Vậy: Những đứa bé không cai quản được cá sấu.
Xét X là tập tất cả các con người đang sống trên thế giới!
p(x) = x là đứa bé,
q(x) = x thì không logic,
r(x) = x bị coi thường,
s(x) = x cai quản được cá sấu.


Suy luận nào sau đây là đúng ?
Mọi người đưa thư đều mang theo túi thư.
An là một người đưa thư.
Vậy An mang theo túi đựng thư.
Mọi công dân tốt đều đóng thuế.
An đã đóng thuế.
Vậy An là một công dân tốt.
Mọi người quan tâm đến môi trường đều để riêng các túi nhựa bỏ đi.
Hà không quan tâm đến môi trường.
Vậy Hà không để riêng các túi nhựa bỏ đi.
Mọi sinh viên nghiêm túc đều không nộp bài chưa làm xong.
Minh không nộp bài chưa làm xong.
Vậy Minh là sinh viên nghiêm túc.



5. Nguyên lý quy nạp
( induction principle )



Các số được nói đến ở đây đều là các số tự nhiên.
Thủ tục quy nạp bao gồm hai bước như sau:

1) Bước cơ sở:
Kiểm tra p(0) đúng.
2) Bước quy nạp:
Giả sử p(n) đúng với n = k ? 0, chứng minh p(n) đúng với n = k + 1.
Dùng phương pháp quy nạp để chứng minh số tập con của tập A có n phần tử bằng 2n.
Dùng phương pháp quy nạp để chứng minh số song ánh từ tập A ? A bằng n! , trong đó n là số phần tử của A.

6. Các vấn đề khác
Phản ví dụ
Để chứng minh biểu thức mệnh đề P(p, q, r) không phải là một hằng đúng chúng ta chỉ ra một trường hợp ?, ?, ? của p, q, r sao cho mệnh đề P(?, ?, ?) sai.

Đó là cách chứng minh bằng phản ví dụ.
Nếu không được tăng lương thì Minh sẽ nghỉ việc.
Nếu Minh nghỉ việc và vợ Minh bị mất việc thì Minh phải bán xe.
Nếu vợ Minh hay đi làm trễ thì vợ Minh sẽ bị mất việc.
Mà Minh được tăng lương.
---------------------------------------------------------------
Vậy: Nếu Minh không bán xe thì vợ Minh không đi làm trễ.
Trong đó:
p: Minh được tăng lương
q: Minh nghỉ việc
r: Vợ Minh bị mất việc
s: Minh phải bán xe
t: Vợ Minh đi làm trễ
Phán đoán đây là một suy luận sai. Chúng ta dùng một phản ví dụ để bác bỏ suy luận này!

Việc này dẫn đến một "hệ phương trình logic" như sau.
Giải hệ phương trình này chúng ta được:

p = t = r = 1, q = s = 0
Khẳng định sau đúng hay sai ?

"Mọi ma trận vuông cấp 2 không suy biến đều có định thức dương"
Định nghĩa đệ quy

* Đôi khi một đối tượng có thể được định nghĩa dễ dàng qua chính nó, đó là cách định nghĩa đệ quy.
* Chúng ta có thể dùng phép định nghĩa đệ quy để định nghĩa dãy số Fibonacci. Chúng ta cũng có thể dùng định nghĩa đệ quy để định nghĩa định thức của các ma trận hoặc định nghĩa biểu thức mệnh đề hoặc định nghĩa các hàm sơ cấp,.
Hàm sơ cấp
1) Hàm lũy thừa, hàm mũ, hàm loga, hàm lượng giác và hàm lượng giác ngược là các hàm sơ cấp.
2) Nếu u, v là các hàm sơ cấp thì u ? v, u ? v, u/v là các hàm sơ cấp.
3) Hợp của các hàm sơ cấp là hàm sơ cấp.
Ví dụ khác
Định nghĩa đệ quy tập S:
1) 3 ? S
2) nếu x,y ? S thì x+y ? S

Ta có S chính là tập tất cả các bội số dương của số 3.

Bên cạnh định nghĩa đệ quy chúng ta còn có các thuật toán đệ quy.
Thuật toán đệ quy
Một thuật toán gọi là đệ quy nếu nó cho phép quy việc giải một bài toán thông qua việc giải một bài toán khác tương tự như vậy, nhưng có các dữ kiện đơn giản hơn.

Thuật toán

Tính định thức ma trận cấp n.
Thuật toán

Tính giai thừa của một số nguyên n, bằng cách dựa vào hệ thức truy hồi
n! = n(n-1)!
Thuật toán

Tính dãy Fibonacci (an)