Thư mục

Hỗ trợ kỹ thuật

  • (Hotline:
    - (04) 66 745 632
    - 0982 124 899
    Email: hotro@violet.vn
    )

Thống kê

  • lượt truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Chào mừng quý vị đến với Thư viện Bài giảng điện tử.

    Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tư liệu của Thư viện về máy tính của mình.
    Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay ô bên phải.

    Toán Rời Rạc(Chương IV: Đại số Bool)

    (Tài liệu chưa được thẩm định)
    Nguồn: Nguyễn Tất Thành
    Người gửi: Nguyễn Huy Long
    Ngày gửi: 20h:10' 01-09-2013
    Dung lượng: 2.3 MB
    Số lượt tải: 56
    Số lượt thích: 0 người
    ĐẠI SỐ
    BOOLE
    CHƯƠNG
    4
    Nội dung
    1. Đại số Boole.
    2. Hàm Boole.
    3. Các cổng Logic.
    4. Mạch tối tiểu.
    5. Phương pháp biểu đồ Karnaugh.
    1. Đại số Boole
    Định nghĩa 1:
    Một đại số Bool là tập hợp A cùng với 2 phép toán  và  thõa mãn các tính chất sau:
    Tính kết hợp
    Tính giao hoán
    Tính phân bố
    Phần tử trung hòa
    Phần tử bù

    1. Đại số Boole
    Các tính chất của đại số Bool:
    i. Tính kết hợp:
    x, y, z  A, ta có:
    x  (y  z) = (x  y)  z và
    x  (y  z) = (x  y)  z

    ii. Tính giao hoán:
    x, y, z  A, ta có:
    x  y = y  x và
    x  y = y  x
    1. Đại số Boole
    iii. Tính phân bố:
    x, y, z  A, ta có:
    x  (y  z) = (x  y)  (x  z) và
    x  (y  z) = (x  y)  (x  z)

    iv. Phần tử trung hòa:
    Tồn tại 2 phần tử trung hòa 0 và 1 đối với 2 phép toán  và  sao cho x  A
    ta có: x  0 = x và
    x  1 = x
    1. Đại số Boole
    v. Phần tử bù:
    x  A, x  A sao cho:
    x  x = 1 và
    x  x = 0

    1. Đại số Boole
    Ví dụ: Xét tập hợp A = {0, 1} với 2 phép toán  và  như sau:
    x  y = x.y (x.y là x nhân với y)
    x  y = x + y – x.y

    Ta kiểm tra 5 tính chất của đại số Bool:

    i. Tính giao hoán:
    x  y = x.y = y.x = y  x  dpcm
    1. Đại số Boole
    ii. Tính kết hợp:
    Trường hợp 1:
    x  (yz) = x.(y.z) = (x.y).z = (xy)  z
    Trường hợp 2: Dùng bảng chân trị.

    1. Đại số Boole
    iii. Tính phân bố: Dùng bảng chân trị.
    Xét trường hợp 1 (SV làm trường hợp 2)

    1. Đại số Boole
    iv. Phần tử trung hòa:
    x  0 = x + 0 – x.0 = x và
    x  1 = x.1 = x
     0 và 1 là 2 phần tử trung hòa của A

    v. Phần tử bù:
    0  0 = 0  1 = 0 + 1 – 0.1 = 1
    1  1 = 1  0 = 1.0 = 0

    Kết luận:
    Tập hợp A = {0, 1} với 2 phép toán được định nghĩa trên là một đại số Bool

    2. Hàm Boole
    Định nghĩa:
    Một hàm Bool n biến là một ánh xạ
    f: Bn  B
    Trong đó B = {0, 1}
    Như vậy, hàm Bool n biến là một hàm số có dạng : f = f(x1, x2, ..., xn);
    Trong đó mỗi biến x1, x2, ..., xn chỉ nhận hai giá trị 0, 1 và f nhận giá trị trong
    B = {0, 1}.
    2. Hàm Boole
    Vì mỗi biến xi chỉ nhận 2 giá trị 0, 1 nên chỉ có 2n trường hợp của bộ biến
    (x1, x2, ..., xn)
    Do đó, để mô tả hàm f, ta có thể lập bảng gồm 2n hàng ghi tất cả các giá trị của f tùy theo 2n trường hợp của biến.
    Ta gọi đây là bảng chân trị của f
    Tập hợp các hàm Bool n biến được ký hiệu bởi Fn

    2. Hàm Boole
    Ví dụ: Xét kết qủa f trong việc thông qua một quyết định dựa vào 3 phiếu bầu x, y, z. Mỗi phiếu chỉ lấy một trong hai giá trị: 1 (tán thành) hoặc 0 (bác bỏ).
    Kết qủa:
    f là 1 (thông qua quyết định) nếu được đa số phiếu tán thành,
    f là 0 (không thông qua quyết định) nếu đa số phiếu bác bỏ.
    Khi đó f là hàm Bool theo 3 biến x, y, z có bảng chân trị như sau:
    2. Hàm Boole
    Các phép toán trên hàm Bool
    Phép cộng: Ký hiệu: 
    Cho 2 hàm Bool f, g  Fn, ta định nghĩa tổng Bool của f và g như sau:
    f  g = f + g – fg

    Phát biểu khác: x = (x1, x2, ..., xn)  Bn
    (f  g)(x) = f(x) + g(x) – f(x)g(x)

    Hiển nhiên: (f  g)  Fn
    Các phép toán trên hàm Bool
    Phép nhân: Ký hiệu: 
    Cho 2 hàm Bool f, g  Fn, ta định nghĩa tích Bool của f và g như sau:
    f  g = fg
    Phát biểu khác: x = (x1, x2, ..., xn)  Bn
    (f  g)(x) = f(x)g(x)
    Ta thường viết fg thay cho f  g
    Hiển nhiên: (f  g)  Fn
    Các phép toán trên hàm Bool
    Phép lấy hàm bù:
    Cho f  Fn, ta định nghĩa hàm bù của f như sau:



    Dạng nối rời chính tắc của hàm Bool
    Cho các hàm Bool: x1, x2, ..., xn  Fn
    Ta có các định nghĩa như sau:
    Từ đơn: là mỗi hàm bool xi hay xi
    Đơn thức: là tích khác không của một số hữu hạn từ đơn
    Từ tối tiểu: là tích khác không của đúng n từ đơn
    Dạng nối rời chính tắc của hàm Bool
    Công thức đa thức: là công thức biểu diễn hàm Bool thành tổng của các đơn thức
    Dạng nối rời chính tắc: là công thức biểu diễn hàm Bool thành tổng của các từ tối tiểu
    Dạng nối rời chính tắc của hàm Bool
    Ví dụ:

    Là công thức đa thức
    3. Các cổng Logic
    Mạng logic:
    Xem hình ảnh tổng quát của một mạng logic sau:



    Trong đó:



    Ta nói mạng logic trên tổng hợp hay biểu diễn hàm Bool f
    3. Các cổng Logic
    Cổng NOT:
    Ký hiệu cổng:


    Bảng chân trị:



    Biểu diễn hàm:
    Nếu đưa mức HIGH vào ngõ vào của cổng, ngõ ra sẽ là mức LOW và ngược lại
    3. Các cổng Logic
    Cổng AND:
    Ký hiệu cổng:

    Bảng chân trị:

    Biểu diễn hàm:
    F(x, y) = xy

    Cổng AND có ít nhất 2 ngõ vào.
    Ngõ ra là 1 khi tất cả các ngõ vào là 1. Ngược lại là 0
    3. Các cổng Logic
    Cổng OR:
    Ký hiệu cổng:

    Bảng chân trị:

    Biểu diễn hàm:
    F(x, y) = x  y

    Cổng OR có ít nhất là 2 ngõ vào.
    Ngõ ra là 1, nếu có một ngõ vào là 1, Ngược lại là 0
    3. Các cổng Logic
    Cổng NAND:
    Ký hiệu cổng:
    Cổng NAND là
    kết hợp 2 cổng
    AND và NOT
    Bảng chân trị:

    Là cổng bù của AND Có ngõ ra là ngược lại với cổng AND
    3. Các cổng Logic
    Cổng NOR:
    Ký hiệu cổng:

    Cổng NOR là
    kết hợp 2 cổng
    OR và NOT

    Bảng chân trị:


    Là cổng bù của OR. Có ngõ ra ngược với cổng OR
    4. Mạch tối tiểu
    Mạch tối tiểu là mạng các cổng logic biểu diễn cho một đa thức tối tiểu.
    Ví dụ:
    Giả sử ta có các đa thức tối tiểu sau:



    Hãy vẽ mạch tối tiểu cho 2 đa thức tối tiểu trên.


    4. Mạch tối tiểu
    Ví dụ một mạch logic của 1 hàm f
    5. Phương pháp biểu đồ Karnaugh
    Công thức đa thức tối tiểu:
    Cho 2 công thức đa thức của 1 hàm bool:
    f = f1 v f2 v ... v fk và
    g = g1 v g2 v ... v gh

    Ta nói rằng công thức f đơn giản hơn công thức g nếu số từ đơn fi không nhiều hơn số từ đơn gj.
    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
    5. Phương pháp biểu đồ Karnaugh
    Công thức đa thức tối tiểu (tt):
    Công thức đa thức tối tiểu của một hàm Bool f là một công thức đa thức của f trong đó không có công thức đa thức nào của f thực sự đơn giản hơn nó.
    Một hàm Bool f có thể có nhiều công thức đa thức tối tiểu
    5. Phương pháp biểu đồ Karnaugh
    Xét hàm Bool f 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 23 = 8 hàng.
    5. Phương pháp biểu đồ Karnaugh
    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:
    Lưu ý: thứ tự xyz
    5. Phương pháp biểu đồ Karnaugh
    Qui ước trong bảng chữ nhật:
    Khi một ô nằm trong dãy được đánh dấu bởi x thì tại đó x = 1, bởi x thì tại đó
    x = 0,
    Tương tự cho y và 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).
    5. Phương pháp biểu đồ Karnaugh
    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:
    Lưu ý: thứ tự xyzt

    5. Phương pháp biểu đồ Karnaugh









    Qui ước trong bảng chữ nhật: Tương tự qui ước với hàm Bool 3 biến xyz

    5. Phương pháp biểu đồ Karnaugh
    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.

    5. Phương pháp biểu đồ Karnaugh
    Qui định tên ô: có 2 cách:








    Yêu cầu: Nên sử dụng cách 1.
    Cách 1:
    Cách 2:
    5. Phương pháp biểu đồ Karnaugh
    Định lý:
    Cho f, g là các hàm Bool theo n biến x1, x2, ..., xn. Khi đó:
    kar(fg) = kar(f)  kar(g)
    kar(f v g) = kar(f)  kar(g)
    kar(f) gồm đúng một ô khi và chỉ khi f là một từ tối tiểu
    5. Phương pháp biểu đồ Karnaugh
    Tế bào:
    Tế bào là hình chữ nhật gồm 2k ô; Với
    k = 1..n-1, n là số biến của hàm Bool f

    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
    Cách xác định tế bào của 1 đơn thức:
    Lần lượt chiếu đơn thức lên các cạnh của nó. Nếu toàn bộ hình chiếu nằm trọn trong một tế bào thì thì đó chính là tế bào cần tìm
    5. Phương pháp biểu đồ Karnaugh
    Ví dụ 1.
    Xét các hàm Bool theo 4 biến x, y, z, t.
    Biểu đồ karnaugh của đơn thức là:
    5. Phương pháp biểu đồ Karnaugh
    Ví dụ 2.
    Xét các hàm Bool theo 4 biến x, y, z, t.
    Biểu đồ karnaugh của đơn thức là:

    5. Phương pháp biểu đồ Karnaugh
    Ví dụ 3.
    Xét các hàm Bool theo 4 biến x, y, z, t.
    Biểu đồ karnaugh của đơn thức là:

    5. Phương pháp biểu đồ Karnaugh
    Ví dụ 4.
    Xét các hàm Bool theo 4 biến x, y, z, t.
    Biểu đồ karnaugh của đơn thức là:

    5. Phương pháp biểu đồ Karnaugh
    Ví dụ 5.
    Xét các hàm Bool theo 4 biến x, y, z, t
    Biểu đồ karnaugh sau đây là của đơn thức nào?



    5. Phương pháp biểu đồ Karnaugh
    Ví dụ 6.
    Xét các hàm Bool theo 4 biến x, y, z, t
    Các biểu đồ karnaugh sau đây là của đơn thức nào?

    x
    x z
    y z t
    5. Phương pháp biểu đồ Karnaugh
    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ả 2 tính chất sau:
    T là một tế bào và T  kar(f)
    Không tồn tại tế bào T’ nào thỏa:
    T’  T và
    T  T’  kar(f)

    Thuật toán tìm đa thức tối tiểu
    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 T 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.
    Thuật toán tìm đa thức tối tiểu
    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ì 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).
    + 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.
    Thuật toán tìm đa thức tối tiểu
    Bước 4 (tt):
    - 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ồm các tế bào lớn của kar(f)

    Thuật toán tìm đa thức tối tiểu
    Bước 5: Xác định các công thức đa thức tối tiểu của 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ác cô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.

    Thuật toán tìm đa thức tối tiểu
    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:
    f(x,y,z,t) =
    Cách làm:

    Thuật toán tìm đa thức tối tiểu
    Thuật toán tìm đa thức tối tiểu
    Bước 1: Vẽ kar(f)



    Bước 2: Kar(f) có các
    tế bào lớn như sau:


    x
    yz
    Thuật toán tìm đa thức tối tiểu
    Bước 3: Xác định các tế bào lớn nhất thiết phải chọn
    Ta có thể đánh số ô để dể theo dõi:

    Thuật toán tìm đa thức tối tiểu
    Ô 1,4,7,8,9,10 nằm trong một tế bào lớn duy nhất là x  Ta chọn x.
    Ô 3,6 nằm trong một tế bào lớn duy nhất là yz  Ta chọn yz
    x
    yz
    Thuật toán tìm đa thức tối tiểu
    Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn
    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 v yz

    x
    yz
    x v yz
    Thuật toán tìm đa thức tối tiểu
    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 duy nhất một công thức đa thức tối tiểu của f là


    5. Phương pháp biểu đồ Karnaugh
    Ví dụ 7: Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ karnaugh như sau:





    5. Phương pháp biểu đồ Karnaugh
    Bước 1: Biểu đồ Karnaugh của f có 2 tế bào lớn:





    Bước 2:
    Ô (3,1) nằm duy nhất trong
    Ô (1,1) nằm duy nhất trong
    Hai tế bào lớn này đã phủ kín kar(f) nên ta qua thẳng bước 4.
    5. Phương pháp biểu đồ Karnaugh
    Bước 4: Ta chỉ có duy nhất 1 phép phủ ứng với công thức đa thức tối tiểu duy nhất của f :

    f =



    5. Phương pháp biểu đồ Karnaugh
    Ví dụ 8: Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ karnaugh như sau:

    5. Phương pháp biểu đồ Karnaugh
    Bước 1: Biểu đồ kar(f) có 4 tế bào lớn:


    5. Phương pháp biểu đồ Karnaugh
    Bước 2:
    Ô (2,4) nằm trong tế bào lớn duy nhất
    Ô (4,2) nằm trong tế bào lớn duy nhất
    Chọn (gạch chéo hoặc tô) 2 tế bào lớn này, ta được sơ đồ sau:




    Còn lại ô (3,3) chưa được phủ, nằm trong 2 tế bào lớn nên ta qua bước 3

    Ô (3,3)
    5. Phương pháp biểu đồ Karnaugh
    Bước 3: Ô (3,3) nằm trong 2 tế bào lớn là
    và .
    Chọn tùy ý một trong 2 tế bào trên ta đều phủ kín kar(f).

    Bước 4: Ta được phép phủ tối tiểu tương ứng với 2 công thức đa thức:
    f =
    f =
    Bước 5: Cả 2 công thức này đều đơn giản như nhau nên ta được 2 công thức đa thức tối tiểu.


    5. Phương pháp biểu đồ Karnaugh
    Ví dụ 9. Tìm các tết bào lớn của hàm Bool f có biểu đồ karnaugh như sau:




    5. Phương pháp biểu đồ Karnaugh
    Kar(f) có 6 tế bào lớn:



    5. Phương pháp biểu đồ Karnaugh
    5. Phương pháp biểu đồ Karnaugh
    5. Phương pháp biểu đồ Karnaugh
    Bài tập 1: Tìm CTĐTTT của hàm f với biểu đồ kar(f) sau:




    Bài tập 2: Tìm CTĐTTT của hàm f với biểu đồ kar(f) sau:


    END
    Add your company slogan

     
    Gửi ý kiến
    print

    Nhấn Esc để đóng