›
›

Tài liệu Cấu trúc rời rạc cho khoa học máy tính - Chapter 1B: Predicate Logic

Download
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH  
TRƯỜNG ĐẠI HỌC BÁCH KHOA  
KHOA KHOA HỌC - KỸ THUẬT MÁY TÍNH  
CẤU TRÚC RỜI RẠC CHO KHMT (CO1007)  
Nhóm:18-TDTT —- Homework  
CHAPTER 1B  
Predicate Logic  
GVHD: Nguyễn An Khương  
SV thực hiện: Đinh Minh Tân – 1613074  
Trương Minh Tiến – 1613544  
Vũ Đào Anh Tuấn – 1613938  
Nguyễn Thị Trà My – 51305086  
Tp. Hồ Chí Minh, Tháng 11/2016  
1 Exercise 1  
1
arity: Một con số thuộc toán học  
Ex: Arity in technology  
variable:biến số  
Ex:x is a variable  
argument:đối số, lí lẽ  
Ex: argument of the vector  
We agreed without much further argument !  
constant:hằng số  
Ex:h is Plang ’s constant  
2
term:số hạng  
Formula: công thức  
Ex: Mathemetical formula is difficult to learn by heart  
expression: biểu thức  
Ex: This is a simple expression x2 + 2x + 1 = 0  
3
free: tự do, độc lập  
Ex: In free liqid surface, water is under oil  
bound: giới hạn  
Ex: compulation bound  
captured: đạt được  
Ex: This lim captured =3  
2 Exercise 2  
1
∃x(P(x) ∧ Q(x)) = ∃xP(x) ∧ ∃xQ(x)  
We need proof ∃xP(x) ∧ ∃xQ(x) 0 ∃x(P(x) ∧ Q(x))  
Let P(x) denotes ”x ≥ 0” and Q(x) denotes ”x < 0”  
It is easy to see that the left hand is always true and the right hand is false  
So we have the proof.  
2
∃x(P(x) ∧ Q(x)) → ∃xP(x) ∧ ∃xQ(x)  
1.  
2.  
3.  
4.  
5.  
6.  
7.  
8.  
∃x(P(x) ∧ Q(x))  
x0 P(x0) ∧ Q(x0)  
P(x0)  
premise  
assumption  
∧e12  
∃xP(x)  
Q(x0)  
∃x i 3  
∧e22  
∃x i 5  
∃xQ(x)  
∃xP(x) ∧ ∃xQ(x) ∧i4, 6  
∃xP(x) ∧ ∃xQ(x) ∃i1, 2 − 7  
1
3
a) ∃x(S(x) ∨ R(x)) ≡ ∃xS(x) ∨ ∃xR(x)  
Proof ∃x(S(x) ∨ R(x)) ` ∃xS(x) ∨ ∃xR(x)  
1.  
2.  
∃x(S(x) ∨ R(x))  
premise  
x0 S(x0) ∨ R(x0)  
S(x0)  
assumption  
assumption  
∃x i 3  
3.  
4.  
∃xS(x)  
5.  
∃xS(x) ∨ ∃xR(x) ∨i1 4  
6.  
R(x0)  
assumption  
∃x i 6  
7.  
∃xR(x)  
∃xS(x) ∨ ∃xR(x) ∨i2 7  
∃xS(x) ∨ ∃xR(x) ∨ e 2, 3–5, 6–8  
∃xS(x) ∨ ∃xR(x) ∃x e 1, 2–9  
8.  
9.  
10.  
Proof ∃x(S(x) ∨ R(x)) a ∃xS(x) ∨ ∃xR(x)  
1.  
2.  
∃xS(x) ∨ ∃xR(x) premise  
∃xS(x)  
x0 S(x0)  
assumption  
assumption  
∨i1 3  
3.  
4.  
S(x0) ∨ R(x0)  
∃x(S(x) ∨ R(x))  
∃xR(x)  
5.  
∃x i 4  
6.  
assumption  
assumption  
∨i2 7  
7.  
x0 R(x0)  
8.  
S(x0) ∨ R(x0)  
∃x(S(x) ∨ R(x))  
∃x(S(x) ∨ R(x))  
9.  
∃x i 8  
10.  
∨ e 1, 2-5, 6-9  
b) ∀x(S(x) ∨ R(x)) ←− ∀xS(x) ∨ ∀xR(x)  
We need proof ∀xS(x) ∨ ∀xR(x) ` ∀x(S(x) ∨ R(x))  
1.  
2.  
∀xS(x) ∨ ∀xR(x) premise  
∀xS(x)  
x0 S(x0)  
assumption  
∀x e 2  
3.  
4.  
S(x0) ∨ R(x0)  
∀x(S(x) ∨ R(x))  
∀xR(x)  
∨i1 3  
5.  
∀x i 3–4  
assumption  
∀x e 6  
6.  
7.  
x0 R(x0)  
8.  
S(x0) ∨ R(x0)  
∀x(S(x) ∨ R(x))  
∀x(S(x) ∨ R(x))  
∨i2 4  
9.  
∀x i 7–8  
∨ e 1, 2–5, 6–9  
10.  
2
c) ∀x(S(x) ∨ R(x)) = ∀xS(x) ∨ ∀xR(x)  
We need proof ∀x(S(x) ∨ R(x)) 0 ∀xS(x) ∨ ∀xR(x)  
Let S(x) denotes ”x ≥ 0” and R(x) denotes ”x < 0”  
It is easy to see that the left hand is always true and the right hand can be false  
For example, S(−1) and R(1) are false, so the right hand is false  
So we have the proof.  
4
∃x(P(x) → Q(x)) = ∃xP(x) → ∃xQ(x)  
We need proof ∃xP(x) → ∃xQ(x) 0 ∃x(P(x) → Q(x))  
Let P(x) denotes ”x ≥ 0” and Q(x) denotes ”x < 0”  
It is easy to see that the left hand is always true and the right hand can be false  
For example, P(1) and Q(1) are false, so the right hand is false  
So we have the proof.  
3 Exercise 3  
Exercise 2.1.  
(a) ∀x(P(x) → A(m, x))  
(b) ∀x∃y(F(x) → Q(y, x))  
Exercise 2.2.  
6. S(x) ∧ ∀zP(x) → Q(z)  
Exercise 2.3.  
1a. (y = 0) ∧ (y = x) ` 0 = x  
1.  
2.  
3.  
4.  
(y = 0) ∧ (y = x) premise  
y = 0  
y = x  
0 = x  
∧e1 1  
∧e2 1  
= e 2, 3  
t1 is y, t2 is 0, ϕ is y = x.  
1b. t1 = t2 ` t + t2 = t + t1  
1.  
t1 = t2  
premise  
2.  
3.  
t + t1 = t + t1 =i  
t + t2 = t + t1 =e 1, 2  
t1 is t1, t2 is t2, ϕ is t + t1 = t + t1  
6a. ∀xP(x) ` ∀yP(y)  
3
1.  
2.  
3.  
4.  
∀xP(x)  
premise  
y0 P(y0) ∀x e 1  
∀yP(y)  
∀yP(y)  
∀y i 2  
∀y i 2-3  
6b. ∀x(P(x) → Q(x)) ` (∀x¬Q(x)) → (∀x¬P(x))  
1.  
2.  
3.  
4.  
5.  
6.  
7.  
∀x(P(x) → Q(x))  
∀x¬Q(x)  
premise  
assumption  
∀x e 1  
P(x0) → Q(x0)  
x0 ¬Q(x0)  
∀x e 2  
¬P(x0)  
∀x¬P(x)  
∀x¬Q(x) → ∀x¬P(x) → i, 2–6  
MT 3, 4  
∀x i 3–5  
6c. ∀x(P(x) → ¬Q(x)) ` ¬(∃x((P(x) ∧ Q(x)))  
1.  
2.  
∀x(P(x) → ¬Q(x)) premise  
∃x(P(x) ∧ Q(x))  
assumption  
assumption  
∧e1 3  
3.  
x0 P(x0) ∧ Q(x0)  
P(x0)  
4.  
5.  
Q(x0)  
∧e2 3  
6.  
P(x0) → ¬Q(x0)  
∀x e 1  
7.  
¬Q(x0)  
→ e 4, 6  
¬ e 5, 7  
∃x e 2, 3–8  
8.  
⊥
⊥
9.  
10.  
¬(∃x(P(x) ∧ Q(x)) PBC 2–9  
7b. ∃x∃yF(x, y) ` ∃u∃vF(u, v)  
1.  
2.  
3.  
4.  
5.  
6.  
7.  
∃x∃yF(x, y)  
premise  
u0 ∃yF(u0, y) assumption  
v0F(u0, v0)  
F(u0, v0)  
F(u0, v0)  
∃vF(u0, v)  
∃uF(u, v)  
assumption  
∃y e 2, 3  
∃x e 1, 2–4  
∃v i 5  
∃u i 6  
9b. S → ∃xQ(x) ` ∃(S → Q(x))  
4
1.  
2.  
S → ∃xQ(x)  
S ∨ ¬S  
S
premise  
LEM  
3.  
assumption  
→ e 2, 3  
assumption  
copy 3  
4.  
∃xQ(x)  
x0 Q(x0)  
S
5.  
6.  
7.  
Q(x0)  
copy 5  
8.  
S → Q(x0)  
→ i 6, 7  
9.  
∃x(S → Q(x)) ∃x i 8  
10.  
11.  
12.  
13.  
14.  
15.  
16.  
17.  
∃x(S → Q(x)) ∃x e 4, 5–9  
¬S  
S
assumption  
assumption  
¬ e 11, 12  
⊥ e 13  
⊥
Q(x0)  
S → Q(x0)  
→ i 12–14  
∃x(S → Q(x)) ∃x i 15  
∃x(S → Q(x)) ∨ e 2, 3–10, 11–16  
5
pdf 6 trang baolam 10940 Free
Download
Bạn đang xem tài liệu "Tài liệu Cấu trúc rời rạc cho khoa học máy tính - Chapter 1B: Predicate Logic", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdftai_lieu_cau_truc_roi_rac_cho_khoa_hoc_may_tinh_chapter_1b_p.pdf