Giáo trình Toán rời rạc - Nguyễn Hữu Anh

ଵ݉ଶ(ݔ ∨ ̅ݔ) = ݔ݉ଵ݉ଶ ∨ ̅ݔ݉ଵ݉ଶ Suy ra: ݉ଵ݉ଶ ∨ ݔ݉ଵ ∨ ̅ݔ݉ଶ = (ݔ݉ଵ݉ଶ ∨ ݔ݉ଵ) ∨ (̅ݔ݉ଶ ∨ ̅ݔ݉ଶ݉ଵ) = ݔ݉ଵ ∨ ̅ݔ݉ଶ Nghĩa là ݉ଵ݉ଶ ≺ ݔ݉ଵ ≺ ̅ݔ݉ଶ  đpcm GS. Nguyễn Hữu Anh 105 Với khái niệm thỏa thuận ta có phương pháp sau để xác định tất cả các tiền đề nguyên tố của một hàm Bool ݂. Bước 1: Viết ݂ dưới dạng công thức thu gọn tùy ý (dạng nối rồi chính tắc chẳng hạn): ݂ = ݉ଵ ∨ ݉ଶ ∨ ∨ ݉௥ Đặt ࣮ = {݉ଵ,݉ଶ , ,݉௥} Gọi ࣰ là danh sách các biến theo một thứ tự nhất định nhưng tùy ý. Bước 2: Trong Bước 2 ta sẽ cập nhật dần ࣮ theo từng biến trong ࣰ như sau: i. Giả sử ݔ là một biến trong ࣰ mà ta đã xét tới với ࣮ đã được cập nhật theo các biến trước ݔ. Ta phần hoạch ࣮ thành 3 phần (rời nhau):  ࣛ gồm các đơn thức chia hết cho ݔ  ℬ gồm các đơn thức chia hết cho ̅ݔ  ࣝ gồm các đơn thức không chia hết cho ݔ lẫn ̅ݔ ii. Nếu ࣛ = ∅ hay ℬ = ∅ ta sẽ xét biến kế tiếp ݔ. Nếu không, ta thêm vào ࣮ tất cả các thỏa thuận của một đơn thức thuộc ࣛ và một đơn thức thuộc ℬ. iii. Mỗi lẩn thêm một phần tử mới vào ࣮ ta phải duyệt lại và loại bớt những phần tử được trội thực sự bởi một phần tử khác (kể cả phần tử mới thêm vào). Bước 3: Sau khi đã duyệt tất cả các biến trong ࣰ ta có: Định lý 4.5.2: Tập hợp ࣮ sau cùng trong Bước 3 chính là tập hợp tất cả các tiền đề nguyên tố của ݂. Chứng minh: Gọi आ là số biến trong ࣰ, và một ݉ là một tiền đề nguyên tố bất kỳ của ݂, ta chứng minh tập hợp ࣮ sau cùng sẽ chứa ݉ bằng quy nạp trên आ. Gọi ݔ là biến đầu tiên trong danh sách ࣰ và ࣛ,ℬ,ࣝ là các tập hợp tương ứng như trong i). Trường hợp 1: ݉ không chia hết cho ݔ lẫn ̅ݔ, ta có: ݉ݔ ≺ ൭ሧ ݊ ௡∈ࣛ ൱ݔ ∨ ቌሧ݌ݔ ௣∈ℬ ቍ ∨ ቌሧ ݍ ௤∈ࣝ ቍݔ Ở đây kí hiệu ሧ ݊ ௡∈ࣛ dùng để chỉ tổng Bool của tất cả các phần tử của A. Các ký hiệu khác cũng tương tự. để ý rằng nếu ݌ ∈ ℬ thì ݌ chia hia hết cho ̅ݔ nên ݌ݔ = 0. Do đó: ݉ݔ ≺ ൭ሧ ݊/ݔ ௡∈ࣛ ൱ ݔ ∨ ቌሧ ݍ ௤∈ࣝ ቍݔ Cho ݔ = 1 ta được ݉ ≺ ൭ሧ ݊/ݔ ௡∈ࣛ ൱ ∨ ቌሧ ݍ ௤∈ࣝ ቍ Tương tự ta có: ݉ ≺ ቌሧ݌/̅ݔ ௣∈ℬ ቍ ∨ ቌሧ ݍ ௤∈ࣝ ቍ GS. Nguyễn Hữu Anh 106 Suy ra ݉ ≺ ቌ ሧ (݊/ݔ) (݌/̅ݔ) ௡∈ࣛ,௣∈ℬ ቍ ∨ ቌሧ ݍ௤∈ࣝ ቍ Giả sử ࣮ đã được cập nhật theo biến ݔ như trong Bước 2 ở trên. Gọi ࣮′ là tập hợp con của ࣮ gồm các đơn thức không chia hết cho ݔ lẫn ̅ݔ. Gọi ݂′ là tổng Bool của các đơn thức trong ࣮′ xem như hàm Bool theo các biến trong ࣰᇱ = ࣰ\{ݔ}. Rõ ràng ݉ là một tiền đề nguyên tố của ݂′ nên theo giả thiết quy nạp, sau khi cập nhật theo biến cuối cùng trong ࣰᇱ ,࣮′ chứa ݉. Nhưng tập hợp ࣮′ sau cùng là tậph ợp con của tập hợp ࣮ sau khi cập nhật theo biến sau cùng của ࣰ′, vì trong quá trình cập nhật theo các biến của ࣰ′, các đơn thức của ࣮ bị loại đi cũng chính là các đơn thức của ࣮′ bị loại đi hoặc là các đơn thức chia hết cho ݔ hoặc ̅ݔ. Nói tóm lại ta đã chứng minh được tậph ợp ࣮ sau cùng chứa ݉. Trường hợp 2: ݉ chia hết cho ݔ hay ̅ݔ. Ta có thể giả sử ݉ chia hết cho ݔ vì trường hợp còn lại chứng minh tương tự. Gọi ࣛ,ℬ, ࣝ là 3 tập hợp tạo thành phân hoạch của ࣮ tương ứng với biến ݔ như trong Bước 2. Cho ݔ = 1 ta được: ݉/ݔ ≺ ൭ሧ(݊/ݔ) ௡∈ࣛ ൱ ∨ ቌሧ ݍ ௤∈ࣝ ቍ Suy ra ݉ ≺ ൭ሧ ݊ ௡∈ࣛ ൱ ∨ ݔቌሧ ݍ ௤∈ࣝ ቍ ≺ ൭ሧ ݊ ௡∈ࣛ ൱ ∨ ቌሧ ݍ ௤∈ࣝ ቍ = ݂ Ứng với mỗi hàm Bool ݃ theo các biến trong ࣰ, ta liên kết một hàm Bool ݃̅ với các biến trong ࣰᇱ = ࣰ\{ݔ} bằng cách cho ݔ = 1. Đặt ࣮ᇱ = ࣛ ∪ࣝ. Khi ấy ݃ ⟼ ݃̅ là một song ánh giữa ࣮′ và một tập hợp ࣮′ഥ các từ đơn theo các biến trong ࣰ′ vì không có phần tử nào của ࣝ là ước của một phần tử của ࣛ (công thức đa thức ban đầu của ݂ là rút gọn). Ta có công thức đa thức rút gọn: ݂̅ᇱ = ൭ሧ ത݊ ௡∈ࣛ ൱ ∨ ቌሧ ݍ ௤∈ࣝ ቍ Hơn nữa tương ứng ݃ ⟼ ݃̅, nếu thu hệp trên tập ࣮′ đã được cập nhật đối vối biến sau cùng, cũng là một song ánh giữa tập hợp này và tập hợp ࣮ത′ đã được cập nhật theo biến sau cùng đối với hàm ݂̅ᇱ, vì nếu có ഥ݉ଵ = ഥ݉ଶ với ݉ଵ ≠ ݉ଶ thì một trong hai đơn thức ݉ଵ,݉ଶ là tích của đơn thức kia và ݔ nên đã được loại trong quá trình cập nhật. Rõ ràng ഥ݉ ≺ ݂,̅ giả sử tồn tại đơn thức ഥ݉ ′ theo các biến trong ࣰ′ sao cho: ഥ݉ ≺ ഥ݉ ᇱ ≺ ݂̅ᇱ GS. Nguyễn Hữu Anh 107 Ta có: ݉ = ݔ ഥ݉ ≺ ݔ ഥ݉ ᇱ ≺ ݔ݂̅ᇱ = ൭ሧ ݔത݊ ௡∈ࣛ ൱ ∨ ݔ ቌሧ ݍ ௤∈ࣝ ቍ ≺ ݂ Do ݉ là tiền đề nguyên tố, ta có ݉ = ݔ ഥ݉ ᇱ Suy ra ഥ݉ = ഥ݉ ᇱ, nghĩa là ഥ݉ là tiền đề nguyên tố của ݂̅ᇱ Như thế theo giả thiết quy nạp, ࣮ത′, sau khi cập nhật theo biến cuối cùng, sẽ chứa ഥ݉ . Tương tự như trong Trường hợp 1, ta thấy tập hợp ࣮ sau khi cập nhật đối với biến cuối cùng, sẽ chứa ࣮′. Suy ra ݉ ∈ ࣮ Cuối cùng do cách cập nhật các đơn thức, trong đơn thức nào trong ࣮ được trội thực sự bởi một đơn thức khác, nghĩa là các phần tử của ࣮ đều là tiền đề nguyên tố của ݂.  đpcm Ví dụ 1: ݂ = ݔݖݐ̅ ∨ ̅ݔݐ̅ݒ ∨ ݕതݖݒ ∨ ݐ̅̅ݒ ∨ ݕݖݐݒ Ta có quá trình cập nhật theo các biến trong ࣰ = [ݔ,ݕ, ݖ, ݐ, ݒ] như sau: Biến ݔ: ݔݖݐ̅ ̅ݔݐ̅ݒ ݕതݖݒ ݐ̅̅ݒ ݕݖݐݒ Thỏa thuận: ݖݐ̅ݒ Biến ݕ: ݕݖ ݐݒ ݕതݖݒ ݔݖݐ̅ ̅ݔݐ̅ݒ ݐ̅̅ݒ ݖݐ̅ݒ Thỏa thuận: ݖݐݒ Biến ݖ: không có thỏa thuận Biến ݐ: ݖݐݒ ݔݖݐ̅ ݖݐ̅ݒ ̅ݔݐ̅ݒ ݐ̅̅ݒ ݕതݖݒ Thỏa thuận: ݔݖݑ ݖݐݒ ݖݐ̅ݒ ݔݖݐ̅ ̅ݔݐ̅ݒ ݐ̅̅ݒ ݕതݖݒ ݔݖݑ Thỏa thuận: ݖݒ Biến ݒ: ݖݒ ݐ̅̅ݒ ݔݖݐ̅ ̅ݔݐ̅ݒ Thỏa thuận: ݖݐ̅ ݐ̅̅ݒ ݔݐ̅̅ݒ ݖݒ ݖݐ̅ Thỏa thuận: ̅ݔݐ̅ Cuối cùng tập hợp các tiền dề nguyên tố là: ࣮ = {̅ݔݐ̅, ݖݐ̅, ݖݒ, ̅ݐ̅ݒ} GS. Nguyễn Hữu Anh 108 Ví dụ 2: ݂ = ̅ݔݕതݖݐ ∨ ̅ݔݕݖݐ ∨ ̅ݔݕݖ̅ݐ ∨ ݔݕݖ̅ݐ ∨ ݔݕݖ̅ݐ̅ Biến ݔ: ̅ݔݕݖ̅ݐ ݔݕݖ̅ݐ ݔݕݖ̅̅ݐ ̅ݔݕതݖݐ ̅ݔݕݖݐ Thỏa thuận: ݕݖ̅ݐ Biến ݕ: ̅ݔݕതݖݐ ̅ݔݕݖݐ ݔݕݖ̅̅ݐ ݕݖ̅ݐ Thỏa thuận: ̅ݔݖݐ Biến ݖ: ݕݖ̅ݐ ̅ݔݖݐ ݔݕݖ̅̅ݐ Thỏa thuận: ̅ݔݕݐ Biến ݐ: ݕݖ̅ݐ ݔݕݖ̅̅ݐ ̅ݔݖݐ ̅ݔݕݐ Thỏa thuận: ݔݕݖ̅ Như vậy tập hợp các tiền đề nguyên tố là ࣮ = {ݔݕݖ̅, ̅ݔݕݐ, ̅ݔݖݐ,ݕݖ̅ݐ} Bây giờ ta xét bài toán 5.2: biểu diễn hàm Bool ݂ như là tổng tối tiểu của các tiền đề nguyên tố. Trong phương pháp Biểu đồ Karnaugh, bài toán trên chính là bài toán phủ tối tiểu của biểu đồ Karnaugh của hàm ݂ bởi các tế bào lớn. Đó là một họ ࣩ các tế bào lớn sao cho: i. Mỗi ô trong biểu đồ Karnaugh nằm trong ít nhất 1 tế bào lớn thuộc ࣩ ii. Nếu rút bớt một tế bào lớn thuộc ࣩ thì phần còn lại không thỏa i) Do các ô thuộc biểu đồ Karnaugh của ݂ chính là biểu đồ Karnaugh của một từ tối tiểu trội bởi ݂, ta có thể phát biểu bài toán phủ tổng quát như sau: Bài toán phủ: tìm một họ ࣮଴ các tiền đề nguyên tố của ݂ sao cho: i. Mỗi từ tối tiểu trội bởi ݂ được trội bởi một tiền đề thuộc ࣮଴ ii. Họ ࣮଴ là từ tối tiểu, nghĩa là nếu rút bớt một phần tử thì phần còn lại không thỏa i) Gọi ࣮ = ൛݉ଵ, ,݉௣ൟ là tập hợp tất cả các tiền dề nguyên tố của ݂ mà ta tìm được khi giải bài toán 5.1 Ta đưa vào các biến Bool ܽଵ,ܽଶ, ,ܽ௣ và tgiet61 lập một hệ phương trình Bool theo các biến Bool như sau: Với mỗi từ tối tiểu ࣮ trội bởi ݂, gọi ݉௜భ ,݉௜మ , ,݉௜ೖ là tất cả các tiền đề nguyên tố của ݂ trội ݐ. Khi ấy ta có một phương trình: ܽ௜భ ∨ ܽ௜మ ∨ ∨ ܽ௜ೖ = 1 Cho ݐ chạy khắp các từ tối tiểu trội bởi ݂, ta được một hệ ݍ phương trình trong đó ݍ là số các từ tối tiểu trội bởi ݂. Giải hệ phương trình Bool trên ta được các nghiệm là bộ ݌: ൞ ܽଵ = ܾଵ ܽଶ = ܾଶ ⋮ ܽ௣ = ܾ௣ Trong đó ଵܾ, ܾଶ, , ܾ௣ là các giá trị cố định bằng 1 hoặc tùy ý. Với các ௜ܾ = 1 ta có ܽ௜ = 1, nghĩa là tiền đề nguyên tố ݉௜ được chọn để phủ ݂. Để giải hệ phương trình Bool có dạng trên, ta thực hiên các bước sau: GS. Nguyễn Hữu Anh 109 Bước 1: loại bỏ các phương trình trùng lắp, nói cách khác giả sử có hai phương trình có dạng: ܽ௜భ ∨ ܽ௜మ ∨ ∨ ܽ௜ೖ = 1 và ௝ܽభ ∨ ௝ܽమ ∨ ∨ ௝ܽ೓ = 1 sao cho {݅ଵ, ݅ଶ, , ݅௞} ⊂ { ଵ݆ , ݆ଶ , , ݆௛} Khi ấy phương trình thứ hai là hệ quả của phương trình đầu và do đó có thể được loại bỏ. Bước 2: Vì hệ phương trình đồng thời nghiệm đúng, ta thấy nó tương đương với một phương trình duy nhất có vế trái là tích của tất cả các vế trái và vế phải bằng 1 Dùng luật phân bố khai triển vế trái và đưa nó về dạng một công thức đa thức. Bước 3: Loại bỏ các đơn thức dư thừa, nghĩa là nó là bội của một đơn thức khác. Nói cách khác đưa vế trái của phương trình đã biến đổi ở Bước 2 về dạng một công thức đa thức rút gọn. Ở đây lưu ý rằng các đơn thức đều là tích của một số biến, không có thừa số đơn nào là phần bù của biến. Phương trình trở thành: ݊ଵ ∨ ݊ଶ ∨∨ ݊௥ = 1 Bước 4: các lời giải là: ݊ଵ = 1 hay ݊ଶ = 1 hay ݊௥ = 1 Mỗi ݊௜ là tích của một số biến, nên lời giải tương ứng chính là các tiền đề nguyên tố tương ứng với biến đó. Ví dụ: trong ví dụ 2 ở trên, ta có 4 tiền đề nguyên tố ݉ଵ = ̅ݔݖݐ,݉ଶ = ̅ݔݕݐ,݉ଷ = ݕݖ̅ݐ,݉ସ = ݔݕݖ̅, và 5 từ tối tiểu ݐଵ = ̅ݔݕതݖݐ, ݐଶ = ̅ݔݕݖݐ, ݐଷ = ̅ݔݕݖ̅ݐ, ݐସ = ݔݕݖ̅ݐ, ݐହݔݕݖ̅ݐ̅. Ta có hệ 5 phương trình: ⎩ ⎪ ⎨ ⎪ ⎧ ܽଵ = 1 ܽଵ ∨ ܽଶ = 1 ܽଶ ∨ ܽଷ = 1 ܽଷ ∨ ܽସ = 1 ܽସ = 1 Phương trình thứ hai là hệ quả của phương trình đầu và phương trình thứ 4 là hệ quả của phương trình cuối: loại bỏ chúng và lấy tích ta được phương trình duy nhất: ܽଵ(ܽଶ ∨ ܽଷ)ܽସ = 1 Khai triển ta được: ܽଵܽଶܽସ ∨ ܽଵܽଷܽସ = 1 Do đó ta có hai lời giải: ܽଵܽଶܽସ = 1 hay ܽଵܽଷܽସ = 1 Nói cách khác ta có hai công thức đa thức: ݂ = ݉ଵ ∨ ݉ଶ ∨ ݉ସ = ̅ݔݖݐ ∨ ̅ݔݕݐ ∨ ݔݕݖ̅ và ݂ = ݉ଵ ∨ ݉ଷ ∨ ݉ସ = ̅ݔݖݐ ∨ ݕݖ̅ݐ ∨ ݔݕݖ̅ Cả hai đều là công thức đa thức tối tiểu. GS. Nguyễn Hữu Anh 110 BÀI TẬP CHƯƠNG 4 1. Chứng minh rằng trong một đại số Bool ࣛ a) Phần bù của một phần tử là duy nhất b) Suy ra qui tắc De Morgan: ∀ݔ,ݕ ∈ ࣛ, ݔ ∨ ݕതതതതതതത = ̅ݔ ∧ ݕത và ݔ ∧ ݕതതതതതതത = ̅ݔ ∨ ݕത 2. Trong đại số Bool ࣛ, xét quan hệ thứ tự ≺ xác định bởi định lý 4.1.1. Chứng minh rằng: a) nếu ݔ ≺ ݕ thì ݔ ∨ ݕ = ݕ b) nếu ݔ ≺ ݕ thì ݕത ≺ ̅ݔ c) nếu ݔ ≺ ݕ thì ݖ ≺ ݐ thì ݔ ∧ ݖ ≺ ݕ ∧ ݐ d) nếu ݔ ≺ ݕ thì ݖ ≺ ݐ thì ݔ ∨ ݖ ≺ ݕ ∨ ݐ 3. Trong một đại số Bool hãy tìm phần bù của: ൫ തܾ ∧ ܿ൯ ∨ (ܿ ∧ ݀) (ܾ ∧ ܿ̅) ∨ ൫തܾ ∧ ܽ൯ ∨ (ܽ ∧ ܿ) 4. Trong đại số Bool ࣛ, một tập hợp con ℬ ≠ ∅ củ ࣛ a được nói là một đại số con nếu với mọi ݔ,ݕ ∈ ℬ thì ݔ ∨ ݕ, ݔ ∧ ݕ và ̅ݔ cũng là phần tử của ℬ. Chứng minh rằng ℬ là một đại số con của ࣛ. a) Chứng minh rằng nếu ℬ là một đại số con của ࣛ thì 0,1 ∈ ℬ b) Với ࣛ = ࣪({ܽ, ܾ, ܿ}). Hãy tìm tất cả các đại số con của ࣛ c) Giả sử ℬ là một tập hợp con của ࣛ sao cho với mọi ݔ,ݕ ∈ ℬ thì ݔ ∨ ݕ ∈ ℬ và ̅ݔ ∈ ℬ. Chứng minh rằng ℬ là một đại số con của ࣛ. 5. ࣛ là một đại số Bool, ܽ ∈ ࣛ. Tập hợp tất cả các phần tử trội bởi ܽ có là một đại số Bool không? Nó có là đại số con không? 6. Giả sử ߮:ࣛ ⟶ ℬ là một đẳng cấu đại số Bool. Chứng minh rằng: a) nếu ܽ là một nguyên tử của ࣛ thì ߮(ܽ) là một nguyên tử của ℬ b) nếu ܵ là một đại số con của ࣛ thì ߮(ܵ) là một đại số con của ℬ 7. Gọi ࣯ଶଵ଴ là tập hợp các ước dương của 210. Trong ࣯ଶଵ଴ ta định nghĩa các phép toán ∨,∧,− như sau: với mọi ݔ,ݕ ∈ ࣯ଶଵ଴ thì: ݔ ∨ ݕ = ܤܵܥܰܰ(ݔ.ݕ) ݔ ∧ ݕ = ܷܵܥܮܰ(ݔ,ݕ) ̅ݔ = 210/ݔ Chứng minh rằng ࣯ଶଵ଴ là một đại số Bool 8. a) Xét ánh xạ ߮ ∶ ࣯ଶଵ଴ ⟶࣪({ܽ, ܾ, ܿ,݀}) Sao cho ߮(2) = {ܽ},߮(3) = {ܾ},߮(5) = {ܿ} và ߮(7) = {݀} Muốn cho ߮ là một đảng cấu đại số Bool thì ảnh của 35, 70, 42 là bao nhiêu? b) Có bao nhiêu đẳng cấu khác nhau từ ࣯ଶଵ଴ lên ࣪({ܽ, ܾ, ܿ,݀}) 9. Giả sử ℬ là một đại số Bool và ࣛ là một tập hợp ≠ ∅. Với ݂,݃ ∈ ℬࣛ định nghĩa: ∀ݔ ∈ ܣ; (݂ ∨ ݃)(ݔ) = ݂(ݔ) ∨ ݃(ݔ) ∀ݔ ∈ ܣ; (݂ ∧ ݃)(ݔ) = ݂(ݔ) ∧ ݃(ݔ) ∀ݔ ∈ ܣ; ݂̅(ݔ) = ݂(ݔ)തതതതതത a) Chứng minh rằng ℬࣛ là một đại số Bool với các phép toán trên b) Chứng minh rằng thứ tự tương ứng trên ℬࣛ chính là thứ tự trong bài tập 27, chương 3 10. Giả sử ࣛ ,ℬ là hai đại số Bool. Trên ࣛ × ℬ định nghĩa: GS. Nguyễn Hữu Anh 111 (ݔ,ݕ) ∨ (ݖ, ݐ) = (ݔ ∨ ݖ,ݕ ∨ ݐ)(ݔ,ݕ) ∧ (ݖ, ݐ) = (ݔ ∧ ݖ,ݕ ∧ ݐ)(ݔ,ݕ)തതതതതതത = (̅ݔ,ݕത) Chứng minh rằng ࣛ × ℬ là một đại số Bool với các phép toán trên. 11. Trên định số Bool ࣛ định nghĩa phép toán ܽ⨁ܾ = ൫ܽ ∧ തܾ൯ ∨ ( തܽ ∧ ܾ) (*) a) Chứng minh rằng phép toán trên thỏa: ∀ܽ, ܾ, ܿ ∈ ࣛ (ܽ⨁ܾ)⨁ܿ = ܽ⨁(ܾ⨁ܿ) ܽ⨁ܾ = ܾ⨁ܽ ܽ⨁0 = ܽ ܽ⨁ܽ = 0 ܽ ∧ (ܾ⨁ܿ) = (ܽ ∧ ܾ)⨁(ܽ ∧ ܿ) Nghĩa là (ࣛ,⨂ ,∧) là một vành giao hoán. b) Ngược lại nếu ⨁ là một phép toán trên ࣛ thỏa các điều kiên trên thì (*) được thỏa. 12. Cho trước phần tử ܽ của Bool ࣛ. Có thể nói gì về phần tử ܾ thỏa một trong các điều kiện sau: a) ܽ ∧ ܾ = 0 b) ܽ ∨ ܾ = 1 c) ܽ ∧ ܾ = 0 và ܽ ∨ ܾ = 1 13. Trong một đại số Bool ࣛ ta khảo sát phương trình: ܽ ∨ ݔ = ܾ (1) trong đó a và b là hai phần tử cho trước của ࣛ và ݔ là ẩn. a) Chứng minh rằng điều kiện cần và đủ để cho (1) có ít nhất một nghiệm là ܽ ≺ ܾ b) Đặt ݕ = ݔ ∨ തܽ. Chứng minh rằng ܾ ∧ ݕ = ݔ và ܾ ∨ ݕ = 1 c) Nếu ݔ là một nghiệm, chứng minh rằng തܽ ∧ ܾ ≺ ݔ ≺ ܾ. Phát biểu và chứng minh phần đảo. d) Chứng minh rằng nghiệm của (1) gồm tất cả các phần tử có dạng ݔ = ܾ ∧ ܿ với ܿ ≻ തܽ. e) Khảo sát tương tự cho phương trình ܽ ∧ ݔ = ܾ 14. Tập hợp ࣯ଵ଻ଶ଼ có là một đại số Bool không? Có các phép toán nào khác để ࣯ଵ଻ଶ଼ trở thành đại số Bool không? 15. a) Mở rộng định nghĩa trong bài tập 10 cho tích của ݊ đại số Bool ࣛଵ ×ࣛଶ × × ࣛ௡. b) Đặc biệt với ࣛଵ = ࣛଶ = ⋯ = ࣛ௡ = ܤ ≡ {0,1} hãy xác định thứ tự tương ứng với cấu trúc đại số Bool có n nguyên tử đều đẳng cấu với ܤ௡ 16. Giả sử ݔ là một phần tử bất kỳ của đại số Bool có ݊ nguyên tử. Gọi ݀(ݔ) là số đỉnh tối thiểu cần phải đi qua để đi từ 0 đến ݔ dọc theo các mũi tên của biểu đồ Hasse (݀(0) =0). a) Tính ݀(ܽ) khi ܽ là một nguyên tử b) Chứng minh rằng với ݔ, ݕ tùy ý ta có: ݀(ݔ ∨ ݕ) = ݀(ݔ) + ݀(ݕ)− ݀(ݔ ∧ ݕ) 17. Tìm giá trị của các hàm Bool dưới đây khi các biến ݔ,ݕ, ݖ và ݐ lấy các giá trị 1,1,0 và 0: a) ݔݕതതത ∨ ̅ݔݕത b) ݐ ∨ ̅ݔݕ c) ݐݔ ∨ ݕത ∨ ݕݖ d) ݐݔ ∨ ݔݕ ∨ ݕݖ e) (ݐݔ ∨ ݕݖ̅) ∨ ݐݕത ∨ (ݐ ∨ ݕ)(̅ݒ ∨ ݕ)തതതതതതതതതതതതതതതതതത 18. Tìm tất cả các giá trị của y và z để các biểu thức dưới đây luôn luôn lấy giá trị 1 biết rằng ݔ = 1: a) ݔ ∨ ݔݕ ∨ ݖ b) ݔݕ ∨ ݖ c) ̅ݔݕ ∨ ݔݖ d) ̅ݔݕ ∨ ݖ 19. Tìm từ tối tiểu theo 4 biến ݔ, ݕ, ݖ, ݐ biết rằng nó lấy giá trị 1 tại: GS. Nguyễn Hữu Anh 112 a) ݔ = ݐ = 0,ݕ = ݖ = 1 b) ݔ = ݕ = 1,ݖ = ݐ = 0 b) ݔ = ݕ = ݖ = 1, ݐ = 0 d) ݔ = ݕ = ݖ = ݐ = 0 20. a) Có bao nhiêu hàm Bool 6 biến lấy giá trị 1 tại các điểm có đúng hai thành phần có giá trị 1 (tại các điểm khác hàm Bool có thể bằng 0 hay 1) b) Có bao nhiêu hàm Bool 6 biến lấy giá trị 1 tại các điểm có ít nhất 2 thành phần có giá trị 1 (tại các điểm khác hàm Bool có thể bằng 0 hay 1) c) Có bao nhiêu hàm Bool 6 biến không phụ thuộc biến thứ nhất. Có bao nhiêu hàm không phụ thuộc 3 biến đầu tiên. 21. Tìm các hàm Bool theo 2 biến sao cho: ݂(ݔ,ݕ) = ݂(ݕ, ݔ) ∀ݔ,ݕ 22. Xác định tất cả các hàm Bool theo 3 biến sao cho: ݂(ݔ,ݕ, ݖ) = ݂(ݕ, ݖ, ݔ) ∀ݔ,ݕ, ݖ (Hướng dẫn: lập bảng chân trị) 23. Xác định các hàm Bool theo 3 biến biết rằng nó không thay đổi giá trị nếu ta hoán vị 2 biến bất kỳ? Câu hỏi tương tự cho hàm 4 biến (Hướng dẫn: lập bảng chân trị) 24. Tồn tại hay không một hàm Bool 3 biến khác 0 biết rằng nó được thay bằng phần bù nếu ta hoán vị 2 biến bất kỳ? Câu hỏi tương tự cho hàm Bool ݊ biến 25. Một hàm Bool ݊ biến ݂ được nói là hàm chẵn nếu:݂(ݔଵതതത, ݔଶതതത, , ݔ௡തതത) = ݂(ݔଵ, ݔଶ, , ݔ௡), ∀ݔଵ, ݔଶ, , ݔ௡. Có bao nhiêu hàm chẵn ݊ biến? Xác định các hàm này khi ݊ = 2 26. Hàm số Bool ݊ biến ݂ được nói là hàm chẵn nếu ݂(ݔଵതതത, ݔଶതതത, , ݔ௡തതത) = ݂̅(ݔଵ, ݔଶ, , ݔ௡), ∀ݔଵ, ݔଶ, , ݔ௡. Có bao nhiêu hàm lẻ ݊ biến? Xác định các hàm này khi ݊ = 2 27. a) Chứng minh rằng mọi hàm Bool ݂ theo ݊ biến đều được viết dưới dạng: ݂(ݔଵ, ݔଶ, , ݔ௡) = [ݔଵ݂(1, ݔଶ, , ݔ௡)] ∨ [ݔଵതതത݂(0, ݔଶ, , ݔ௡)] b) Sử dụng hệ thức trên để xây dựng một song ánh giữa ℱ௡ × ℱ௡ và ℱ௡ାଵ. Áp dụng để tìm lại số phần tử của ℱ௡ c) Sử dụng hệ thức trên để chứng minh lại sự tồn tại của dạng nối rời chính tắc. 28. Giả sử ݂ là tích của ݌ từ đơn phân biệt a) Trong dạng nối rời chính tắc của ݂ có bao nhiêu từ tối tiểu xuất hiện b) Có bao nhiêu hàm Bool trội ݂ 29. Tìm dạng nối rời chính tắc của các hàm Bool ݂ theo 4 biến biết rằng ݂ thỏa một trong hai điều kiện: a) ݂ିଵ(1) = {0101,0110,1000,1011} b) ݂ିଵ(0) = {0000,0001,0010,0100,1000,1001,0110} Ở đây ta viết 0101 thay vì (0,1,0,1) để chỉ ra phần tử của ܤସ 30. Tìm dạng nối rời chính tắc của hàm Bool theo 3 biến: a) ݔݕ ∨ ̅ݔݖ b) ݔ(ݕ ∨ ̅ݔ)ݖ b) ݔݕ ∨ ݕݖ ∨ ݔݖ d) ݔݕത(ݖ ∨ ݔݕത) c) ݔݕݖ ∨ ̅ݔݖ̅ f) [ݔ(ݕ ∨ ݖ) ∨ ̅ݔ] ∨ ݕത d) (ݔ ∨ ݕݖ)(̅ݔ ∨ ݕതݖ̅) h) ݔ(ݕ ∨ ݔݖ) ∨ ݖ ̅ e) (ݔ ∨ ݕݖ)(ݔ ∨ ݖݔ)(ݖ ∨ ݔݕ) j) (̅ݔ ∨ ݕݖ)(ݕത ∨ ݖݔ)(ݖ̅ ∨ ݔݕ) 31. Tìm dạng nối rời chính tắc của hàm Bool theo 4 biến: a) (ݔݕ ∨ ݖݐ)(ݔ ∨ ݖ)(ݔݖ ∨ ݕݐ)(ݔݐ ∨ ݕݖ) b) ݔݕݖ ∨ ݕതݖݐ ∨ ݔݐ̅ [(ݔ ∨ ݕ)(ݖ ∨ ݐ)] ∨ [(ݔ ∨ ݖ)(ݕ ∨ ݐ)] ∨ [(ݔ ∨ ݐ)(ݕ ∨ ݖ)] c) (ݔݕ ∨ ݕݖ̅ ∨ ݔ̅ݐ )ݔݕݐ ∨ ݕݖ ∨ ݖݐ ∨ ݐݔ 32. Một bài thi có 4 câu A,B,C,D với số điểm tối đa 8,5,4,3.Nếu trả lời đúng một câu, sinh viên được điểm tối đa, trả lời sai được 0 điểm. Muốn đạt sinh viên phải được 10 điểm trờ lên. Ta liên kết với các câu 4 biến Bool a,b,c,d và một hàm Bool ݂(a,b,c,d) lấy giá trị 1 nếu sinh viên đạt và bằng 0 nếu sinh viên không đạt. Hãy tìm dạng nối rời chính tắc của hàm ݂. GS. Nguyễn Hữu Anh 113 33. Hãy vẽ mạng sử dụng các cổng NOT, AND, OR để tổng hợp hàm Bool a) (̅ݔ ∨ ݕത)(ݔ ∨ ݕത)(̅ݔ ∨ ݕ) b) ݔݖ̅ ∨ ݕݖ̅ ∨ ݔ c) (ݔ ∨ ݖ̅)(ݕ ∨ ݖ̅)̅ݔ d) ݔ ∨ ݕത(̅ݔ ∨ ݖ) 34. Hãy tổng hợp phép toán ∨ mà chỉ sử dụng cổng AND và cổng NOT 35. Hãy tổng hợp các cổng AND, OR, NOT mà chỉ sử dụng cổng NOR 36. Viết ra biểu thức hàm ݂ tổng hợp bởi mạng các cổng dưới đây: ݔ ݕ ݖ ݂ ݐ 37. Hãy vẽ một mạch chỉ có cổng NOR tổng hợp các hàm Bool theo 4 biến ݂ sao cho ݂ lấy giá trị 1 khi và chỉ khi số biến lấy giá trị 1 là số chẵn. Tương tự đối với cổng NAND. 38. Tìm công thức đa tối tiểu của các hàm Bool có biểu đồ Karnaugh dưới đây: 39. Tìm công thức đa tối tối tiểu của các hàm sau: a) ݖ̅(ݔݕത ∨ ݕݐ) ∨ ݕ(ݔݖ̅ ∨ ̅ݔݖ) b) ݔݕݖݐ ∨ ̅ݔݕത ∨ ݔݖ̅ݐ ∨ ݕݖ̅ݐ̅ c) ݕത(ݖݐ ∨ ݖ̅̅ݐ ) ∨ ݕ(ݖ̅ݐ̅ ∨ ݔݖݐ) ∨ ̅ݔݖݐ d) ݔݕݖݐ ∨ ݔݕത ∨ ݔݖ̅ ∨ ݕݖ ∨ ݔݖ(ݖ̅ ∨ ݐ̅) e) ݖ̅ݐ̅ ∨ ݔݕ̅ݐ ∨ ̅ݔݕݖ̅ ∨ ̅ݔݕതݖݐ̅ ∨ ݔݕതݖ̅ݐ ∨ ݕതݖݐ f) (ݔ ∨ ݐ)(ݔ ∨ ݖ)(ݕ ∨ ݐ)(ݕ ∨ ݖ) g) ݕݐ(ݕ ∨ ݖ) ∨ ݖ̅(ݔ ∨ ݕ) ∨ ݔݕݖ̅ h) ݕݐ(ݔ ∨ ݖ̅ ) ∨ ̅ݔ(ݖ̅ݐ̅ ∨ ݕݐ) ∨ ̅ݔݕതݖ̅ݐ i) ݕݐ̅ ∨ ݔݕݖ̅ ∨ ̅ݔݕݖ ∨ ݔݕതݖݐ̅ ∨ ̅ݔݕതݖ̅ݐ ̅ 40. Tìm các công thức đa thức tối tiểu của hàm Bool ݂ dưới đây. Cho biết số cổng để thiết kế các mạng tối ưu tổng hợp ݂ a) ݂ là hàm Bool 3 biến và lấy giá trị 1 khi và chỉ khi có đúng 2 biến lấy giá trị 1 b) ݂ là hàm Bool 3 biến và lấy giá trị 1 khi và chỉ khi có ít nhất 2 biến lấy giá trị 1 c) ݂ là hàm Bool 4 biến và lấy giá trị 1 khi và chỉ khi số biến lấy giá trị 1 là một số lẻ GS. Nguyễn Hữu Anh 114 GIẢI ĐÁP MỘT SỐ BÀI TẬP CHƯƠNG 1 1. Các mệnh đề là a,c,f 2. a) ܲ ∧ ܳ b) ¬ܲ ∧ ܳ c) ܲ ∨ (¬ܳ ∧ ¬ܲ) d) ܲ ⟶ ¬ܳ e) (ܲ ∧ ¬ܳ) ∨ (¬ܲ ∧ ¬ܳ) 3. a) ܲ ∧ ܴ ∧ ¬ܳ b) ܲ ∧ ܳ ∧ ¬(ܳ ∧ ܴ) c) ¬(ܴ ∧ ¬ܲ) d)¬[(ܴ ∨ ܳ) ∧ ¬ܲ] e) ¬ܳ ∧ ¬ܴ ∧ ܲ 12. b, c, e, f 13. a, b,d, f, h 14. a) Để dạng mệnh đề đã cho lấy chân trị 1, hai dạng mệnh đề sau cần lấy chân trị 1: (¬ݍ ∨ ݎ) ∧ ¬ݏ, ݒà ¬ݏ ⟶ ¬ݎ Nghĩa là ¬ݏ, ¬ݎ và ¬ݍ ∨ ݎ phải lấy chân trị 1. Tóm lại ta phải chọn: ݌ = 1,ݍ = 0,ݎ = 0 và ݏ = 0. b) Do ¬ݎ ∧ ݌ có chân trị 0 ta suy ra ¬ݏ có chân trị 0, nghĩa là ݏ có chân trị 1. Trong trường hợp này ݍ và ݎ có chân trị tùy ý. 15. Dạng mệnh đề đã cho là : a) Mâu thuẫn b),c) Tùy ý d) Hằng đúng 17. a) Thay thế ݌ ∨ ݍ bởi ݏ ta cần chứng minh dạng mệnh đề (ݏ ⟶ ݎ) ⟷ (¬ݎ ⟶ ¬ݏ) là hằng đúng. Do qui tắc thay thế thứ nhất, dạng mệnh đề trên tương đương logic với: (¬ݏ ∨ ݎ) ⟷ (ݎ ∨ ¬ݏ) ⟺ 1 b) Thay (݌ ∨ ݍ) ⟶ ݎ bởi ݑ ta cần chứng minh dạng mệnh đề sau là hằng đúng: [ݑ ∨ (ݏ ∧ ݐ)] ⟷ [(ݑ ∨ ݏ) ∧ (ݑ ∨ ݐ)] Đây chính là luật phân bố 22. a) Sai b) Đúng, PP phủ định c) Sai d) Đúng, Tam đoạn luận 29. a), b) ݌ = 1, ݍ = 1, ݎ = 1, ݏ = 0 30. a) Phép suy luận có dạng: (݌ ∧ ݍ) ⟶ ݎ ݎ ⟶ ݏ¬ݏ ∴ ¬݌ ∨ ¬ݍ Sử dụng Tam đoạn luận và PP Phủ định b) Phép suy luận có dạng ݌ ⟶ ݍ ݎ ⟶ ݏ(ݏ ∧ ݍ) ݐ ∴ ⟶ (݌ ∧ ݐ) ⟶ ¬݌¬ݎ ∨ ¬݌ Dùng phép phản chứng. c) Phép suy luận có dạng: GS. Nguyễn Hữu Anh 115 ݌ ⟶ ݍ ݎ ⟶ ݏ(ݍ ∨ ݏ)¬ݐ ∴ ⟶ ݐ ¬݌ ∧ ¬ݎ Dùng PP Phủ định 3 lần 34. a) Sai b) Đúng c) Đúng d) Đúng: chọn ݔ = 1 e) Sai: chọn x=0 37. a) Đúng: nếu thay ݔ bởi phần tử tùy ý sao cho ݌(ݔ) đúng thì ݔ = 2 hay ݔ = 3. Khi đó ݔ > 0 b) Sai: chọn ݔ = 5 thì ݌(5) đúng và ¬ݎ(5) sai c) Đúng: chọn ݔ = 0 thì ݍ(0) sai nên ݍ(0) ⟶ ݎ(0) đúng d) Đúng: chọn ݔ = 0 thì ݌(0) sai nên ݌(0) ⟶ ¬ݎ(0) đúng 38. a) Sai b) Đúng c) Đúng d) Đúng e) Cho ݕ tùy ý, chọn ݔ = ݕ thì ݌(ݔ,ݕ) đúng f) Sai cì có phủ định đúng là: ∀ݕ∃ݔ, ¬݌(ݔ,ݕ) . Thật vậy cho ݕ tùy ý, chọn ݔ = ݕ + 1 thì ¬݌(ݔ,ݕ) đúng. g) Đúng h) Đúng 39. a) Sai: chọ ݔ = −1 và ݕ = 0 thì ݔଶ > ݕଶ nhưng ݔ < ݕ. Phủ định đã cho được viết đúng. b) Đúng. Phủ định đã cho được viết đúng. c) Đúng. 1.3=3 là số lẻ. Phủ định được viết không chính xác. Phủ định đúng là: tích của hai số lẻ bất kỳ là số chẵn. d) Đúng. Phủ định được viết không chính xác. Phủ định đúng là : tồn tại số hữu tỉ có bình phương là số vô tỉ 40. a) Tồn tại số nguyên ݊ sao cho ݔ chia hết cho 2 và ݊ số chẵn b) Tồn tại số nguyên chẵn có bình phương là số lẻ c) Tồn tại các số nguyên ݇,݉,݊ sao cho ݇ − ݉,݊ − ݊ và ݇ − ݊ là số lẻ. d) Tồn tại số thực ݔ sao cho ݔଶ > 16 và −4 ≤ ݔ ≤ 4 e) Tồn tại số thực ݔ sao cho |ݔ − 3| < 7 trong khi ݔ ≤ −4 hay ݔ ≥ 10. 41. a) ∀ݔ, ൫¬݌(ݔ) ∨ ݍ(ݔ)൯ ⟺ ∀ݔ, ¬݌(ݔ) ∧ ¬ݍ(ݔ) b) ∃ݔ, ¬൫݌(ݔ) ∧ ¬ݍ(ݔ)൯ ⟺ ∃ݔ, ¬݌(ݔ) ∨ ݍ(ݔ) ⟺ ∃ݔ,݌(ݔ) → ݍ(ݔ) c) ∃ݔ, ¬൫݌(ݔ) → ݍ(ݔ)൯ ⟺ ∃ݔ, ¬൫¬݌(ݔ) ∨ ݍ(ݔ)൯ ⟺ ∃ݔ,݌(ݔ) ∧ ¬ ݍ(ݔ) d) ∀ݔ, ൫݌(ݔ) ∨ ݍ(ݔ)൯ ∧ ¬݌(ݔ) ⟺∀ݔ, ݍ(ݔ) ∧ ¬݌(ݔ) 43. a) ∃ݑ∀ݔ, ݔݑ = ݔ b) ∀ݔ∃ݔᇱ , ݔ + ݔᇱ = 0 c) ∀ݔ, (ݔ ≠ 0) → (∃ݔᇱ , ݔݔᇱ = 1) d) Trong ࢆ b) vẫn như trên trong khi đó c) phải được thay bởi ∀ݔ, (|ݔ| = 1) → (∃ݔᇱ , ݔݔᇱ = 1) 44. a) ∀ݔ ∈ ࡾ, ൫(ݔ ≠ 0) → ∃! ݔᇱ:ݔݔᇱ = 1൯. Nếu ࡾ được hiểu ngầm thì mệnh đề trên có thể viết: ∀ݔ ≠ 0,∃! ݔᇱ: ݔݔᇱ = 1 b) ∀ݔ ∈ ࡾ,∀ݕ ∈ ࡾ,∃! ݖ ∈ ࡾ: ݖ = ݔ + ݕ c) ∀ݔ,∃!ݕ:ݕ = 3ݔ + 7 45. ∀ݔ,∃!ݕ,ݕ = −2ݔ đúng trong khi ∃! ݕ,∀ݔ,ݕ = −2ݔ sai. Thật ra ta cần kiểm tra ∃ݔ,∀ݕ,ݕ ≠ −2ݔ đúng. Muốn vậy, ta cho ݕ = ܾ tùy ý và chọn ݔ = − ௕ ଶ + 1 thì ܾ = −2ݔ + 2 ≠ −2ݔ GS. Nguyễn Hữu Anh 116 Với kết quả trên thì a) sai và b) đúng 46. Chọn ݔ = 0,ݕ = 0, ݖ = 2 thì ݌(ݔ, ݕ) và ݌(ݔ, ݖ) đúng trong khi ݕ ≠ ݖ . Như vậy ∀ݔ ∃!ݕ ݌(ݔ,ݕ) sai. Suy ra ∃! ݕ∀ݔ;݌(ݔ,ݕ) cũng sai. Từ đó ta thấy cả hai kết luận a) và b) đều đúng. 47. Với tập hợp vũ trụ ࣯ = {1,2} thì mệnh đề “∃! ݔ, ݔ > 1” đúng trong khi với ࣯ = {1,2} thì mệnh đề trên sai. 49. a) Đúng. Qui tắc đặc biệt hóa phổ dụng và PP khẳng định đã được sử dụng. b) Sai. Có thể ông Bình đã đóng thuế nhưng vẫn không là công dân tốt (vi phạm luật giao thông chẳng hạn!) c) Sai. Có thể Hà không quan tâm đến môi trường nhưng vẫn để riêng các túi nhựa bỏ đi (bị mẹ bắt chẳng hạn!) d) Sai.Có thể Minh không nộp bài chưa làm xong vì không chịu làm bài (do đó Minh không phải là sinh viên nghiêm túc). 50. a) b) hiển nhiên. c) Sử dụng Qui tắc đặc biệt hóa phổ dụng, Qui tắc tổng quát hóa phổ dụng và Phép chứng minh theo trường hợp, d) Xét hai vị từ trên ࢆ: ݌(ݔ): "ݔ ≥ 0" ݍ(ݔ): "ݔ ≤ 0" Khi ấy “ ∀ݔ,݌(ݔ) ∨ ݍ(ݔ)” đúng trong khi cả “ ∀ݔ,݌(ݔ)” và “ ∀ݔ, ݍ(ݔ)” đều sai. 54.Suy luận sai ngay ngay trong bước qui nạp đầu tiên: ݌(1) → ݌(2). 55. Giả sử 3 số liên tiếp bất kỳ có tổng ≤ 38. Khi ấy ta có: 3. (1 + 2 + ⋯+ 25) ≤ 25.38 nghĩa là 25.39 ≤ 25.38: mâu thuẫn 56. a) Suy ra dễ dàng từ nguyên lý qui nạp. b) Cần chứng minh bằng qui nạp bất đẳng thứ phụ nếu ݊ > 2 thì 2݊+ 1 < 2௡ c) Cần chứng minh bằng qui nạp 2 bất đẳng thứ phụ: nếu ݊ > 5 thì 6݊ + 10 < 2௡ và nếu ݊ > 6 thì 3݊ଶ + 3݊ + 1 < 2௡ 57. Giả sử 1 + 2 +⋯+ ݇ = ቀ݇ + 12ቁଶ2 Khi ấy: 1 + 2 +⋯+ ݇ + 1 = ቀ݇ + 12ቁଶ2 + ݇ + 1 = ቀ݇ + 1 + 12ቁଶ2 Tuy nhiên ܵ(1) đã sai nên không áp dụng nguyên lý qui nạp được. 58. Công thức cần chứng minh là (݊ଶ + 1) + (݊ଶ + 2) + ⋯+ (݊ + 1)ଶ = ݊ଷ + (݊ + 1)ଷ,݊ ≥ 0 Giả sử công thức trên đúng với ݊ = ݇. Ta có: ((݇ + 1)ଶ + 1) + ((݇ + 1)ଶ + 2) +⋯+ (݇ + 2)ଶ GS. Nguyễn Hữu Anh 117 = (݇ଶ + 2݇ + 1 + 1) + (݇ଶ + 2݇ + 1 + 2) + + (݇ଶ + 2݇ + 1 + 2݇ + 1) + ൫(݇ + 1)2 + 2݇ + 2൯ + ൫(݇+ 1)2 + 2݇+ 3൯ = (݇ଶ + 1) + (݇ଶ + 2) + ⋯+ (݇ଶ + 1) + (2݇ + 1). (2݇ + 1) + 2 + 4݇ + 5 = (݇ + 1)ଷ + ݇ଷ + 6݇ଶ + 12݇ + 8 = (݇ + 1)ଷ + (݇ + 2)ଷ CHƯƠNG 2 1. Bốn tập hợp bằng nhau. Tuy nhiên 3 cách viết sau không hợp lý vì có những phần tử được kể 2 lần trong tập hợp. 2. a) Đúng b) Đúng c) Đúng do a) d) Đúng do b) e) Sai. Ta phải viết ൛{2}ൟ ⊂ ܣ. f) Sai. Ta phải viết {2} ∈ ܣ 3. a) Sai. b) c) d) Đúng. 4. a) {0,2} b) ቄ2, ହ ଶ , ଵ଴ ଷ , ଶ଺ ହ , ହ଴ ଻ ቅ c) ቄଵ ଶ , ଵ ଵଶ , ଵ ଷ଴ , ଵ ହ଺ , ଵ ଽ଴ , ଵ ଵଷଶ ቅ 5. a) b) c) e) Đúng. d) và f) Sai 7. Chỉ có d) khác ∅ vì phươn trình tương ứng có nghiệm. 8. a) {1,2,3,5} b) ܣ c) và d) ࣯\{2} e) {4,8} f) {1,2,3,4,5,8} g) ∅ h) {1} i) {1,3,4,5,8} 9. a) c) d) Đúng. b) e) f) Sai 10. a) ܧ b) ܤ c) ܦ d) ܦ f) ܧ e) ̅ܣ = {2݊ + 1/݊ ∈ ࢆ} 12. a) Sai, chọn ࣯ ≠ 0 tùy ý và ܣ = ܥ = ∅,ܤ = ࣯ b) Sai, chọn ࣯ ≠ 0 tùy ý và ܣ = ∅,ܤ = ܥ = ࣯ c) Đúng. Ta có: (ܣ ∩ ܤത) ∪ (ܥ ∩ ܤത) = (ܣ ∪ ܥ) ∩ܤത = (ܤ ∪ ܥ) ∩ ܤത = ܤ ∩ ܥ ∩ ܤത = ∅ Suy ra (ܣ ∩ ܤത) ⊂ ܣ ∩ (ܥ ∩ ܤത) = ܣ ∩ ܥ ∩ ܤത = ܤ ∩ ܥ ∩ ܤത = ∅ Do 11. d) ܣ ⊂ ܤ. Tương tự ta có ܤ ⊂ ܣ. Nghĩa là ܣ = ܤ. 13. a) Sai. Chọn ܣ = {1},ܤ = {2} b) Đúng 15. a) ܣ ∩ (ܤ ∩ ̅ܣ ) = (ܣ ∩ ̅ܣ ) ∩ ܤ = ∅ b) (ܣ ∩ ܤ) ∪ (ܣ ∩ ܤ ∩ ̅ܥ ∩ ܦ) ∪ (̅ܣ ∩ ܤ) = ܤ c) ̅ܣ ∪ ܤത ∪ (ܣ ∩ ܤ ∩ ̅ܥ) = ܣ ∩ ܤ ∩ ܥതതതതതതതതതതതതത d) Tập hợp đã cho bằng ܣ ∩ ܤ ∩ ܥ ∩ ܦതതതതതതതതതതതതതതതതതത 21. a) ݂ ∘ ݃(ݔ) = 3ݔ − 1 và ݃ ∘ ݂(ݔ) = 3ݔ − 3 ℎ ∘ ݃(ݔ) = ℎ(3ݔ) = ℎ(ݔ);݃ ∘ ℎ(ݔ) = ൜0 ݊ếݑ ݔ ܿℎẵ݊3 ݊ếݑ ݔ ݈ẻ ݂ ∘ ݃ ∘ ℎ(ݔ) = 3ℎ(ݔ) − 1 b) ݂ଶ(ݔ) = ݔ − 2, ݂ଷ(ݔ) = ݔ − 3,݃ଶ(ݔ) = 9ݔ,݃ଷ(ݔ) = 27ݔ ℎଶ = ℎ,ℎଷ = ℎଶ = ℎ. Bằng qui nạp ℎଵ଴଴ = ℎ 22. ݂ଶ(ܣ) = ݂൫ܶ ∩ (ܵ ∪ ܣ)൯ = ܶ ∩ ቀܵ ∪ ൫ܶ ∩ (ܵ ∪ ܣ)൯ቁ = ൫ܶ ∩ (ܵ ∪ ܶ)൯ ∩ (ܵ ∪ ܣ) = ܶ ∩ (ܵ ∪ ܣ) = ݂(ܣ) 23. a) ݂ là song ánh. Ánh xạ ngược ݂ିଵ:ࡾ → ࡾ cho bởi ݂ିଵ(ݕ) = ݕ − 7. b) ݂(1) = ݂(−3) = 0 nên ݂ không đơn ánh GS. Nguyễn Hữu Anh 118 c) Hàm số ݂ tăng ngặt trên [4,9] nên ݂ là đơn ánh. Mặt khác ݂([4,9]) ⊂ [21,96]. Hơn nữa với ݕ ∈ [21,96] thì phương trình ݔଶ + 2ݔ − 3 = ݕ có nghiệm duy nhất là ݔ = −1 + ඥ4 + ݕ. Do đó ݂ là song ánh với ánh xạ ngược là ݂ିଵ(ݕ) = −1 + ඥ4 + ݕ. d) ݂ là song ánh. Ánh xạ ngược: ݂ିଵ(ݕ) = ൝ݕ ݊ếݑ ݕ ≥ 0ݕ5 ݊ếݑ ݕ < 5 e) ݂ là song ánh. ݂ିଵ(ݕ) = ln(ݕ)− 1,ݕ ∈ (0, +∞) f) ݂ là đơn ánh nhưng ݂ không toàn ánh vì 1 ∉ ݂(ܣ) 27. a) ݂ିଵ(−10) = −3,݂ିଵ(0) = 7,݂ିଵ(2) = 1,݂ିଵ(6) = 5 b) ݂ିଵ([−5,−1]) = [2,6], ݂ିଵ([−2,4]) = ݂ିଵ([−2,0])∪ ݂ିଵ൫(0.3)൯ ∪ ݂ିଵ([3,4]) = (−1,7] 28. a) Chú ý rằng ݂ là một song ánh giữa ࢆା ={1,2,} va tập hợp các số nguyên tự nhiên lẻ, cũng như là một song ánh giữa ࢆି ∪ {0} = { ,−2,−1,0} tập hợp các số nguyên tự nhiên chẵn. Suy ra ݂ là một song ánh giữa ࢆ và ࡺ. b) ݂ିଵ(ݕ) = ൞ ݕ + 12 ݊ếݑ ݕ ݈à ݏố ݊݃ݑݕê݊ ݐự ݊ℎ݅ê݊ ݈ẻ − ݕ2 ݊ếݑ ݕ ݈àݏ݋ố ݊݃ݑݕê݊ ݐự ݊ℎ݅ê݊ ܿℎẵ݊ 29. a) ݂(ݔ) = ݂(ݔᇱ) ⟹ ݃൫݂(ݔ)൯ = ݃൫݂(ݔᇱ)൯ ⟹ ݔ = ݔ′ b) Do ݃ ∘ ݂ toàn ánh nên cho ݖ ∈ ܥ tùy ý, sẽt tồn tại ݔ ∈ ܣ sao cho ݖ = ݃ ∘ ݂(ݔ) = ݃(ݕ) với ݕ = ݂(ݔ) ∈ ܤ. Điều này chứng tỏ ݃ toàn ánh. c) (݃ ∘ ݂)ିଵ = ݂ିଵ ∘ ݃ିଵ d) Chọn ݂(ݔ) = 2ݔ với ݔ ∈ ࡺ và ݃(ݔ) = ൞ݔ2 ݊ếݑ ݔ ݈à ݉ộݐ ݏố ݊݃ݑݕê݊ ݐự ݊ℎ݅ê݊ ܿℎẵ݊ݔ − 12 ݊ếݑ ݔ ݈à ݏố ݊݃ݑݕê݊ ݐự ݊ℎ݅ê݊ ݈ẻ 30. a) ݂(݊) = ݊ ± 1 nên ݊ và ݂(݊) khác tính chẵn lẻ. b) Giả sử ݂(݉) = ݂(݊). Khi ấy ݉ và ݊ cùng tính chẵn lẻ nên (−1)௠ = (−1)௡.Suy ra ݉ = ݊ ∶ ݂ là đơn ánh c) ݂ଶ(݊) = ݂(݊) + (−1)௙(௡) = ݊ + (−1)௡ − (−1)௡ = ݊,∀݊ ∈ ࢆ Như vậy ݂ là song ánh và ݂ିଵ = ݂. d) Ta có ݊ = ݂ିଵ(365) = ݂(365) = 365 + (−1)ଷ଺ହ = 364 31. i) Giả sử ݉ + ݊ < ݉ᇱ + ݊′. Khi ấy ݂(݉ + ݊) ≤ (݉ + ݊)(݉ + ݊ + 3)2 ≤ (݉ᇱ + ݊ᇱ − 1)(݉ᇱ + ݊ᇱ + 2)2 < ݂(݉ᇱ + ݊′) Tương tự nếu ݉ᇱ + ݊ᇱ < ݉ + ݊ thì ݂(݉ᇱ + ݊ᇱ) < ݂(݉,݊). Mặt khác nếu ݉ + ݊ = ݉ᇱ + ݊′ và ݂(݉,݊) = ݂(݉ᇱ,݊ᇱ) thì ݉ᇱ = ݉,݊ᇱ = ݊. Tóm lại ݂ là đơn ánh. ii) Đặt ܣ = ݂(ࡺ × ࡺ). Ta có 0 = ݂(0,0) ∈ ܣ GS. Nguyễn Hữu Anh 119 Mặt khác, giả sử ݇ = ݂(݉,݊). Khi ấy ݇ + 1 = ݂(݉ − 1,݊ + 1) nếu ݉ > 0 và ݇ + 1 = ݂(݊ + 1,0) nếu ݉ = 0. Suy ra ݂(ࡺ × ࡺ) = ࡺ theo Nguyên lý Qui nạp. 33. a) ቀ105 ቁ = 252 b) ቀ74ቁ = 35 c) ቀ105 ቁ − ቀ94ቁ − ቀ84ቁ = 56 34. a) Đó là các tập hợp có dạng ܣ ∪ ܤ với ܣ là một tập con của ≠ ∅ của {2,4,6,8,10} và ܤ ⊂ {1,3,5,7,9,11}. Do đó theo Nguyên lý nhân số tập hợp này là: (2ହ − 1)2଺ b) Tương tự như trên, số tập hợp con có dạng này là 2଺(2଺ − 1) c) Tổng quát hóa: nếu ܯ là một tập hợp số chẵn có ݉ phần tử và ܰ là một tập hợp số chẵn có ݊ phần tử thì số tập hợp con của ܯ ∪ܰ chứa ít nhất một số chẵn là: (2௠ − 1)2௡ 35. ݊ = 20 38. a) Số nhãn hiệu thỏa ít nhất 2 tính năng là: |(ܣ ∩ ܤ) ∪ (ܤ ∩ ܥ) ∪ (ܣ ∩ ܥ)| = |ܣ ∩ ܤ| + |ܤ ∩ ܥ| + |ܣ ∩ ܥ| = 4 Số nhãn hiệu thỏa ít nhất 1 tính năng là: |(ܣ ∩ ܤ) ∪ (ܤ ∩ ܥ)∪ (ܣ ∩ ܥ)| = 18− 4 = 14 Do đó số nhãn hiệu thỏa đúng 1 tính năng là 10. b) Số nhãn hiệu không thỏa tính năng nào là 15 - 14=1. 40. a) 2଻ − 2 = 126; 2଻ − 2 − ቀ71ቁ − ቀ76ቁ = 112 b) 2௡ − 2; 2௡ − 2 − 2݊ 41. ቀ ݊ ݊ଵ ቁቀ ݊ − ݊ଵ ݊ଶ ቁ ቀ݊௥݊௥ቁ = ௡!௡భ!௡మ!௡ೝ! 44. Gọi ܣ,ܤ,ܥ là tập hợp các sinh viên làm thí nghiệm thứ nhất, thứ hai và thứ ba tương ứng. Ta có: |ܣ| = 21 − 5 = 16, |ܤ| = 21 − 7 = 14, |ܣ| = 21 − 6 = 15. Áp dụn 38. ta được |ܣ ∩ ܤ| + |ܤ ∩ ܥ| + |ܣ ∩ ܥ| = 33 Số sinh viên làm ít nhất hai thí nghiệm là: |(ܣ ∩ ܤ) ∪ (ܤ ∩ ܥ) ∪ (ܣ ∩ ܥ)| = 33− 3|ܣ ∩ ܤ ∩ ܥ| + |ܣ ∩ ܤ ∩ ܥ| = 15 Do đó có 21 − 15 = 6 sinh viên chỉ làm được một 1 thí nghiệm. 45. Mỗi đường đi được xác định bởi ݉ ký tự ࡺ (đi ngang) chọn một dãy gồm có ݉ + ݊ ký tự ܰ và ܮ (đi lên). Do đó số các đường đi khác nhau là ቀ ݉ + ݊ ݉ ቁ = ቀ݉ + ݊ ݊ ቁ 46. ቀ10 + 4 − 14 − 1 ቁ = ቀ133 ቁ = 286 47. a) ቀ10 + 5 − 15− 1 ቁ = ቀ144 ቁ = 1001 b) Chia cho đứa trẻ lớn nhất hai hòn bi, còn lại chia cho 5 đứa: ቀ8 + 5− 15− 1 ቁ = ቀ124 ቁ = 495 c) Chia 5 hòn bi còn lạc họ đứa: ቀ5 + 5− 15− 1 ቁ = ቀ94ቁ = 126 48. a) Cho vào mỗi hợp một vật, còn lại ݎ − ݊ vật chia cho ݊ hộp: ቀݎ − ݊ + ݊ − 1 ݊ − 1 ቁ = ቀݎ − 1݊ − 1ቁ GS. Nguyễn Hữu Anh 120 b) ቀݎ − 1 ݊ − 1ቁ 49. a) Đây là số nghiệm ≥ 0 của phương trình ݕଵ + ݕଶ + ݕଷ + ݕସ = 8 ቀ8 + 4 − 14− 1 ቁ = ቀ113 ቁ = 165 b) Chỉ có 1 nghiệm: ݔଵ = ݔଶ = ݔଷ = ݔସ = 8 c) Chính là số nghiệm của phương trình ݕଵ + ݕଶ + ݕଷ + ݕସ = 28 với ݕଵ,ݕଶ,ݕଷ ≥ 0,0 ≤ ݕସ ≤ 24: ቀ313 ቁ− ቀ63ቁ = 4475 ở đây ቀ63ቁ chính là số nghiệm ≥ 0 của ݕଵ + ݕଶ + ݕଷ + ݕସ = 3 50. a) Theo Nguyên lý nhân, số các số hạng ݔ(2ݕ)ଶ(3ݖ)ଷݐ là: 7 × ቀ62ቁ× ቀ43ቁ = 420 Do đó hệ số của ݔݕଶݖଷݐ là 420 × 2ଶ × 3ଷ = 15120 b) Số số hạng có dạng ݔఈభݕఈమݖఈయݐఈరݒఈఱ là số nghiệm của phương trình ߙଵ + ߙଶ + ߙଷ + ߙସ + ߙହ = 7, với ߙ௜ ∈ ࡺ, 1 ≤ ݅ ≤ 5: ቀ7 + 5 − 15− 1 ቁ = ቀ114 ቁ = 330 53. a) ቀ82ቁ = 28 b) ቀ84ቁ = 70 c) ቀ86ቁ = 28 d) Đây cũng là số byte có nhiều nhất 2 bit 0: ቀ80ቁ+ ቀ81ቁ+ ቀ82ቁ = 37 55. a) ቀ152 ቁ = 105 b) ቀ253 ቁ = 2300, ቀ254 ቁ = 12650 56. a) ቀ ݊3ቁ = ௡(௡ିଵ)(௡ିଶ)଺ b) Có ݊ tam giác có chung hai cạnh với đa giác đều và ݊(݊ − 4) tam giác có chung một cạnh với đa giác đều. Do đó số tam giác không có cạnh chung là ݊(݊ − 1)(݊− 2)6 − ݊(݊ − 4)− ݊ = ݊6 (݊ଶ − 9݊ + 20) 59. a) (1 + 2)௡ = 3௡ b) (1 + ݔ − ݔ)௡ = 1 c) ෍ 1 ݅! (݊ − 1)!௡ ௜ୀ଴ = 1݊!෍ቀ݊݅ቁ௡ ௜ୀ଴ = 2௡ ݊! d) ෍ 1 ݅! (݊ − 1)!௡ ௜ୀ଴ = 1݊!෍(−1)௜௡ ௜ୀ଴ ቀ ݊ ݅ ቁ = 1݊! (1− 1)௡ = 0 60. Giả sử mỗi cửa có ít hơn bồ câu. Khi ấy ta có: ݉ ≤ ݊ ቀቒ௠ ௡ ቓ − 1ቁ < ݊௠ ௡ = ݉: mâu thuẫn 61. a) Ít nhất 7 lần: Nguyên lý chuồng bồ câu b) Gọi ݉ là số lần tung. Do 60. Ta cần có: ቒ௠ ଺ ቓ ≥ 3 Do đó giá trị nhỏ nhất của ݉ là 13 c) 6(݊ − 1) + 1 GS. Nguyễn Hữu Anh 121 63. a) Ta chọn 10 của chuồng bồ câu: [1,2),[2,3),,[9,10),{10}. Do nguyên lý chuồng bồ câu có hai phần tử ݔ ≠ ݕ có căn bậc hai cùng thuộc một tập hợp, nghĩa là: 0 < ห√ݔ −ඥݕห <1. b) Cho trước một số nguyên ݇ > 0. Trong ݊ + 1 phần tử khác nhau của {1,2, ,݊௞}, có ít nhất 2 phần tử ݔ,ݕ sao cho: 0 < ห √ݔೖ − ඥݕೖ ห < 1 64. Vẽ 9 tam giác đều có các cạnh song song với các cạnh của tam giác đều đã cho vaa2 đỉnh chọn trong số 3 đỉnh, 6 diểm chia các cạnh theo tỉ số ଵ ଷ và tâm của tam giác đều. Theo Nguyên lý chuồng bồ câu, có ít nhất 2 trong số 10 điểm đã cho thuộc về cùng một tam giác đều nhỏ. Khoảng cách của chúng ≤ ଵ ଷ . Dấu = chỉ xảy ra đối với 2 đỉnh của một tam giác đều nhỏ. Tuy nhiên chỉ có một đỉnh duy nhất nằm bên trong tam giác đều đã cho. CHƯƠNG 3 1. a) ݔ = 0, (ݕ, ݖ, ݐ) ∈ ܣଶ × ܣଷ × ܣସ tùy ý: có 4.7ଶ = 196 bộ 4 ݔ ≠ 0 tùy ý, ݖ = 0, (ݕ, ݐ) ∈ ܣଶ × ܣସ tùy ý: có 4ଶ. 7 = 112 bộ 4 ݔ ≠ 0 tùy ý, ݕ tùy ý, ݖ ≠ 0 tùy ý, ݐ = 0: có 4ଶ. 6 = 96 bộ 4 Vậy |ℛଵ| = 196 + 112 + 96 = 404 b) ݔ ≠ 0 tùy ý, ݕ tùy ý, ݖ ≠ 0 tùy ý, ݐ = 0 tùy ý Vậy |ℛଶ| = 4ଶ. 6.3 = 288 2. a) |ܣ× ܤ| = 3ଶ = 9 b) 2|஺×஻| = 2ଽ = 512 c) 2|஺×஺| = 512 d) Đó là số tập hợp con của ܣ × ܤ\{(1,2), (1,5)} = 2଻ = 128 e) Đó là số tập hợp con 5 phần tử của ܣ × ܤ: ቀ95ቁ = 126 f) 2ଽ − ቀ90ቁ − ቀ91ቁ − ቀ92ቁ = 466 3. 2|஺||஻| = 4096 = 2ଵଶ ⟹ 3|ܣ| = 12 ⟹ |ܣ| = 4 4. a) Quan hệ hàm: ݂:ࡾ → ࡾ, ݂(ݔ) = ݔଶ + 7 b) Quan hệ hàm: ݂:ࡾ → ࡾ, ݂(ݕ) = ݕଶ c) Quan hệ hàm: ݂:ࡾ → ࡾ, ݂(ݔ) = 3ݔ+ 1 hay ݃:ࡾ → ࡾ,݃(ݕ) = ௬ିଵ ଷ = ݂ିଵ(ݕ) d) Không phải là quan hệ hàm e) Quan hệ hàm: ݂: [0,1] ⟶ [0,1],݂(ݔ) = √1 − ݔଶ hay ݃ : [0,1] ⟶ [0,1],݃(ݕ) = ඥ1 − ݕଶ = ݂ିଵ(ݕ) = ݂(ݕ) 5. a) ߨ஺(ℛ) = [0, +∞),ߨ஻(ℛ) = ࡾ b) ߨ஺(ℛ) = ࡾ,ߨ஻(ℛ) = [−1,1] c) ߨ஺(ℛ) = [−1,1],ߨ஻(ℛ) = [−1,1] 6. a) Quan hệ trên ܣଷ × ܣସ × ܣହ trong đó dòng 2 và 3 đồng nhất nên loại bớt 1 và dòng 5 và 6 đồng nhất nên loại bớt 1. b) ܣଵ ×ܣଶ đều có thẻ dùng làm khóa chính 7. a) Quan hệ chiếu lên ܣଵ × ܣଶ gồm 2 cột đầu và đủ 6 dòng. Quan hệ chiếu lên ܣଷ × ܣସ × ܣହ gồm 3 cột đầu và đủ 6 dòng. GS. Nguyễn Hữu Anh 122 b) Không có khóa chính vì mỗi cột đều có giá trị lặp lại. c) ܣଵ × ܣଶ,ܣଵ × ܣଷ,ܣଶ × ܣଷ,ܣଶ × ܣହ,ܣଷ × ܣହ. 8. a) ℛ = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (2,3), (3,2)} b) ℛ = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (2,3), (1,3)} c) ℛ = {(1,1), (2,2), (1,2), (2,1)} 9. a) Phản xạ, đối xứng, bắc cầu. Tuy nhiên không phản xứng trừ trường hợp ܥ = ܧ b), e), f), g) Phản xạ, đối xứng, bắc cầu nhưng không phản xứng c) Đối xứng nhưng không có ba tính chất kia d) Phản xạ, phản xứng, bắc cầu nhưng không đối xứng 11. a) (ℛ∗)∗ = ℛ b) ℛ = ℛ∗ khi và chỉ khi ℛ đối xứng c) bắc cầu, phản xứng khi và chỉ khi ℛ∗ bắc cầu, phản xứng. Theo b) nếu ℛ đối xứng thì ℛ∗ = ℛ cũng đối xứng. 12. a) |ܣ × ܣ| = 16, |∆஺| = 4 nên số quan hệ phản xạ là: 2ଵ଺ିସ = 4096 b) Gọi ࣮ = {(݅, ݆)/1 ≤ ݅ < ݆ ≤ 4}. Với ܵ ⊂ ࣮ ∪ ∆஺ thì ܵ ∪ {(ܽ, ܾ)(ܾ, ܽ) ∈ ܵ} là một quan hệ đối xúng và ngược lại. Do đó số quan hệ đối xứng là 2࣮∪∆ಲ = 2ଵ଴ = 1024 c) Một quan hệ phản xạ và đối xứng xác định duy nhất bởi tập hợp ܵ ⊂ ࣮ nên số quan hệ phản xạ và đối xứng là 2|࣮| = 2଺ = 64. d) Giả sử ℛ phản xứng, đặt ଵܵ = ℛ ∩ ∆஺, ଶܵ = ℛ ∩࣮ và ܵଷ = ℛ∗ ∩ ࣮ : rõ ràng ℛ được xác định duy nhất bởi ଵܵ, ܵଶ , ଷܵ. Do đó số các quan hệ phản xứng là : 2ସ෍ቀ6݇ቁ2଺ି௞ = 11.664଺ ௞ୀ଴ e) Đó là quan hệ ℛ ⊂ ∆஺: có 2ସ = 16 quan hệ f) Quan hệ duy nhất là ℛ = ∆஺. 13. Ta viết ܣ = {ܽଵ,ܽଶ, ,ܽ௡}. Đặt ࣮ = ൛൫ܽ௜ , ௝ܽ൯/݅ < ݆ൟ. Ta có |ܶ| = ௡(௡ିଵ)ଶ . Tương tự như trên, mỗi quan hệ phản xứng ℛ tương ứng với các tập con ଵܵ, ܵଶ, ܵଷ. ℛ là tối đại khi và chỉ khi ଵܵ = ∆஺ và ܵଶ ∪ ܵଷ = ࣮, nghĩa là |ℛ| = ௡(௡ିଵ)ଶ + ݊ = ௡(௡ାଵ)ଶ Hơn nữa số quan hệ như vậy chính là 2೙(೙షభ)మ . 14. a) Trực tiếp từ định nghĩa b) [1] = {1,2} = [2], [3] = {3} c) [4] = {4,5} = [5] và [6] = {6}. Do đó ta có phân hoạch của ܣ thành các lớp tương đương: ܣ = {1,2}∪ {3} ∪ {4,5} ∪ {6} 15. Ngoài đường chéo chính ∆஺, còn chứa các cặp {1,2},{2,1},{3,4},{4,3}. 16. Ta có (1,2) và (2,3) nhưng (1,3) ∉ ℛ nên ℛ không phải là quan hệ tương đương. 17. a) Hiển nhiên GS. Nguyễn Hữu Anh 123 b) [(ݔ,ݕ)] = {(ݔ, ݐ)/ݐ ∈ ℛ}. Đấy chính là đường thẳng song song với trục tung và đi qua điểm (ݔ, ݕ) 19. a) Đó là quan hệ tương đương b) [∅] = ൛∅, {3}ൟ, [{1}] = ൛{1}, {1,3}ൟ, [{2}] = ൛{2}, {2,3}ൟ, [{1,2}] = ൛{1,2}, {1,2,3}ൟ c) [{1,3,5}] = {{1,3,4},{1,3,5}}. Mỗi lớp tương đương đều chứa một tập hợp con duy nhất của ܥ nên số lớp tương đương chính là 2|஼| = 2ଷ = 8 21. a) ଵ ଶ ቀ63ቁ = 10 b) ቀ63ቁቆ1 + ቀ31ቁቇ = 80 c) ቀ64ቁ × 2 = 30 d) 10 + 80 + 30 + ቀ଺ହቁ = 126 22. a) Suy trực tiếp từ định nghĩa b) {݂ିଵ(ݕ)/ݕ ∈ ݂(ܤ)} 23. ℛ = (ܣଵ ×ܣଵ) ∪ (ܣଶ × ܣଶ) ∪ (ܣଷ × ܣଷ) 25. Xét ࣪ଵ = ࣪({1,2,3}) và ࣪ଶ = {ܣ ⊂ ܧ/4 ∈ ܣ}. Khi ấy biểu đồ Hasse của ࣪ଵ và ࣪ଶ là 2 hình lập phương 3 chiều. Nối mỗi đỉnh ܣ ∈ ࣪ଵ đến đỉnh ܣ ∪ {4} ∈ ࣪ଶ bởi 1 cung có hướng xuất phát từ ܣ. Tập hợp các đỉnh trong ࣪ଵ và ࣪ଶ và các cung trong ࣪ଵ và ࣪ଶ cùng với các cung mới thêm vào như trên chính là biểu đồ Hasse của ࣪(ܧ). 26. a) Kiểm tra trực tiếp của định nghĩa b) ≺ không nhất thiết là toàn phần. ví dụ ܣ = ܤ = {0,1} và ≺஺,≺஻ là thứ tự thông thường 27. a) Trực tiếp từ định nghĩa b) Với ݂,݃ ∈ ܤா tùy ý. Định nghĩa ánh xạ ℎ:ܧ → ܤ bởi ℎ(ݔ) = ݂(ݔ) ∨஻ ݃(ݔ),∀ݔ ∈ ܧ. Khi ấy ℎ = sup{݂,݃} Tương tự ta thấy inf(݂,݃) là ánh xạ ܧ → ܤ: inf(݂,݃) (ݔ) = ݂(ݔ) ∧஻ ݃(ݔ),∀ݔ ∈ ܧ 29. Tính phản xạ hiển nhiên. Gọi ݅ là chỉ số sao cho ܽଵ = ܾଵ,ܽଶ = ܾଶ, ,ܽ௜ = ܾ௜ và ݅ = ݉ hoặc ܽ௜ାଵ ܾ௜ାଵ nếu ݅ < ݉. Gọi ݆ là chỉ số tương tự xác định từ ݏଶ ≺ ݏଷ.  Nếu ݆ ≥ ݅ thì ta có ܽଵ = ܿଵ, ,ܽ௜ = ܿ௜ và ݅ = ݉ hoặc ܽ௜ାଵ ܾ௜ାଵ ≺ ܿ௜ାଵ nếu ݅ < ݉.  Nếu ݆ < ݅ thì ݆ < ݊ nên ta có ܽଵ = ܿଵ, , ௝ܽ = ௝ܿ và ܽ௜ାଵ ≺ ܾ௜ାଵ ܿ௜ାଵ. Trong cả hai trường hợp ta đều có ݏଵ ≺ ݏଷ và ≺ có tính bắc cầu. Chú ý rằng trong trường hợp trên nếu ݏଷ = ݏଵ thì trường hợp 2 không xảy ra và khi đó ݏଵ = ݏଶ, nghĩa là ≺ là phản xứng. Xét hai chuỗi khác rỗng ݏଵ, ݏଶ như trên. Nếu ܽ௜ = ܾ௜ với 1 ≤ ݅ ≤ min(݉,݊) thì ta có ݏଵ ≺ ݏଶ hay ݏଶ ≺ ݏଵ theo Định nghĩa của ≺. Trong trường hợp ngược lại sẽ có chỉ số ݅ bé nhất để ܽ௜ ≠ ܾ௜ , nghĩa là ܽଵ = ܾଵ, ,ܽ௜ିଵ = ܾ௜ିଵ. Do thứ tự trên ࣛ là tòan phần ta có ܽ௜ ௜ܾ hay ܽ௜ ܾ௜. Nói cách khác ݏଵ ≺ ݏଶ hay ݏଶ ≺ ݏଵ. Tóm lại thứ tự trên ܵ là toàn phần. 30. Trong 3 biểu đồ đầu, định nghĩa trội trực tiếp bị vi phạm. Ngoài ra trong biểu đồ thứ 2 tính phản xứng cũng bị vi phạm. Chỉ có biểu đồ cuối cùng là biểu đồ Hasse 34. a) Chỉ có một chặn trên gồm 3 phần tử {1,2,3} Số chặn trên gồm 4 phần tử: ቀ41ቁ = 4 Số chặn trên gồm 5 phần tử: ቀ42ቁ = 6 GS. Nguyễn Hữu Anh 124 b) 11 + ቀ43ቁ+ ቀ44ቁ = 16 c) {1,2,3} d) Một chặn dưới duy nhất:∅ e) ∅ 35. a) (࣪({1,2}),⊂) là 1 dàn nhưng thứ tự ⊂ không toàn phần. b) Nếu ≺ toàn phần thì với ݔ,ݕ ∈ ܣ tùy ý ta có: sup{ݔ,ݕ} = max(ݔ,ݕ) ݒà inf{ݔ,ݕ} = min(ݔ,ݕ) Do đó ܣ là một dàn. 37. a) ܽ b) ܽ c) ܿ d) ݁ e) ݖ f) ݁ g) ݒ 38. a) ݖ là phần tử lớn nhất và ܽ là phần tử bé nhất b) (ܣ,≺) là một dàn 39. Sử dụng các qui luật logic 40. a) ∀ݔ,ݕ, min{ݔ,ݕ} tồn tại. Vậy thứ tự tốt toàn phần. Tuy nhiên ≤ là thứ tự toàn phần trên ࢆ nhưng không phải là thứ tự tốt. b) Do định nghĩa của thứ tự tốt c) ≤ là thứ tự tốt trên ࡺ nhưng ࡺ không có phần tử lớn nhất. {1,2} là 1 tập hợp sắp tốt có phần tử lớn nhất. 41. a), e), f) là tập hợp sắp tốt. b) Không phải là tập sắp tốt. Mặt khác tập hợp {1, ଵ ଶ , , ଵ ௡ , } không có phần tử bé nhất nên (ܳ,≤) và (ܳା,≤) không phải là tập sắp tốt. g) Giả sử ࣛ là bộ mẫu tự gồm 2 chữ cái ܽ ≺ ܾ. Khi ấy {ܾܽ,ܾܽܽ,ܾܽܽܽ, } là một tập con của ܵ không có phần tử bé nhất nên ܵ không phải là tập sắp tốt. 42. a) ݏ(ݔ) = min{ݕ ∈ ܣ ≺ ݔ ݕ} chính là trội trực tiếp duy nhất của ݔ. b) Giả sử ݔ ݕ. Khi ấy ݏ(ݔ) ≺ ݕ ݏ(ݕ) nên ݏ là đơn ánh. Tuy nhiên phần tử bé nhất ߙ của ܣ không thuộc ݏ(ܣ). c) Định nghĩa ánh xạ ߮:ࡺ → ܣ bởi ߮(0) = ߙ,߮(݊) = ݏ௡(ߙ), trong đó ݏ௡(ߙ) được định nghĩa bằng qui nạp: ݏ௡(ߙ) = ݏ൫ݏ௡ିଵ(ߙ)൯. Khi ấy ߮ là một đẳng cấu giữa hai tập hợp sắp thứ tự (ࡺ,≤) và (ܣ,≺) 43. a) 1 b) 22 c) 6 d) 11 e) 3 a) 2ଶ. 3ଷ. 5ଷ. 11 và 2ସ. 3. 5ଶ. 7ଶ. 11ଶ b) ܷܵܥܮܰ = 2ଶ. 3.5ଶ. 11 = 3300 ܤܵܥܰܰ = 2ସ. 3ଷ. 5ଷ. 7ଶ. 11ଶ = 320.166.000 47. a) 2௔. 5௕. 7௖, 0 ≤ ܽ ≤ 3,0 ≤ ܾ ≤ 2,0 ≤ ܿ ≤ 4 b) Các ước số dương của ݉ có dạng ݌ଵ ௦భ݌ଶ ௦మ݌ଷ ௦య với 0 ≤ ݏଵ ≤ ݎଵ, 0 ≤ ݏଶ ≤ ݎଶ , 0 ≤ ݏଷ ≤ ݎଷ. Do đó theo Nguyên lý nhân, số ước số dương là (ݎଵ + 1)(ݎଶ + 1)(ݎଷ + 1). c) Nếu ݉ = ݌ଵ௥భ݌ଶ௥మ݌௡௥೙ thì ݊ có (ݎଵ + 1)(ݎଶ + 1) (ݎ௡ + 1) ước số dương. d) Suy ra ݎ௜ + 1 = 2௔೔, nghĩa là ݎ = 2௔೔ − 1,ܽ௜ ∈ ࢆା, 1 ≤ ݅ ≤ ݊ 49. a) Sinh viên thứ ݊ lật đ62ng xu thứ 100 khi và chỉ khi ݊ là ước số của 200 = 2ଷ. 5ଶ. Do đó số lần mà dồng xu thứ 200 dược lật là 4.3 = 12. b) Giả sử đồng xu thứ ݉ = ݌௔ݍ௕ݎ௖ < 200 được lật ngược (ܽ + 1)(ܾ + 1)(ܿ + 1) = 12 lần. Khi ấy ݉ có thể lấy các giá trị sau: 2ହ. 3 = 96 2ହ. 5 = 160 2ଷ. 3ଶ = 72 3ଶ. 2ଶ = 108 2ଶ. 3.5 = 60 2ଶ. 3.7 = 84 GS. Nguyễn Hữu Anh 125 2ଶ. 3.11 = 132, 2ଶ. 3.13 = 156 , 2ଶ. 5.7 = 140, 3ଶ. 2.7 = 126, 3ଶ. 2.11 = 198 52. a) Giả sử (ݔ,ݕ) là một lời giả thì ܽ là ước của ݕ do Mệnh đề 3.6.3: ݕ = ݇ܽ. Khi ấy ݔ = ܾ݇ Ngược lại (ܾ݇, ݇ܽ),݇ ∈ ࢆ là một lời giả. b) Gọi ݀ = ܷܵܥܮܰ(ܽ, ܾ). Ta có ݔ ௔ ௗ = ݕ ௕ ௗ nên do a) các lời giải có dạng (݇ ௕ ௗ , ݇ ௔ ௗ ), ݇ ∈ ࢆ c) Gọi ݀ = ܷܵܥܮܰ(ܽ, ܾ) = ݉ܽ + ܾ݊,݉,݊ ∈ ࢆ (Định lý 3.6.2) Do đó nếu ݔ,ݕ thỏa ݀ = ݔܽ + ݕܾ thì (ݔ − ݉)ܽ = (݊ − ݕ)ܾ Theo b), ݔ −݉ = ݇ ௕ ௗ ,݊ − ݕ = ݇ ௔ ௗ , với ݇ ∈ ࢆ Nghĩa là ݔ = ݉ + ݇ ௕ ௗ và ݕ = ݊ − ݇ ௔ ௗ 53. Dùng thuật chia Euclide để tìm ݀,݉,݊: a) ݀ = 2,݉ = −1,݊ = 3;ݔ = −1 + 8݇,ݕ = 3 − 23݇, ݇ ∈ ࢆ b) ݀ = 4,݉ = −1,݊ = 2; ݔ = −1 + 16݇,ݕ = 3− 31݇, ݇ ∈ ࢆ c) ݀ = 1,݉ = −26,݊ = 271;ݔ = −26 + 331݇,ݕ = 271− 3450݇, ݇ ∈ ࢆ 54. a) Giả sử ܽܽᇱ ≡ 1 (݉݋݀ ݊) khi ấy ta có ݔ ≡ ܽܽᇱݔ = ܽᇱܾ(݉݋݀ ݊) Do đó ܾܽ′ là nghiệm duy nhất trong ࢆ௡ của phương trình đồng dư đã cho. b) Gọi ݀ = ܷܵܥܮܰ(ܽ,݊) > 1. Nếu ܾ không chia hết cho ݀, thì phương trình dồng dư là vô nghiệm. Mặt khác giả sử ݀|ܾ khi ấy ta đưa về việc giải phương trình đồng dư ݉݋݀ ݊ᇱ = ௡ ௗ : ܽ ݀ ݔ ≡ ܾ ݀ (݉݋݀ ݊′) Theo a) phương trình trên có nghiệm duy nhất trong ࢆ௡ᇱ : ݔ ≡ ܽᇱ ௕ ௗ(݉݋݀ ݊ᇱ) ݒớ݅ ܽ′ ܽ ݀ ≡ 1(݉݋݀ ݊ᇱ) Đó cũng là nghiệm của phương trình đồng dư ban đầu. 55. a) (3,16)=1. Ta có 3 × 11 ≡ 33 ≡ 1(݉݋݀ 16) nên ݔ ≡ 11 × 7 ≡ 13(݉݋݀ 16) b) (5,23)=1. Ta có 5 × 14 ≡ 70 ≡ 1(݉݋݀ 23) nên ݔ ≡ 14(6− 7) ≡ 9(݉݋݀ 23) c) Phương trình có dạng 3ݔ ≡ −12 ≡ 10(݉݋݀ 11) Mà 3 × 4 ≡ 1(݉݋݀ 11) nên ݔ ≡ 4 × 10 ≡ 7݉݋݀(11) d) Phương trình có dạng 5ݔ ≡ −52 ≡ 12(݉݋݀ 64) Mà 5 × 13 ≡ 65 ≡ 1(݉݋݀ 64) nên ݔ ≡ 13 × 12 ≡ 28(݉݋݀ 64) CHƯƠNG 4 1. a) Giả sử ̅ݔ và ݔ′ là hai phần bù của ݔ. Ta có: (̅ݔ ∧ ݔ) ∨ ݔᇱ = 0 ∨ ݔᇱ = ݔ′ Mà (̅ݔ ∧ ݔ) ∨ ݔᇱ = (̅ݔ ∨ ݔᇱ) ∧ (ݔ ∨ ݔᇱ) = (̅ݔ ∨ ݔᇱ) ∧ 1 = ̅ݔ ∨ ݔᇱ Suy ra ̅ݔ ≺ ̅ݔ ∨ ݔᇱ = ݔ′ Tương tự nếu xét (̅ݔ ∧ ݔ) ∨ ݔᇱ ta cũng có ݔᇱ ≺ ̅ݔ. Nghĩa là ̅ݔ = ݔ′ b) Kiểm tra trực tiếp từ định nghĩa của phần bù rồi sử dụng a). GS. Nguyễn Hữu Anh 126 2. a) Do ݔ ≺ ݕ nên ݕ là trội chung của ݔ và ݕ. Hơn nữa nếu ݖ là trội chung của ݔ,ݕ thì ݕ ≺ ݖ. Như thế ݕ = sup{ݔ,ݕ} = ݔ ∨ ݕ b) Do a) ݔ ≺ ݕ ⟹ ݔ ∨ ݕ = ݕ ⟹ ̅ݔ ∧ ݕത = ݕത: ݕത ≺ ̅ݔ c) ݔ ∧ ݖ ≺ ݔ ≺ ݕ và ݔ ∧ ݖ ≺ ݖ ≺ ݐ. Suy ra ݔ ∧ ݖ ≺ ݕ ∧ ݐ d) ݔ ≺ ݕ ≺ ݕ ∨ ݐ và ݖ ≺ ݐ ≺ ݕ ∨ ݐ. Suy ra ݔ ∨ ݖ ≺ ݕ ∨ ݐ 3. a) ൫ തܾ ∧ ܿ൯ ∨ (ܿ ∧ ݀) = ൫തܾ ∨ ݀൯ ∧ ܿ nên ൫തܾ ∧ ܿ൯ ∨ (ܿ ∧ ݀)തതതതതതതതതതതതതതതതതതതതത = തܾ ∨ ݀തതതതതതത ∨ ܿ̅ = ൫ܾ ∧ ݀̅൯ ∨ ܿ̅ b) (ܾ ∧ ܿ̅) ∨ ቀ൫തܾ ∧ ܽ൯ ∨ (ܽ ∧ ܿ)ቁ = (ܾ ∧ ܿ̅) ∨ ቀ൫തܾ ∨ ܿ൯ ∧ ܽቁ = ቀ(ܾ ∧ ܿ̅ ) ∨ (ܾ ∧ ܿ̅ )തതതതതതതതതതቁ ∧ ൫(ܾ ∧ ܿ̅ ) ∨ ܽ൯ = (ܾ ∧ ܿ̅ ) ∨ ܽ Do đó phần bù của nó là: ൫തܾ ∨ ܿ൯ ∧ ܽ 4. a) Xét một phần tử ݔ ∈ ℬ. Khi ấy ̅ݔ ∈ ℬ và 0 = ݔ ∧ ̅ݔ ∈ ℬ, 1 = ݔ ∨ ̅ݔ ∈ ℬ b) Có 4 đại số con là ࣛ,ℬଵ = ൛∅, {ܽ}, {ܾ, ܿ}, {ܽ, ܾ, ܿ}ൟ,ℬଶ = ൛∅, {ܾ}, {ܽ, ܿ}, {ܽ, ܾ, ܿ}ൟ,ℬଷ = ൛∅, {ܿ}, {ܽ, ܾ}. {ܽ, ܾ, ܿ}ൟ. c) Với ݔ,ݕ ∈ ℬ tùy ý ta có ̅ݔ,ݕത ∈ ℬ nên ݔത ∨ ݕത ∈ ℬ. Suy ra ݔ ∧ ݕ = ̅ݔ ∨ ݕഥതതതതതതത ∈ ℬ. 5. Đó là đại số Bool với phần tử trung hòa đối với ∧ là ܽ. Hơn nữa với ݔ ≺ ܽ thì ̅ݔ ∧ ܽ là phần bù của ݔ. Tuy nhiên nó không phải là đại số con nếu ܽ ≠ 1 vì khi ấy nó không chứa 1 6. a) Giả sử ݕ ≺ ߮(ܽ), tồn tại ݔ sao cho ߮(ݔ) = ݕ. Ta có ߮(ݔ) ≺ ߮(ܽ) nên ݔ ≺ ܽ suy ra ݔ = 0 hay ݔ = ܽ, nghĩa là ݕ = 0 hay ݕ = ܾ. b) Trực tiếp từ định nghĩa của đại số con. 8. a) Do 35 = ܤܵܥܰܰ(5,7), 70 = ܤܵܥܰܰ(35,2) ݒà 42 = ܤܵܥܰܰ(2,3,7) ta phải có ߮(35) ={ܿ,݀},߮(70) = {ܽ, ܿ,݀},߮(42) = {ܽ, ܾ,݀}. b) Mỗi đẳng cấu phải biến nguyên tử thành nguyên tử nên được xác định hoàn toàn bởi một song ánh giữa {2,3,5,7} và {ܽ, ܾ, ܿ,݀}. Có tất cả 4! = 24 đẳng cấu khác nhau. 11. a) (ܽ⨁ܾ)⨁ܿ = ቂቀ൫ܽ ∧ തܾ൯ ∨ ( തܽ ∧ ܾ)ቁ ∧ ܿ̅ቃ ∨ ൣ( തܽ ∨ ܾ) ∧ ൫ܽ ∨ തܾ൯ ∧ ܿ൧ = ൫ܽ ∧ തܾ ∧ ܿ̅൯ ∨ ( തܽ ∧ ܾ ∧ ܿ̅) ∨ (ܽ ∧ ܾ ∧ ܿ) ∨ ൫തܽ ∧ തܾ ∧ ܿ൯ = ቂܽ ∧ ቀ(ܾ ∧ ܿ) ∨ ൫തܾ ∧ ܿ̅൯ቁቃ ∨ ቂ തܽ ∧ ቀ(ܾ ∧ ܿ̅) ∨ ൫തܾ ∧ ܿ൯ቁቃ = ൫ܽ ∧ ܾ⨁ܿതതതതതത൯ ∨ ( തܽ ∧ ܾ⨁ܿ) = ܽ⨁(ܾ⨁ܿ) ܽ ∧ ܾ⨁ܿ = (ܽ ∧ ܾ ∧ ܿ̅) ∨ ൫ܽ ∧ തܾ ∧ ܿ൯ = ൫ܽ ∧ ܾ ∧ ( തܽ ∨ ܿ̅)൯ ∨ ቀ(ܽ ∧ ܿ) ∧ ൫ തܽ ∨ തܾ൯ቁ = (ܽ ∧ ܾ)⨁(ܽ ∧ ܿ) Các tính chất khác hiển nhiên. b) Đặt = ൫ܽ ∧ തܾ൯ ∨ (ܾ ∧ തܽ) (ܽ⨁ܾ) ∧ ൫ܽ ∧ തܾ൯ = ൫ܽ ∧ ܽ ∧ തܾ൯⨁൫ܾ ∧ ܽ ∧ തܾ൯ = ܽ ∧ തܾ Suy ra ܽ ∧ തܾ ≺ ܽ⨁ܾ Tương tự ܾ ∧ തܽ ≺ ܽ⨁ܾ GS. Nguyễn Hữu Anh 127 Vậy ܽ⨁′ܾ ≺ ܽ⨁ܾ Do đó (ܽ⨁ܾ) ∨ ܽ⨁′ܾതതതതതതത = 1 Mặt khác (ܽ⨁ܾ) ∧ ܽ⨁′ܾതതതതതതത = ቀܽ ∧ ( തܽ ∨ ܾ) ∧ ൫ܽ ∨ തܾ൯ቁ⨁ቀܾ ∧ ( തܽ ∨ ܾ) ∧ ൫ܽ ∨ തܾ൯ቁ = (ܽ ∧ ܾ)⨁(ܽ ∧ ܾ) = 0 Như thế ܽ⨁ܾ = ܽ⨁′ܾതതതതതതതതതതതതതത = ܽ⨁′ܾ 13. a) ܽ ∨ ݔ = ܾ ⟹ ܽ ≺ ܾ Mặt khác giả sử ܽ ≺ ܾ. Đặt ݔ = തܽ ∧ ܾ. Ta có: ܽ ∨ ݔ = ܽ ∨ ܾ = ܾ b) ܾ ∧ ݕ = (ܾ ∧ ݔ) ∨ (ܾ ∧ തܽ) = ݔ ∨ (ݔ ∧ തܽ) = ݔ ܾ ∨ ݕ = ܾ ∨ ݔ ∨ തܽ = ܾ ∨ തܽ ≻ ܽ ∨ തܽ = 1 c) Ta có തܽ ∧ ܾ = തܽ ∧ ݔ ≺ ݔ ≺ ܾ. Ngược lại giả sử ܽ ≺ ܾ và തܽ ∧ ܾ ≺ ݔ ≺ ܾ. Khi ấy ܽ ∨ ܾ = ܽ ∨ (ܽ ∧ ܾ) ≺ ܽ ∨ ݔ ≺ ܽ ∨ ܾ Suy ra ݔ là nghiệm của (1). d) Nếu ݔ là nghiệm, do b) ݔ có dạng ܾ ∧ ܿ với ܿ = ݔ ∨ തܽ ≺ തܽ . Ngược lại nếu ݔ = ܾ ∧ ܿ với ܿ ≻ തܽ thì തܽ ∧ ݔ = തܽ ∧ ܿ ∧ ܾ = തܽ ∧ ܾ. Như thế ܽ ∧ ܾ ≺ ݔ ≺ ܾ nên ݔ là nghiệm do c). e) Nghiệm của ܽ ∧ ݔ = ܾ cũng là nghiệm của തܽ ∧ ̅ݔ = ഥܾ nên ta đưa về (1). 14. Do 1728 = 2଺. 3ଷ chia hết cho chính phương nên ࣯ଵ଻ଶ଼ không là đại số Bool. Hơn nữa số mũ 6 không có dạng 2௔ − 1,ܽ ∈ ࢆ nên không có thứ tự nào trên ࣯ଵ଻ଶ଼ để cho nó trở thành dàn bù phân bố, nghĩa là đại số Bool. 16. a) ݀(ܽ) = 1 nếu ܽ là nguyên tử. b) Nhận xét rằng nếu ܽ là nguyên tử không trội bởi ݔ thì ݔ ∨ ܽ là trội trực tiếp của ݔ. Do đó ta có thể chứng minh bằng qui nạp rằng ݀(ݔ) = ݉ nếu có đúng ݉ nguyên tử trội bởi ݔ. Suy ra ݀(ݔ ∨ ݕ) = ݀(ݔ) + ݀(ݕ)− ݀(ݔ ∧ ݕ) 17. a) 0 b) 0 c) 0 d) 1 e) 1 18. a), b) ݕ = 1 ℎܽݕ ݖ = 1 c), d) ݖ = 1,ݕ ݐùݕ ý 19. a) ̅ݔݕݖݐ̅ b) ݔݕݖ̅ݐ̅ c) ݔݕݖݐ̅ d) ̅ݔݕതݖ̅ݐ ̅ 20. a) Có ቀ62ቁ = 15 điểm có đúng 2 thành phần bằng 1. Còn lại (2଺ − 15) = 49 điểm, nên có 2ସଽ hàm Bool thỏa điều kiện này. b) Có ቀ60ቁ+ ቀ61ቁ = 7 điểm ở đó số thành phần có giá trị 1 béhoơn 2, nên tổng số hàm Bool thỏa điều kiện này là 2଻ = 128. c) 2ଶఱ = 2ଷଶ và 2ଶయ = 2଼ = 256. 21. Ta có ݂(1,0) = ݂(0,1) nên các hàm Bool này đều có dạng ߙݔݕ ∨ ߚ̅ݔݕത ∨ ߛ(ݔݕത ∨ ̅ݔݕ), với ߙ,ߚ, ߛ là các hằng số bất kỳ thuộc {0,1} 22. Ta có ݂(1,0,0) = ݂(0,0,1) = ݂(0,1,0) và ݂(1,1,0) = ݂(1,0,1) = ݂(0,1,1) Do đó các hàm Bool này đều có dạng: ݂(ݔ,ݕ, ݖ) = ߙݔݕݖ ∨ ߚ̅ݔݕതݖ̅ ∨ ߛ(ݔݕݖ̅ ∨ ݔݕതݖ ∨ ̅ݔݕݖ) ∨ ߜ(ݔݕതݖ̅ ∨ ̅ݔݕݖ̅ ∨ ̅ݔݕതݖ) trong đó là các hằng số tùy ý thuộc {0,1}. GS. Nguyễn Hữu Anh 128 23. Hàm Bool 3 biến không thay đổi giá trị khi ta hoán vị 2 biến bất kỳ chính là các hà m Bool trong 22. Tương tự một hàm Bool 4 biến khi thay đổi giá trị khi ta hoán vị 2 biến bất kỳ có dạng: ݂(ݔ,ݕ, ݖ, ݐ) = ߙݔݕݖݐ ∨ ߚ̅ݔݕതݖ̅̅ݐ ∨ ߛ(ݔݕഥݖത̅ݐ ∨ ݔഥݕݖത̅ݐ ∨ ݔഥݕഥݖ̅ݐ ∨ ݔഥݕഥݖതݐ) ∨ ߜ(ݔݕݖത̅ݐ ∨ ݔݕഥݖ̅ݐ ∨ ݔݕഥݖതݐ ∨ ݔഥݕݖ̅ݐ ∨ ݔഥݕݖതݐ ∨ ݔഥݕഥݖݐ) ∨ ߝ(ݔݕݖ̅ݐ ∨ ݔݕݖതݐ ∨ ݔݕഥݖݐ ∨ ݔഥݕݖݐ) với ߙ,ߚ, ߛ, ߜ, ߝ là các hằng số tùy ý thuộc {0,1}. 24. Xét ܽ, ܾ, ܿ ∈ {0,1} . Khi ấy ít nhất 2 trong số 3 số trên bằng nhau. Giả sử ܽ = ܾ. Ta có: ݂(ܾ,ܽ, ܿ)തതതതതതതതതതതത = ݂(ܽ, ܾ, ܿ)തതതതതതതതതതതത ⟹ ݂(ܽ, ܾ, ܿ) = 0 Tương tự trong các trường hợp khác ta cũng có ݂ = 0. Nếu ݊ > 2 cũng không tồn tại hàm Bool ݊ biến ≠ 0 thỏa điều kiện trên. Tuy nhiên nếu ݊ = 2 thì các hàm Bool như vậy có dạng ݂(ݔ,ݕ) = ߙതݔݕത ∨ ߙത̅ݔݕ với ߙ là hằng số tùy ý thuộc {0,1}. 25.Lập bảng chân trị. Khi ấy hàm chẵn được xác định hoàn toàn bởi ଵ ଶ 2௡ = 2௡ିଵ dòng đầu tiên. Do đó hàm chẵn là 2ଶ௡ିଵ. Với ݊ = 2, ta được 4 hàm chẵn: ݔݕ ∨ ̅ݔݕത,ݔݕത ∨ ̅ݔݕ, 0,1 26. Tương tự trong 25, số hàm lẻ ݊ biến là 2ଶ೙షభ. Với ݊ = 2, ta được 4 hàm lẻ: ݔ, ̅ݔ,ݕ,ݕത 27. a) Hai vế bằng nhau khi ݔଵ = 1 hay ݔଵ = 0 b) Xét ánh xạ ℱ௡ × ℱ௡ ⟶ ℱ௡ାଵ( ଵ݃ ,݃ଶ) ⟼ ݂ với ݂(ݔଵ, ݔଶ, , ݔ௡ାଵ) = ݔଵ ଵ݃(ݔଶ, , ݔ௡ାଵ) ∨ ̅ݔଵ݃ଶ(ݔଶ, , ݔ௡ାଵ). Khi ấy ta kiểm được dễ dàng ánh xạ trên là song ánh. Suy ra |ℱ௡ାଵ| = |ℱ௡| × |ℱ௡|.Bằng qui nạp trên ݊ ta suy ra |ℱ௡| = 2ଶ೙ c) Bằng qui nạp trên ݊ và tính phân bố 28. a) Viết hàm hằng 1 theo ݊ − ݌ biến còn lại như là tổng Bool của 2௡ି௣ từ tối tiểu và sử dụng tính phân bố, ta viết được ݂ như là tổng Bool của 2௡ି௣ từ tối tiểu theo ݊ biến. b) ݂ ≺ ݃ ⟺ ∃ℎ: ݂ = ݃ℎ. Do đó ݃ là tích của một số từ đơn xuất hiện trong ݂. Suy ra có 2௣ hàm Bool trội ݂. 29. a) ݂ = ̅ݔݕݖതݐ ∨ ݔഥݕݖ̅ݐ ∨ ݔݕഥݖത̅ݐ ∨ ݔݕഥݖݐ b) ݂ = ݔഥݕഥݖݐ ∨ ݔഥݕݖതݐ ∨ ݔഥݕݖݐ ∨ ݔݕഥݖ̅ݐ ∨ ݔݕഥݖݐ ∨ ݔݕݖത̅ݐ ∨ ݔݕݖതݐ ∨ ݔݕݖ̅ݐ ∨ ݔݕݖݐ 31. a) ݔݕݖݐ ∨ ݔݕݖݐ̅ ∨ ݔݕݖ̅ݐ ∨ ݔݕതݖݐ ∨ ̅ݔݕݖݐ b) ݔݕݖݐ ∨ ݔݕݖݐ̅ ∨ ݔݕݖ̅ݐ ∨ ݔݕݖ̅ݐ̅ ∨ ݔݕതݖݐ ∨ ݔݕതݖ̅ݐ ∨ ݔݕതݖ̅ݐ ∨ ̅ݔݕݖݐ ∨ ̅ݔݕݖ̅ݐ ∨ ̅ݔݕതݖݐ ∨ ̅ݔݕݖݐ̅ 32. ܾܽܿ݀ ∨ ܾܽܿ݀̅ ∨ ܾܽܿ̅݀ ∨ ܾܽܿ̅݀̅ ∨ ܽതܾܿ݀ ∨ ܽ തܾܿ݀̅ ∨ ܽതܾܿ̅݀ ∨ തܾܽܿ݀ 34. ݔ ݔത ݔതݕത ݔ ∨ ݕ ݕ ݕത 35. Cổng NOT có thể tổng hợp như sau: ݔ ̅ݔ GS. Nguyễn Hữu Anh 129 Do đó cổng AND và cổng OR được tổng hợp nhờ các công thức: ݔݕ = ̅ݔ ∨ ݕതതതതതതത và ݔ ∨ ݕ = ݔ ∨ ݕധധധധധധധ 36. ݂ = (ݔ ∨ ݕതതതതതതതݖݐ) ∨ ݔ ∨ ݕതതതതതതതݖതതݐ = ̅ݔݕതݖݐ̅ ∨ (ݔ ∨ ݕ ∨ ݖ̅)ݐ 37. ݂ = ݔݕݖݐ ∨ ݔݕݖ̅ݐ̅ ∨ ݔݕതݖݐ̅ ∨ ݔݕതݖ̅ݐ ∨ ̅ݔݕݖݐ̅ ∨ ̅ݔݕݖ̅ݐ ∨ ̅ݔݕതݖݐ ∨ ̅ݔݕതݖ̅ݐ̅. Ta viết ݔݕݖݐ = ̅ݔ ∨ ݕത ∨ ݖ̅ ∨ ݐ̅തതതതതതതതതതതതതതതത để sử dụng một cổng NOR vào tổng hợp từ tối tiểu này. Tương tự cho các từ tối tiểu khác. Mặt khác ta có thể viết ݂ = ݔݕݖݐതതതതതത ݔݕݖ̅ݐ̅തതതതതതതതതതതതതതതതതതതതതത để thiết kệ mạng chỉ dùng cổng NAND. 38. a) Các tế bào lớn: ݔݖݐ̅,ݕݖ̅ݐ, ̅ݔݕݖ, ̅ݔݕݐ,ݕݖ̅ݐ. Dùng phương pháp biểu đồ Karnaugh ta đuộc hai công thức: ݂ = ݔݖݐ̅ ∨ ݕݖ̅ݐ ∨ ̅ݔݕݖ, ݂ = ݔݖݐ̅ ∨ ݕݖ̅ݐ ∨ ݕݖݐ̅ ∨ ̅ݔݕݐ, trong đó chỉ cố công thức dầu Là tối tiểu. b) Các tế bào lớn: ݔݖ̅, ݔݕ,ݕݖݐ, ̅ݔݖݐ, ̅ݔݕതݐ,ݕതݖ̅ݐ. Có 3 công thức đa tối tiểu: ݂ = ݔݖ̅ ∨ ݔݕ ∨ ̅ݔݕതݐ ∨ ݕݖݐ, ݂ = ݔݖ̅ ∨ ݔݕ ∨ ̅ݔݕതݐ ∨ ̅ݔݖݐ, ݂ = ݔݖ̅ ∨ ݔݕ ∨ ̅ݔݖݐ ∨ ݕതݖ̅ݐ c) Dạng nối rời chính tắc cũng là công thức đa thức tối tiểu duy nhất. d) Các tế bào lớn: ݕത,ݔݖ̅, ̅ݔݖ, ݐ̅. Công thức công thức đa thức tối tiểu duy nhất: ݂ = ݕത ∨ ݐ̅ ∨ ݔݖ̅ ∨ ̅ݔݖ e) Các tế bào lớn: ݕതݐ̅,ݖݐ̅,ݕݖ,ݕݐ. Có 2 công thức đa thức tối tiểu: ݂ = ݕതݐ̅ ∨ ݕݖ ∨ ݕݐ ݂ = ݕതݐ̅ ∨ ݕݐ ∨ ݖ̅ݐ f) Các tế bào lớn: ݔݕതݐ̅, ݔݖ̅ݐ̅, ݔݕݖ̅, ݔݕݐ,ݕݖݐ, ̅ݔݕݖ Có 3 công thức đa thức tối tiểu: ݂ = ݔݕതݐ̅ ∨ ̅ݔݕݖ ∨ ݔݖ̅ݐ̅ ∨ ݔݕݐ ݂ = ݔݕതݐ̅ ∨ ̅ݔݕݖ ∨ ݔݕݖ̅ ∨ ݔݕݐ ݂ = ݔݕതݐ̅ ∨ ̅ݔݕݖ ∨ ݔݕݖ̅ ∨ ݕݖݐ 39. a) ݂ = ݔݖ̅ ∨ ̅ݔݕݖ ∨ ݕݖ̅ݐ và ݂ = ݔݖ̅ ∨ ̅ݔݕݖ ∨ ̅ݔݕݐ b) ݂ = ̅ݔݕത ∨ ݔݕݐ ∨ ݕݖ̅ݐ̅ ∨ ݕݖ̅̅ݐ ݂ = ̅ݔݕത ∨ ݔݕݐ ∨ ݔݖ̅ݐ ∨ ݕݖ̅ݐ̅ c) ݂ = ݖݐ ∨ ݖ̅ݐ̅ d) ݂ = ݔ ∨ ݕݖ e) Dùng phương pháp biểu đồ Karnaugh được 6 công thức trog đó chỉ có một công thức tối tiểu: ݂ = ̅ݔݕݖ̅ ∨ ݔݕݐ̅ ∨ ݖ̅ݐ̅ ∨ ̅ݔݕതݖ ∨ ݔݕതݐ f) ݂ = ݔݕ ∨ ݐݖ g) ݂ = ݔݖ̅ ∨ ݕݖ̅ ∨ ݕݐ h) ݂ = ݕݐ ∨ ̅ݔݖ ̅ i) ݂ = ݔݖݐ̅ ∨ ݔݕݖ̅ ∨ ̅ݔݕݖ ∨ ̅ݔݖ̅ݐ̅ 40. a) ݂ = ݔݕݖ̅ ∨ ݔݕതݖ ∨ ̅ݔݕݖ. Đây cũng là công thức đa thức tối tiểu duy nhất. mạng tối ưu sử dụng 6 cổng AND và 2 cổng OR. b) ݂ = ݔݕ ∨ ݕݖ ∨ ݔݖ. Đây cũng là công thức đa thức tối tiểu duy nhất. Mạng tối ưu sử dụng 3 cổng AND và 2 cổng OR. c) ݂ = ݔݕݖݐ̅ ∨ ݔݕݖ̅ݐ ∨ ݔݕതݖݐ ∨ ̅ݔݕݖݐ ∨ ݔݕതݖ̅ݐ̅ ∨ ̅ݔݕݖ̅ݐ̅ ∨ ̅ݔݕതݖݐ̅ ∨ ̅ݔݕതݖ̅ݐ. Đây cũng là công thức đa thức tối tiểu duy nhất. Mạng tối ưu sử dụng 24 cổng AND và 7 cổng OR.