Bài tập — Propositional Logic

Quy ước ký hiệu

Toán tử: ¬ (phủ định), ∧ (và), ∨ (hoặc), ⇒ (kéo theo), ⇔ (tương đương).
Thứ tự ưu tiên (mạnh → yếu): ¬ > ∧ > ∨ > ⇒ > ⇔. Khi cần, dùng ngoặc.
T = đúng (true, 1), F = sai (false, 0).
Model m = một cách gán T/F cho mọi ký hiệu. Với n ký hiệu có 2ⁿ model.
M(α) = tập model làm α đúng. KB ⊨ α: α đúng trong mọi model mà KB đúng (⇔ M(KB) ⊆ M(α)).

Phần 1 — Dịch câu sang logic mệnh đề

📖 Slide 9–11

Đặt ký hiệu mệnh đề thích hợp rồi viết công thức cho mỗi câu.

1.

"Nếu trời mưa thì đường ướt."
Ký hiệu: Công thức:
2.

"An đỗ môn Toán và môn Lý, nhưng trượt môn Hoá."
Ký hiệu: Công thức:
3.

"Tôi đi học nếu và chỉ nếu tôi khoẻ."
Ký hiệu: Công thức:
4.

"Muốn tốt nghiệp thì phải qua hết các môn." (điều kiện cần)
Ký hiệu: Công thức:
5.

"Tối nay tôi đi xem phim hoặc ở nhà đọc sách, nhưng không làm cả hai." (hoặc loại trừ)
Ký hiệu: Công thức:
6.

"Nếu trời không mưa và tôi rảnh thì tôi sẽ đi chơi."
Ký hiệu: Công thức:
7.

(Suy luận) Với câu 1, đặt thêm "biết rằng đường không ướt". Hãy viết tất cả tiền đề dưới dạng công thức và cho biết kết luận logic rút ra được là gì; gọi tên luật.
Tiền đề: Kết luận: Tên luật:

Phần 2 — Bảng chân trị & tập model M(α)

📖 Slide 13, 17, 18

Lập bảng chân trị đầy đủ và liệt kê M(α).

α = ¬(P ∧ Q)

Có 2 ký hiệu → 2² = 4 model. Lập bảng chân trị và liệt kê M(α).

P	Q	P ∧ Q	α = ¬(P ∧ Q)
F	F
F	T
T	F
T	T

M(α) = { } — gồm ___ model.

β = (P ⇒ Q) ∧ (Q ⇒ R)

Có 3 ký hiệu → 2³ = 8 model. Lập bảng chân trị, liệt kê M(β) và cho biết |M(β)| trên tổng số model.

P	Q	R
F	F	F
F	F	T
F	T	F
F	T	T
T	F	F
T	F	T
T	T	F
T	T	T

M(β) = { } — gồm ___ / 8 model.

Phần 3 — Phân loại công thức: hằng đúng / thoả được / mâu thuẫn

📖 Slide 17–19

Với mỗi công thức, lập bảng và phân loại: valid (hằng đúng — đúng ở mọi model), unsatisfiable (mâu thuẫn — sai ở mọi model), hay satisfiable nhưng không valid (contingent — đúng ở một số model).

1.

P ∨ ¬P

Phân loại: Lý do:
2.

P ∧ ¬P

Phân loại: Lý do:
3.

(P ⇒ Q) ⇒ (¬Q ⇒ ¬P)

Phân loại: Bảng chân trị (nếu cần):
4.

P ⇒ (Q ⇒ P)

Phân loại: Lý do:
5.

(P ⇒ Q) ∧ (P ∧ ¬Q)

Phân loại: Lý do:
6.

(P ∨ Q) ⇒ (P ∧ Q)

Phân loại: Bảng chân trị:

Phần 4 — Kiểm tra entailment (KB ⊨ α?)

📖 Slide 19–20

Dùng model checking: chỉ xét các model làm KB đúng; nếu tất cả đều làm α đúng → KB ⊨ α; nếu có một model KB đúng mà α sai → đó là phản ví dụ, KB ⊭ α.

1.

KB = (P ⇒ Q) ∧ P ⊨ Q ?

Kết luận (⊨ hay ⊭): Giải thích / phản ví dụ:
2.

KB = (P ∨ Q) ∧ (P ⇒ R) ∧ (Q ⇒ R) ⊨ R ?

Kết luận (⊨ hay ⊭): Liệt kê model KB đúng:
3.

KB = (P ⇒ Q) ⊨ (¬P ⇒ ¬Q) ?

Kết luận (⊨ hay ⊭): Phản ví dụ (nếu ⊭):
4.

KB = (P ⇒ Q) ∧ ¬P ⊨ ¬Q ?

Kết luận (⊨ hay ⊭): Phản ví dụ (nếu ⊭):

Phần 5 — Luật suy diễn có đúng đắn (sound) không?

📖 Slide 21–23

Một luật dạng {tiền đề} ⊨ kết luận là sound khi mọi model thoả tất cả tiền đề đều thoả kết luận. Với mỗi luật dưới đây, dùng bảng chân trị xác định nó sound hay không; nếu không, chỉ ra phản ví dụ.

1.

Modus Tollens:
{P ⇒ Q, ¬Q} ⊨ ¬P

Sound hay không? Giải thích / phản ví dụ:
2.

Phủ định tiền đề:
{P ⇒ Q, ¬P} ⊨ ¬Q

Sound hay không? Giải thích / phản ví dụ:
3.

Tam đoạn luận tuyển:
{P ∨ Q, ¬P} ⊨ Q

Sound hay không? Giải thích / phản ví dụ:
4.

Tam đoạn luận bắc cầu:
{P ⇒ Q, Q ⇒ R} ⊨ (P ⇒ R)

Sound hay không? Giải thích / phản ví dụ:
5.

Khẳng định hậu kiện:
{P ⇒ Q, Q} ⊨ P

Sound hay không? Giải thích / phản ví dụ:

Phần 6 — Chứng minh tương đương logic

📖 Slide 26

Chứng minh các tương đương sau. Có thể dùng bảng chân trị (hai cột cuối trùng nhau ở mọi dòng) hoặc biến đổi bằng luật tương đương.

1.

P ⇒ Q ≡ ¬P ∨ Q

(khử kéo theo)

Chứng minh:
2.

¬(P ⇒ Q) ≡ P ∧ ¬Q

Chứng minh:
3.

P ⇔ Q ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)

Chứng minh:
4.

¬(P ∨ Q) ≡ ¬P ∧ ¬Q

(De Morgan)

Chứng minh:
5.

P ∨ (P ∧ Q) ≡ P

(luật hấp thụ)

Chứng minh:

Tổng cộng: 25 câu — 6 phần theo trình tự kiến thức slide. Ghi rõ từng bước lập luận để nhận trọn điểm.