Chứng minh mệnh đề hệ quả toán rời rạc 1 năm 2024

Mệnh đề là một trong những chương đầu tiên của toán rời rạc. Ở bài viết này, TTnguyen sẽ trình bày về các phép toán logic mệnh đề cơ bản là phủ định, hợp, tuyển, kéo theo, tương đương và cách chứng minh mệnh đề logic.

Logic mệnh đề chính là nghĩa đúng/sai của mệnh đề. Nếu logic của mệnh đề là:

• đúng thì nó được ký hiệu là T hoặc 1.
• sai thì nó được ký hiệu là F hoặc 0.

Quy ước các chữ cái được sử dụng cho các biến mệnh đề là p,q,r,s,…

II. Các phép toán trong logic mệnh đề

Phép tuyển

Mệnh đề p tuyển với mệnh đề q (ký hiệu p ∨ p) là một mệnh mà nó chỉ nhận giá trị T khi và chỉ khi ít nhất một trong hai mệnh đề p, q nhận giá trị T. Mệnh đề p ∨ q nhận giá trị F khi và chỉ khi cả p, q đều nhận giá trị F.

Phép hội

Mệnh đề p hội mệnh đề q (ký hiệu p ∧ q ) là một mệnh đề mà nó chỉ nhận giá trị T khi và chỉ khi p, q nhận giá trị T. Mệnh đề p ∧ q nhận giá trị F khi và chỉ khi hoặc p, q, hoặc cả hai nhận giá trị F.

Phủ định mệnh đề

Phủ định mệnh đề p (kí hiệu ¬p) là một mệnh đề nhận giá trị F khi và chỉ khi mệnh đề p nhận giá trị T, nhận giá trị F khi và chỉ khi p nhận giá trị T.

Phép tuyển

Mệnh đề tuyển loại của p và q, được ký hiệu là p⊕q, là một mệnh đề chỉ đúng khi một trong p hoặc q là đúng và sai trong các trường hợp khác còn lại.

Phép kéo theo

Mệnh đề p suy ra mệnh đề q (ký hiệu p → q) nhận giá T khi và chỉ khi p nhận giá trị F hoặc p và q cùng nhận giá trị T. Mệnh đề p→q nhận giá trị F khi và chỉ khi p nhận giá trị T và q nhận giá trị F.

Phép tương đương

Hai mệnh đề p, q được gọi là kéo theo nhau (ký hiệu: p ⇔ q) có giá trị đúng khi p và q có cùng giá trị chân lý và sai trong các trường hợp khác còn lại.

III. Bảng giá trị chân lý của các phép toán

p q p ∨ q p ∧ q ¬p p ⊕ q p → q p ⇔ q T T T T F F T T T F T F F T F F F T T F T T T F F F F F T F T T

IV. Bài tập logic mệnh đề có lời giải

Bài 1: Trong các phát biểu sau, phát biểu nào là mệnh đề? Nếu là mệnh đề, hãy biểu diễn nó thành công thức logic tương ứng.

1. Hà Nội là thủ đô của Mỹ.

→ Là mệnh đề sai. Biểu diễn a.

2. Hãy biết tận dụng tài nguyên thời gian của bạn.

→ Là câu lời khuyên, không phải là câu khẳng định. Không phải mệnh đề.

3. Linh học toán có giỏi không?

→ Là câu hỏi, không phải câu nói khẳng định nên không là mệnh đề.

4. Nếu bạn đi học bằng xe máy thì hãy mang theo bằng lái xe.

a: bạn đi học bằng xe máy.

b: hãy mang theo bằng lái xe.

Biểu diễn a→b. a là mệnh đề, b không phải là mệnh đề.

Vậy a→b không là mệnh đề.

5. Bạn sẽ đến lớp học đúng giờ khi và chỉ khi bạn đi học bằng xe máy.

a: bạn sẽ đến lớp đúng giờ.

b: bạn đi học bằng xe máy.

a là mệnh đề khẳng định, b cũng là mệnh đề khẳng định.

→ Là mệnh đề. Biểu diên a↔b.

6. Số nguyên x là số dương.

→ Khẳng định có thể vừa đúng hoặc vừa sai nên không là mệnh đề.

7. Số nguyên lẻ không chia hết cho 2.

→ Là mệnh đề. Biểu diễn: a.

8. Bộ phép toán (¬, ∧,∨) là một hệ đầy đủ.

→ Là một mệnh đề. Biểu diễn a.

9. Điều kiện cần để Nam được chọn đi học là nam phải biết tiếng Anh hoặc tiếng Nhật.

a: Nam phải biết tiếng Anh

b: Nam phải biết tiếng Anh

→ Là mệnh đề. Biểu diễn: a ∨ b.

V. Lập bảng giá trị chân lý cho các mệnh đề

Bài 1. Lập bảng giá trị chân lý cho các mệnh đề phức hợp sau:

1. A=(p → q) ↔ (¬q→¬p)

p q ¬p ¬q p → q ¬q→¬p A 1 1 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1

2. (p →q) →(q →p)

p q p → q q → p (p → q) → (q → p) 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1

3. (p ↔ q) ∨ (p ⊕ ¬q)

p q ¬q p ↔ q p ⊕ ¬q (p ↔ q) ∨ (p ⊕ ¬q) 1 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1

4. (p ⊕ q) → (p ⊕¬q)

p q ¬q p ⊕ q p ⊕ ¬q (p ⊕ q) → (p ⊕ ¬q) 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1

VI. Chứng minh mệnh đề logic

Bài 1: Dùng bảng chân lý chứng minh luật giao hoán: p ∨ q ⇔ q ∨ p

p q p ∨ q q ∨ p True True True True True False True True False True True True False False False False

Bài 2. Dùng bảng chân lý chứng minh luật kết hợp: (p ∨ q) ∨ r ⇔ p ∨ ( q ∨ r)

Dưới đây là bảng giá trị chân lý cho biểu thức (p ∨ q) ∨ r và p ∨ (q ∨ r):

p q r (p ∨ q) ∨ r p ∨ (q ∨ r) 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0

Kết quả bảng giá trị chân lý cho thấy cả hai phía của biểu thức [(p ∨ q) ∨ r] và [p ∨ (q ∨ r)] có cùng giá trị chân lý cho mọi giá trị của p, q và r. Do đó, ta kết luận rằng luật kết hợp (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) đã được chứng minh.

Bài 3. Chứng minh các công thức sau đây là đồng nhất đúng bằng cách lập bảng giá trị chân lý:

1. ( X→(Y→Z)) →((X →Y)→(X→Z));

X Y Z Y → Z X → (Y → Z) (X → Y) → (X → Z) (X → (Y → Z)) → ((X → Y) → (X → Z)) 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1

Kết quả bảng giá trị chân lý cho thấy biểu thức (X → (Y → Z)) → ((X → Y) → (X → Z)) luôn đúng cho tất cả các giá trị của X, Y và Z. Vì vậy, chúng ta có thể kết luận rằng biểu thức đã cho là đồng nhất đúng.

Trên đây là một số bài tập toán rời rạc chương 1 có lời giải. Cảm ơn các bạn đã theo dõi trên ttnguyen.net