Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Tối thiểu số literal của hàm Boole

    Cho hàm Boole f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} qua bảng chân trị (liệt kê theo thứ tự minterm 0,1,…,2n−10,1,\dots,2^n-10,1,…,2n−1). Hãy biểu diễn fff ở dạng tổng các tích (SOP) và tìm tổng số literal nhỏ nhất có thể (mỗi implicant cố định kkk biến đóng góp kkk literal). Dùng tập prime implicant rồi phủ tối ưu. Quy ước: hàm hằng 0 hoặc hằng 1 có 0 literal.

    • Định dạng đầu vào:

      Dòng đầu: nnn. Dòng sau: 2n2^n2n giá trị 0/1 cách nhau bởi dấu cách (bảng chân trị).

    • Ràng buộc đầu vào:

      1≤n≤41 \le n \le 41≤n≤4.

    • Định dạng đầu ra:

      Một dòng: tổng số literal nhỏ nhất.

    Ví dụ:

    Đầu vào:

    2 0 1 1 1

    Đầu ra:

    0

    Giải thích:

    $f=x_1\lor x_2$ (đúng trừ minterm 0); dạng tối thiểu $x_1+x_2$ có 2 literal.

    Đang tải editor...