Tài liệu cầm tắt bài xích giảng môn Toán tách rạc vì Nguyễn Ngọc Trung biên soạn có cấu tạo gồm 4 chương cung cấp cho tất cả những người đọc những kiến thức: Mệnh đề, phép đếm, quan hệ, đại số Boole.

Bạn đang xem: Công thức toán rời rạc

Mời chúng ta cùng tìm hiểu thêm nội dung bỏ ra tiết.

Đang xem: công thức toán rời rạc

TRƯỜNG ĐẠI HỌC SƯ PHẠM tp.hcm KHOA TOÁN – TIN HỌC TÓM TẮT BÀI GIẢNG MônTOÁN RỜI RẠC giảng viên biên soạn: Nguyễn Ngọc Trung thành phố hồ chí minh 9.2006 MỤC LỤCChương 1. Mệnh đề……………………………………………………………………………. 3 1.1 Mệnh đề – Tính chất……………………………………………………………….. 3 1.1.1 Mệnh đề và những phép toán mệnh đề …………………………………….. 3 1.1.2 Dạng mệnh đề …………………………………………………………………. 5 1.1.3 những quy tắc diễn dịch ………………………………………………………… 7 1.2 Vị trường đoản cú – Lượng từ…………………………………………………………………… 11 1.3 nguyên tắc quy nạp……………………………………………………………….. 14Chương 2. Phép đếm………………………………………………………………………… 15 2.1 Tập hòa hợp – Tính chất……………………………………………………………… 15 2.2 Ánh xạ ……………………………………………………………………………….. 17 2.3 Giải tích tổ hợp ……………………………………………………………………. 18 2.3.1 Các nguyên tắc cơ bản của phép đếm: ………………………………… 18 2.3.2 Giải tích tổng hợp ……………………………………………………………… 19 2.3.3 nguyên tắc Dirichlet. (nguyên lý chuồng người tình câu) …………………. 23Chương 3. Quan hệ tình dục ………………………………………………………………………….. 24 3.1 quan hệ giới tính ……………………………………………………………………………… 24 3.2 quan lại hệ tương tự …………………………………………………………… 25 3.3 quan liêu hệ thứ tự – Biểu vật dụng Hasse ……………………………………………… 26Chương 4. Đại số Boole ……………………………………………………………………. 30 4.1 Đại số Boole: Định nghĩa – tính chất ……………………………………… 30 4.2 Hàm Boole – Dạng nối rời chính tắc ……………………………………….. 36 4.3 câu hỏi mạch năng lượng điện – Mạng những cổng………………………………………. 42 4.4 Tìm công thức đa thức buổi tối tiểu – phương pháp Karnaugh …………… 44TÀI LIỆU THAM KHẢO……………………………………………………………….. 51Tóm tắt bài xích giảng Toán rời rộc rạc Trường ĐHSP tp.hcm 1 Chương 1. Mệnh đề1.1 Mệnh đề – Tính chất1.1.1 Mệnh đề và những phép toán mệnh đềĐịnh nghĩa. Mệnh đề là các xác định có cực hiếm chân lý xác minh (đúng hoặc sai,nhưng quan trọng vừa đúng, vừa sai). Các mệnh đề đúng được nói là gồm chân trịđúng, những mệnh đề không nên được nói là có chân trị sai.Ví dụ: – Các xác minh sau là mệnh đề: . “1 + 2 = 5” là mệnh đề sai. . “10 là số chẵn” là mệnh đề đúng. – Các khẳng định sau chưa phải là mệnh đề: . “Tôi đi học” . “n là số nguyên tố”Ký hiệu: Ta thường cam kết hiệu những mệnh đề bằng các chữ loại in hoa: P, Q, R, … vàchân trị đúng (sai) được ký kết hiệu vày 1 (0).Các phép toán mệnh đề:  Phép đậy định: tủ định của mệnh đề p được ý hiệu vì chưng P (đọc là “không P” hoặc “phủ định của P”. Chân trị của P là 0 trường hợp chân trị của P là một và ngược lại. VD. P = “3 là số nguyên tố” là mệnh đề đúng. Cho nên vì vậy mệnh đề P = “3 ko là số yếu tắc là mệnh đề sai. Bảng sau gọi là bảng chân trị của phép đậy định: p. P 0 1 1 0  Phép nối liền: Mệnh đề nối liến của nhì mệnh đề phường và Q được cam kết hiệu bởi p.  Q (đọc là “P cùng Q”. Chân trị của p.  Q là 1 trong những nếu cả p. Lẫn Q đều có chân trị là 1, trong các trường hợp khác p  Q có chân trị là 0. VD. P. = “Hôm nay trời đẹp” với Q = “Trận soccer hấp dẫn”. Lúc đó ta gồm mệnh đề gắn liền của p và Q là: phường  Q = “Hôm nay trời đẹp cùng trận đá bóng hấp dẫn”. Mệnh đề nối liền này vẫn đúng ví như như cả hai mệnh đề phường và Q phần nhiều Trang 3Tóm tắt bài bác giảng Toán rời rạc Trường ĐHSP tp.hồ chí minh đúng. Ngược lại nếu có một trong những hai mệnh đề trên sai hoặc cả hai cùng sai thì mệnh đề nồi liền vẫn là sai. Bảng chân trị của phép nối liền: phường Q phường Q 0 0 0 0 1 0 1 0 0 1 1 1  Phép nối rời: Mệnh đề nối rời của nhị mệnh đề p và Q được ký kết hiệu bởi p  Q (đọc là “P giỏi Q”. Chân trị của phường  Q là 0 ví như cả p. Lẫn Q đều phải sở hữu chân trị là 0, trong các trường phù hợp khác p  Q tất cả chân trị là 0. VD. P. = “An là ca sĩ”, p = “An là giáo viên”. Lúc ấy ta bao gồm mệnh đề nối tránh của phường và Q là p  Q = “An là ca sĩ xuất xắc An là giáo viên”. Mệnh đề nối liền này vẫn đúng nếu như như một trong các hai mệnh đề bên trên là đúng hoặc cả nhì mệnh đề trên những đúng. Nếu cả nhị mệnh đề p và Q các sai thì p.  Q vẫn sai. Bảng chân trị của phép nối rời: p. Q PQ 0 0 0 0 1 1 1 0 1 1 1 1  Phép kéo theo: Mệnh đề p. Kéo theo Q được ký hiệu là phường  Q . Để xác định chân trị của mệnh đề p. Kéo theo Q ta xét lấy ví dụ như sau: phường = “An trúng số”, Q = “An sở hữu xe máy”, lúc ấy mệnh đề p. Kép theo Q sẽ là “Nếu An trúng số thì An sẽ cài xe máy”. Ta có các trường hợp sau đây:  An vẫn trúng số cùng anh ta sở hữu xe máy: phân minh mệnh đề p  Q là đúng.  An vẫn trúng số nhưng anh ta không cài đặt xe máy: ví dụ mệnh đề p.  Q là sai.  An không trúng số cơ mà anh ta vẫn cài xe máy: mệnh đề phường  Q vẫn đúng.  An ko trúng số và anh ta không download xe máy: mệnh đề p.  Q đúng. Trang 4Tóm tắt bài giảng Toán rời rạc Trường ĐHSP tp.hồ chí minh Bảng chân trị của phép kéo theo: p. Q PQ 0 0 1 0 1 1 1 0 0 1 1 1  Phép kéo theo nhị chiều: Mệnh đề p kéo theo Q và ngược lại được cam kết hiệu bởi p.  Q là mệnh đề tất cả chân trị đúng vào khi P và Q tất cả chân trị kiểu như nhau (cùng đúng hoặc cùng sai) và có chân trị sai khi p và Q tất cả chân trị khác nhau. VD. P = “An học tập giỏi”, Q = “An lấy điểm cao”. Lúc ấy mệnh đề phường  Q = “Nếu An học giỏi thì An sẽ tiến hành điểm cao với ngược lại”. Bảng chân trị của phép kéo theo hai chiều như sau: p Q PQ 0 0 1 0 1 0 1 0 0 1 1 11.1.2 Dạng mệnh đềĐịnh nghĩa. Dạng mệnh đề được xây cất từ: – những mệnh đề (là các hằng mệnh đề) – các biến mệnh đề p, q, r, … rất có thể lấy cực hiếm là những mệnh đề làm sao đó. – các phép toán bên trên mệnh đề, và những dấu ngoặc ( ).Ví dụ. E ( p, q, r )   p  q    r  phường  là một trong dạng mệnh đề trong đó p, q, r là cácbiến mệnh đề.Để ý rằng ta rất có thể xây dựng những dạng mệnh đề phức tạp từ những dạng mệnh đềđơn giản hơn bằng cách sử dụng các phép toán mệnh đề để kết hợp chúng lại.Chẳng hạn như dạng mệnh đề E(p,q,r) nghỉ ngơi trên được kết nối từ hai dạng mệnh đềE1 ( p, q, r )  phường  q với E2 ( p, q, r )  r  phường bằng phép toán nối rời (  ).Mỗi dạng mệnh đề vẫn được sẽ sở hữu được một bảng chân trị xác minh trong kia mỗi mẫu chobiết chân trị của dạng mệnh đề đó theo những chân trị ví dụ của các biến. Trang 5Tóm tắt bài xích giảng Toán rời rạc Trường ĐHSP TP.HCMVí dụ. E ( p, q, r )   p.  q    r  p  gồm bảng chân trị như sau: p. Q r r pq r  p E(p,q,r) 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1Định nghĩa. Hai dạng mệnh đề E với F được nói là tương đương lô ghích nếu chúng cócùng bảng chân trị. Lúc đó ta viết E  F .Chú ý rằng ví như E cùng F tương đương súc tích thì dạng mệnh đề phường  Q luôn lấy giá chỉ trịlà 1 dù các biến tất cả lấy bất kể giá trị nào.Định nghĩa. I. Một dạng mệnh đề được gọi là 1 trong những hằng đúng ví như nó luôn luôn lấy chân trị 1 ii. Một dạng mệnh đề được gọi là 1 hằng sai trường hợp nó luôn luôn lấy chân trị 0.Mệnh đề. Nhì dạng mệnh đề E cùng F tương đương xúc tích và ngắn gọn khi và chỉ còn khi phường  Q là mộthằng đúng.Định nghĩa.

Xem thêm: Tin Tức, Hình Ảnh Mới Nhất Về Irina, Irina Shayk

Dạng mệnh đề F được nói là hệ quả xúc tích và ngắn gọn của dạng mệnh đề E nếuE  F là một trong những hằng đúng. Lúc đó ta viết E  F .Các quy hiện tượng logic:Định lý. Cùng với p, q, r là những biến mệnh đề, 1 là hằng đúng, 0 là hằng sai, ta bao gồm cáctương đương logic: i. Tủ định của bao phủ định: p  p ii. Quy tắc De Morgan:   p.  q   p  q cùng   p  q   p  q iii. Pháp luật kéo theo: p.  q  p  q iv. Nguyên lý giao hoán: pq  q p. Trang 6Tóm tắt bài xích giảng Toán rời rốc Trường ĐHSP tp.hcm và p  q  q  p v. điều khoản phân phối: p  q  r    p.  q   p.  r  và p   q  r    p.  q    phường  r  vi. Lao lý kết hợp: p.  q  r    p.  q  r và p   q  r    phường  q   r vii. Dụng cụ lũy đẳng: p phường  p và p p  p viii. Qui định trung hòa: p. 1  p và p0 p ix. Phần tử bù: p.  p  0 và p.  p  1 x. Cách thức thống trị: p0  0 và p. 1  1 xi. Cách thức hấp thụ: p   p  q  phường và p.   p.  q  pVí dụ. Sử dụng những quy cơ chế logic minh chứng rằng dạng mệnh đềE ( p, q)   p.   p.  q    q là hằng đúng.Giải. E(p,q)   p   p  q    q   p.  p    p.  q    0   p.  q    q   p  q  q  p   q  q  p  1  11.1.3 các quy tắc suy diễnTrong chứng minh toán học, xuất phát từ một số khẳng định đúng (mệnh đề đúng)gọi là tiền đề, ta vẫn áp dụng các quy tắc suy diễn nhằm suy ra chân lý của một khẳngđịnh q cơ mà ta gọi là kết luận. Nói giải pháp khác, ta sẽ nên tìm cách chứng minh dạngmệnh đề  p1  p2    pn   q là 1 hằng đúng, trong những số đó p1 , p2 ,…, pn , q là cácdạng mệnh đề theo một số biến xúc tích nào đó. Trang 7Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCMVí dụ. đưa sử ta có các tiền đề: p1: “Nếu An học siêng thì An ăn điểm cao” p2: “Nêu An không hay đi dạo thì An học tập chăm” p3: “An không ăn điểm cao”Ta ao ước dùng những quy tắc suy diễn nhằm suy ra kết luận: q = “An hay phải đi chơi”. Muốnvậy, ta bắt buộc trừu tượng hóa những mệnh đề nguyên thủy: “An học tập chăm”, “An xuất xắc đichơi” với “An đạt điểm cao” thành các biến mệnh đề p, q, r. Như vậy những tiền đềbây giờ đồng hồ trở thành những dạng mệnh đề: p1  p.  r p2  q  phường p3  rTa phải chứng tỏ dạng mệnh đề sau là 1 trong hằng đúng:  p.  r    q  phường   r   qTa tất cả thể minh chứng điều này bằng phương pháp lập bảng chân trị của dạng mệnh đề trên.Tuy nhiên phương pháp này sẽ gặp mặt rất nhiều trở ngại khi các biến mệnh đề khủng (số dòngcủa bảng chân trị bởi 2n, với n là số đổi mới mệnh đề). Một phương thức khác là sửdụng các quy tắc suy diễn để chia việc ra thành nhiều cách nhỏ, nghĩa là từ cáctiền đề ta suy ra một số kết luận trung gian trước khi áp dụng những quy tắc suy diễnđể suy ra kết luận. Để luôn thể ta quy mô hóa phép suy diễn thành sơ thứ như sau: p1 p2  pn qSau đây là một số luật lệ suy diễn thường được sử dụng mà chân lý của nó hoàn toàn có thể đượckiểm tra dễ dàng bằng phương pháp lập bảng chân trị.  quy tắc Modus Ponens (Phương pháp khẳng định): phép tắc này được diễn tả bởi hằng đúng:  phường  q   phường   q hoặc bên dưới dạng sơ đồ: pq p q Ví dụ. Trường hợp An học chăm thì An sẽ được điểm cao, nhưng mà An học tập chăm. Suy ra An đạt điểm cao. Trang 8Tóm tắt bài xích giảng Toán rời rộc rạc Trường ĐHSP tp.hồ chí minh  Tam đoạn luận (Syllogism). Phép tắc này được thể hiện bằng hằng đúng:  p  q    q  r     p  r  hay bên dưới dạng mô hình: pq qr p  r Ví dụ. Trường hợp An không hay đi dạo thì An học chuyên và giả dụ An học chuyên thì An sẽ tiến hành điểm cao. Suy ra nếu như An không hay đi dạo thì An sẽ được điểm cao.  quy tắc Modus Tollens (phương pháp lấp định) quy tắc này được trình bày bởi hằng đúng:  p.  q   q   p hay dưới dạng tế bào hình: pq q p Ví dụ. Giả dụ trời mưa thì mặt đường ướt mà hàng không ướt. Suy ra trời ko mưa.  Quy tắc mâu thuẫn (chứng minh bằng phản chứng) quy tắc này dựa trên tương đương logic sau:  p1  p2    pn   q    p1  p2    pn  q   0  Ví dụ. Hãy sử dụng phương pháp phản triệu chứng cho chứng tỏ sau: pr p  q qs r  s – Trước hết, ta lấy đậy định của kết luận:   r  s     r  s   r  s – kế tiếp ta đã thêm vào những tiền đề hai giả thiết phụ r và s tìm cách chứng minh suy luận sau là đúng: Trang 9Tóm tắt bài bác giảng Toán rời rộc Trường ĐHSP tp.hcm pr p  q qs r s 0 công việc suy luận đang được tiến hành như sau: p  q qs p  s (Tam đoạn luận) cơ mà s p (PP phủ định) mà pr r (PP khẳng định) kết luận r cùng rất giả thiết phụ r mang lại ta r  r  0 . Cho nên vì thế theo phương pháp phản chứng, hội chứng minh lúc đầu là đúng.  Quy tắc chứng minh theo trường hợp: quy tắc này được thể hiện bởi hằng đúng sau:  phường  r    q  r     p.  q   r  Ý nghĩa của luật lệ này là giả dụ một mang thiết hoàn toàn có thể tác ra thành nhị trường hợp p. đúng xuất xắc q đúng, và ta đã chứng minh được riêng rẽ rẽ đến từng trường thích hợp là tóm lại r đúng, lúc ấy r cũng giống trong cả nhị trường hợp. Ví dụ. Để minh chứng rằng f(n) = n(n+1) luôn chia hết mang đến 2 với mọi số tựnhiên n, ta xét nhì trường hòa hợp là n chẵn, n lẻ cùng thấy rằng trong cả nhì trường hợpf(n) luôn chia hết đến 2. Vậy ta rút ra kết luận cần chứng tỏ là f(n) luôn chia hếtcho 2 với mọi số tự nhiên n.Trên đấy là một số quy tắc suy diễn ta hay được dùng trong các quá trình suy luận.Sau đây ta đang xét một ví dụ rõ ràng có sử dụng kết hợp nhiều luật lệ suy diễn:Ví dụ. Kiểm soát suy luận sau đúng tốt sai: “Nếu nghệ sỹ Văn cha không trình diễnhay số vé đẩy ra ít hơn 50 vé thì đêm diễn sẽ bị hủy vứt và Ông bầu sẽ tương đối buồn. Nếuđêm diễn bị hủy vứt thì đề nghị trả lại vé cho những người xem. Tuy vậy tiền vé dường như không đượctrả lại cho tất cả những người xem. Vậy người nghệ sỹ Văn cha đã trình diễn”.Để kiểm soát suy luận trên, ta thay những mệnh đề nguyên thủy bằng những biến mệnh đề: p: “nghệ sĩ Văn cha đã trình diễn” Trang 10Tóm tắt bài bác giảng Toán rời rạc Trường ĐHSP thành phố hồ chí minh q: “số vé bán ra ít hơn 50 vé” r: “đêm diễn bị diệt bỏ” s: “ông thai rất buồn” t: “trả chi phí vé lại cho tất cả những người xem”Từ đó, suy luận thuở đầu có thể mô dường như sau:  p  q    r  s  r t t pSuy luận trên có thể được thực hiện theo công việc sau:  p  q    r  s  ( tiền đề) r  s  r (hằng đúng) r t (tiền đề)   p  q   t (tam đoạn luận mở rộng) cơ mà t (tiền đề) p  q (phương pháp bao phủ định và cơ chế DeMorgan) nhưng  phường  q   phường (hằng đúng) p (phương pháp khẳng định) Vậy suy luận ban đầu là chính xác.1.2 Vị tự – Lượng từĐịnh nghĩa. Một vị tự là một khẳng định p(x,y, …) trong các số ấy có chứa một số trong những biếnx,y, … đem giá trị trong những tập hợp cho trước A, B, … sao cho: i. Bản thân p(x,y,…) chưa phải là mệnh đề ii. Nếu vắt x, y, … bằng những a  A , b  B , …ta sẽ được một mệnh đề p(a,b,…) tức thị chân trị của nó hoàn toàn xác định. Các biến x, y, … được nói là biến thoải mái của vị từ.Ví dụ. A. P(n) = “n là số nguyên tố” là 1 trong những vị tự theo biến tự do n   , với n = 2, 11, 13 ta được những mệnh đề đúng p(2), p(11), p(13) còn cùng với n = 4, 10, 20 ta được các mệnh đề không đúng p(4), p(10), p(20). B. Q(x,y) = “x + y là số lẻ” là vị trường đoản cú theo 2 biến tự do thoải mái x, y   , chẳng hạn q(2,5) là một trong những mệnh đề đúng, q(-3, -7) là 1 trong những mệnh đề sai, … Trang 11Tóm tắt bài bác giảng Toán rời rộc Trường ĐHSP TP.HCMĐịnh nghĩa. đến trước các vị trường đoản cú p(x), q(x) theo một phát triển thành x  A . Khi đó: i. Tủ định của p, ký hiệu là p là vị từ bỏ theo đổi mới x mà khi núm x bằng 1 phần tử a thắt chặt và cố định của A thì ta được mệnh đề   phường  a   . Ii. Phéo gắn liền (tương ứng nối rời, kéo theo, …) của phường và q, ký hiệu bởi p.  q ( p.  q , p.  q , …) là vị từ bỏ theo thay đổi x cơ mà khi nỗ lực x bằng 1 phần tử a thắt chặt và cố định của A thì ta được mệnh đề p  a   q  a   p(a)  q(a), p(a)  q(a),…Ví dụ: p(x) = “x là số nguyên tố”, q(x) = “x là số chẵn”. Lúc đó ta có:  che định của p: p ( x) = “x ko là số nguyên tố”  Phép nối sát của phường và q: phường  q ( x) = “x là số nguyên tố va x là số chẵn”  …Định nghĩa. Các mệnh đề “ x  A, p( x) ” và “ x  A, p. ( x) ” được điện thoại tư vấn là lượng từ bỏ hóacủa vị từ bỏ p(x) do lượng từ phổ dụng (  ) với lượng từ lâu dài (  ).Chú ý: a. Trong những mệnh đề lượng trường đoản cú hóa, trở nên x không hề là biến tự do nữa, ta nói nó bị buộc bởi những lượng từ  tuyệt  .