Chương I: Mệnh đề và Vị từ - Giải bài tập Logic Tính chân trị | Môn Toán rời rạc - Đại học Cần Thơ

lOMoAR cPSD| 58488183
CHƯƠNG I (Mệnh đề và vị từ)
2/ Nếu Q có chân trị là T, hãy xác định chân trị của các biến mệnh đề P, R, S nếu biểu thức mệnh đề sau cũng là đúng
(Q → ((P ∨R) ∧ S )) ∧ (S → ( R ∧Q)) Đáp án:
(Q → (( P ∨R) ∧ S )) ∧ ( S → ( R ∧Q))
Thay Q = T và biểu thức mệnh đề bẳng T
(T → (( P ∨R) ∧ S )) ∧ ( S → ( R ∧ T)) = T
=> (T → (( P ∨R) ∧ S )) = T (1) và ( S → ( R ∧ T)) = T (2)
Từ (1) (T → (( P ∨R) ∧ S )) = T T → T = T =>
S = T => S=F (3) Thay (3) vào (1) và (2):
(T → (( P ∨R) ∧ T )) = T (1) và (T → ( R ∧ T)) = T (2)
=> ( P ∨R) = T và R = T => R = F => P, R, S = F
9/ Không lập bảng chân trị, sử dụng các công thức tương đương logic, chứng minh rằng các biểu thức mệnh đề sau là hằng đúng
b/ P→(P→ P) c/ P→((Q→ (P∧Q))) e/
((P→Q) ∧ (Q→R)) → (P→R) Đáp án:
b/ P→( P→ P) // Khử phép kéo theo
= ¬P ∨ (¬ ¬P ∨ P) // phủ định của phủ định
= ¬P ∨ (P ∨ P) // luật lũy đẳng
= ¬P ∨ P = T // luật về phần tử bù
c/ P→(Q→ (P∧Q)) //khử phép kéo theo
= ¬P ∨ (¬Q ∨ (P∧Q)) //phân phối
= ¬P ∨ ((¬Q ∨ P) ∧ (¬Q ∨ Q)) //luật về phần tử bù
= ¬P ∨ ((¬Q ∨ P) ∧ T) // luật trung hòa (hội với hằng đúng)
= ¬P ∨ ¬Q ∨ P // giao hoán
= ¬P ∨ P ∨ ¬Q //luật về phần tử bù
= T ∨ ¬Q = T //luật thống trị lOMoAR cPSD| 58488183
e/ ((P→Q) ∧ (Q→R)) → (P→R)
= ((¬P ∨ Q) ∧ (¬Q ∨ R)) → (¬P ∨ R)
= ¬ ((¬P ∨ Q) ∧ (¬Q ∨ R)) ∨ (¬P ∨ R)
= (¬ (¬P ∨ Q) ∨ ¬ (¬Q ∨ R)) ∨ (¬P ∨ R)
= (¬ (¬P ∨ Q) ∨ ¬ (¬Q ∨ R)) ∨ (¬P ∨ R)
= ((¬ ¬P ∧ ¬Q) ∨ (¬¬Q ∧ ¬R)) ∨ (¬P ∨ R)
= (P ∧ ¬Q) ∨ (Q ∧ ¬R) ∨ ¬P ∨ R
= (¬P ∨ (P ∧ ¬Q)) ∨ (R ∨ (Q ∧ ¬R))
= ((¬P ∨ P) ∧ (¬P ∨ ¬Q)) ∨ ((R ∨ Q) ∧ (R ∨ ¬R))
= (T ∧ (¬P ∨ ¬Q)) ∨ ((R ∨ Q) ∧ T) = (¬P ∨ ¬Q) ∨ (R ∨ Q) = (Q ∨ ¬Q) ∨ R ∨ ¬P = T ∨ R ∨¬P = T
10/ Không lập bảng chân trị, sử dụng các công thức tương đương logic, xét xem biểu thức mệnh đề G có là hệ quả của F không? a/ F = P∧(Q∨R) G = (P∧Q)∨R Đáp án:
a/ F = P∧(Q∨R)
G = (P∧Q)∨R
Cần chứng minh F->G là hằng đúng thì G sẽ là mệnh đề hệ quả của F
(P∧(Q∨R)) → ((P∧Q)∨R)
= ¬ (P∧(Q∨R)) ∨ ((P∧Q)∨R)
= ¬P ∨ ¬ (Q∨R) ∨ (P∧Q)∨R
= ¬P ∨ (P∧Q) ∨ ¬ (Q∨R) ∨R
= ((¬P ∨ P) ∧ (¬P∨Q)) ∨ (¬Q∧¬R) ∨R
= (T ∧ (¬P∨Q)) ∨ (¬Q∧¬R) ∨R
= (¬P∨Q) ∨ ((¬Q∨R )∧(¬R∨R))
= (¬P∨Q) ∨ ((¬Q∨R ) ∧ T) = ¬P∨Q ∨ ¬Q ∨ R
= ¬P∨ (Q ∨ ¬Q) ∨ R = T
11/ Tương tự bài tập 9 và 10, chứng minh các tương đương logic sau đây:
b/ (P Q∨ ∧ ∨) R Q ⇔ Q∧R
i/ P ∧ ((Q → (R∧R)) ∨ Q R S∨ ∧ ∨ ∧( ) (R S) ) ⇔ P
j/ (P∨Q∨R) ∧ (P ∨ S ∨ Q) ∧ (P ∨ S ∨ R) ⇔ P ∨ (R ∧ (S ∨ Q) Đáp án: lOMoAR cPSD| 58488183
b/ (P Q R Q∨ ∧ ∨) ⇔ Q∧R
VT = (P Q R Q∨ ∧ ∨) = ((P ∨ Q) ∧ R) ∧ Q = Q ∧ (Q ∨ P) ∧ R = Q ∧ R
i/ P ∧ ((Q → (R∧R)) ∨ Q R S∨ ∧ ∨ ∧( ) (R S) ) ⇔ P
VT= P ∧ ((Q → (R∧R)) ∨ Q R S∨ ∧ ∨ ∧( ) (R S))
= P ∧ ((Q ∨ (R∧R)) ∨ (¬Q ∧ ¬(R ∧ S) ∧ ¬(R ∧ ¬S)))
= P ∧ ((Q ∨ R) ∨ (¬Q ∧ ¬(R ∧ S) ∧ ¬(R ∧ ¬S)))
= P ∧ ((Q ∨ R) ∨ (¬Q ∧ (¬R ∨ ¬S) ∧ (¬R ∨ S)))
= P ∧ ((Q ∨ R) ∨ (¬Q ∧ (¬R ∨ (¬S ∧ S))))
= P ∧ ((Q ∨ R) ∨ (¬Q ∧ ¬R))
= P ∧ ((Q ∨ R) ∨ ¬(Q ∨ R)) = P = VP
j/ (P∨Q∨R) ∧ (P ∨ S ∨ Q) ∧ (P ∨ S ∨ R) ⇔ P ∨ (R ∧ (S ∨ Q))
VT = (P∨Q∨R) ∧ (P ∨ S ∨ Q) ∧ (P ∨ S ∨ R)
= P ∨ ((Q∨R) ∧ (S ∨ Q) ∧ (S ∨ R))
= P ∨ ((Q∨R) ∧ ( S ∨ R) ∧ (S ∨ Q))
= P ∨ ((R ∨ (Q ∧ S ))∧ (S ∨ Q))
= P ∨ (R ∧ (S ∨ Q))= VP
12/ Cho 2 vị từ P(x) xác định như sau: P(x) = {x ≤ 3} Q(X) = {x+ 1 là số lẻ}
Nếu không gian là tập số nguyên, hãy xác định chân trị của những mệnh đề sau: a) P(1) b) Q(1) c) P (3) d) Q(6) e) P(7)∧Q(7) f) P(3)∧Q(4) g) P(4) Đáp án:
h) P( 4)− ∨Q( 3)−
i) P (-4) ∧Q(-3) a) P(1) = T b) Q(1) = F c) P (3) = F d) Q(6) = T e) P(7)∧Q(7) = F f) P(3)∧Q(4) = T g) P(4) = F lOMoAR cPSD| 58488183
h) P( 4)− ∨Q( 3)− = T
i) P (-4) ∧Q(-3) = F
13/ Các vị từ P(x), Q(x), R(x) được cho như sau: P(x) = {x ≤ 3} Q(X) = {x+ 1 là số lẻ} R(x) = {x > 0}.
Không gian của vị từ là tập số nguyên.
a) Xác định chân trị của những biểu thức mệnh đề sau:
1. P(3) ∨ [Q(3)∨R (3)] = T
2. P (3) ∧ [Q(3) ∨ [Q(3) ∨ R(3)]] = F
3. P(2) → [Q(2) → R(2)] = T
4. [P(2)↔ Q(2)] → R(2) = T
5. P(0) → [Q(1) ↔R(1)] = T
5. [P(-1) ↔ Q(-2)] ↔ R(-3) = F
b) Xác định tất cả các giá trị x sao cho [P(x) ∧ Q(x)] ∧ R(x) là một mệnh đề đúng. x≤ 3
x+1 là số lẻ ⇒ x= 2 x> 0
c) Tìm 5 giá trị nguyên dương nhỏ nhất của x sao cho vị từ:
P(x) → [Q(x) ∧ R(x)] là biểu thức mệnh đề đúng. Đáp án:
16/ Trên không gian là tập số nguyên, cho các vị từ sau: P(x) = {x>0) Q(x) = {x là số chẵn}
R(x) = {x là số chính phương} S(x) = {x chia hết cho 4} T(x) = {x chia hết cho 5}
a) Viết dạng ký hiệu của những mệnh đề sau:
1. Có ít nhất 1 số nguyên chẵn. ∃x Q(x)
2. Tồn tại 1 số nguyên dương là số chẵn. ∃x [P(x) ∧ Q(x) ]
3. Nếu x chẵn, thì x không chia hết cho 5. ∀x [Q(x) → T (x)]
4. Không có số nguyên chẵn nào là chia hết cho 5. ∀x [Q(x) ∧ T (x)]
5. Tồn tại 1 số nguyên chẵn chia hết cho 4. lOMoAR cPSD| 58488183 ∃x [Q(x) ∧ S(x)]
6. Nếu x chẵn và x là số chính phương, thì x chia hết cho 4.
∀x [[Q(x) ∧ R(x)] → S(x)]
b) Xác định chân trị của mỗi mệnh đề a). Với mỗi mệnh đề sai, hãy cho một dẫn chứng cụ thể. 1. T 2. T 3.F 4.F 5.T 6.
c) Viết thành lời các dạng ký hiệu sau: 1. ∀x [R(x) → P(x)] 2. ∀x [S(x) → Q(x)]
3. ∀x [S(x) → T (x)]
4. ∃x [S(x) ∧R (x)]
5. ∀x [ R (x) ∨Q(x) ∨ S(x)] Đáp án:
17/ Cho các vị từ trên không gian là tập số thực như sau: P(x) = {x ≥ 0) Q(x) = {x2 ≥ 0} R(x) = {x2 - 3x -4 = 0} S(x) = {x2 - 3 > 0}
Xác định giá trị đúng, sai của những biểu thức mệnh đề sau. Cho dẫn chứng hoặc giải thích cụ thể: a) ∃x [P(x) ∧ R(x)] b) ∀x [P(x) → Q(x)] c) ∀x [Q(x) → S(x)] d) ∀x [R(x) ∨ S(x)] e) ∀x [R(x) → P(x)] Đáp án: a) ∃x [P(x) ∧ R(x)]: T
R(x) = {x2 - 3x -4 = 0} ⇔ x = -1 hoặc x = 4 ≥ 0
b) ∀x [P(x) → Q(x)] : T (x = 0, x = 1 ,…) c) ∀x [Q(x) → S(x)]: F Q(x) = {x2 ≥ 0}
S(x) = {x2 - 3 > 0} ⇔ x2 > 3 x2 = 1, x2 = 2, x2 = 3 d) ∀x [R(x) ∨ S(x)]: T
R(x) = {x2 - 3x -4 = 0} ⇔ x = -1 hoặc x = 4 S(x) = {x2 - 3 > 0} e) ∀x [R(x) → P(x)]: F
R(x) = {x2 - 3x -4 = 0} ⇔ x = -1 hoặc x = 4 P(x) = {x > 0} 22/ Cho vị từ:
P(x) = {x nói được tiếng anh}
Q(x) = {x biết ngôn ngữ C++} lOMoAR cPSD| 58488183
Cho không gian là tập hợp các sinh viên lớp bạn. Hãy diễn đạt các câu sau bằng
cách dùng P(x), Q(x), các lượng từ và các phép toán logic.
a) Có một sinh viên ở lớp bạn nói được tiếng Anh và biết C++
b) Có một sinh viên ở lớp bạn nói được tiếng Anh nhưng không biết C++
c) Mọi sinh viên ở lớp bạn đều nói được tiếng Anh hoặc biết C++
d) Không có một sinh viên nào ở lớp bạn nói được tiếng Anh hoặc biết C++ Đáp án:
a) ∃x [P(x) ∧ Q(x)] b) ∃x [P(x) ∧ ¬Q(x)] c) ∀x [P(x) v Q(x)] d)¬∃x[P(x) v Q(x)]