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] Kiểm tra hằng đúng (tautology)

    Một biểu thức logic là hằng đúng (tautology) nếu nó nhận giá trị 111 với mọi tổ hợp giá trị của các biến.

    Cho một biểu thức, hãy in YES nếu nó là hằng đúng, ngược lại NO.

    Quy ước: biến là một chữ cái thường (a..z), hằng 0/1. Toán tử: ! (phủ định, NOT), & (và, AND), | (hoặc, OR), -> (kéo theo, IMP). Độ ưu tiên từ cao đến thấp: !, &, |, ->. Phép -> kết hợp phải. Có thể dùng dấu ngoặc ( ). Phép kéo theo p→qp \to qp→q chỉ sai khi p=1,q=0p=1, q=0p=1,q=0.

    Ví dụ: a|!a (luật bài trung) luôn đúng → YES.

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

      Một dòng: biểu thức logic.

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

      Số biến phân biệt ≤16\le 16≤16, độ dài biểu thức ≤200\le 200≤200.

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

      Một dòng: YES nếu hằng đúng, ngược lại NO.

    Ví dụ:

    Đầu vào:

    a|!a

    Đầu ra:

    YES

    Giải thích:

    Với $a=0$ ra 1, với $a=1$ ra 1 → luôn đúng → YES.

    Đang tải editor...