Bài 1 ôn tập: logic mệnh đề - cấu trúc dữ liệu giải thuật | Đại học Kinh tế Kỹ thuật Công nghiệp
Là một câu khẳng định mà có thể xác định được tính đúng (True) hoặc sai (False). Phủ định (¬): Đảo ngược giá trị chân lý của một mệnh đề. Hội (∧): Kết hợp hai mệnh đề, chỉ đúng nếu cả hai đều đúng. Tuyển (∨): Chỉ cần một trong hai mệnh đề đúng. Kéo theo (→): P→Q chỉ sai khi P=True và Q=False. Tương đương (↔): P↔Q đúng khi P và Q có cùng giá trị chân lý.
Môn: Cấu trúc dữ liệu và giải thuật (KTKTCN)
Trường: Đại học Kinh tế kỹ thuật công nghiệp
Thông tin:
Tác giả:
Thông tin :
Môn:
Cấu trúc dữ liệu và giải thuật (KTKTCN)
Trường:
Đại học Kinh tế kỹ thuật công nghiệp
Tác giả:
Tài liệu liên quan:
Preview text:
Logic Toan Lp trinh Logic Bai 1 On tp
Logic Toán - Lập trình Logic Bài 1 Ôn tập: Logic mệnh đề Vũ Quốc Hoàng (vqhoang@fit.hcmus.edu.vn) FIT, HCMUS HCMC, 2013 Nội dung
• Cú pháp Logic mệnh đề
• Ngữ nghĩa Logic mệnh đề • Chân lý và mâu thuẫn
• Hệ quả và tương đương logic • Dạng chuẩn CNF
• Suy diễn và chứng minh • Hệ chứng minh • Hợp giải • Logic Horn 2 Logic?
• Trí tuệ = Tri thức ⊕ Suy luận
(Intelligence = Knowledge ⊕ Reasoning)
– Hai vấn đề cơ bản là biểu diễn và xử lý tri thức
• Logic là một phương tiện gần gũi, mạnh mẽ và hiệ hi u ệ quả u đ quả ể đ bi b ể i u ể di u ễ di n ễ v n à v xử à l ý l t ý r t i r t h t ứ h c ứ c ủa c co c n on người
• Logic là một ngôn ngữ hình thức:
– mỗi tri thức được biểu diễn bằng một câu logic đúng
cú pháp và có ngữ nghĩa xác định (chính xác và đơn giản)
– ngữ nghĩa của một câu logic là đúng hoặc sai 3 Cú pháp Logic mệnh đề (Propositional Logic)
• Tập các kí hiệu Logic mệnh đề (dictionary):
– 2 hằng: true và false
– Các biến: A, ,
B C, …, P, Q, R, …
– 5 toán tử: ¬, ∧, ∨, →, ↔ – 22 kí k hi ệ hi u ệ p u hụ: ( v à )
• Biểu thức logic là dãy các kí hiệu logic • Ví dụ:
– ¬(A ∨ B) → C là biểu thức logic
– A¬ ∨ B) → là biểu thức logic
– A and B ? không là biểu thức logic vì and và ? không là những kí hiệu logic 4 Cú pháp Logic mệnh đề
• Câu logic (sentence) là biểu thức logic đúng theo các qui tắc cú pháp sau:
(1) true và false là các câu
(2) Các biến là các câu: …, P, Q, R, …
(3) Nếu α, β là các câu thì
¬α, α ∧ β, α ∨ β, α → β, α ↔ β cũng là các câu
(4) Nếu α là câu thì (α) cũng là câu
(5) Ngoài ra, không còn câu nào khác
• Câu theo qui tắc (1), (2) gọi là câu đơn; câu theo qui tắc (3) gọi là câu phức 5 Cú pháp Logic mệnh đề • Ví dụ: – true là câu đơn – P là câu đơn – ¬P là câu phức
– ¬(A ∨ B) là câu phức
– ¬(A ∨ B) → C là câu phức – ¬ không là câu
– ¬(A không là câu
– A¬ ∨ B) → không là câu 6 Cú pháp Logic mệnh đề
Độ ưu tiên của các toán tử
• Độ ưu tiên của các toán tử logic giúp xác định qui tắc cú
pháp nào được áp dụng trước
• Các toán tử logic có độ ưu tiên giảm dần như sau: ¬, ∧, ∨, →, ↔ • Cặ C p ặ ng p o ng ặ o c ặ tr ò tr n ò x n á x c á đị nh đị qui nh qui t ắ t c ắ c ú c pháp ú đượ pháp đư c á p á dụn p g trước tiên • Ví dụ:
– ¬A ∨ B là (¬A) ∨ B
– A ∨ B ∧ C là A ∨ (B ∧ C)
– A ↔ B ∨ C → D là A ↔ ((B ∨ C) → D)
– (A ∨ B) ∧ C 7
Ngữ nghĩa Logic mệnh đề
• Tập gồm 2 giá trị {đúng, sai} hay {t, f} hay {1, 0} được gọi là tập chân trị
• Phép gán biến là phép gán chân trị cho tập biến logic
– Ví dụ: {A = 1, B = 0, C = 1, …} • ữ Ngữ n hĩ ghĩa ủ của một â c u l ogic mệnh đ ề l à l ộ m t h c ân trị, ứ t l c à
hoặc đúng (1) hoặc sai (0)
• Ngữ nghĩa của câu có chứa biến phụ thuộc vào chân trị của biến
• Ngữ nghĩa của câu phức thì phụ thuộc vào ngữ nghĩa của câu thành phần 8
Ngữ nghĩa Logic mệnh đề
• Cho Φ là một phép gán biến, A là một biến, ta kí hiệu Φ(A)
là chân trị được gán cho biến A trong phép gán biến Φ
– Ví dụ, Φ = {A = 1, B = 0, C = 1, …} thì Φ(A) = 1
• Ngữ nghĩa của một câu đơn được xác định theo các qui tắc n ữ gữ n hĩ gh a sau:
– Φ(true) = 1 không phụ thuộc vào Φ
– Φ(false) = 0 không phụ thuộc vào Φ
– Với A là biến thì Φ(A) là chân trị được gán cho biến A trong phép gán biến Φ Φ đọc là phi 9
Ngữ nghĩa Logic mệnh đề
• Ngữ nghĩa của một câu phức được xác định theo
các qui tắc ngữ nghĩa cho trong các bảng chân trị (truth table) như sau Φ(α) Φ(¬α ¬ ) 0 1 1 0 Φ(α) Φ(β) Φ(α∧ α β ∧ ) Φ(α∨ α β ∨ ) Φ(α→β α ) Φ(α↔β) 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 10