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ương đương logic hai biểu thức

    Hai biểu thức logic tương đương (≡\equiv≡) nếu chúng có cùng giá trị chân lý với mọi tổ hợp giá trị của các biến.

    Cho hai biểu thức, hãy in YES nếu chúng tương đương, ngược lại NO. Tập biến là hợp các chữ cái thường xuất hiện trong cả hai biểu thức.

    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->b tương đương !a|b (luật kéo theo) → YES.

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

      Dòng 1: biểu thức thứ nhất. Dòng 2: biểu thức thứ hai.

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

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

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

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

    Ví dụ:

    Đầu vào:

    a->b
!a|b

    Đầu ra:

    YES

    Giải thích:

    Luật kéo theo: $a\to b \equiv \lnot a \lor b$, đúng với mọi $a,b$ → YES.

    Đang tải editor...