GT:Toán rời rạc

CHƯƠNG 1. LÝ THUYẾT CƠ SỞ
BÀI 1: LOGIC VÀ MỆNH ĐỀ
Mở đầu:
Các quy tắc của logic cho ý nghĩa chính xác của các mệnh đề. Các quy tắc này dùng được sử dụng để phân biệt giữa các lập luận toán học đúng hoặc không đúng.
Các quy tắc của logic đóng vai trò quan trọng trong suy luận toán học và nhiều ứng dụng trong lĩnh vực tin học như: thiết kế các mạng trong máy tính, xây dựng các chương trình máy tính, kiểm tra tính đúng đắn của các chương trình và nhiều ứng dụng khác.
Mệnh đề:
Khái niệm:
Một mệnh đề là một câu trần thuật đúng hoặc sai, chứ không thể vừa đúng vừa sai.
Ví dụ:
+ Ví dụ 1: Xét các câu sau:
Hà nội là thủ đô của Việt nam
Việt trì là một thành phố biển.
1 + 1 = 2
2 + 4 = 5
Các câu 1 và 3 là đúng, trong khi các câu 2 và 4 là sai và như vậy cả 4 câu trên là các mệnh đề.
+ Ví dụ 2: Xét các câu sau:
Hôm nay là thứ mấy?
Vấn đề này cần được xem xét cẩn thận.
x + 1 = 2
x + y = z
Các câu 1 và 2 không phải là mệnh đề vì chúng không phải là câu trần thuật. Còn các câu 3 và 4 không phải là mệnh đề vì chúng chẳng đúng cũng chẳng sai bởi các biến trong các câu đó còn chưa được gán cho giá trị cụ thể nào.
Từ các câu loại này có thể tạo thành các mệnh đề bằng nhiều cách khác nhau (xem phần sau của chương này).
Phân loại mệnh đề:
Mệnh đề đơn (sơ cấp): Là những mệnh đề chỉ có một câu.
Mệnh đề phức hợp: Là những mệnh đề được kết hợp từ nhiều mệnh đề.
Quy ước:
Các mệnh đề và các biến được ký hiệu bởi các chữ cái như: p,q,r,s,...
Giá trị chân lý của một mệnh đề là đúng và sẽ được ký hiệu là T nếu đó là một mệnh đề đúng, và là sai và được ký hiệu là F, nếu đó là một mệnh đề sai.
Một bảng chân lý trình bày mối quan hệ giữa các giá trị chân lý của các mệnh đề. Bảng giá trị chân lý đặc biệt có ý nghĩa trong việc xác định giá trị chân lý của các mệnh đề được tạo ra từ các mệnh đề đơn giản hơn.
Các định nghĩa phép toán mệnh đề:
Phép toán mệnh đề là phương pháp tạo ra các mệnh đề mới từ các mệnh đề đã có – Geogre Boole “Các định luật của tư duy”.
+ Định nghĩa 1: Giả sử p là một mệnh đề. Câu “không phải là p” là một mệnh đề, được gọi là phủ định của p. Phủ định của p được ký hiệu là ¬p (hoặc
)
Bảng chân lý:
p
¬p

T
F
F
T


Ví dụ: Tìm phủ định của mệnh đề: “Hôm nay là chủ nhật”.
Phủ định của mệnh đề trên là: “Hôm nay không phải là chủ nhật”.
Phủ định của một mệnh đề cũng có thể được xem như là kết quả tác dụng của toán tử phủ định lên một mệnh đề. Toán tử phủ định xây dựng một mệnh mới từ mệnh đề đơn hiện có.
+ Định nghĩa 2: Giả sử p và q là hai mệnh đề. Mệnh đề “p và q” được ký hiệu bởi p ^ q là đúng khi cả p và q là đúng, còn sai trong các trường hợp còn lại. Mệnh đề p ^ q được gọi là hội của p và q.
Bảng chân lý:
p
Q
p^q

T
T
F
F
T
F
T
F
T
F
F
F


Ví dụ: Giả sử p là mệnh đề “Hôm nay là chủ nhật” và q là mệnh đề “Hôm nay trời mưa”. Tìm hội của các mệnh đề p và q.
Giải: Hội của hai mệnh đề p ^ q là mệnh đề “Hôm nay là chủ nhật và trời mưa”. Mệnh đề này là đúng vào hôm chủ nhật trời mưa và là sai vào bất kỳ ngày nào không phải là chủ nhật và vào ngày chủ nhật nhưng trời không mưa.
+ Định nghĩa 3: Giả sử p và q là hai mệnh đề. Mệnh đề “p hoặc q”, được ký hiệu là p ۷ q, là mệnh sai khi cả p và q đều sai, và đúng trong các trường hợp còn lại (có nghĩa là hoặc q là đúng, hoặc q là đúng, hoặc cả p và q cùng đúng). Mệnh đề p ۷ q được gọi là tuyển của p và q.
Bảng chân lý:

p
Q
p v q

T