代做IS 203 Exercise Set 5调试Haskell程序
- 首页 >> Algorithm 算法IS 203
Exercise Set 5
Exercise Sets should be completed through group work, but each student will submit their own solutions. The following problems must be submitted through the assignment page in Canvas by 11:59 pm on Sunday, September 29, 2024.
Exercise sets are distributed as Word files so students have an easier time using the assignment. To properly see some symbols, the document must be opened in Word. Students who prefer to print out the exercise set and write their answers (or write answers on a tablet directly onto a document or pdf) should first insert extra lines between questions and problems.
Items highlighted yellow must be complete before class on Monday.
Items highlighted blue must be complete before class on Wednesday.
Items highlighted pink must be complete before class on Friday.
Items with no highlighting are suggestions of when to complete work in order to complete the exercise set on time.
|
|
Problems to Submit
|
When to Complete |
|
Part 1 |
3 & 4 |
Monday
|
|
Part 2 |
|
Tuesday
|
|
Part 3 |
2 & 3 |
Wednesday
|
|
Part 4
|
|
Thursday |
|
Part 5
|
2 & 3 |
Friday |
|
Part 6 |
|
Sunday
|
Part 1: Proofs Using Universal Instantiation and Existential Generalization
Prove the following statements and theorems.
(∀x(Fx → Gx) ᴧ ∀x(Gx → Hx)) → (Fa → Ha)
1. Show(∀x(Fx → Gx) ᴧ ∀x(Gx → Hx)) → (Fa → Ha) 2-3 CD
2. Assume ∀x(Fx → Gx) ᴧ ∀x(Gx → Hx) Assumption CD
3. Show Fa → Ha 4-5 CD
4. Assume Fa Assumption CD
5. Show Ha 6-11 DD
6. ∀x(Fx → Gx) 2 Simp
7. ∀x(Gx → Hx) 2 Simp
8. Fa → Ga 6 UI
9. Ga → Ha 7 UI
10. Ga 4,8 MP
11. Ha 9,10 MP
2.¬(Fa ᴧ Ga) → ∃x(¬Fx v ¬Gx)
1. Show ¬(Fa ᴧ Ga) → ∃x(¬Fx v ¬Gx) 2-3 CD
2. Assume ¬(Fa ᴧ Ga) Assumption CD
3. Show ∃x(¬Fx v ¬Gx) 4-5 DD
4. ¬Fa ν ¬Ga 2 DM
5. ∃x(¬Fx v ¬Gx) 4 EG
3. ∀x¬(Fx → Gx) → (∃xFx ʌ ∃x¬Gx)
1.show ∀x¬(Fx → Gx) → (∃xFx ʌ ∃x¬Gx) 2-3 CD
2.Assume ∀x¬(Fx → Gx) Assumption CD
3. Show (∃xFx ʌ ∃x¬Gx) 4-10 DD
4. ∃aFa ʌ ∃a¬Ga 3 EI
5. ∃aFa 4 Simp
6. ∃a 5 SImp
7. Fa 5 Simp
8. ∃a¬Ga 5 Simp
9. ∃a 8 Simp
10. ¬Ga 8 Simp
4. ꓯxꓱy(Fx ↔ ¬Fy) → ꓱy(Fy ↔ ¬Fy)
1.Show ꓯxꓱy(Fx ↔ ¬Fy) → ꓱy(Fy ↔ ¬Fy) 2,3 CD
2.Assume ꓯxꓱy(Fx ↔ ¬Fy) Assumption CD
3. Show ꓱy(Fy ↔ ¬Fy) 4 DD
4. ꓱy(Fy ↔ ¬Fy) 2 UI
Part 2: Existential Instantiation
→Task: Watch lecture video 17.
Part 3: Proof Using Existential Instantiation
Prove the following statements and theorems.
1. ¬∃x(Fx ᴧ ¬Fx)
1. Show ¬∃x(Fx ᴧ ¬Fx) 2-3 CD
2. Assume ¬¬∃x(Fx ᴧ ¬Fx) Assumption CD
3. show ∃x(Fx ᴧ ¬Fx) 2 DN
4. Fa ᴧ ¬Fa 3 EI
5. Fa 4 Simp
6. ¬Fa 4 Simp
2. ∀x(Fx → Gx) → (∃xFx → ∃xGx)
1. Show (∀x(Fx → Gx) → (∃xFx → ∃xGx)) 2-3 CD
2. Assume ∀x(Fx → Gx) Assumption CD
3. Show ∃xFx → ∃xGx 4-5 CD
4. Assume ∃xFx Assumption CD
5. Show ∃xGx 6-9 DD
6. Fa 4 EI
7. Fa→ Ga 2 UI
8. Ga 6, 7 MP
9. ∃xGx 8 EG
3. ∀x(Fx → Gx) → (∃x¬Gx → ∃x¬Fx)
1.Show ∀x(Fx → Gx) → (∃x¬Gx → ∃x¬Fx) 2-3 CD
2.Assume ∀x(Fx → Gx) Assumption CD
3. Show (∃x¬Gx → ∃x¬Fx) 4-5 CD
4. Assume ∃x¬Gx Assumption CD
5. Show ∃x¬Fx 6-9 DD
6. Ga 4 EI
7. Ga →Fa 2 UI
8. Fa 6,7 MP
9. ∃x¬Gx 8 EG
Part 4: Quantifier Negation
→Task: Watch lecture video 18.
Part 5: Quantifier Negation
Prove the following theorems.
1. ∃x(Fx ν ¬Fx)
1. Show ∃x(Fx ν ¬Fx) 2-8 ID
2. Assume ¬∃x(Fx ν ¬Fx) Assumption ID
3. ꓯx¬(Fx ν ¬Fx) 2 QN
4. (Fa ν ¬Fa) 3 UI
5. ¬Fa ʌ ¬¬Fa 4 DM
6. ¬Fa 5 Simp
7. ¬¬Fa 5 Simp
8. Fa
2. ꓯx(Fx → Gx) → (ꓯxFx → ꓯxGx)
1.Show ꓯx(Fx → Gx) → (ꓯxFx → ꓯxGx) 2,3 CD
2.Assume ꓯx(Fx → Gx) Assumption CD
3. Show ꓯxFx → ꓯxGx 4, 5 CD
4. Assume ꓯxFx Assumption CD
5. Show ꓯxGx 6-11 CD
6. Assume ¬ ꓯxGx Assumption ID
7. ∃x¬ Gx 6 QN
8. ¬ Ga 7 EI
9. Fa → Ga 2 UI
10. Fa 4 UI
11. Ga 9, 10 MP
3. ꓱx(Fx ν Gx) → (ꓱxFx ν ꓱxGx) 2,3 CD
1.Show ꓱx(Fx ν Gx) → (ꓱxFx ν ꓱxGx) Assumption CD
2. Assume ꓱx(Fx ν Gx) 4-13 CD
3. Show (ꓱxFx ν ꓱxGx) Assumption ID
4. Assume ¬ (ꓱxFx ν ꓱxGx) 4 DM
5. ¬ ꓱxFx ᴧ ¬ ꓱxGx 5 Simp
6. ¬ ꓱxFx · 5 Simp
7. ¬ ꓱxGx 6 DM
8. ꓯx¬ Fx 7 DM
9. ꓯx¬ Gx 2 UI
10. Fa ν Ga 2 EI
11. ¬ Fx 8 UI
12. ¬ Gx 9 UI
13. Ga 10,11 DS
Part 6: Sets
→ Task: Watch lecture videos 19 and 20.