Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh

Mục tiêu: Ngƣời học biết vận dụng các nguyên lý của bài toán đếm để tìm số lƣợng một cấu

hình tổ hợp nào đó. Ngƣời học biết ứng dụng phƣơng pháp sinh phần tử kế tiếp, phƣơng

pháp quay lui để liệt kê tất cả các cấu hình cần đếm hoặc các cấu hình thỏa mãn thêm một

hoặc một số điều kiện nào đó.

1.1 BÀI TOÁN ĐẾM

1.1.1 Nguyên lý cộng, nguyên lý nhân, nguyên lý bù trừ

Kí hiệu: N(X) là số phần tử của tập hợp X.

Nguyên lý cộng: Nếu thì ( ) ( ) ( ).

Đặc biệt ̅ thì ( ) ( ) ( ̅).

Nếu { ( ̅̅̅̅̅̅) thì ( ) ( ) ( ) ( )

Nguyên lý nhân: N( ) = N(A1) N(A2) N(Am).

Nguyên lý bù trừ: ( ) ( ) ( ) ( ).

Tổng quát : ( ) ( ) .

với Nk = ∑ ( ) là số các phần tử thuộc về giao ít

nhất k tập hợp khác nhau lấy từ m tập đã cho.

Ví dụ 1: Có bao nhiêu xâu nhị phân có độ dài 6 bit?

Giải. Đặt * +. Mỗi xâu nhị phân độ dài 6 được coi là một phần tử của tích Đề-cac

Do vậy số xâu nhị phân độ dài 6 là : ( ) .

Ví dụ 2: Có bao nhiêu xâu nhị phân có độ dài 10 bắt đầu 00 hoặc kết thúc 11?

Giải. Gọi A0 = Tập hợp tất cả các xâu nhị phân có độ dài 10 bắt đầu bằng 00,

A1 = Tập hợp tất cả các xâu nhị phân có độ dài 10 kết thúc bằng 11.

A0A1 = Tập hợp tất cả các xâu nhị phân có độ dài 10 bắt đầu bằng 00 và kết thúc bằng 11.

Vậy số xâu nhị phân thỏa mãn yêu cầu bài toán là:

( ) ( ) ( ) ( )

Ví dụ 3: Từ 1 đến 1000 có bao nhiêu số không chia hết cho bất kì số nào trong các số 3, 5, 7?

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 1

Trang 1

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 2

Trang 2

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 3

Trang 3

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 4

Trang 4

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 5

Trang 5

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 6

Trang 6

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 7

Trang 7

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 8

Trang 8

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 9

Trang 9

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh trang 10

Trang 10

Tải về để xem bản đầy đủ

pdf 113 trang xuanhieu 3900
Bạn đang xem 10 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh

Bài giảng Toán rời rạc - Nguyễn Thị Thúy Hạnh
iệc và vợ ông ấy mất việc thì phải bán xe. 
Biết rằng, vợ ông ấy hay đi làm trễ thì trước sau gì cũng sẽ bị mất việc. Nhưng ông Minh đã 
được tăng lương. 
Suy ra, nếu ông Minh không bán xe thì vợ ông ta đã không đi làm trễ. 
Giải. 
Toán rời rạc – Chương 6. Đại cương về toán logic Page 100 
Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH 
 Kí hiệu các mệnh đề như sau: Từ bài toán và theo quy tắc phản đảo ta có các 
 tiền đề (các khẳng định đúng) và quy tắc suy 
 p: Ông Minh được tăng lương. diễn sau: 
 q: Ông Minh nghỉ việc. ̅ ̅ 
 ( ) ( ) 
 r: Vợ ông Minh mất việc. 
 s: Ông Minh bán xe. 
 ( ̅ ̅ ) ( )
 t: Vợ ông Minh hay đi làm trễ. 
Một phản ví dụ thỏa mãn mọi tiền đề đều đúng nhưng kết luận sai là: 
 . 
Vậy suy luận trên không đúng. Tức là ông Minh không bán xe thì vợ ông Minh vẫn có thể đi 
làm trễ. 
Thật vậy, ông Minh được tăng lương nên ông Minh không bỏ việc. Mà ông Minh không bỏ 
việc thì chắc chắn không phải bán xe. Do vậy việc vợ ông ấy hay đi làm trễ (tức là vợ bị mất 
việc) không ảnh hưởng đến việc ông Minh không phải bán xe. 
Ví dụ 2 : Cho các tiền đề : 
 „Nếu anh đến thì em đi chơi khuya‟. 
 „Nếu anh không đến thì em đi ngủ sớm‟. 
 „Nếu em ngủ sớm thì mai em sẽ đi học đúng giờ‟. 
Hãy chứng minh hệ quả logic: „Nếu em không đi chơi khuya thì mai em sẽ đi học đúng giờ‟ . 
Giải. 
 Áp dụng các quy tắc suy diễn như sau: 
Kí hiệu các mệnh đề Sơ đồ suy diễn là : 
là: ̅ ̅ (Từ (1) và quy tắc phản 
 ( ) ̅ đảo) 
p: Anh đến. ̅ ( ) (Tiền đề (2)) 
 ̅ 
q : Em đi chơi khuya. ( ) (Quy tắc tam đoạn luận) 
r: Em đi ngủ sớm. 
 ̅ ̅ (Tiền đề (3)) 
s: Em đi học đúng (Quy tắc tam đoạn luận) 
giờ. 
Vậy : „Nếu em không đi chơi khuya thì mai em sẽ đi học đúng giờ‟ là đồng nhất đúng. 
Chú ý : Phải dùng hằng các đồng nhất đúng để suy luận, nếu dùng TIẾP LIÊN (là một công 
thức không phải là đồng nhất đúng, cũng không phải là đồng nhất sai), chúng sẽ khiến suy 
luận thành NGỤY BIỆN. 
Toán rời rạc – Chương 6. Đại cương về toán logic Page 101 
 Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH 
 Bảng 3.4. Một số suy diễn là NGỤY BIỆN. 
 Tiếp liên Ngụy biện Ví dụ 
 Ngụy biện khẳng Nếu anh ta cƣới vợ thì anh ta sẽ có con. Anh 
 ,( ) - 
 định kết luận ta đã có con. Vậy anh ta đã có gia đình. 
 Nếu anh ta cƣới vợ thì anh ta sẽ có con. Anh 
 ,( ) ̅- ̅ Ngụy biện phủđịnh ta không lập gia đình. Vậy anh ta không thể 
 giả thiết có con. 
 6.2. LOGIC VỊ TỪ 
 Trong các khẳng định toán học ta hay gặp các phát biểu có liên quan đến biến nhƣ: 
 ; với điều kiện x, y, z là các số thực. Ta chƣa xác 
 định đƣợc các phát biểu này đúng hay sai bởi vì các biến chƣa có giá trị. 
 Trong các chƣơng trình máy tính (Chẳng hạn, ngôn ngữ Prolog, ngôn ngữ lập trình suy luận 
 trên cơ sở logic toán học để giải quyết các bài toán trong lĩnh vực trí tuệ nhân tạo), ta cũng 
 hay gặp các biểu thức chứa biến kiểu nhƣ vậy, với miền xác định của các biến đã biết. 
 Kí hiệu các phát biểu trên là: 
 ( ) ( ) ( ) ( ). 
 Rõ ràng, bản thân các phát biểu ( ) ( ) ( ) chƣa phải là một mệnh đề. Tuy vậy, 
 khi gán giá trị cụ thể cho các biến hoặc chỉ ra một miền xác định của các biến thì các phát 
 biểu đó trở thành các mệnh đề. Chẳng hạn : 
 Phát biểu : P(2) = “22 + 3.2 – 4 > 0”, là một mệnh đề ĐÚNG (gán x = 2). 
 Phát biểu : Với mọi ( ) ( ) ( ) là một 
 mệnh đề SAI. 
 Phát biểu : Q(2,1) = “2 = 1 + 2” là một mệnh đề SAI (gán x = 2, y = 1) . 
 Ta gọi các phát biểu ở (*) là các hàm mệnh đề hay là các vị từ . 
 Dạng tổng quát ta có định nghĩa sau: 
6.2.1. Các định nghĩa. 
 (1) Vị từ : Cho X1; X2 ; ; Xn là tập hợp các đối tƣợng nào đó. Đặt 
 và (x1; x2; ; xn) tức xi Xi , ̅̅ ̅̅ ̅ . Một phát biểu có n biến x1; x2; ; xn đƣợc 
 kí hiệu là P(x1; x2; ; xn) đƣợc gọi là một hàm mệnh đề xác định trên X nếu thỏa mãn : 
 Toán rời rạc – Chương 6. Đại cương về toán logic Page 102 
Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH 
- Phát biểu P(x1; x2; ; xn) chƣa phải là mệnh đề. 
- Nhƣng thay (x1; x2; ; xn) với xi Xi thành giá trị cụ thể ( ̅̅ ̅ ̅̅ ̅ ̅ ) thì phát biểu 
 ( ̅̅ ̅ ̅̅ ̅ ̅ ) là một mệnh đề. 
 Hàm mệnh đề P(x1; x2; ; xn) còn gọi là vị từ n ngôi xác định trên . 
(2) Sự lượng hóa : Cho P(x) là vị từ một ngôi xác định trên A. Các mệnh đề lượng từ hóa 
 của P(x) xác định nhƣ sau : 
(i) Lượng từ “với mọi” hay "phổ dụng", kí hiệu . Mệnh đề “Với mọi x thuộc A, P(x)”, kí 
 hiệu : 
 ( ) (2i) 
 Mệnh đề (2i) là ĐÚNG nếu với bất kì x0 thuộc A thì mệnh đề P(x0) luôn nhận giá trị 
 đúng. 
 Ngƣợc lại, (2i) là SAI nếu có ít nhất một phần tử x0 thuộc A để P(x0) sai. 
(ii) Lượng từ “tồn tại”, kí hiệu . Mệnh đề “Tồn tại một x thuộc A, P(x)” hay “Có ít nhất 
 một x thuộc A, P(x)”, kí hiệu : 
 ( ) (2ii) 
 Mệnh đề (2ii) là ĐÚNG nếu có ít nhất một giá trị x0 thuộc A để P(x0) đúng. 
 Ngƣợc lại, mệnh đề (2ii) là SAI nếu với bất kì x0 thuộc A thì P(x0) luôn nhận giá trị sai. 
Tóm lại, nếu * + thì : 
 (2i) ( ) ( ) ( ) ( ). 
 (2ii) ( ) ( ) ( ) ( ). 
Tức là, để xác định chân trị của (2i) là đúng thì phải thử tất cả các giá trị xi thuộc A; còn để 
xác định chân trị của (2ii) là đúng thì ta chỉ cần tìm một giá trị của xi thuộc A. 
Ví dụ 1: Cho P(x) = “x2 + 3x – 4 > 0” với x là số thực ; S(n) = “ ( ) ” với n là số 
tự nhiên. 
- Mệnh đề , P(x) := “ – . Đây là một mệnh đề SAI. Vì 
thử với x = 0, P(0) là một mệnh đề sai. 
- Mệnh đề x , P(x) – . Dễ thấy, mệnh đề này là ĐÚNG 
(chẳng hạn đúng với x = 2). 
- Mệnh đề n ( ) := n ( ) . 
 Đây là một mệnh đề ĐÚNG. Vì thử với số tự nhiên n bất kì, xảy ra hai trường hợp: n chẵn (n 
= 2k) hoặc n lẻ (n = 2k + 1) thì S(2k) = “2k.(2k + 1) 2” và S(2k + 1) =“(2k+1).(2k+2) 2” 
là các mệnh đề đúng. 
- Hiển nhiên, mệnh đề n ( ) n ( ) là ĐÚNG (Chẳng hạn đúng 
với n = 2). 
Lưu ý: Thứ tự các lượng từ đối với vị từ nhiều ngôi là quan trọng, ta chỉ không phân biệt thứ 
tự khi tất cả các lƣợng từ là “với mọi”, hoặc tất cả các lƣợng từ là “tồn tại”. 
Toán rời rạc – Chương 6. Đại cương về toán logic Page 103 
Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH 
 Bảng 6.4. Ý nghĩa của các lƣợng từ đối với vị từ hai ngôi Q(x,y). 
Mệnh đề lượng từ hóa của Q(x,y) Ý nghĩa các lượng từ 
 Là một mệnh đề đúng nếu Q(x,y) là đúng với mọi cặp 
(1) ( ) (x,y) tùy ý. 
Hay * ( )+ Là một mệnh đề sai nếu có ít nhất một cặp (x,y) nào đó 
 để Q(x,y) là sai. 
 Là một mệnh đề đúng nếu với giá trị x bất kì, có ít nhất 
(2) ( ) một giá trị y để Q(x,y) là đúng, 
Hay * ( )+ Là một mệnh đề sai nếu có ít nhất một giá trị x để Q(x,y) 
 là sai với mọi y. 
 Là một mệnh đề đúng nếu có ít nhất một giá trị x để 
(3) ( ) Q(x,y) là đúng với mọi y. 
Hay * ( )+ Là một mệnh đề sai nếu với x bất kì, có ít nhất một giá 
 trị y để Q(x,y) là sai. 
(4) ( ) Là một mệnh đề đúng nếu có ít nhất một cặp (x,y) nào 
 đó để Q(x,y) là đúng. 
Hay * ( )+ Là một mệnh đề sai nếu Q(x,y) là sai với mọi cặp (x,y) 
 tùy ý. 
Ví dụ 2 : Xét hai mệnh đề lượng từ hóa của vị từ Q(x,y) = “x = y + 2” với : 
 ( ) . Phát biểu là : "Với mọi số thực x, tồn tại số thực y 
thỏa mãn : x = y + 2". Đây là một mệnh đề ĐÚNG. Vì : với số thực x tùy ý, chọn y = x – 2 
thì x = y + 2. 
 ( ) . Phát biểu là : "Tồn tại ít nhất một số thực y, để với 
mọi số thực x ta có: x = y+2". Đây là một mệnh đề SAI. Vì: với mọi số thực y, chọn x = y+3 
thì . 
Định lý : Cho Q(x,y) là một vị từ theo hai biến x, y xác định trên . Khi đó : 
 (1) ( ) ( ) . 
 (2) ( ) ( ) . 
 (3) ( ) ( ) . 
Theo Ví dụ 2 ở trên thì chiều đảo của (3) nói chung không đúng. 
Quy tắc đặc biệt hóa phổ dụng : Nếu một mệnh đề lƣợng từ hóa chứa lƣợng từ phổ dụng ( ) 
trƣớc biến , LÀ ĐÚNG, khi ấy nếu thay x bởi thì ta sẽ đƣợc một mệnh đề 
ĐÚNG. 
Ví dụ 3: Vì : "Mọi người đều có quê hương", mà Mai là người, nên "Mai cũng có quê 
hương". 
Toán rời rạc – Chương 6. Đại cương về toán logic Page 104 
 Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH 
6.2.2. Phủ định của vị từ và lƣợng từ. 
 Từ Định nghĩa của lƣợng từ "với mọi" và "tồn tại" và Bảng 6.4 - bảng ý nghĩa của các lƣợng 
 từ đối với vị từ hai ngôi, ta có Phủ định của các mệnh đề lượng từ hóa của vị từ một ngôi và 
 vị từ hai ngôi nhƣ sau : 
 Bảng 6.5. Phủ định của vị từ và lƣợng từ 
 Mệnh đề lượng từ hóa Phủ định của mệnh đề lượng từ hóa 
 ( ) ̅ ̅ ̅̅̅ ̅̅̅ ̅̅ ̅ ̅̅(̅ ̅̅) ̅̅(̅̅ ̅̅) 
 ( ) ̅̅ ̅̅̅ ̅̅̅ ̅ ̅̅ ̅̅(̅ ̅̅) ̅̅(̅̅ ̅̅) 
 ( ) ̅̅ ̅̅̅ ̅̅̅ ̅̅ ̅ ̅̅ ̅̅ ̅̅̅ ̅̅ ̅ ̅̅̅(̅ ̅̅ ̅ ̅̅) ̅̅̅(̅ ̅̅ ̅ ̅)̅ 
 ( ) ̅̅ ̅̅̅ ̅̅̅ ̅̅ ̅ ̅̅ ̅̅ ̅̅̅ ̅̅ ̅ ̅̅̅(̅ ̅̅ ̅ ̅̅) ̅̅̅(̅ ̅̅ ̅ ̅)̅ 
 ( ) ̅̅ ̅̅̅ ̅̅̅ ̅̅ ̅ ̅̅ ̅̅ ̅̅̅ ̅̅ ̅ ̅̅̅(̅ ̅̅ ̅ ̅̅) ̅̅̅(̅ ̅̅ ̅ ̅̅) 
 ( ) ̅̅ ̅̅̅ ̅̅̅ ̅̅ ̅ ̅̅ ̅̅ ̅̅̅ ̅̅ ̅ ̅̅̅(̅ ̅̅ ̅ ̅̅) ̅̅̅(̅ ̅̅ ̅ ̅̅) 
 Ví dụ 1 : Ta có định nghĩa, một hàm thực y = f(x) liên tục tại điểm x0 nếu : 
 *( | | ) | ( ) ( )| + 
 Suy ra, hàm thực y = f(x) không liên tục tại điểm x0 nếu : 
 ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
 *( | | ) | ( ) ( )| + 
 ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
 {( | | ) | ( ) ( )| } 
 *( | | ) | ( ) ( )| + . 
6.2.3. Dịch các câu thông thƣờng thành biểu thức logic 
 Sử dụng các vị từ và các lượng từ chúng ta có thể biểu diễn đƣợc một tập hợp rộng lớn các 
 câu thông thƣờng thành các biểu thức logic. 
 Việc làm này nhằm mục đích loại đi những đi những điều chƣa rõ ràng và ngƣời ta có thể sử 
 dụng các biểu thức này trong việc lập trình logic và trí tuệ nhân tạo. 
 Xét các ví dụ sau đây. 
 Ví dụ 1 : Dùng vị từ và lượng từ, ta có thể biểu diễn các suy luận thông thường như sau : 
 Toán rời rạc – Chương 6. Đại cương về toán logic Page 105 
Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH 
 Câu thông thường Vị từ Biểu thức logic 
1. Nếu một người nào đó P(x) : x là nữ. 
 là nữ và đã sinh con thì ( ) ( ) ( ) 
 người đó sẽ là mẹ của Q(x): x đã sinh con. 
 một người khác. (A là tập hợp tất cả loài người). 
 R(x,y) : x là mẹ của 
 y 
2. Tất cả sư tử đều hung P(x) : x là sư tử. 
 dữ. Nhưng một số sư tử ( ) ( )
 không uống cà phê. Vì Q(x) : x là hung dữ. ( ) ̅̅(̅̅ ̅̅) 
 vậy, có một số sinh vật 
 ( ) ̅̅(̅̅ ̅̅)
 hung dữ không uống cà R(x) : x uống cà 
 phê 
 phê. (A là tập hợp tất cả các sinh vật) 
3. Tất cả các con chim P(x) : x là chim 
 ruồi đều có màu sặc sỡ. ruồi. ( ) ( ) ( ) 
 Nhưng không có con ̅̅ ̅̅̅ ̅̅̅ ̅̅ ̅ ̅̅(̅ ̅̅)̅̅ ̅̅̅̅ ̅(̅̅ ̅̅) ( )
 Q(x) : x là lớn. 
 chim lớn nào sống ̅̅(̅̅ ̅̅) ̅̅(̅̅ ̅̅) ( )
 bằng mật ong. Và các 
 con chim không sống R(x) : x có màu sặc ( ) ̅̅̅(̅ ̅̅̅) 
 bằng mật ong đều sỡ 
 không có màu sặc sỡ. (A là tập hợp tất cả các sinh vật) 
 Do vậy, chim ruồi là S(x) : x sống bằng 
 nhỏ. mật ong 
Nhận xét: Suy luận trong câu thứ 3 ở Ví dụ 1 trên đây, được chứng minh suy diễn logic theo 
sơ đồ sau: 
 ̅̅ ̅̅̅ ̅̅ ̅̅ ̅̅ ̅̅(̅̅ ̅̅̅)̅ ̅̅̅ ̅̅(̅ ̅̅) - Khử phép kéo theo trong tiền đề (3.2) 
 ̅̅̅(̅̅ ̅̅̅)̅ ̅̅̅ ̅̅(̅ ̅̅) - Phủ định của lượng từ tồn tại 
 ̅̅̅̅̅̅
 ( ) ( ) - Luật De Morgan 
 ̅̅(̅̅ ̅̅) ̅̅(̅̅ ̅̅) - Tiền đề (3.3) 
 ( ) ̅̅(̅̅ ̅̅) 
 ̅̅(̅̅̅̅) ̅̅̅(̅̅̅)
 - Quy tắc phản đảo với (3.1) 
 ( ) ̅̅̅(̅ ̅̅)̅ 
 ̅̅̅̅̅̅
 ( ) ( ) - Theo định nghĩa của hội ( ) 
 ̅ ̅ ̅̅ ̅̅ ̅̅̅ ̅̅̅ ̅̅ ̅ ̅̅(̅ ̅̅)̅̅ ̅̅̅ ̅̅̅̅(̅̅ ̅̅̅)̅ ̅ - Quy tắc phản đảo 
Toán rời rạc – Chương 6. Đại cương về toán logic Page 106 
Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH 
 BÀI TẬP CHƢƠNG 6 
6.1. Cho các mệnh đề sau: 
 p: Bạn bị ốm, nghỉ học nhiều. 
 q: Bạn thi trƣợt kì thi kết thúc học phần. 
 r: Bạn đƣợc lên lớp. 
Phát biểu các mệnh đề sau theo cách nói thông thƣờng: 
 a) d) ( ̅) ( ̅) 
 b) ̅ e) ( ) ( ̅ ). 
 c) ̅ 
6.2. Cho các mệnh đề: 
 p: Bạn nhận đƣợc điểm giỏi trong kì thi cuối khóa. 
 q: Bạn làm hết bài tập trong quyển sách này. 
 r: Bạn sẽ đƣợc công nhận là sinh viên xuất sắc trong lớp. 
Hãy viết lại các mệnh đề sau thành các biểu thức logic: 
 a) Bạn đƣợc công nhận là sinh viên xuất sắc trong lớp nhƣng bạn không làm hết bài tập 
 trong quyển sách này. 
 b) Bạn nhận đƣợc điểm giỏi trong kì thi cuối khóa, bạn làm hết bài tập trong quyển sách 
 này và bạn sẽ đƣợc công nhận là sinh viên xuất sắc trong lớp. 
 c) Để đƣợc công nhận là sinh viên xuất sắc trong lớp bạn cần phải nhận đƣợc điểm giỏi 
 trong kì thi cuối khóa. 
 d) Bạn nhận đƣợc điểm giỏi ở kì thi cuối khóa, nhƣng bạn không làm hết các bài tập 
 trong quyển sách này, tuy nhiên bạn vẫn đƣợc công nhận là sinh viên xuất sắc trong 
 lớp. 
 e) Nhận đƣợc điểm giỏi trong kì thi cuối khóa, và bạn làm hết bài tập trong quyển sách 
 này là đủ để bạn đƣợc công nhận là xuất sắc trong lớp. 
 f) Bạn sẽ đƣợc công nhận là xuất sắc trong lớp nếu và chỉ nếu bạn làm hết bài tập trong 
 quyển sách này hoặc nhận đƣợc điểm giỏi trong kì thi cuối khóa. 
6.3. Dựa vào bảng chân trị, hãy chỉ ra công thức nào là đồng nhất đúng? Đồng nhất sai? 
 Tiếp liên? 
 a) ( ) e) ( ) ( ̅) 
 b) ( ) f) ( ) ( ) 
 c) ̅ ( ) ̅ g) ( ) (( ) ( ̅ ̅)) 
 d) ̅ ( ) ̅ h) (( ) ) ( ( )) 
6.4. Chứng minh các công thức sau là đồng nhất đúng bằng cách lập bảng chân trị hoặc sử 
 dụng điều kiện đồng nhất đúng. 
 a) ̅ ( ) d) ( ̅ ) ( ̅) 
 b) ̅ ̅̅ ̅̅̅̅ ̅ e) ( ) ( ) 
 c) ̅ ̅̅ ̅̅̅̅ ̅ ̅ f) ,( ) ( ) ( )- 
Toán rời rạc – Chương 6. Đại cương về toán logic Page 107 
 Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH 
 6.5. Chứng minh các tƣơng đƣơng logic sau: 
 a) ( ) ( ) d) ( ̅ ̅) ( ) 
 b) ( ) e) ( ) 
 c) ( ) f) ( ) 
 6.6. Chứng minh các suy luận sau là ĐÚNG? 
 ( )
 ( ) 
 a) b) c) d) e) 
 ( ) ( ) 
 k) ( ) 
 f) g) h) 
 ̅ 
 6.7. Tìm một phản ví dụ chứng tỏ suy luận sau là SAI? 
 a) ( ) b) 
 6.8. Cho các vị từ: ( ) ( ) ; ( ) . 
 Hãy phát biểu mệnh đề hóa lƣợng từ sau và xác định giá trị chân lý của nó. 
 a) ( ) c) ( ). 
 b) ( ) d) ( ) 
 e) ( ). 
 6.9. Xác định phủ định của các mệnh đề lƣợng từ hóa sau? Xác định giá trị chân lý của các 
 mệnh đề phủ định đó? 
 a) 
 b) 
6.10. Dịch các suy diễn sau thành các biểu thức logic? Suy diễn đó là đúng hay sai? Giải 
 thích? 
 a) Biết rằng không có con vịt nào sẵn lòng khiêu vũ cả. Không có viên sĩ quan nào từ 
 chối khiêu vũ. Nhƣng toàn bộ đàn gia cầm của tôi là vịt bởi vậy, toàn bộ đàn gia cầm 
 của tôi không phải là các sĩ quan. 
 b) Tất cả những đứa bé là không logic. Mà những ngƣời không logic thì bị coi thƣờng. 
 Thế nhƣng, không ai bị coi thƣờng nếu cai quản đƣợc cá sấu. Do vậy những đứa bé 
 không cai quản đƣợc cá sấu. 
 c) Tất cả các giải thích rõ ràng đều là thỏa đáng. Một số lý do là không thỏa đáng. Vậy 
 có một số lý do không phải là giải thích rõ ràng. 
 Toán rời rạc – Chương 6. Đại cương về toán logic Page 108 
Học viện Nông nghiệp Việt Nam – Khoa CNTT - Bộ môn TTƯD – NTTH 
Tài liệu tham khảo: 
 . Vũ Kim Thành, Toán rời rạc, NXB Đại học Sƣ phạm, 2008. 
 . Nguyễn Hữu Anh, Toán rời rạc, NXB giáo dục, 2000. 
 . Đỗ Đức Giáo, Toán rời rạc, NXB Đại học Quốc gia Hà Nội, 2008. 
 . Hoàng Chí Thành, Đồ thị và các thuật toán, NXB giáo dục, 2007. 
 . Nguyễn Đức Nghĩa – Nguyễn Tô Thành, Toán rời rạc, NXB Đại học quốc gia Hà 
 Nội, 2003. 
 . Kenneth H. Rosen, Toán rời rạc (Bản dịch tiếng Việt của Phạm Văn Thiều – Đặng 
 Hữu Thịnh), Nhà xuất bản Khoa học và Kỹ Thuật Hà Nội. 
 Page 109 

File đính kèm:

  • pdfbai_giang_toan_roi_rac_nguyen_thi_thuy_hanh.pdf