Xem mẫu
- TOÁN RỜI RẠC
Chương 01
Logic
Giảng viên: ThS. Trần Quang Khải
- Nội dung
1. Propositional Logic.
2. Predicate Logic.
Toán rời rạc Chương 1: Logic 2
- What is LOGIC?
Logic is the study of arguments.
Toán rời rạc Chương 1: Logic 3
- What is LOGIC?
Logic is the study of arguments.
In philosophy
Logic (from the Greek) is the formal systematic
study (sự nghiên cứu có tính hệ thống) of the
principles (quy tắc) of valid inference and
correct reasoning (lập luận có căn cứ và suy luận
đúng).
Toán rời rạc Chương 1: Logic 4
- What is LOGIC?
Trong toán học:
các quy luật Logic giúp xác định ý nghĩa
chính xác của các phát biểu toán học.
Logic toán học là một nhánh của toán học có quan
hệ chặt chẽ với khoa học máy tính và logic triết học.
Phân biệt các suy luận đúng (valid) và không đúng
(invalid)
Toán rời rạc Chương 1: Logic 5
- TOPIC 1
PROPOSITIONAL LOGIC
(Logic mệnh đề)
Giảng viên: ThS. Trần Quang Khải
Toán rời rạc Chương 1: Logic 6
- Propositions
Mệnh đề (Proposition)
là 1 câu (hoặc 1 phát biểu) tường thuật chỉ
có giá trị “đúng” hoặc “sai”
Mệnh đề không thể vừa đúng vừa sai
Giá trị đúng hoặc sai của mệnh đề: chân trị.
TRUTH
VALUE
Toán rời rạc Chương 1: Logic 7
- Propositions - Examples
1. “Pigs can fly.”
2. “1 + 1 = 2.“
3. “2 + 2 = 3.”
4. “Your teacher is Superman.”
5. “Hanoi is the capital of Vietnam.”
6. “Paris is the capital of London.”
Toán rời rạc Chương 1: Logic 8
- Sentences not to be propositions
1. What time is it?
2. Do your homework.
3. x + 1 = 3.
4. x + y = z.
5. What a pretty girl!
Toán rời rạc Chương 1: Logic 9
- Biểu diễn mệnh đề
Biểu diễn 1 mệnh đề bằng 1 kí tự (letter).
VD: p, q, r, s, t, …
Gọi là biến mệnh đề (propositional variables or statement
variables).
Phủ định một mệnh đề: ký hiệu ¬p
Quy ước:
Truth table
TRUE: T or 1.
FALSE: F or 0. p ¬p p ¬p
T F 1 0
F T 0 1
Toán rời rạc Chương 1: Logic 10
- Xác định chân trị
Xác định 1 mệnh đề là true/false:
không phải là nhiệm vụ của Logic
Ex: Today is Friday.
true or false depends on what is today.
Toán rời rạc Chương 1: Logic 11
- Negation (phủ định)
Phủ định của một mệnh đề:
“Today is Friday.”
“It is not the case that today is Friday.”
“Today is not Friday.”
“It is not Friday today.”
Toán rời rạc Chương 1: Logic 12
- Compound propositions
Mệnh đề kết hợp
(Mệnh đề phức hợp)
Các phát biểu thường gồm 1 hay nhiều mệnh đề.
Các mệnh đề kết hợp bằng toán tử logic (logical
operators).
Toán rời rạc Chương 1: Logic 13
- Compound propositions
George Boole (1854) – English mathematician
“The Mathematical Analysis of Logic” (1848).
“The Law of Thought” (1854) Boolean Algebra.
Toán rời rạc Chương 1: Logic 14
- Toán tử Logic
Gọi p, q là các mệnh đề:
¬p: negation (phủ định).
p q: conjunction (hội).
p q: disjunction (tuyển).
p q: exclusive-OR (tuyển loại – phép XOR).
p q: implication (kéo theo).
Kết quả của việc kết hợp các mệnh đề bằng các toán
tử cũng là một mệnh đề.
Toán rời rạc Chương 1: Logic 15
- Toán tử Logic – Bảng chân trị
p q ¬p pq pq pq pq pq
T T F T T F T T
T F F T T F F
F T T F T T T F
F F F F F T T
Toán rời rạc Chương 1: Logic 16
- Phép hội: p q
Mệnh đề “p và q” là:
TRUE khi cả p và q đều TRUE.
FALSE trong các trường hợp còn lại.
Trong lập trình:
Kết hợp các điều kiện AND.
if (a > 1 AND a < 4) then … p q pq
T T T
T F F
F T F
T F F
Toán rời rạc Chương 1: Logic 17
- Phép tuyển: p q
Mệnh đề “p hoặc q” là:
FALSE khi cả p và q đều FALSE.
TRUE trong các trường hợp còn lại.
Trong lập trình:
Kết hợp các điều kiện OR.
if (a > 1 OR a < 4) then … p q pq
T T T
T F T
F T T
F F F
Toán rời rạc Chương 1: Logic 18
- Phép tuyển loại: p q
Mệnh đề “p q” là:
FALSE khi p và q đều là TRUE hoặc FALSE.
Nhận xét: p và q giống nhau.
TRUE trong các trường hợp còn lại.
Nhận xét: p và q khác nhau.
Trong lập trình: p q pq
Phép XOR. T T F
T F T
F T T
F F F
Toán rời rạc Chương 1: Logic 19
- Toán tử “kéo theo”: p q
Toán tử p → q có vai trò đặc biệt quan trọng
trong toán học:
p: giả thiết (hypothesis).
q: kết luận (conclusion).
“Nếu p, thì q”
“p chỉ nếu q”
“p suy ra q”
“p là đủ cho q”
“Điều kiện cần cho p là q”
Toán rời rạc Chương 1: Logic 20
nguon tai.lieu . vn