Toán Rời Rạc - Chương 1: Cơ Sở Logic - Công Nghệ Thông Tin

Đăng nhập / Đăng ký

• ViOLET.VN
• Bài giảng
• Giáo án
• Đề thi & Kiểm tra
• Tư liệu
• E-Learning
• Kỹ năng CNTT
• Trợ giúp

Thư mục

Các ý kiến mới nhất

bài giảng rất hay, nội dung phong phú. Cám ơn...

BÀI 5 T1 SỬ DỤNG ĐIỆN THOẠI...

Bài 5. Em vượt qua khó khăn trong học tập...

Bài 9. Triều Lý và việc định đô ở Thăng...

Bài 9. Triều Lý và việc định đô ở Thăng...

Bài 11 T3 Năng lượng mặt trời,  gió và nước...

Bài 11 T2 Năng lượng mặt trời,  gió và nước...

BAI 6 T2 NÓI VÀ NGHE...

BAI 6 T1 BUOI SANG Ở TP HỒ CHÍ MINH...

BAI 5 T4 VIET BAI VAN KCST...

BAI 5 T3 LTVC LT VỀ ĐẠI TỪ...

BAI 5 T1,2 TRƯỚC NGÀY GIÁNG SINH...

BAI 36 CHIA MỘT SỐ TN CHO MỘT SỐ TN...

BAI 35 CHIA MOT SO TP CHO MOT SO TN...

Thành viên trực tuyến

857 khách và 1244 thành viên

lê minh hải

khổng mai phương

Hoàng Văn Thái

Vi Lo Anh Phat

Nguyễn Thị Hằng

Trần Thị Hạnh

Trương Thị Thu Vân

nguyễn thị thảo linh

Nguyễn Chi

Hoàng Nghĩa Ánh

Lê Thị Thảo

Đinh Thị Nghĩa

Trần Thị Hà Trang

Nguyễn Quế Chi

Lê Thị Thúy

Vũ Thị Lệ

Lê Đức Hiệp

Nguyễn Hồng Loan

Trần Thị Bích Thuỷ

Khổng Thanh Hiền

Tìm kiếm theo tiêu đề

Đăng nhập

Tên truy nhập Mật khẩu Ghi nhớ   Quên mật khẩu ĐK thành viên

Tin tức cộng đồng

5 điều đơn giản cha mẹ nên làm mỗi ngày để con hạnh phúc hơn

Tìm kiếm hạnh phúc là một nhu cầu lớn và xuất hiện xuyên suốt cuộc đời mỗi con người. Tác giả người Mỹ Stephanie Harrison đã dành ra hơn 10 năm để nghiên cứu về cảm nhận hạnh phúc, bà đã hệ thống các kiến thức ấy trong cuốn New Happy. Bà Harrison khẳng định có những thói quen đơn...

Hà Nội công bố cấu trúc định dạng đề minh họa 7 môn thi lớp 10 năm 2025

23 triệu học sinh cả nước chính thức bước vào năm học đặc biệt

Xem tiếp

Tin tức thư viện

Chức năng Dừng xem quảng cáo trên violet.vn

Kính chào các thầy, cô! Hiện tại, kinh phí duy trì hệ thống dựa chủ yếu vào việc đặt quảng cáo trên hệ thống. Tuy nhiên, đôi khi có gây một số trở ngại đối với thầy, cô khi truy cập. Vì vậy, để thuận tiện trong việc sử dụng thư viện hệ thống đã cung cấp chức năng...

Khắc phục hiện tượng không xuất hiện menu Bộ công cụ Violet trên PowerPoint và Word

Thử nghiệm Hệ thống Kiểm tra Trực tuyến ViOLET Giai đoạn 1

Xem tiếp

Quảng cáo

Hướng dẫn sử dụng thư viện

Bài 4: Quản lí ngân hàng câu hỏi và sinh đề có điều kiện

Ở , , chúng ta đã biết cách tạo một đề thi từ ngân hàng có sẵn hay tự nhập câu hỏi, tạo cây thư mục để chứa đề thi cho từng môn. Trong bài này chung ta tiếp tục tìm hiểu cách xây dựng và quản lý ngân hàng câu hỏi mà mình đã đưa lên và...

Bài 3: Tạo đề thi trắc nghiệm trực tuyến dạng chọn một đáp án đúng

Bài 2: Tạo cây thư mục chứa câu hỏi trắc nghiệm đồng bộ với danh mục SGK

Bài 1: Hướng dẫn tạo đề thi trắc nghiệm trực tuyến

Lấy lại Mật khẩu trên violet.vn

Kích hoạt tài khoản (Xác nhận thông tin liên hệ) trên violet.vn

Đăng ký Thành viên trên Thư viện ViOLET

Tạo website Thư viện Giáo dục trên violet.vn

Xác thực Thông tin thành viên trên violet.vn

Hỗ trợ trực tuyến trên violet.vn bằng Phần mềm điều khiển máy tính từ xa TeamViewer

Xem tiếp

Hỗ trợ kĩ thuật

• (024) 62 930 536
• 0919 124 899
• hotro@violet.vn

Liên hệ quảng cáo

• (024) 66 745 632
• 096 181 2005
• contact@bachkim.vn

Tìm kiếm Bài giảng

Đưa bài giảng lên Gốc > Cao đẳng - Đại học > Công nghệ thông tin >

• Toán Rời Rạc - Chương 1: Cơ Sở Logic
• Cùng tác giả
• Lịch sử tải về

Toán Rời Rạc - Chương 1: Cơ Sở Logic

• 
• 
• 
• 
• 
• 
• 0 / 0
• 

Nhấn vào đây để tải về Báo tài liệu có sai sót Nhắn tin cho tác giả (Tài liệu chưa được thẩm định) Nguồn: Đại Học Công Nghệ Thông Tin - ĐHQG.TPHCM Người gửi: Võ Ngọc Thảo Ngày gửi: 18h:11' 09-06-2016 Dung lượng: 796.3 KB Số lượt tải: 160 Số lượt thích: 0 người CẤU TRÚC RỜI RẠC1CHƯƠNG I: CƠ SỞ LÔGICMệnh đềBiểu thức logic (Dạng mệnh đề)Qui tắc suy diễnVị từ, lượng từQuy nạp toán học2 “Toan tính của chiến lược gia 44 tuổi đã suýt thành công nếu ông không tính tới đột biến từ những ngôi sao đối phương”. Nguồn:http://thethao.vnexpress.net/tin-tuc/champions-league/sneijder-ket-lieu-juventus-trong-con-mua-tuyet-2922371.html3Mệnh đề Định nghĩa: Mệnh đề là một khẳng định có giá trị chân lý xác định, đúng hoặc sai. Câu hỏi, câu cảm thán, mệnh lệnh… không là mệnh đề.Ví dụ: - Đại học CNTT trực thuộc ĐHQG TP.HCM.- 1+7 =8.- Hôm nay em đẹp quá! (không là mệnh đề)- Hôm nay ngày thứ mấy? (không là mệnh đề)4Mệnh đềKý hiệu: người ta dùng các ký hiệu P, Q, R… (p,q,r,…) để chỉ mệnh đề.Chân trị của mệnh đề: Một mệnh đề chỉ có thể đúng hoặc sai, không thể đồng thời vừa đúng vừa sai. Khi mệnh đề P đúng ta nói P có chân trị đúng, ngược lại ta nói P có chân trị sai. Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1(hay Đ,T) và 0(hay S,F)5Mệnh đềPhân loại: gồm 2 loại Mệnh đề phức hợp: là mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết bằng các liên từ (và, hay, khi và chỉ khi,…) hoặc trạng từ “không” Mệnh đề sơ cấp (nguyên thủy): Là mệnh đề không thể xây dựng từ các mệnh đề khác thông qua liên từ hoặc trạng từ “không”6Mệnh đềVí dụ:- 2 là số nguyên tố.- 2 không là số nguyên tố.- 2 là số nguyên tố và là số lẻ.- An đang xem ti vi hay đang học bài.7Các phép toán: có 5 phép toánPhép phủ định: phủ định của mệnh đề P là một mệnh đề, ký hiệu là P hay (đọc là “không” P hay “phủ định của” P). Bảng chân trị : Ví dụ:- 2 là số nguyên tố.Phủ định: 2 không là số nguyên tố- 15 > 5 Phủ định: 15 ≤ 5Mệnh đề8 Phép hội (nối liền, giao): của hai mệnh đề P, Q là một mệnh đề, kí hiệu P  Q (đọc là “P và Q)Bảng chân trị:NX: PQ đúng khi và chỉ khi P và Q đồng thời đúng.Ví dụ: P: “Hôm nay là chủ nhật” Q: “Hôm nay trời mưa” P  Q: “ Hôm nay là chủ nhật và trời mưa”Mệnh đề9 Phép tuyển (nối rời, hợp): của hai mệnh đề P, Q là một mệnh đề, kí hiệu P  Q (đọc là “P hay Q”). Bảng chân trị:NX: P  Q sai khi và chỉ khi P và Q đồng thời sai. Ví dụ: - e > 4 hay e > 5 (S) - 2 là số nguyên tố hay là số lẻ (Đ)Mệnh đề10 Phép kéo theo: Mệnh đề P kéo theo mệnh đề Q là một mệnh đề, kí hiệu P  Q (đọc là “P kéo theo Q” hay “Nếu P thì Q” hay “P là điều kiện đủ của Q” hay “Q là điều kiện cần của P”). Bảng chân trị:NX: P  Q sai khi và chỉ khi P đúng mà Q sai. Ví dụ: e >4 kéo theo 5>6Mệnh đề11 Phép kéo theo hai chiều (phép tương đương): Mệnh đề P kéo theo mệnh đề Q và ngược lại (mệnh đề P tương đương với mệnh đề Q) là một mệnh đề, ký hiệu P  Q (đọc là “P nếu và chỉ nếu Q” hay “P khi và chỉ khi Q” hay “P là điều kiện cần và đủ của Q”). Bảng chân trị:NX: P  Q đúng khi và chỉ khi P và Q có cùng chân trịVí dụ: 6 chia hết cho 3 khivà chỉ khi 6 chia hết cho 2Mệnh đề12 Định nghĩa: Biểu thức logic được cấu tạo từ: - Các mệnh đề (các hằng mệnh đề) - Các biến mệnh đề p, q, r, …, tức là các biến lấy giá trị là các mệnh đề nào đó - Các phép toán logic , , , ,  và dấu đóng mở ngoặc () để chỉ rõ thứ tự thực hiện của các phép toán.Ví dụ:E(p,q) = (p  q)F(p,q,r) = (p  q)  (q  r)Biểu thức logic (Dạng mệnh đề)13 Độ ưu tiên của các toán tử logic: - Ưu tiên mức 1: ()- Ưu tiên mức 2: - Ưu tiên mức 3: , - Ưu tiên mức 4: ,  Bảng chân trị của một biểu thức logic: là bảng liệt kê chân trị của biểu thức logic theo các trường hợp về chân trị của tất cả các biến mệnh đề trong biểu thức logic hay theo các bộ giá trị của bộ biến mệnh đề. Biểu thức logic14Bảng chân trị của một biểu thức logic.Ví dụ: Với một biến mệnh đề, ta có hai trường hợp là 0 hoặc 1.Với hai biến mệnh đề p,q ta có bốn trường hợp chân trị của bộ biến (p,q) là các bộ giá trị (0,0), (0,1), (1,0) và (1,1).NX: Trong trường hợp tổng quát, nếu có n biến mệnh đề thì ta có trường hợp chân trị cho bộ n biến. Biểu thức logic15 Ví dụ: Cho E(p,q,r) =(p  q)  r . Ta có bảng chân trị sau:Biểu thức logic16Tương đương logic: Hai biểu thức logic E và F theo các biến mệnh đề nào đó được gọi là tương đương logic nếu chúng có cùng bảng chân trị.Ký hiệu: E  F (E tương đương với F).Ví dụ: (p  q)  p  qBiểu thức logic E được gọi là hằng đúng nếu chân trị của E luôn bằng 1(đúng) trong mọi trường hợp về chân trị của các biến mệnh đề có trong E. Nói cách khác, E là hằng đúng khi ta có E  1.Biểu thức logic17Tương tự, E là một hằng sai khi ta có E  0.Ví dụ: E(p,q) = p  p là hằng sai. F(p,q) =(pq)  (p  q) là hằng đúng.Định lý: Hai biểu thức logic E và F tương đương với nhau khi và chỉ khi E  F là hằng đúng.Ví dụ: (pq)  (p  q)Hệ quả logic: F được gọi là hệ quả logic của E nếu E  F là hằng đúng.Ký hiệu: E  FVí dụ: (p  q)  pBiểu thức logic18Phủ định của phủ định: p  pQui tắc De Morgan:  (p  q)   p   q  (p  q)   p   qLuật giao hoán: p  q  q  p p  q  q  pLuật kết hợp: (p  q)  r  p  (q  r) (p  q)  r  p  (q  r)Các luật logic19Luật phân phối: p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r)Luật lũy đẳng: p  p  p p  p  pLuật trung hòa: p  0  p p  1  pLuật về phần tử bù: p  p  0 p  p  1 Các luật logic20 Luật thống trị: p  0  0 p  1  1 Luật hấp thu: p  (p  q)  p p  (p  q)  p Luật về phép kéo theo: p  q  p  q   q   pVí dụ: Cho p, q, r là các biến mệnh đề. Chứng minh rằng: (p  r)  (q  r)  (p  q)  r Các luật logic21Các luật logic22Qui tắc De Morgan:  (p  q)   p   q  (p  q)   p   qVD: Dùng bảng chân trị chứng minh qui tắc De MorganVí dụ: Cho p, q, r là các biến mệnh đề. Chứng minh rằng: (p  r)  (q  r)  (p  q)  r .Giải: Các luật logic23 ( p  r)  (q  r) ( p  r )  ( q  r) ( p   q )  r ( p  q )  r ( p  q )  r (p  q )  rĐịnh nghĩa: Trong các chứng minh toán học, ta thường thấy những lý luận dẫn xuất có dạng: nếu và và thì q. Dạng lý luận này là đúng khi ta có biểu thức là hằng đúng.Ta gọi dạng lý luận trên là một quy tắc suy diễn và thường được viết theo các cách sau đây:Cách 1: Biểu thức hằng đúngQui tắc suy diễn24Định nghĩa: Cách 2: Dòng suy diễnCách 3: Mô hình suy diễnCác biểu thức logic được gọi là giả thiết (hay tiên đề), biểu thức q được gọi là kết luận.Qui tắc suy diễn25 Qui tắc khẳng định (Modus Ponens): [(p  q)  p]  q Ví dụ: Học tốt thi đậu SV A học tốtSuy ra: SV A thi đậu Nếu chuồn chuồn bay thấp thì mưa  Thấy chuồn chuồn bay thấpSuy ra: trời mưaQui tắc suy diễn 262. Qui tắc phủ định (Modus Tollens): [(p  q)  q ]   p Ví dụ: • Nếu A đi học đầy đủ thì A đậu toán rời rạc.• A không đậu toán rời rạc.Suy ra: A không đi học đầy đủ.Qui tắc suy diễn273. Qui tắc tam đoạn luận: [(p  q)  (q  r)]  (p  r) Ví dụ: • Nếu trời mưa thì đường ướt• Nếu đường ướt thì đường trơnSuy ra: nếu trời mưa thì đường trơn.Qui tắc suy diễn2829Qui tắc suy diễn Qui tắc phản chứng: * Tổng quát:Qui tắc suy diễn30Để chứng minh vế trái là một hằng đúng, ta chứng minh nếu thêm phủ định của q vào các tiên đề thì được một mâu thuẫn. Qui tắc phản chứng:Ví dụ: Qui tắc suy diễn31 Qui tắc chứng minh theo trường hợp : [(p  r)  (q  r)]  [(p  q)r]* Tổng quát:Qui tắc suy diễn326.Phản ví dụ: Để chứng minh một phép suy luận là sai hay không là một hằng đúng, ta chỉ cần chỉ ra một phản ví dụ.Qui tắc suy diễn33Để tìm một phản ví dụ ta chỉ cần chỉ ra một trường hợp về chân trị của các biến mệnh đề sao cho các tiên đề trong phép suy luận là đúng còn kết luận là sai.6.Phản ví dụ: Ví dụ: Hãy kiểm tra suy luận:NX: Ta sẽ tìm p,q,r thỏaDễ dàng tìm thấy một phản ví dụ: p=1,q=0,r=1.Vậy suy luận đã cho là không đúngQui tắc suy diễn346. Phản ví dụVí dụ: Ông Minh nói rằng nếu không được tăng lương thì ông ta sẽ nghỉ việc. Mặt khác, nếu ông ấy nghỉ việc và vợ ông ấy bị mất việc thì phải bán xe.Biết rằng nếu vợ ông Minh hay đi làm trễ thì trước sau gì cũng sẽ bị mất việc và cuối cù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ễ.Qui tắc suy diễn35p: ông Minh được tăng lương.q: ông Minh nghỉ việc.r: vợ ông Minh mất việc.s: gia đình phải bán xe.t: vợ ông hay đi làm trể. Ví dụ:Suy luận sau đúng hay saiQui tắc suy diễn3637 Ví dụ:Suy luận sau đúng hay saiHD: Dùng phản ví dụ: Chọn Qui tắc suy diễn37p=1, q=0, r=1, s=0, t=1Suy luận (lập luận) sau đúng hay sai?3839Qui tắc suy diễn40Giải41Định nghĩa: Vị từ là một khẳng định p(x,y,..), trong đó x,y...là các biến thuộc tập hợp A, B,.. cho trước sao cho:- Bản thân p(x,y,..) không phải là mệnh đề- Nếu thay x,y,.. thành giá trị cụ thể thì p(x,y,..) là mệnh đề.Ví dụ:- p(n) = “n +1 là số nguyên tố”- q(x,y) = “x + y = 1” Vị từ - Lượng từ42Các phép toán trên vị từCho trước các vị từ p(x), q(x) theo một biến xA. Khi ấy, ta cũng có các phép toán tương ứng như trên mệnh đề: Phủ định: p(x) Phép nối liền (hội, giao): p(x)  q(x) Phép nối rời (tuyển, hợp): p(x)  q(x) Phép kéo theo: p(x)  q(x) Phép kéo theo hai chiều: p(x)  q(x)Vị từ - Lượng từ43Cho p(x) là một vị từ theo một biến xác định trên A. Các mệnh đề lượng từ hóa của p(x) được định nghĩa như sau:- Mệnh đề “Với mọi x thuộc A, p(x) ”, kí hiệu: “x  A, p(x)” là mđ đúng khi và chỉ khi p(a) luôn đúng với mọi giá trị a  A.  đgl lượng từ phổ dụng- Mệnh đề “Tồn tại (có ít nhất một) x thuộc A, p(x)” kí hiệu “x  A, p(x)” là mệnh đề đúng khi và chỉ khi có ít nhất một giá trị x= a’ A nào đó sao cho mệnh đề p(a’) đúng.  đgl lượng từ tồn tạiVị từ - Lượng từ4445Cho p(x, y) là một vị từ theo hai biến x, y xác định trên AB. Ta định nghĩa các mệnh đề lượng từ hóa của p(x, y) như sau:“xA,yB, p(x, y)”  “xA, (yB, p(x, y))”“xA, yB, p(x, y)”  “xA, (yB, p(x, y))”“xA, yB, p(x, y)”  “xA, (yB, p(x, y))”“xA, yB, p(x, y)”  “xA, (yB, p(x, y))”Vị từ - Lượng từ47Ví dụ: Các mệnh đề sau đúng hay sai?- “x  R, ”- “x  R, ”- “x  R, y  R, 2x + y < 1”- “x  R, y  R, 2x + y < 1”- “x  R, y  R, x + 2y < 1”- “x  R, y  R, x + 2y < 1”Vị từ - Lượng từ4849505152Định lýCho p(x, y) là một vị từ theo hai biến x, y xác định trên AB. Khi đó: “xA, yB, p(x, y)”  “yB, xA, p(x, y)” “xA, yB, p(x, y)”  “yB, xA, p(x, y)” “xA, yB, p(x, y)”  “yB, xA, p(x, y)”Phủ định của mệnh đề lượng từ hóa vị từ p(x,y,..) có được bằng cách: thay  thành , thay  thành , và p(x,y,..) thành  p(x,y,..).Vị từ - Lượng từ53Với vị từ theo 1 biến ta có :Với vị từ theo 2 biến Vị từ - Lượng từ54Ví dụ phủ định các mệnh đề sau- “x  A, 2x + 1  0”- “>0,  > 0:(xR: x – a