Trang 1
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.1. SƠ LƯỢC VỀ LÔGICH MỆNH ĐỀ Toán học là một ngành khoa học lý thuyết được phát triển trên cơ 1.1.1. Mệnh đề sở tuân thủ nghiêm ngặt các qui luật lập luận của tư duy lô gich Lôgích mệnh đề là một hệ thống lôgich đơn giản nhất, với đơn vị hình thức. Các qui luật cơ bản của lô gich hình thức đã được phát cơ bản là các mệnh đề mang nội dung của các phán đoán, mỗi triển từ thời Aristote (Arít-xtốt) (thế kỷ thứ 3 trước công nguyên) phán đoán được giả thiết là có một giá trị chân lý nhất định là cùng với sự phát triển rực rỡ của văn minh cổ Hy Lạp. đúng hoặc sai. Để chỉ các mệnh đề chưa xác định ta dùng các chữ cái p, q, r … Tuy nhiên mãi đến thế kỷ 17 với những công trình của De Morgan và gọi chúng là các biến mệnh đề. (Đờ Mocgan), Boole (Bun) ... thì lô gích hình thức mới có một cấu Nếu biến mệnh đề p đúng ta cho p nhận giá trị 1 và p sai ta cho trúc đại số đẹp đẽ và cùng với lý thuyết tập hợp giúp làm chính xác nhận giá trị 0. Giá trị 1 hoặc 0 được gọi là thể hiện của p. hoá các khái niệm toán học và thúc đẩy toán học phát triển mạnh Mệnh đề phức hợp được xây dựng từ các mệnh đề đơn giản hơn mẽ. bằng các phép liên kết lôgich mệnh đề. 9/6/2018 1 9/6/2018 2 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.1.2. Các phép liên kết lôgich mệnh đề 4. Phép kéo theo (implication) 1. Phép phủ định (negation) Mệnh đề p kéo theo q được ký hiệu p q : đọc p kéo theo hoặc suy ra q. Phủ định của mệnh đề p là mệnh đề được ký hiệu p , đọc là không p. Mệnh đề p q chỉ sai khi p đúng và q sai. Mệnh đề p đúng khi p sai và p sai khi p đúng. 5. Phép tương đương (equivalence) Mệnh đề p tương đương q được ký hiệu p q , là mệnh đề: 2. Phép hội (conjunction) (p q)(q p) Hội của hai mệnh đề p q là mệnh đề được ký hiệu p q , đọc “p và q”. , p q p q Mệnh đề đúng khi và cùng đúng hoặc cùng sai. Mệnh đề p q chỉ đúng khi p và q đồng thời cùng đúng. p q p,q Mệnh đề sai khi hai mệnh đề lấy giá trị khác nhau. 3. Phép tuyển (disjunction) Một công thức gồm các biến mệnh đề và các phép liên kết mệnh đề Tuyển của hai mệnh đề p q là mệnh đề được ký hiệu p q , đọc “p hoặc q”. được gọi là một công thức mệnh đề. , Mệnh đề p q chỉ sai khi p và q đồng thời cùng sai. Bảng liệt kê các thể hiện của công thức mệnh đề được gọi là bảng chân trị. 9/6/2018 3 9/6/2018 4 1
Trang 2
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLELÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Một số bảng chân trị 1.1.3. Các tính chất Dùng bảng chân trị ta dễ dàng kiểm chứng các mệnh đề hằng đúng 1) p p : luật phủ định kép, 2) (p q) (p q), 3) p q q p; p q q p : luật giao hoán, 4) p (q r) (p q) r; p (q r) (p q)r : luật kết hợp, 5) p (q r) (p q)(p r); p (q r) (p q)(p r) : luật phân phối, Một công thức mệnh đề được gọi là hằng đúng nếu nó luôn nhận giá trị 1 6) Mệnh đề p p luôn đúng: luật bài trung trong mọi thể hiện của các biến mệnh đề có trong công thức. Mệnh đề p p luôn sai: luật mâu thuẫn, Ta ký hiệu mệnh đề tương đương hằng đúng là “” thay cho “” 7) p q p q; p q p q : luật De Morgan. 9/6/2018 5 9/6/2018 6 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.2. TẬP HỢP 1.2.1. Khái niệm tập hợp Khái niệm tập hợp, ánh xạ và các cấu trúc đại số là các khái niệm Khái niệm tập hợp và phần tử là khái niệm cơ bản của toán học, cơ bản: vừa là công cụ vừa ngôn ngữ của toán học hiện đại. Vì vai không thể định nghĩa qua các khái niệm đã biết. trò nền tảng của nó nên khái niệm tập hợp được đưa rất sớm vào Các khái niệm “tập hợp”, “phần tử” xét trong mối quan hệ phân tử chương trình toán phổ thông (toán lớp 6). của tập hợp trong lý thuyết tập hợp là giống với khái niệm “đường Khái niệm tập hợp được Cantor (Căng-to) đưa ra vào cuối thế kỷ thẳng”, “điểm” và quan hệ điểm thuộc đường thẳng được xét trong 19. Sau đó được chính xác hoá bằng hệ tiên đề về tập hợp. Có thể hình học. tiếp thu lý thuyết tập hợp theo nhiều mức độ khác nhau. Tập hợp được đặc trưng tính chất rằng một phần tử bất kỳ chỉ có thể Chúng ta chỉ tiếp cận lý thuyết tập hợp ở mức độ trực quan kết hoặc thuộc hoặc không thuộc tập hợp. hợp với các phép toán lô gich hình thức như “và”, “hoặc”, phép Nếu x là phần tử của tập A ta ký hiệu xA và đọc x thuộc A. kéo theo, phép tương đương, lượng từ phổ biến, lượng từ tồn tại. Nếu x không là phần tử của tập A ta ký hiệu xA và đọc x không Với các phép toán lô gích này ta có tương ứng các phép toán thuộc A. giao, hợp, hiệu các tập hợp con của các tập hợp. 9/6/2018 7 9/6/2018 8 2
Trang 3
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Có thể biểu diễn tập hợp theo hai cách sau b) Nêu đặc trưng tính chất của các phần tử tạo thành tập hợp a) Liệt kê tất cả các phần tử của tập hợp trong dấu ngoặc nhọn Có những tập hợp không thể liệt kê các phần tử của chúng (có vô số phần tử, các phần tử không có quy luật dễ nhận biết), khi đó ta biểu Trường hợp tập hợp có hữu hạn phần tử hoặc các phần tử của tập diễn tập hợp này bằng cách đặc trưng các tính chất của phần tử tạo hợp có thể liệt kê theo một quy luật dễ nhận biết thì ta có thể biểu nên tập hợp. diễn các phần tử trong dấu ngoặc nhọn. Ví dụ 1.2: Tập các số chính phương: n2|nN 1, 4, 9, …. Ví dụ 1.1: Tập các số tự nhiên lẻ nhỏ hơn 10 là 1, 3, 5, 7, 9 . Tập hợp các nghiệm của phương trình x2 1 0 là 1,1. Giản đồ Venn Để có hình ảnh trực quan về tập hợp, người ta thường biểu diễn tập Tập hợp các số tự nhiên chẵn có thể biểu diễn dưới dạng: hợp như là miền phẳng giới hạn bởi đường cong khép kín không tự P 0, 2, 4, 6,... hoặc P 2n n N cắt được gọi là giản đồ Venn. 9/6/2018 9 9/6/2018 10 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Tập hợp có thể được biểu diễn bằng cách đặc trưng tính chất của 1.2.3. Một số tập hợp số thường gặp phần tử thông qua khái niệm hàm mệnh đề . Tập các số tự nhiên N 0, 1, 2, ... . Hàm mệnh đề xác định trong tập hợp D là một mệnh đề S(x) phụ Tập các số nguyên 0, 1, 2, ... . thuộc vào biến xD. Khi cho biến x một giá trị cụ thể thì ta được mệnh đề lôgich (mệnh đề chỉ nhận một trong hai giá trị hoặc đúng Tập các số hữu tỉ p q q 0, p q, . hoặc sai). Tập các số thực R (gồm các số hữu tỉ và vô tỉ). Tập hợp các phần tử x D sao cho S(x) đúng là miền đúng của hàm mệnh đề S(x) và ký hiệu D hoặc xD|S(x). Tập các số phức z x iy x y, R; i2 1. S x( ) 9/6/2018 11 9/6/2018 12 3
Trang 4
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.2.4. Tập con Tập hợp tất cả các tập con của X được ký hiệu P (X) Tập A được gọi là tập con của B nếu mọi phần tử của A đều là P Vậy A (X) khi và chỉ khi A X phần tử của B, khi đó ta ký hiệu A B hay B A. Tập X là tập con của chính nó nên là phần tử lớn nhất N R là phần tử bé nhất trong P(X) Hai tập A,B bằng nhau, ký hiệu A= B khi và chỉ khi A B và B A. Để chứng minh A B ta chỉ cần chứng minh x A x B . Ví dụ 1.4: X a b c, , Để chứng minh A B ta chỉ cần chứng minh x A x B . P(X) ,{ },{ },{ },{ , },{ , },{ , },a b c a b b c c a X Tập rỗng là tập không chứa phần tử nào, ký hiệu . Ta có thể chứng minh: nếu X có n phần tử thì P(X) có 2n phần tử. Một cách hình thức ta có thể xem tập rỗng là tập con của mọi tập hợp. 9/6/2018 13 9/6/2018 14 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.2.5 Các phép toán trên các tập hợp Thông thường giả thiết tất cả các tập được xét là các tập con của một 1. Phép hợp tập cố định gọi là tập phổ dụng U. Tập U \ B được gọi là phần bù của Hợp của hai tập A và B, ký hiệu A B, là tập gồm các phần tử thuộc B trong U và được ký hiệu làCB hoặc B . U ít nhất một trong hai tập A, B Ví dụ 1.5: Xét các tập U a b c d e f g h, , , , , , , ;A a b c d, , , ,B b d e f, , , (x AB) (x A)(x B) 2. Phép giao A B a b c d e f, , , , , ,A B b d, ,A \ B a c, Giao của hai tập A và B, ký hiệu A B, là tập gồm các phần tử thuộc đồng thời A B CA e f g h, , , ,CB a c g h, , , . cả hai tập , U U (x AB) (x A)(x B) 3. Hiệu của hai tập Hiệu của hai tập A và B, ký hiệu A \ B, là tập gồm các phần tử thuộc A nhưng không thuộc B (x A\B) (x A)(x B) 9/6/2018 15 9/6/2018 16 4
Trang 5
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Phép hợp và giao các tập hợp được mở rộng cho n tập con A ,...,A Tính chất: Sử dụng lôgích mệnh đề có thể chứng minh các tính chất sau 1 n như sau: 1) A B B A A; B B A : tính giao hoán, n Hợp A ... A (hoặc ký hiệu A ) là tập có các phần tử thuộc 2) A (B C) (A B)C; A (B C) (A B)C : tính kết hợp, 1 n k k1 ít nhất một trong các tập A ,...,A . 1 n 3) A (B C) (A B)(A C); A (B C) (A B)(A: C) x A ... A i {1,2,...,n} : x A tính phân phối, 1 n i n 4) AA A U; A A; A , Giao A ... A (hoặc ký hiệu A ) là tập có các phần tử thuộc 1 n k k1 đồng thời tất cả các tập A ,...,A . 5) AAU A; A , 1 n x A ... A x A;i 1,2,...,n A B A B; A B A B 1 n i 6) : luật De Morgan. 9/6/2018 17 9/6/2018 18 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 7) A B\ AB A; (AB)A\(AB)CA B , Ví dụ 1.6: A Chứng minh rằng nếu A C A B A; C A B thì C B. 8) A A A A; A A : tính lũy đẳng, Cách 1: Chứng minh x C x B 9) ABAAB A; BBAB , x A x AC x AB x B x C x AC x AB x A x B x A x A AC DA 10) ABC ; DAB . BC DB Cách 2: sử dụng tính chất hấp thu và tính phân bố 11) B : A (A B) A A; (A B) A : luật hấp thu. C (A C)C (A B) C (A C) (B C) (A B)(B C) (A C) B (A B) B B 12) A B A A B B A B . 9/6/2018 19 9/6/2018 20 5
Trang 6
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.2.7 Lượng từ phổ biến và lượng từ tồn tại Mở rộng khái niệm lượng từ tồn tại với ký hiệu !x D, S x( ) Giả sử S(x) là một mệnh đề xác định trên tập D có miền đúng: D x D S x( ) đọc là tồn tại duy nhất xD,S(x) nếu D có đúng một phần tử. S x( ) S(x) a) Mệnh đề xD, S(x)(đọc là với mọi xD, S(x)) là một mệnh đề đúng nếu D D và sai trong trường hợp ngược lại. Phép phủ định lượng từ S(x) Ký hiệu (đọc là với mọi) được gọi là lượng từ phổ biến, x D S x, ( ) x D S x, ( ) Khi D đã xác định ta thường viết tắt x, S(x) hay (x), S(x). b) Mệnh đề xD, S(x)(đọc là tồn tại xD, S(x)) là một mệnh đề x D S x, ( ) x D S x, ( ) đúng nếu DS(x) và sai trong trường hợp ngược lại. Ký hiệu (đọc là tồn tại) được gọi là lượng từ tồn tại. 9/6/2018 21 9/6/2018 22 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Ví dụ 1.7 Theo định nghĩa của giới hạn 1.2.7. Phép hợp và giao suy rộng lim f x( ) L 0, 0;x : 0 x a f x( )L A là tập gồm các phần tử thuộc ít nhất một tập nào đó trong các tậpA . i i xa iI Sử dụng mệnh đề hằng đúng: (p q) (p q) x A (i I; x A ) i 0 i iI 0 Ta có 0 |x a | | f x( )L | tương đương với: A là tập gồm các phần tử thuộc đồng thời tất cả các tập A . i i iI x a f x( )L x A (i I; x A ) i i iI Ví dụ 1.8 và x a f x( )L x a f x( )L n A x 0 x A 0; 1 n n 1 n n1 Vậy phủ định của lim f x( ) L là: 1 1 xa B x x 1 B 0; 1 n n 1 n 1 n 0, 0;x : 0 x a f x( )L n1 9/6/2018 23 9/6/2018 24 6
Trang 7
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.3. Tích Descartes của các tập hợp Nhận xét 1.1 Tích Descartes của hai tập X,Y là tập, ký hiệu XY, gồm các phần 1. Với mọi (x ,...,x ) X ... X ; (x ' ,...,x ' ) X ...X tử có dạng (x,y) trong đó x X và y Y : 1 n 1 n 1 n 1 n ta có (x ,...,x ) (x ' ,...,x ' ) x x ' ,i 1,...,n X Y ( ,x y) x X vμ y Y 1 n 1 n i i Ví dụ 1.9 X a b c, , ,Y 1,2 2. Tích Descartes X1 X2 ... Xn còn được ký hiệu iI Xi , X Y ( ,1),( ,1),( ,1),( ,2),( ,2),( ,2)a b c a b c 3. Tích Descartes của các tập hợp không có tính giao hoán, Y X (1,a),(2,a),(1, ),(2, ),(1, ),(2, )b b c c 4. Khi X ... X X ta ký hiệu X n thay cho X...X 1 n Ta có thể chứng minh được rằng nếu X có n phần tử,Y có m phần n lÇn tử thì XY có n.m phần tử. Chẳng hạn Rn (x ,x , ...,x ) x ,x , ...,x R 1 2 n 1 2 n Tích Descartes của n tập hợp X1, X2,..., Xn : R2 ( ,x y) x y, R R3 ( ,x y z, ) x y z, , R X X ... X (x ,x ,...,x ) x X , i 1,2,...,n 1 2 n 1 2 n i i x 1 ( ,x y) (1,3) R2 y 3 9/6/2018 25 9/6/2018 26 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.4. ÁNH XẠ 1.4.1. Định nghĩa và ví dụ Khái niệm ánh xạ được khái quát hoá từ khái niệm hàm số trong Một ánh xạ từ tập X vào tậpY là một quy luật cho tương ứng mỗi một đó hàm số thường được cho dưới dạng công thức tính giá trị của phần tử xX với một phần tử duy nhất y f(x) của Y thỏa mãn hai hàm số phụ thuộc vào biến số. điều kiện sau: 1. Mọi xX đều có ảnh tương ứng y f(x) Y Khái niệm ánh xạ giúp ta mô tả các phép tương ứng từ một tập này đến tập kia thoả mãn điều kiện rằng mỗi phần tử của tập 2. Với mỗi xX ảnh y f(x) là duy nhất nguồn chỉ cho ứng với một phần tử duy nhất của tập đích và mọi Ký hiệu f : X Y hoặc X f Y phần tử của tập nguồn đều được cho ứng với phần tử của tập x y f x( ) x y f x( ) đích. Ở đâu có tương ứng thì ta có thể biểu diễn được dưới X Y được gọi là tập nguồn, được gọi là tập đích. ngôn ngữ ánh xạ. Biểu thức y f(x) được gọi là công thức xác định ảnh. 9/6/2018 27 9/6/2018 28 7
Trang 8
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Ví dụ 1.17: Mỗi hàm số y f(x) bất kỳ đều có thể xem là ánh xạ từ tập xác định D vào R hoặc vào miền giá trị của nó. Hàm lôgarit y lnx là ánh xạ ln : R* R x y lnx Hàm căn bậc hai y x là ánh xạ : R R hoặc : R R x y x x y x Hai ánh xạ f : X Y g; : X ' Y ' Tương ứng a) không thỏa mãn điều kiện thứ 2. được gọi là bằng nhau, ký hiệu f g , nếu thỏa mãn: Tương ứng b) không thỏa mãn điều kiện 1. X X ', Y Y ' Chỉ có tương ứng c) xác định một ánh xạ từ X vào Y. f x( ) g x( ); x X 9/6/2018 29 9/6/2018 30 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Ảnh và ảnh ngược của tập qua ánh xạ 1.4.2. Phân loại các ánh xạ Xét ánh xạ f : X Y Ánh xạ f:X Y được gọi là đơn ánh nếu ảnh của hai phần tử phân Cho tập con AX, ta ký hiệu và gọi tập sau là ảnh của A qua ánh xạ f biệt là hai phần tử phân biệt: x ,x X x; x f x( ) f x( ) f A( ) y Y x A : y f x( ) Y 1 2 1 2 1 2 hoặc một cách tương đương y Y : y f A( ) x A : y f x( ) x ,x X f x; ( ) f x( ) x x 1 2 1 2 1 2 Ký hiệu Imf f(X) và gọi là tập ảnh hay tập giá trị của ánh xạ f . Ánh xạ f: X Y được gọi là toàn ánh nếu mọi phần tử củaY là ảnh Cho tập con B Y, ta ký hiệu và gọi tập sau là nghịch ảnh của B qua của phần tử nào đó của X ánh xạ f y Y;x X : y f x( ) f1(B) x X f x( ) B X 1 Ánh xạ vừa đơn ánh vừa toàn ánh được gọi là song ánh x X : x f (B) f x( ) B Vậy f là một song ánh khi thỏa mãn điều kiện sau: Ta viết f 1( )y thay cho f 1({ })y . Vậy f 1( )y x X y f x( ) y Y;!x X : y f x( ) 9/6/2018 31 9/6/2018 32 8
Trang 9
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Khi ánh xạ f : X Y được cho dưới dạng công thức xác định ảnh Ví dụ 1.20 a) Cho ánh xạ f : R R yf(x) thì ta có thể xác định tính chất đơn ánh, toàn ánh của ánh xạ x y f x( ) x2 x f bằng cách giải phương trình: Xét phương trình f x( ) y có dạng x2 x y 0; ,x y R(*). f x( ) y; x X y, Y Biệt số 1 4y. trong đó ta xem x là ẩn và y là tham biến. 1 y Y x X f • Khi y 0: Phương trình (*) vô nghiệm. Vậy f không Nếu với mọi phương trình luôn có nghiệm thì là toàn ánh. 4 toàn ánh. Nếu với mỗi yY phương trình có không quá 1 nghiệm xX thì f là 1 đơn ánh. • Khi y 0: Phương trình (*) có hai nghiệm phân biệt: 4 Nếu với mọi yY phương trình luôn có duy nhất nghiệm xX thì f là 1 1 4y 1 1 4y song ánh. x , x 1 2 2 2 Trường hợp ánh xạ không cho công thức xác định ảnh ta xét loại của f Vậy không đơn ánh. ánh xạ bằng cách dựa trực tiếp vào định nghĩa. 9/6/2018 33 9/6/2018 34 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Ví dụ 1.20 b) Cho ánh xạ f : N N Ví dụ 1.21 Các hàm số đơn điệu chặt: x y f x( ) x2 x • Đồng biến chặt: x x f x( ) f x( ) 1 2 1 2 Xét phương trình f x( ) y có dạng x2 x y 0;x y, N(**). • Nghịch biến chặt: x x f x( ) f x( ) 1 2 1 2 Biệt số 1 4y. là các song ánh từ tập xác định lên miền giá trị của nó • y 0 0: Phương trình (**) có hai nghiệm thực phân biệt: 1 1 4y 1 1 4y x , x 1 2 2 2 Vì x N , dó đó phương trình (**) có không quá 1 nghiệm. Vậy 2 f là một đơn ánh. • Khi x N , chẳng hạn y 1: Phương trình (**) vô nghiệm. Vậy 1 f không toàn ánh. 9/6/2018 35 9/6/2018 36 9
Trang 10
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.4.3. Ánh xạ ngược của một song ánh Giả sử f : X Y là một song ánh !x X y Y Như vậy ta có thể xác định một ánh xạ từ Y vào X bằng cách cho tương ứng mỗi phần tử yY với phần tử duy nhất x X thỏa mãn y f(x). Ánh xạ này được gọi là ánh xạ ngược của f , ký hiệu f 1. Vậy f 1 :Y X f1( )y x y f x( ) Có thể chứng minh được f 1 cũng là một song ánh. Ví dụ 1.20 Hàm mũ y ax ; a 0, a 1 là một song ánh (vì hàm mũ đơn điệu chặt) có hàm ngược là hàm lôgarit y ax x log y a 9/6/2018 37 9/6/2018 38 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Ví dụ 1.21 Xét hàm 1.4.4. Hợp của hai ánh xạ Với hai ánh xạ f : X Y g, :Y Z ; xét tương ứng: đơn điệu tăng chặt và toàn ánh nên nó là một song ánh X f Y g Z Hàm ngược được ký hiệu x f x( ) g f x( ( )) x arcsiny y sinx,x [ 2; 2 ,] y [ 1;1] Tương ứng x ↦ g(f(x)) xác định một ánh xạ từ X vào Z được gọi là hợp của hai ánh xạ f và g, ký hiệu g○f. Vậy: Tương tự x arccosy y cosx,x [0;],y [ 1;1] g f : X Z x g f x( ( )) x arctany y tanx, x ; ,y ( ; ) 2 2 Ánh xạ hợp g○f : X Z có công thức xác định ảnh g○f (x) g(f(x)). x arc coty y cotx, x (0;),y ( ; ) 9/6/2018 39 9/6/2018 40 10
Trang 11
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Ví dụ 1.26 Ví dụ 1.27 Xét hai hàm số f : R R , g : R R với công thức xác định ảnh: Xét hai hàm số f : R R , g : R R f x( ) sin( ), ( )x g x 2x2 4 với công thức xác định ảnh f(x)2x+3, g(x)sinx. Ta có thể thiết lập hai hàm hợp từ R vào R Khi đó hàm hợp g○f có công thức xác định ảnh f g x( ) sin(2x2 4) 1 g f (x)=sin(2x+3). ○ g f x( ) 2sin2 x 4 4 Hàm số u sin2(2x+3) là hợp của 3 hàm số có công thức xác Qua ví dụ trên ta thấy nói chung g○f f○g. định ảnh sau: y f(x)2x+3; z g(y) siny và u h(z) z2. Nói cách khác phép hợp ánh xạ không có tính giao hoán. 9/6/2018 41 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.4.5. Lực lượng của một tập hợp 1.7. ĐẠI SỐ BOOLE Khái niệm lực lượng của tập hợp có thể xem như là sự mở rộng khái Lý thuyết đại số Boole được George Boole (1815 - 1864) giới thiệu vào niệm số phần tử của tập hợp. năm 1854 trong bài báo "Các quy luật của tư duy", trong đó kỹ thuật Tập X có n phần tử nếu có thể liệt kê dạng X = {x1, x2, …, xn}. đại số được dùng để phân tích các quy luật của lôgích và các phương Vậy X có n phần tử khi tồn tại song ánh từ tập {1, 2, …, n} lên X . pháp suy diễn. Hai tập hợp X, Y được gọi là cùng lực lượng nếu tồn tại song ánh từ Sau đó đại số Boole được áp dụng trong các lĩnh vực khác nhau của X lên Y . toán học như đại số, giải tích, xác suất... Tập có lực lượng n hoặc 0 được gọi là các tập hữu hạn. Vào khoảng năm 1938, Claude Shannon (Clau Sê-nôn) (một kỹ sư Tập không hữu hạn được gọi là tập vô hạn. viễn thông người Mỹ) là người đầu tiên đã áp dụng đại số Boole vào Tập có cùng lực lượng với tập các số tự nhiên N hay hữu hạn được lĩnh vực máy tính điện tử và lý thuyết mạng. gọi là tập đếm được . 9/6/2018 43 9/6/2018 44 11
Trang 12
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.7.1. Định nghĩa và các tính chất cơ bản của đại số Boole Ví dụ 1.43: Giả sử X : Một đại số Boole (B,,,) là một tập khác trống B với hai phép toán hai ngôi , : B B B Các luật hợp thành , là phép hợp, phép giao các tập con của X và phép toán một ngôi : B B thoả mãn các tiên đề sau: và phép toán một ngôi là phép lấy phần bù của tập con trong X. B : , có tính kết hợp, nghĩa là với mọi a, b, c B P 1 a) Xét (X ) là tập các tập con của X a (b c) (a b) c, a (b c) (a b) c B2: , có tính giao hoán, nghĩa là với mọi a, b B Khi đó (P (X),,,) là đại số Boole với phần tử không là và a b b a, a b b a B : Tồn tại phần tử không và phần tử đơn vị 0, 1 B, 0 1 phần tử đơn vị là chính tập X . 3 sao cho với mọi a B: a 0 a, a 1 a B : Với mọi a B thì a B là phần tử đối theo nghĩa sau: b) Xét B {, X} thì (B ,,,) là đại số Boole có 2 phần tử. 4 X X a a ' 1, a a ' 0 B5: phân phối đối với và phân phối đối với a (b c) (a b) (a c), a (b c) (a b) (a c) 9/6/2018 45 9/6/2018 46 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Ví dụ 1.44 Có thể chứng minh được đại số Boole hữu hạn phần tử có số phần Xét B {0, 1}tập gồm hai phần tử ký hiệu 0 và 1. Ta định nghĩa tử chẵn. Vì vậy đại số Boole ít phần tử nhất sau B có 4 phần tử. 2 2 1 nÕu Ýt nhÊt mét trong hai phÇn tö a b, lμ 1 a b Ví dụ 1.45: Đại số Boole có 4 phần tử xác định như sau: 0 nÕu ngîc l¹i Xét B4 {0, 1,a,b}, ta định nghĩa các phép toán 1 n Õu c¶ h ai p hÇn tö a b, lμ 1 1 nÕu a 0 a b a 0 n Õu ng î c l¹i 0 nÕu a 1 thì (B ,,,) là một đại số Boole có 2 phần tử (đại số Boole ít 2 (B ,,,) thì 4 là một đại số Boole có 4 phần tử. phần tử nhất). 9/6/2018 47 9/6/2018 48 12
Trang 13
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.7.2. Công thức Boole, hàm Boole và nguyên lý đối ngẫu Hai công thức Boole trong đại số Boole (B,,,) được gọi là đối ngẫu Một biểu thức chứa các biến được liên kết với một số hữu hạn lần nếu trong một công thức ta thay , , 0, 1 lần lượt bằng , , 1, 0 thì các phép toán ,, và hai phần tử 0, 1 của đại số Boole (B,,,) gọi ta được công thức hai. là một công thức Boole. Hai công thức x (y 1) và x (y 0) là đối ngẫu. (x y ') 1,(x ' y) z là hai công thức Boole Trong mỗi tiên đề của hệ tiên đề B1-B5 của đại số Boole đều chứa Mỗi công thức Boole của đại số Boole (B,,,) xác định một hàm nhận từng cặp công thức đối ngẫu nhau, vì vậy ta có nguyên lý đối ngẫu giá trị thuộc B vì khi thay các biến có mặt trong công thức bởi các phần sau. tử của B thì nhận được giá trị là phần tử của B. Mỗi hàm xác định bởi công thức Boole được gọi là Hàm Boole. Nguyên lý đối ngẫu : Nếu hai công thức của đại số Boole được chứng minh là tương đương Hai công thức Boole xác định cùng một hàm Boole được gọi là hai dựa trên cơ sở hệ tiên đề B -B thì hai công thức đối ngẫu của chúng 1 5 công thức tương đương. cũng tương đương x (y z) và (x y) (x z)là hai công thức tương đương. Chẳng hạn, ta sẽ chứng minh a 1 1, Ta kí hiệu x (y z) (x y) (x z). Do đó theo nguyên lý đối ngẫu ta có a 0 0. 9/6/2018 49 9/6/2018 50 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Tính chất Áp dụng các tính chất này cùng với hệ tiên đề B -B ta có thể rút gọn 1 5 Giả sử (B,,,) là đại số Boole với phần tử không và đơn vị là 0, 1, khi đó công thức Boole bất kỳ. với mọi a, b B ta có Ví dụ 1.49 Rút gọn công thức Boole (x y) (x y ') (x ' y) 1) a a a a; a a : tính lũy đẳng, Giải: (x y) (x y ') x (y y ') x 1 x 2) 0' 1 1'; 0 , (x y)(x y ')(x 'y) x (x 'y) (x x ')y 1y 1. 3) a 1 1; a 0 0 , Ví dụ 1.50 Rút gọn công thức Boole (x y ') x (y z)' z 4) a (a b) a a; (a b) a: tính hấp thu, Giải: (x y ') x (y z)' z (x y ') (x y ') (x z ') z 5) Nếu tồn tại c B sao cho a c b c a; c b c thì a b , (x y ') (x z ') z (x y ') (x z) (z ' z) 6) Nếu a b 1; a b 0 thì b a ' : tính duy nhất của phần bù, (x y ') (x z) 1 7) (a b)' a 'b ';(a b)' a 'b ' : công thức De Morgan. (x y ') (x z) (x y ') x z x z. 9/6/2018 51 9/6/2018 52 13
Trang 14
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Ví dụ 1.51 1.7.3 Phương pháp xây dựng hàm Boole trong B2 thỏa mãn giá trị cho Rút gọn công thức Boole trước (x y z) (x y z ') (x ' y z) Một vài trường hợp khi ứng dụng đại số Boole để giải quyết vấn đề thực tế sẽ dẫn đến bài toán cần tìm các hàm Boole theo các biến Giải: nào đó trong đại số Boole B2 thỏa mãn các điều kiện cho trước. (x y z) (x y z ') (x ' y z) Chúng ta chỉ ra hai phương pháp xây dựng các hàm như thế: (x y z) (x y z ') (x y z) (x ' y z) • Phương pháp thứ nhất biểu diễn hàm cần tìm dạng “tổng () (x y) (z z ') (y z) (x x ') các tích ()”. (x y) (y z) y (x z). • Sử dụng nguyên lý đối ngẫu ta có phương pháp thứ hai dạng “tích các tổng”. 9/6/2018 53 9/6/2018 54 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Để xây dựng hàm cần tìm dạng “tổng các tích” ta thực hiện các bước Ví dụ 1.52 sau: Tìm hàm của hai biến F(x,y) nhận giá trị 1 khi x, y đồng thời nhận giá trị 1) Lập bảng các giá trị các biến xiB2 có mặt trong công thức và 1 hoặc 0. giá trị tương ứng của hàm F theo các biến này (tương tự bảng x y F x y( , ) Biểu thức theo hàng chân trị trong mục 1.2). 1 1 1 x y 2) Chỉ xét các hàng của bảng trên mà hàm F nhận giá trị 1. Trong 1 0 0 mỗi hàng này ta lập biểu thức là của các biến: 0 1 0 xi nếu x nhận giá trị 1, 0 0 1 x ' y ' i x’i nếu xi nhận giá trị 0. 3) Hàm F cần tìm có được bằng cách lấy của các biểu thức Vậy hàm cần tìm là F x y( , ) (x y) (x ' y '). theo các hàng. 9/6/2018 55 9/6/2018 56 14
Trang 15
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.7.4. Ứng dụng đại số Boole vào mạng chuyển mạch Ta ký hiệu các chuyển mạch bởi các biến x,y,z, ... Ta chỉ xét các mạng gồm các chuyển mạch (switching networks) có hai Nếu x ở trạng thái mở ta cho x nhận giá trị 0 và ở trạng thái đóng ta trạng thái đóng (dòng điện đi qua được) và mở (dòng điện không qua cho x nhận giá trị 1. được). Trong một mạng nếu hai chuyển mạch luôn cùng trạng thái thì ta ký Hai mạng đơn giản nhất là mạng song song cơ bản (basic parallel hiệu cùng một biến. Hai chuyển mạch có trạng thái luôn ngược nhau, network) và mạng nối tiếp cơ bản (basic series network) được mô tả nếu một chuyển mạch được ký hiệu là x thì chuyển mạch kia được trong hình vẽ sau: ký hiệu là x. Mạng song song cơ bản nhận giá trị 1 khi có ít nhất một trong hai chuyển mạch x, y nhận giá trị 1, ta ký hiệu x y. Mạng nối tiếp cơ bản nhận giá trị 1 khi đồng thời hai chuyển mạch x, y nhận giá trị 1, ta ký hiệu x y. Một mạng bất kỳ có thể nhận được bằng cách ghép nối tiếp hay song Như vậy x, y, x, x y, x y có thể được xem như các biến nhận song các mạng cơ bản này. giá trị trong đại số Boole B2. 9/6/2018 57 9/6/2018 58 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE Bằng phương pháp này ta có thể biểu diễn một mạng bất kỳ bởi một Trong các công thức cần xét ta thay: công thức Boole và ngược lại (x y)' bởi x ' y ' và (x y)' bởi x ' y '. Hai mạng N1 và N2 được gọi là tương đương nếu nó thực hiện cùng có công thức Boole tương ứng một chức năng, nghĩa là với bất kỳ cách chọn các trạng thái đóng mở (y z) (x y ') ở mọi vị trí chuyển mạch trong mạng thì trạng thái đầu vào và đầu ra của N1 và N2 đều như nhau. Ta có thể áp dụng đại số Boole để giải quyết hai vấn đề sau: Công thức Boole Với một mạng cho trước tìm mạng tương đương đơn giản hơn (x z) (y z) (y ' x) Tìm mạng tương ứng xác định bởi công thức Boole tương đương biểu diễn mạng đơn giản hơn. Thiết kế một mạng thoả mãn các điều kiện cho trước. Xây dựng hàm Boole thỏa mãn điều kiện cho trước. 9/6/2018 59 9/6/2018 60 15
Trang 16
9/6/2018 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.7.4.1 Tìm mạng tương đương đơn giản hơn Ví dụ 1.54 Tìm mạng tương đương đơn giản hơn Ví dụ 1.53 Tìm mạng tương đương đơn giản hơn của mạng sau Công thức Boole tương ứng A(z x)x (yz') (z x)(z y) Công thức Boole rút gọn (z x)x (y z ') x z (y z ') Công thức Boole tương ứng Công thức Boole rút gọn x (z z ')y x (x z)y (x w)w y (x z w)y A x (z x)(z y) x (z y) 9/6/2018 61 9/6/2018 62 MỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀ LÔGÍCH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỞ ĐẦU VỀMỞ ĐẦU VỀ LÔGICHLÔGICH MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLEMỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ ĐẠI SỐ BOOLE 1.7.4.2 Thiết kế một mạng thoả mãn các điều kiện cho trước Ví dụ 1.55 Thiết kế một mạng điện cho một bóng đèn ở cầu thang mà có thể bật tắt ở cả hai đầu cầu thang. Gọi x và y là hai công tắc ở hai đầu cầu thang. Theo yêu cầu đặt ra ta cần thiết kế một mạng điện sao cho khi thay đổi trạng thái của một trong hai vị trí x, y thì trạng thái của đầu ra (bóng đèn) phải thay đổi. Công thức Boole thỏa mãn điều kiện trên (x 'y)(y ' x) (x 'y ')(y x) BÀI TẬP 9/6/2018 63 16
Hiển thị 16 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!