- Trường Đại học Công nghiệp Thành phố Hồ Chí Minh
- Cơ sở dữ liệu
- Question
Cho hàm Bool 4 biến x, y, z, t với: f-1 [0] = {1010, 1110, 0110, 0010}
- Tìm biểu đồ Karnaugh của f
- Tìm tất cả các tế bào lớn của biểu đồ Karnaugh của f c. Tìm công thức đa thức tối tiểu của f
All replies
- Để tìm biểu đồ Karnaugh của hàm Bool f, ta cần xác định giá trị của f cho tất cả các tổ hợp giá trị của biến x, y, z, t. Dựa vào thông tin đã cho, ta có: f[0,0,0,0] =
Related Answered Questions
- Cơ sở dữ liệu [123]4 months ago tại sao MDM lại quan trọng trong các công ty có nhiều nguồn dữ liệu
- Cơ sở dữ liệu [123]5 months ago
- Cơ sở dữ liệu [123]5 months ago Bốn yếu tố của một DBMS là gì
- Cơ sở dữ liệu [123]5 months ago Những tác động gì đối với mô hình smac trong kinh doanh
- Cơ sở dữ liệu [123]5 months ago mô tả các mối quan hệ trong mô hình smac
- Cơ sở dữ liệu [123]7 months ago Cho tập thứ tự [{3, 4, 12, 24, 48, 72}, |]. a. Vẽ biểu đồ Hasse cho tập thứ tự trên b. Tìm phần tử tối đại, tối tiểu, lớn nhất và nhỏ nhất [nếu có] Công thức đa thức tối tiểu Đơn giản hơn Cho hai công thức đa thức của một hàm Bool : f = m1 m2 …. mk [F] f =M1 M2 … Ml [G] Ta nói rằng công thức F đơn giản hơn công thức G nếu tồn tại đơn ánh h: {1,2,..,k} → { 1,2,…, l} sao cho với mọi i {1,2,..,k} thì số từ đơn của mi không nhiều hơn số từ đơn của Mh[i]
- Công thức đa thức tối tiểu Đơn giản như nhau Nếu F đơn giản hơn G và G đơn giản hơn F thì ta nói F và G đơn giản như nhau ** Công thức đa thức tối tiểu: Công thức F của hàm Bool f được gọi là tối tiểu nếu với bất kỳ công thức G của f mà đơn giản hơn F thì F và G đơn giản như nhau
- Phương pháp biểu đồ Karnaugh. Xét f là một hàm Bool theo n biến x1,x2,…,xn với n = 3 hoặc 4. Trường hợp n = 3: f là hàm Bool theo 3 biến x, y, z. Khi đó bảng chân trị của f gồm 8 hàng. Thay cho bảng chân trị của f ta vẽ một bảng chữ nhật gồm 8 ô, tương ứng với 8 hàng của bảng chân trị, được đánh dấu như sau:
- Với qui ước: Khi một ô nằm trong dãy được đánh dấu bởi x thì tại đó x =1, bởi thì tại đó x =0, tương tự cho y, z. Các ô tại đó f bằng 1 sẽ được đánh dấu [tô đậm hoặc gạch chéo]. Tập các ô được đánh dấu được gọi là biểu đồ Karnaugh của f, ký hiệu là kar[f].
- Trường hợp n = 4: f là hàm Bool theo 4 biến x, y, z, t. Khi đó bảng chân trị của f gồm 16 hàng. Thay cho bảng chân trị của f ta vẽ một bảng chữ nhật gồm 16 ô, tương ứng với 16 hàng của bảng chân trị, được đánh dấu như sau:
- Với qui ước: Khi một ô nằm trong dãy được đánh dấu bởi x thì tại đó x =1, bởi thì tại đó x =0, tương tự cho y, z, t. Các ô tại đó f bằng 1 sẽ được đánh dấu [tô đậm hoặc gạch chéo]. Tập các ô được đánh dấu được gọi là biểu đồ karnaugh của f, ký hiệu là kar[f]. Trong cả hai trường hợp, hai ô được gọi là kề nhau [theo nghĩa rộng], nếu chúng là hai ô liền nhau hoặc chúng là ô đầu, ô cuối của cùng một hàng [cột] nào đó. Nhận xét rằng, do cách đánh dấu như trên, hai ô kề nhau chỉ lệch nhau ở một biến duy nhất.
- Định lý Cho f, g là các hàm Bool theo n biến x1,x2,…,xn. Khi đó: a] kar[fg] = kar[f]kar[g]. b] kar[fg] = kar[f]kar[g]. c] kar[f] gồm đúng một ô khi và chỉ khi f là một từ tối tiểu
- Tế bào Tế bào là hình chữ nhật [theo nghĩa rộng] gồm 2n-k ô Nếu T là một tế bào thì T là biểu đồ karnaugh của một đơn thức duy nhất m, cách xác định m như sau: lần lượt chiếu T lên các cạnh, nếu toàn bộ hình chiếu nằm trọn trong một từ đơn nào thì từ đơn đó mới xuất hiện trong m.
- Ví dụ 1. Xét các hàm Bool theo 4 biến x, y, z, t.
- Ví dụ 2. Xét các hàm Bool theo 4 biến x, y, z, t.
- Ví dụ 3. Xét các hàm Bool theo 4 biến x, y, z, t.
- Ví dụ 4. Xét các hàm Bool theo 4 biến x, y, z, t.
- Ví dụ 5. Xét các hàm Bool theo 4 biến x, y, z, t. Tế bào sau: Là biểu đồ Karnaugh của đơn thức nào?
- Tế bào lớn. Cho hàm Bool f. Ta nói T là một tế bào lớn của kar[f] nếu T thoả hai tính chất sau: a] T là một tế bào và T kar[f]. b] Không tồn tại tế bào T’ nào thỏa T’ T và T T’ kar[f].
- Ví dụ. Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ karnaugh như sau:
- Kar[f] có 6 tế bào lớn như sau:
- Thuật toán. Bước 1: Vẽ biểu đồ karnaugh của f. Bước 2: Xác định tất cả các tế bào lớn của kar[f]. Bước 3: Xác định các tế bào lớn m nhất thiết phải chọn. Ta nhất thiết phải chọn tế bào lớn T khi tồn tại một ô của kar[f] mà ô này chỉ nằm trong tế bào lớn T và không nằm trong bất kỳ tế bào lớn nào khác.
- Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn Nếu các tế bào lớn chọn được ở bước 3 đã phủ được kar[f] thì tacó duy nhất một phủ tối tiểu gồm các tế bào lớn của kar[f]. Nếu các tế bào lớn chọn được ở bước 3 chưa phủ được kar[f] thì: Xét một ô chưa bị phủ, sẽ có ít nhất hai tế bào lớn chứa ô này,ta chọn một trong các tế bào lớn này. Cứ tiếp tục như thế ta sẽtìm được tất cả các phủ gồm các tế bào lớn của kar[f]. Loại bỏcác phủ không tối tiểu, ta tìm được tất cả các phủ tối tiểu gồmcác tế bào lớn của kar[f].
- Từ các phủ tối tiểu gồm các tế bào lớn của kar[f] tìm được ởbước 4 ta xác định được các công thức đa thức tương ứng của f • Loại bỏ cáccông thức đa thức mà có một công thức đa thức nào đó thực sựđơn giản hơn chúng. • Các công thức đa thức còn lại chính là các • công thức đa thức tối tiểu của f. • Bước 5: Xác định các công thức đa thức tối tiểu của f.
- Ví dụ 1 • Tìm tất cả các công thức đa thức tối tiểu của hàm Bool:
- Bước 1:Vẽ kar[f]:
- Bước 2: Kar[f] có các tế bào lớn như sau: x yz
- Bước 3: Xác định các tế bào lớn nhất thiết phải chọn: - Ô 1 nằm trong một tế bào lớn duy nhất x. Ta chọn x. - Ô 3 nằm trong một tế bào lớn duy nhất yz. Ta chọn yz. x yz
- Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn x Ta được duy nhất một phủ tối tiểu gồm các tế bào lớn của kar[f]: xν yz. yz
- Bước 5: Xác định các công thức đa thức tối tiểu của f. Ứng với phủ tối tiểu gồm các tế bào lớn tìm được ở bước 4 ta tìm được duynhất một công thức đa thức tối tiểu của f: x yz
- B1: Vẽ Kar[f]
- B2: Xác định tế bào lớn
- B3: Xác định các tế bào lớn nhất thiết phải chọn
- Bước 3: Xác định các tế bào lớn nhất thiết phải chọn • Ô 6 nằm trong một tế bào lớn duy nhất . Ta chọn • Ô 1 nằm trong một tế bào lớn duy nhất . Ta chọn • Ô 4 nằm trong một tế bào lớn duy nhất xzt . Ta chọn xzt
- B4: Xác định các phủ tối tiểu gồm các tế bào lớn
- Còn lại ô 5 chưa bị phủ Ô 5 nằm trong 2 tế bào lớn: 2 cách chọn B4: Xác định các phủ tối tiểu gồm các tế bào lớn
- Còn lại ô 5 chưa bị phủ Ô 5 nằm trong 2 tế bào lớn: 2 cách chọn B4: Xác định các phủ tối tiểu gồm các tế bào lớn
- Còn lại ô 5 chưa bị phủ Ô 5 nằm trong 2 tế bào lớn: 2 cách chọn B4: Xác định các phủ tối tiểu gồm các tế bào lớn
- Bước 5: Xác định các công thức đa thức tối tiểu của f
- Haõy xaùc ñònh caùc coâng thöùc ña thöùc toái tieåu cuûa haøm Bool:
- Bieåu ñoà Karnaugh:
- Caùc teá baøo lôùn: • Caùc teá baøo lôùn baét buoäc phaûi choïn laø • Coøn laïi oâ [1,4] coù theå naèm trong 2 teá baøo lôùn
Do ñoù coù 2 coâng thöùc ña thöùc töông öùng vôùi phuû toái tieåu: • Trong ñoù chæ coù coâng thöùc thöù hai laø toái tieåu