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] Suy diễn modus ponens nhiều bước

    Ta có một tập mệnh đề cơ sở đã biết là đúng, và một tập luật suy diễn dạng p1∧p2∧⋯∧pr⇒qp_1 \wedge p_2 \wedge \dots \wedge p_r \Rightarrow qp1​∧p2​∧⋯∧pr​⇒q (nếu mọi tiền đề pip_ipi​ đúng thì kết luận qqq đúng). Áp dụng lặp lại modus ponens cho tới khi không suy ra được mệnh đề mới nào. Hỏi mệnh đề mục tiêu ggg có suy ra được hay không.

    Các mệnh đề được đánh số nguyên từ 111 tới nnn.

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

      Dòng đầu chứa nnn, fff (số mệnh đề cơ sở đúng), RRR (số luật), ggg (mục tiêu). Dòng thứ hai chứa fff số là các mệnh đề cơ sở. Tiếp theo RRR dòng, mỗi dòng: số rrr rồi rrr tiền đề rồi 111 kết luận.

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

      1≤n≤1051 \le n \le 10^51≤n≤105, 0≤f≤n0 \le f \le n0≤f≤n, 0≤R≤1050 \le R \le 10^50≤R≤105, tổng số tiền đề ≤2⋅105\le 2\cdot 10^5≤2⋅105.

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

      In YES nếu suy ra được mệnh đề mục tiêu ggg, ngược lại in NO.

    Ví dụ:

    Đầu vào:

    4 1 2 4
1
2 1 2 3
1 3 4

    Đầu ra:

    NO

    Giải thích:

    Biet 1 dung nhung luat can ca 1 va 2; chua co 2 nen khong suy ra 3, do do khong toi 4 -> NO.

    Đang tải editor...