Chương 1_Logic mệnh đề

Chương 1. Tổng quan thiết kế mạch logic_Hướng dẫn bài tập
Chương 1. Tổng quan thiết kế mạch logic_Hướng dẫn bài tập

http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 1

CHƯƠNG

1 LOGIC

MỆNH ĐỀ

I-

MỆNH ĐỀ

I.1- Khái niệm: •

Mệnh đề

là một câu khẳng đònh đúng hoặc một câu khẳng đònh sai. • Câu khẳng đònh đúng gọi là

mệnh đề

đúng (mệnh

đề

có chân trò đúng). • Câu khẳng đònh sai gọi là

mệnh đề

sai (mệnh

đề

có chân trò sai). • Kí hiệu các

mệnh

đề: P, Q, R, …. • Kí hiệu chân trò đúng là 1 (hay T – True), chân trò sai là 0 (hay F – False) Ví dụ 1: a/ Hà Nội là thủ đô của nước Việt Nam. b/ Thượng Hải là thủ đô của Ấn Độ. c/ 5 + 5 = 10 d/ 43 chia hết cho 5 e/ Hôm nay trời đẹp quá ! f/ Hôm nay trời có đẹp không? g/ Hãy học bài đi! h/ n là một số nguyên tố Là

mệnh đề

đúng (1). Kí hiệu mđ: P Là

mệnh đề

sai (0). Kí hiệu mđ: Q Là

mệnh đề

đúng (1). Kí hiệu mđ: R Là

mệnh đề

sai (0). Kí hiệu mđ: T Không phải là

mệnh

đề. Câu cảm thán. Không phải là

mệnh

đề. Câu hỏi nghi vấn. Không phải là

mệnh

đề. Câu

mệnh

lệnh. Không phải là

mệnh

đề. Là vò từ (mệnh

đề

chứa biến).Nếu n=3 ta được

mệnh đề

đúng, n= 4 ta được

mệnh đề

sai. * Biến

mệnh

đề: p gọi là biến

mệnh đề

nếu nó nhận giá trò là một

mệnh đề

nào đó. Ví dụ 2: p là biến

mệnh đề

có thể nhận giá trò là các

mệnh đề

P, Q, R, T ở trên. I.2- Các phép toán lôgic: I.2.1: Phép phủ đònh (NOT): Phủ đònh của

mệnh đề

P kí hiệu là P . Chân trò của P là 0 nếu chân trò của P là 1 và ngược lại. Bảng chân trò của phép phủ đònh: Ví dụ 3:

mệnh đề

P: “ 2 là số hữu tỉ” P : “ 2 không phải là số hữu tỉ” ( 2 là số vô tỉ) I.2.2 Phép hội (AND): Phép hội của hai

mệnh đề

P, Q kí hiệu là P∧Q (đọc là P và Q) chỉ đúng khi cả P và Q cùng đúng. Bảng chân trò của phép hội: P Q P∧Q 0 0 1 1 0 1 0 1 0 0 0 1 Ví dụ 4: + “Chiều nay trời đẹp và trận bóng đá sẽ hấp dẫn”: P ∧Q + “Danh sách sinh viên nam và tuổi từ 20 trở lên”: P∧Q Điều kiện lọc danh sách là: (PHAI=”Nam”) AND (Year(Date())-Year(NgaySinh)>=20) P P 0 1 1 0 http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 2 + “Danh sách sinh viên nữ có quê ở Long An”: P∧Q Điều kiện lọc danh sách là: (PHAI=”Nữ”) AND (QUEQUAN=”Long An”) I.2.3 Phép tuyển (OR): Phép tuyển của hai

mệnh đề

P, Q kí hiệu là P∨Q (đọc là P hoặc Q) chỉ sai khi cả P và Q cùng sai. Bảng chân trò của phép tuyển: P Q P∨Q 0 0 1 1 0 1 0 1 0 1 1 1 Ví dụ 5: + “Danh sách sinh viên quê ở Cần Thơ hoặc/hay/và Long An”: P∨Q Điều kiện lọc danh sách là: (QUEQUAN=”Cần Thơ”) OR (QUEQUAN=”Long An”) I.2.4 Phép tuyển loại (XOR): Phép tuyển loại của hai

mệnh đề

P, Q kí hiệu là P ∨ Q (đọc là hoặc P hoặc Q) chỉ đúng khi chỉ một trong 2

mệnh đề

là đúng. Bảng chân trò của phép tuyển loại: P Q P∨ Q 0 0 1 1 0 1 0 1 0 1 1 0 Ví dụ 6: + “Sinh viên An quê ở Cần Thơ hoặc Long An”: P ∨ Q + “ 2 là số hữu tỉ hoặc là số vô tỉ”: P∨ Q + “5 giờ chiều nay Minh đi học thêm Anh văn hoặc đi dự đám cưới bạn Lan”: P ∨ Q I.2.5 Phép kéo theo: Phép kéo theo của hai

mệnh đề

P, Q kí hiệu là P ⇒ Q là một

mệnh đề

chỉ sai khi P đúng Q sai. Bảng chân trò của phép kéo theo: P Q P ⇒ Q 0 0 1 1 0 1 0 1 1 1 0 1 Ví dụ 7: + “Nếu An vượt đèn đỏ thì An sẽ vi phạm luật giao thông”: P ⇒ Q + “Vì 50 chia hết cho 10 nên 50 chia hết cho 5” (P đúng, Q đúng:

mệnh đề

đúng) + “202 là số chẵn suy ra 202 chia hết cho 4” (P đúng, Q sai:

mệnh đề

sai) Lưu ý: • P gọi là điều kiện đủ

để

có Q, hoặc Q gọi là điều kiện cần

để

có P • Q ⇒ P gọi là

mệnh đề

đảo của

mệnh đề

P ⇒ Q http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 3 I.2.6 Phép tương đương: Phép tương đương của hai

mệnh đề

P, Q kí hiệu là P ⇔ Q là một

mệnh đề

chỉ đúng khi cả P và Q cùng đúng hoặc cùng sai. Bảng chân trò của phép kéo theo: P Q P ⇔ Q 0 0 1 1 0 1 0 1 1 0 0 1 Ví dụ 8: + “Tam giác ABC có ba góc bằng nhau nếu và chỉ nếu tam giác đó có ba cạnh bằng nhau” + “36 chia hết cho 4 và chia hết cho 3 khi và chỉ khi 36 chia hết cho12” + P: “Tứ giác ABCD là hình vuông” Q: “Tứ giác ABCD là hình chữ nhật có hai đường chéo vuông góc” Ta có P ⇔ Q I.3 Phép toán bit (NOT, AND, OR, XOR: thực hiện trong máy tính) • Bit là đơn vò thông tin nhỏ nhất ứng với một trong hai kí số nhò phân 0 hoặc 1. • Chuỗi bit là chuỗi gồm các kí số 0, 1. Cho 2 chuỗi 4 bit A = 0011; B = 0101. Ta thực hiện các phép toán bít như sau: A 0 0 1 1 B 0 1 0 1 NOT A A AND B A OR B A XOR B 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 II- CÔNG THỨC

MỆNH ĐỀ

II.1 Các khái niệm II.1.1 Công thức

mệnh đề

(biểu thức lôgic) Công thức

mệnh đề

(còn gọi là biểu thức lôgic) là một biểu thức được xây dựng từ: • Các

mệnh đề

P, Q, R, …. • Các biến

mệnh đề

p, q, r, … có thể nhận giá trò là các

mệnh

đề. • Các phép toán trên các

mệnh đề

và biến

mệnh đề

theo một trật tự nào đó. Ví dụ 9: A = (p ∧q) ∨ ( r ⇒ q) E = p ∨ (q ∧ r) F = (p ∨ q) ∧ r Nhận xét: Lập bảng chân trò của E và F ta thấy E ≠ F, suy ra thứ tự thực hiện phép toán logic là rất quan trọng. II.1.2 Công thức tương đương Hai công thức E và F gọi là tương đương logic nếu chúng có cùng bảng chân trò. Kí hiệu hai công thức tương đương logic là E ≡ F hay đơn giản là E = F. Ví dụ 10: E = p ⇒ ⇒⇒ ⇒ q và F = p ∨ ∨∨ ∨ q là hai công thức tương đương (c/m bằng bảng chân trò) http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 4 p q p p ⇒ ⇒⇒ ⇒ q p ∨ ∨∨ ∨ q (p ⇒ ⇒⇒ ⇒ q) ⇔ ( p ∨ ∨∨ ∨ q) 0 0 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 (E) (F) (G) II.1.3 Công thức

mệnh đề

hằng đúng, hằng sai Công thức

mệnh đề

gọi là công thức hằng đúng nếu nó luôn nhận gía trò 1 (E ≡ 1). Công thức

mệnh đề

gọi là công thức hằng sai nếu nó luôn nhận gía trò 0 (E ≡ 0). Ví dụ 11: G = (p ⇒ ⇒⇒ ⇒ q) ⇔ ( p ∨ ∨∨ ∨ q) là công thức hằng đúng; G ≡ 1 (suy ra từ ví dụ 9). II.1.4 Qui tắc thay thế: Qui tắc 1: Nếu trong công thức

Bài Hay  Phán Đoán Phức - Phán Đoán - Logic Hình Thức (Logic Học Đại Cương)

mệnh đề

E ta thay thế một biểu thức con bởi một công thức

mệnh đề

tương đương thì được một công thức

mệnh đề

mới tương đương logic với E. Ví dụ 12: p ⇒ ⇒⇒ ⇒ (q ⇒ ⇒⇒ ⇒ r) ≡ p ⇒ ⇒⇒ ⇒ ( q ∨ ∨∨ ∨ r) ≡ p ∨ ∨∨ ∨ q ∨ ∨∨ ∨ r Qui tắc 2: Nếu E là công thức

mệnh đề

hằng đúng thì khi ta thay biến

mệnh đề

p trong E bởi một công thức

mệnh đề

tùy ý thì được một công thức

mệnh đề

mới vẫn là hằng đúng. Ví dụ 13: G = (p ⇒ ⇒⇒ ⇒ q) ⇔ ( p ∨ ∨∨ ∨ q) ≡ 1 (suy ra từ ví dụ 10) suy ra G’ = ((r ∧ ∧∧ ∧ t) ⇒ ⇒⇒ ⇒ q) ⇔ (( r t∧ ) ∨ ∨∨ ∨ q) ≡ 1 II.2 Các qui luật logic Với p, q, r là các biến

mệnh

đề, 1 là hằng đúng, 0 là hằng sai ta có các tương đương logic sau: 1/ Phủ đònh của phủ đònh: P ≡ p 2/ Qui tắc

De

Morgan: qpqp ∨≡∧ )( ; qpqp ∧≡∨ )( 3/ Luật giao hoán: p ∧ q ≡ q ∧ p ; p ∨ q ≡ q ∨ p 4/ Luật kết hợp: p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r ; p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r 5/ Luật phân phối: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p∧ r) ; p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p∨ r) 6/ Luật lũy đẳng: p ∧ p ≡ p ; p ∨ p ≡ p 7/ Luật trung hòa (luật đồng nhất): p ∧ 1 ≡ p ; p ∨ 0 ≡ p 8/ Luật về phần tử bù: p ∧ p ≡ 0 (Luật bài trung) P ∨ p ≡ 1 (Luật mâu thuẫn) 9/ Luật thống trò: p ∧ 0 ≡ 0 ; p ∨ 1 ≡ 1 10/ Luật hấp thụ: p ∧ (p ∨ q) ≡ p ; p ∨ (p ∧ q) ≡ p * Chứng minh các công thức trên bằng cách lập bảng chân trò. Chẳng hạn ta chứng minh luật hấp thụ 10/ bằng bảng sau: p q p ∨ q p ∧ q p ∧ (p ∨ q) p ∨ (p ∧ q) 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 5 III – QUI TẮC SUY LUẬN III.1 – Khái niệm: Trong các chứng minh toán học, ta thường xuất phát từ tiền

đề

là các khẳng đònh đúng p 1 , p 2 , . . . , p n và áp các qui tắc suy luận toán học

để

khẳng đònh kết luận q là đúng. Công thức tổng quát của qui tắc suy luận là: (p 1 ∧ ∧∧ ∧ p 2 ∧ ∧∧ ∧ . . . ∧ ∧∧ ∧ p n ) ⇒ ⇒⇒ ⇒ q Hay viết theo mô hình là: p 1 p 2 . . . p n q III.2 – Các qui tắc suy luận thường dùng: III.2.1 – Qui tắc khẳng đònh (Modus Ponens) Qui tắc này được thể hiện bởi công thức hằng đúng (c/m bằng cách lập bảng chân trò): (( p ⇒ ⇒⇒ ⇒ q) ∧ ∧∧ ∧ p) ⇒ ⇒⇒ ⇒ q hay dưới dạng sơ đồ p ⇒ q p q Ví dụ 14: a/ Tam giác cân có hai cạnh bằng nhau. (p ⇒ q) Tam giác ABC cân tại A (p) KL: AB = AC (q) b/ Mọi số chẵn đều chia hết cho 2 mà 2006 là một số chẵn. Suy ra số 2006 chia hết cho 2. c/ Nếu học giỏi sẽ được thưởng mà Lan đạt loại giỏi. Vậy Lan sẽ được thưởng. III.2.2 – Qui tắc tam đoạn luận (Modus Syllogism) / Chứng minh bắc cầu Qui tắc này được thể hiện bởi công thức hằng đúng (c/m bằng cách lập bảng chân trò): (( p ⇒ ⇒⇒ ⇒ q) ∧ ∧∧ ∧ ( q ⇒ ⇒⇒ ⇒ r)) ⇒ ⇒⇒ ⇒ (p ⇒ ⇒⇒ ⇒ r) hay dưới dạng sơ đồ p ⇒ q q ⇒ r p ⇒ r Ví dụ 15: a/ Bình chơi Game Online thì Bình không học Toán ứng dụng. Bình không học Toán ứng dụng thì Bình thi rớt Toán ứng dụng. Mà Bình ham chơi Game Online nên Bình thi rớt Toán ứng dụng. Tiền

đề

Kết luận http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 6 b/ 75 chia hết cho 15; 15 chia hết cho 5. Vậy 75 chia hết cho 5. c/ Một con ngựa rẻ thì hiếm. Cái gì hiếm thì đắt. Suy ra một con rẻ thì đắt (!). Suy luận trên là hợp logic. Nhưng kết luận sai do dựa trên một tiền

đề

sai. III.2.3 – Qui tắc phủ đònh (Modus Tollens) / Chứng minh phản đảo Qui tắc này được thể hiện bởi công thức hằng đúng (c/m bằng cách lập bảng chân trò): (( p ⇒ ⇒⇒ ⇒ q) ∧ ∧∧ ∧ q ) ⇒ ⇒⇒ ⇒ p hay dưới dạng sơ đồ p ⇒ q q p Ví dụ 16: a/ Nếu học giỏi sẽ được thưởng mà An không được thưởng. Vậy An không học giỏi. b/ Hai góc đối đỉnh thì bằng nhau. Góc O 1 khác góc O 2 nên hai góc ấy không đối đỉnh. III.2.4 – Qui tắc tam đoạn luận rời/ Chứng minh loại trừ Qui tắc này được thể hiện bởi công thức hằng đúng (c/m bằng cách lập bảng chân trò): (( p ∨ ∨∨ ∨ q) ∧ ∧∧ ∧ p ) ⇒ ⇒⇒ ⇒ q Ý nghóa của qui tắc này là khi chỉ có đúng hai trường hợp có thể xảy ra và mộtt trường hợp đã được khẳng đònh là sai thì trng hợp còn lại là đúng. Ví dụ 17: a/ Sáng nay hai bạn An và Bình được phân công làm trực nhật. Nhưng bạn An đi học trễ. Vậy bạn Bình làm trực nhật. b/ Tích a.b = 0 (suy ra a = 0 hoặc b = 0) mà a ≠ 0 Vậy b = 0. III.2.5 – Qui tắc mâu thuẫn / Chứng minh phản chứng Qui tắc này được thể hiện bởi tương đương logic sau: ( p ⇒ ⇒⇒ ⇒ q) ≡ ≡≡ ≡ (( p ∧ ∧∧ ∧ q ) ⇒ ⇒⇒ ⇒ 0) Do đó, nếu chứng minh được công thức

mệnh đề

bên phải là hằng đúng thì công thức bên trái cũng là hằng đúng. Nghóa là nếu ta giả sử q là sai và cùng với tiền

đề

dẫn đến điều vô lí thì kết luận q là đúng. Đó là cơ sở của phương pháp chứng minh phản chứng. Ví dụ 18: Chứng minh rằng 2 là số vô tỉ. Giả sử 2 là một số hữu tỉ. Khi đó 2 = p/q với p/q là phân số tối giản. ⇒ 2 = p 2 /q 2 ⇒ 2q 2 =p 2 ⇒ p 2 ⋮ 2 ⇒ p⋮2 (vì nếu p-lẻ thì p 2 cũng lẻ mâu thuẫn với p 2 ⋮ 2) ⇒ p = 2k. Suy ra 2q 2 = 4k 2 ⇒ q 2 = 2k 2 ⇒ q 2 ⋮ 2 ⇒ q⋮2. Do đó p, q có ước số chung là 2, trái với giả thiết p/q là phân số tối giản. Vậy 2 là một số vô tỉ. http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 7 IV- VỊ TỪ – LƯNG TỪ IV.1 – Vò từ: Vò từ là một khẳng đònh chứa biến dạng P(x) với x∈A sao cho: • P(x) không phải là

mệnh

đề. • Cho x= a∈ A thì P(a) là một

mệnh

đề. Ví dụ 18: a/ P(x) = “x < 5” ; x∈ N với N = {0, 1, 2, 3, 4, 5, . . . } P(0) = “ 0 < 5” là

Bài Hay  Bài tập : Phần đại số Boole. I. Nội dung bài tập Tính biểu thức của các

mệnh đề

đúng. P(5) = “ 5 < 5” là

mệnh đề

sai. P(1) = “ 1 < 5” là

mệnh đề

đúng. P(6) = “ 6 < 5” là

mệnh đề

sai. P(2) = “ 2 < 5” là

mệnh đề

đúng. P(7) = “ 7 < 5” là

mệnh đề

sai. P(3) = “ 3 < 5” là

mệnh đề

đúng. P(8) = “ 8 < 5” là

mệnh đề

sai. P(4) = “ 4 < 5” là

mệnh đề

đúng. … b/ P(n) = “n là số nguyên tố” ; n ∈ N (Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước số là 1 và chính nó) P(0) = “ 0 là số nguyên tố” :

mệnh đề

sai. P(1) = “ 1 là số nguyên tố” :

mệnh đề

sai. P(2) = “ 2 là số nguyên tố” :

mệnh đề

đúng. P(3) = “ 3 là số nguyên tố” :

mệnh đề

đúng. P(4) = “ 4 là số nguyên tố” :

mệnh đề

sai. P(5) = “ 5 là số nguyên tố” :

mệnh đề

đúng. . . . c/ P(x, y) = “x + y là số nguyên chẵn” ; n∈ Z = {0, ±1, ±2, ±3, ±4, ±5, . . . } Ta thấy P(2, 4) là

mệnh đề

đúng, còn P(5,2) là

mệnh đề

sai, . . . IV.2 – Lượng từ: •

Để

chỉ một phần tử bất kì thuộc tập A ta viết: ∀ ∀∀ ∀x∈ ∈∈ ∈A (lượng từ với mọi) •

Để

chỉ ít nhất một phần tử thuộc tập A ta viết: ∃ ∃∃ ∃x∈ ∈∈ ∈A (lượng từ tồn tại) •

Để

chỉ một phần tử duy nhất thuộc A ta viết: ∃ ∃∃ ∃! !! !x∈ ∈∈ ∈A (lượng từ tồn tại duy nhất) + Ghép các lượng từ với vò từ ta được các

mệnh đề

sau: ∀ ∀∀ ∀x∈ ∈∈ ∈A, P(x) ∃ ∃∃ ∃x∈ ∈∈ ∈A, P(x) ∃ ∃∃ ∃! !! !x∈ ∈∈ ∈A, P(x) + Phủ đònh các

mệnh đề

trên ta được các

mệnh đề

tương logic sau: (∀ ∀∀ ∀x∈ ∈∈ ∈A, P(x)) ≡ ∃ ∃∃ ∃x∈ ∈∈ ∈A, P(x) (∃ ∃∃ ∃x∈ ∈∈ ∈A, P(x)) ≡ ∀ ∀∀ ∀x∈ ∈∈ ∈A, P(x) Ví dụ 19: P(n) = “n là số nguyên tố” ; n∈ N (Xem ví dụ 18b) • ∀n∈N, P(n) = “Mọi số tự nhiên n đều là số nguyên tố” : mđ sai. (1) • ∃n∈N, P(n) = “Có số tự nhiên n là số nguyên tố” : mđ đúng. (2) • ∃!n∈N, P(n) = “Có duy nhất 1 số tự nhiên n là số nguyên tố” : mđ sai. Phủ đònh của (1) ta được: ∃n∈N, P(n) = “Có số tự nhiên n không phải là số nguyên tố” : mđ đúng. Phủ đònh của (2) ta được: ∀n∈N, P(n) = “Mọi số tự nhiên n không phải là số nguyên tố” : mđ sai. http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 8 V – QUY NẠP VÀ

ĐỆ

QUY V.1 – QUY NẠP V.1.1 – Nguyên lí quy nạp: Nguyên lí quy nạp dựa trên

mệnh đề

hằng đúng sau đây: P(0) ∧ ∧∧ ∧ [∀ ∀∀ ∀n∈ ∈∈ ∈N, P(n) ⇒ ⇒⇒ ⇒ P(n+1)] ⇒ ⇒⇒ ⇒ ∀ ∀∀ ∀n∈ ∈∈ ∈N, P(n) V.1.2 – Các bước chứng minh quy nạp: Như vậy,

để

chứng minh

mệnh đề

P(n) là đúng ∀ ∀∀ ∀n∈ ∈∈ ∈N ta thực hiện các bước sau: Bước 1/ Khẳng đònh P(0) là đúng. Bước 2/ Giả sử P(n) là đúng suy ra P(n+1) cũng đúng. Bước 3/ Kết luận: P(n) đúng , ∀n∈N Lưu ý: Nguyên lý quy nạp có thể bắt đầu từ n 0 ∈ N. Tức là P(n) đúng ∀n∈N, n ≥ n 0 . Khi đó

mệnh đề

P(0) trong bước 1 được thay bởi P(n 0 ) Ví dụ 20: a/ P(n) : 0 + 1 + 2 + . . . + n = n(n+1)/2 ; ∀n∈N + P(0) đúng vì 0 = 0(0+1)/2 + Giả sử P(n) đúng, tức là 0 + 1 + 2 + . . . + n = n(n+1)/2 Suy ra 0 + 1 + 2 + . . . + n + (n+1) = n(n+1)/2 + (n+1) = (n+1)(n+2)/2 =(n+1)[(n+1)+1]/2 Suy ra P(n+1) đúng. Vậy, P(n) đúng ∀n∈N. b/ Chứng minh rằng P(n) = n 3 + 5n chia hết cho 6, ∀n∈N. + Với P(0) ta có: 0 ⋮ 6. Suy ra P(0) đúng. + Giả sử P(n) đúng, tức là n 3 + 5n ⋮ 6 Ta xét P(n+1): (n+1) 3 + 5(n+1) = (n 3 + 3n 2 + 3n + 1) + 5n + 5 = (n 3 + 5n) + 3(n 2 + n +2) = (n 3 + 5n) + 6(n(n+1)/2 + 1) ⋮ 6 Vậy (n+1) 3 + 5(n+1) ⋮ 6, tức là P(n+1) là đúng. + Kết luận: n 3 + 5n ⋮ 6, ∀n∈N. c/ Tương tự, hãy chứng minh rằng 2 n+2 > 2n + 5 ; ∀n∈ N, n ≥ 1. V.2 –

Đệ

quy V.2.1 – Đònh nghóa

đệ

quy (đònh nghóa quy nạp): Đôi khi rất khó đònh nghóa một đối tượng một cách tường minh, nhưng lại

dễ

dàng đònh nghóa đối tượng này thông qua chính nó. Đònh nghóa như vậy gọi là đònh nghóa

đệ

quy (hay đònh nghóa quy nạp). Ví dụ 21: a/ Đònh nghóa tập hợp số tự nhiên N

đệ

quy như sau: • 0 là số tự nhiên • Nếu n là số tự nhiên thì n+1 cũng là số tự nhiên. Khi đó ta có: N = {0, 1, 2, 3, 4, 5, . . . } b/ Đònh nghóa hàm số f

đệ

quy như sau: • f(0) = 3 (với n = 0) • f(n) = 2f(n-1) + 3 với n = 1, 2, 3, … http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 9 Khi đó ta có: f(1) = 2f(0) + 3 = 2 × 3 + 3 = 9 f(2) = 2f(1) + 3 = 2 × 9 + 3 = 21 f(3) = 2f(2) + 3 = 2 × 21 + 3 = 45 f(4) = 2f(3) + 3 = 2 × 45 + 3 = 93 V.2.2 – Thuật toán

đệ

quy: Một thuật toán được gọi là

đệ

quy nếu nó giải bài tóan bằng cách rút gọn liên tiếp bài toán ban đầu tới chính bài toán ấy nhưng có dữ liệu đầu vào nhỏ hơn. Ví dụ 22: a/ Tính giá trò a n , với a là số thực khác 0, n là số tự nhiên: Ta đònh nghóa a n

đệ

quy như sau: • Khi n = 0: a 0 =1 • Khi n > 0: a n = a. a n-1 Như vậy

để

tính a n ta quy về các trường hợp có số mũ n nhỏ hơn cho đến khi n = 0 thì dừng. Ta có thuật toán

đệ

quy tính lũy thừa của a như sau (mã VB): Function LuyThua(a, n) as Double If n = 0 then LuyThua = 1 else LuyThua = a * LuyThua(a, n-1) End If End Function b/ Tính giá trò n! = 1.2.3. . .(n-1).n = (n-1)! . n nếu n > 0 ; 0! = 1. + Thủ tục

đệ

quy: Function GiaiThua(n) as Long If n = 0 then GiaiThua = 1 else GiaiThua = n * GiaiThua(n-1) End If End Function + Thủ tục lặp (Không

đệ

quy): Function GiaiThua(n) as Long T = 1 For i = 1 to n T = T * i Next GiaiThua = T End Function c/ Tính giá trò: S = 1 + 2 + 3 + . . . + n Dùng cách tính tổng lặp (lặp lại đối với S): S = 0 For i = 1 to n S = S + i Next http://www.ebook.edu.vn

Chương

1 – Logic

mệnh đề

Toán ứng dụng trong Tin học Biên soạn: Trường Sơn 10 BÀI TẬP

CHƯƠNG

1 – LÔGIC

MỆNH ĐỀ

1.1- Trong các câu sau, cho biết câu nào là

mệnh

đề: a) Trần Hưng Đạo là một vò tướng tài. b) x + 1 là một số nguyên dương. c) 9 là một số chẵn. d) Hôm nay trời đẹp làm sao ! e) Hãy học Toán ứng dụng. f) Nếu bạn đến trễ thì tôi sẽ đi xem bóng đá trước. 1.2- Gọi P và Q là các

mệnh

đề: P: “Minh giỏi Toán” Q: “Minh yếu Anh văn”. (Giả sử:không giỏi là yếu, không yếu là giỏi) Hãy viết lại các

mệnh đề

sau dưới dạng hình thức trong đó sử dụng các phép toán

mệnh

đề. a) Minh giỏi toán nhưng yếu Anh văn. b) Minh yếu cả Toán lẫn Anh văn. c) Minh giỏi Toán hay Minh vừa giỏi Anh văn vừa yếu Toán. d) Nếu Minh giỏi Toán thì Minh giỏi Anh văn. e) Minh giỏi Toán và Anh văn hay Minh yếu Toán nhưng giỏi Anh văn. 1.3- Gọi P, Q, R là các

Bài Hay  TOÁN RỜI RẠC BÀI TẬP ÔN TẬP GIỮA KỲ LOGIC Lập bảng chân trị cho các

mệnh

đề: P: “Bình đang học Toán”. Q: “Bình đang học Tin học”. R: “Bình đang học Anh văn”. Hãy viết lại các

mệnh đề

dưới đây dưới dạng hình thức trong đó sử dụng các phép toán. a) Bình đang học Toán và Anh văn nhưng không học Tin học. b) Bình đang học Toán và Tin học nhưng không học cùng một lúc Tin học và Anh văn. c) Không đúng là Bình đang học Anh văn mà không học Toán. d) Không đúng là Bình đang học Anh văn hay Tin học mà không học Toán. e) Bình không học Tin học lẫn Anh văn nhưng đang học Toán. 1.4- Hãy lấy 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) 15 chia hết cho 3 nhưng không chia hết cho 4. c) Hình 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ì sẽ bò đuổi việc. e) Mọi tam giác đều có các góc bằng 60 o . 1.5- Cho biết chân trò của các

mệnh đề

sau: a) π = 2 và tổng các góc của một tam giác bằng 180 o . b) π = 3,1416 kéo theo tổng các góc của một tam giác bằng 170 o . c) π = 3 kéo theo tổng các góc của một tam giác bằng 170 o . d) Nếu 2 > 3 thì nước sôi ở 100 o C. e) Nếu 3 < 4 thì 4 < 3. f) Nếu 4 < 3 thì 3 < 4. […].. .Chương 1 – Logic

mệnh đề

http://www.ebook.edu.vn Toán ứng dụng trong Tin học 1.6- Giả sử P và Q là hai

mệnh đề

nguyên thủy sao cho P → Q sai Hãy xác đònh chân trò của các

mệnh đề

sau: (Kí hiệu ¬P là phủ đònh của P) a) P ∧ Q b) ¬ P ∨ Q c) Q → P 1.7- Gọi P, Q, R là các

mệnh đề

sau: P: ABC là một tam giác cân Q: ABC là một tam giác đều R: Tam giác ABC có 3 góc bằng nhau Hãy viết lại các

mệnh đề

sau… x là một biến nguyên Tìm chân trò của các

mệnh đề

sau: a) p(1) b) q(1) c) ¬ p(2) f) ¬ (p(-1) ∨ q(-1)) d) q(3) e) p(6) ∨ q(6) 1.18- Xét vò từ p(x): “x2 – 3x + 2 = 0” Cho biết chân trò của các

mệnh đề

sau: a) p(0) b) p(1) c) p(2) e) ∀x, p(x) d) ∃x, p(x) 1.19- Xét vò từ theo hai biến nguyên lớn hơn 0: p(x, y): “x là ước của y” Hãy xác đònh chân trò của các

mệnh đề

sau: a) p(2, 3) b) p(2, 6) e) ∀y, ∃x,… hình chữ nhật hay nó là hình thoi d/ Ngày mai Nam không đi làm nhưng vẫn không bò đuổi việc e/ Có tam giác mà các góc khác 60o 1.5

Mệnh đề

đúng: c, d, f

Mệnh đề

sai: a, b, e 1.6 a) Đúng c) Đúng 1.8 Có 3 cách đặt dấu () vào biểu thức đã cho: Câu b, d, e : không phải là

mệnh đề

b/ ¬ P ∧ Q c/ P ∨ (¬ Q ∧ ¬ P) e/ (P ∧ ¬ Q) ∨ (¬ P ∧ ¬ Q) b) Sai a/ ¬ (P ∨ Q ∨ R) b/ ¬ (P ∨ Q) ∨ R c/ ¬ (R ∧ ¬ P) ≡ ¬ R ∨ P c/… ∀n∈ N 2! 3! (n + 1)! (n + 1)! g) (1 + a)n ≥ 1 + na, ∀n∈ N, a> -1 h) 2n > n ; ∀n∈ N i) 2n+2 > 2n + 5 ; ∀n∈ N, n ≥ 1 Biên soạn: Trường Sơn 13

Chương

1 – Logic

mệnh đề

Toá http://www.ebook.edu.vn n ứng dụng trong Tin học HƯỚNG DẪN VÀ ĐÁP SỐ 1.1 Câu a, c, f : là

mệnh đề

; 1.2 a/ P ∧ Q d/ P ⇒ ¬ Q 1.3 a/ P ∧ R ∧¬ Q b/ P ∧ Q ∧¬ (Q ∧ R) d/ ¬ ((R∨ Q) ∧¬ P) e/ ¬ Q ∧ ¬ R ∧ P 1.4 a/ Không đúng là ngày mai nếu trời… Hãy viết lại các

mệnh đề

sau theo ngôn ngữ thông thường: a) Q → P b) ¬ P → Q c) P ∧ ¬ Q d) R → P 1.8- Có bao nhiêu cách đặt dấu “( )” khác nhau vào dạng

mệnh đề

¬ p ∨ q ∨ r Lập bảng chân trò cho từng trường hợp 1.9- Lập bảng chân trò cho các dạng

mệnh đề

sau và chỉ ra các hằng đúng: a) ¬ p → (p ∨ q) b) ¬ p → (¬ q ∨ r) c) (p ∧ q) → ¬ p d) (p ∨ r) → (r ∨ ¬ p) f) (p ∨ ¬ q) ∧ (¬ p ∨ q) e) (p → q) ∨ (q →… ∴¬ t ¬s ¬s∧¬t ¬ (s ∨ t) r→s∨t ∴¬ r (¬ p ∨ q) → r ∴¬ (¬ p ∨ q) p∧¬q ∴p Biên soạn: Trường Sơn (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13)

Chương

1 – Logic

mệnh đề

http://www.ebook.edu.vn Toán ứng dụng trong Tin học 1.16- Hãy kiểm tra các suy luận sau, suy luận nào là đúng / sai ? (∴ký hiệu kết luận) b) p → q c) p → (q → r) a) p → q ¬q r→¬q ¬q→¬p ¬r… đúng thì Hà được điểm cao Mà Hà không được điểm cao Suy ra c) Nếu chiều nay Minh đá bóng thì Minh không được xem Tivi Mà Vậy Minh không đá bóng chiều nay Biên soạn: Trường Sơn 11

Chương

1 – Logic

mệnh đề

Toá http://www.ebook.edu.vn n ứng dụng trong Tin học 1.13- Cho biết suy luận nào trong các suy luận sau là đúng và qui tắc suy luận nào đã được sử dụng? a) Điều kiện đủ

để

Cảng SG thắng trận… p) (6) ≡ ¬ [(p ∨ q) ∧ (q ∧p)] (7) ≡ ¬ [(q ∧p) ∧(p ∨ q)] (8) ≡ ¬ [q ∧[p ∧(p ∨ q)]] (9) ≡ ¬ (q ∧ p) c*) C/minh: p→ (q → r) ≡ p ∧ q→ r ; (p→ q) ∧ [¬q ∧ (r ∨ ¬q)] ≡ ¬ (q ∨ p) 1.12- Hãy điền

mệnh đề

thích hợp vào chỗ trống

để

cho các suy luận sau đây theo phương pháp khẳng đònh và phủ đònh là đúng: a) Nếu xe của Minh không khởi động được thì anh phải kiểm tra bugi Mà xe của Minh không khởi động . có: (1+ a) k ≥ 1+ ka ⇒ (1+ a) k (1+ a) ≥ (1+ ka) (1+ a) , a> -1 ⇒ (1+ a) k +1 ≥ 1+ (k +1) a+ ka 2 ≥ 1+ (k +1) a ⇒ (1+ a) k +1 ≥ 1+ (k +1) a ⇒ (*) đúng với n=k +1 Vậy (1+ a). thụ 10 / bằng bảng sau: p q p ∨ q p ∧ q p ∧ (p ∨ q) p ∨ (p ∧ q) 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 http://www.ebook.edu.vn Chương 1 – Logic mệnh

Bạn đang xem bài viết: Chương 1_Logic mệnh đề. Thông tin do Elive chọn lọc và tổng hợp cùng với các chủ đề liên quan khác.

Leave a Comment