Temat17 rozwiazania

[ Pobierz całość w formacie PDF ]
ROZWIĄZANIA ĆWICZEŃ
DOWODZENIE I: REGUŁY
∀
ELIM ORAZ
∃
WPR
Ćwiczenie 17.I.
Uzupełnij brakujące informacje.
(a)
(b)
1.
Ca
Zał.
1.
∀
x
Ax
Zał.
2.
Db
∧
Aa
Zał.
2.
~
∃
x
(
Bx
∧
Ax
)
Zał.
3.
Aa
∧
Elim 2
3.
∀
x
Ax
∧
~
∃
x
(
Bx
∧
Ax
)
∧
Wpr 1, 2
4.
Aa
∧
Ca
∧
Wpr 3, 1
4.
~
∃
x
(
Bx
∧
Ax
)
∧
∀
x
Ax
∧
Wpr 2, 1
(c)
(d)
1.
∀
x
Ax
∧
∃
x
Bx
Zał.
1.
∀
x
Ax
Zał.
2.
∀
x
(
Cx
∧
Dx
)
Zał.
2.
∃
x
Bx
Zał.
3.
∀
x
Ax
∧
Elim
1
3.
∀
x
Ax
∧
∃
x
Bx
∧
Wpr 1, 2
4.
∃
x
Bx
∧
Elim 1
4.
∃
x Bx
∧
(
∀
x Ax
∧
∃
x Bx
)
∧
Wpr 2, 3
(e)
(f)
1.
∀
x
Ax
∧
∃
x
Bx
Zał.
1.
~
∀
x
Ax
∧
∃
x
Bx
Zał.
2.
∃
x
Bx
→
∀
x
Cx
Zał.
2.
∃
x
Bx
∨
∀
x
Ax
Zał.
3.
∃
x
Bx
∧
Elim 1
3. ~
∀
x
Ax
∧
Elim 1
4.
∀
x
Cx
→
Elim 2, 3
4.
∃
x
Bx
∨
Elim 2, 3
(g)
(h)
1.
(
∀
x Ax
∨
Ba
)
≡
∀
xCx
Zał.
1.
~
∀
x
Ax
∨
∃
x
Bx
Zał.
2.
Ba
Zał.
2.
~~
∀
x
Ax
Zał.
3.
∀
x
Ax
∨
Ba
∨
Wpr 2
3.
∃
x
Bx
∨
Elim 1, 2
4.
∀
x
Cx
≡
Elim 1, 3
4.
∃
x
Bx
∧
~~
∀
x
Ax
∧
Wpr 3, 2
Ćwiczenie 17.II.
Przeprowadź następujące dowody.
(a) Dowieść, że:
∀
(b) Dowieść, że:
x
Ax
→
(
∃
x
Bx
∧
∀
x
Cx
)
~
∀
x
Ax
1.
∀
x
Ax
→
∀
x
Cx
Zał.
1.
∀
x
Ax
→
∃
x
Bx
Zał.
2.
∀
x
Ax
→
∃
x
Bx
Zał.
2.
∀
x
Ax
→
~
∃
x
Bx
Zał.
3.
∀
x
Ax
Zał. (
→
Wpr)
3.
∀
x
Ax
Zał. (~Wpr)
4.
∃
x
Bx
→
Elim 2, 3
4.
∃
x
Bx
→
Elim 1, 3
5.
∀
x
Cx
→
Elim 1, 3
5.
~
∃
x
Bx
→
Elim 2, 3
6.
∃
x
Bx
∧
∀
x
Cx
∧
Wpr 4, 5
6.
~
∀
x
Ax
~Wpr 3–4, 3–5
7.
∀
x
Ax
→
(
∃
x
Bx
∧
∀
x
Cx
)
→
Wpr 3–6
© Katarzyna Paprzycka
R17-1
Samouczek logiki zdań. Rozwiązania ćwiczeń
(wersja wstępna)
Wszelkie prawa zastrzeżone
Uwagi proszę kierować na adres:
Katarzyna.Paprzycka@swps.edu.pl
(c) Dowieść, że:
(
(d) Dowieść, że:
∃
x
Bx
→
∀
x
Cx
)
→
(
∀
x
Ax
→
∀
x
Cx
)
~~
∀
x
Cx
1.
∀
x
Ax
→
∃
x
Bx
Zał.
1.
(
∀
x
Cx
∧
∃
x
Bx
)
∧
∀
x
Ax
Zał.
2.
∃
x
Bx
→
∀
x
Cx
Zał. (
→
Wpr)
2.
~
∀
x
Cx
Zał. (~Wpr)
3.
∀
x
Cx
∧
∃
x
Bx
∧
Elim 1
3.
∀
x
Ax
Zał. (
→
Wpr)
4.
∀
x
Cx
∧
Elim 3
4.
∃
x
Bx
→
Elim 1, 3
5.
~
∀
x
Cx
R 2
5.
∀
x
Cx
→
Elim 2,4
6. ~~
∀
x
Cx
~Wpr
2-4,
2-5
6.
∀
x
Ax
→
∀
x
Cx
→
Wpr 3–5
7.
(
∃
x
Bx
→
∀
x
Cx
)
→
x
Cx
)
→
Wpr 2–6
→
(
∀
x
Ax
→
∀
Elim.I.
Zdecyduj, w których wypadkach wolno zastosować regułę
∀
∀
Elim i w tych wypadkach ją zastosuj
podstawiając stałą indywiduową
a
za zmienną
x
.
(a)
(b)
1.
∀
x
Ax
Zał.
1.
~
∀
x
Ax
Zał.
2.
Aa
∀
Elim 1
2.
XXX
(c)
(d)
1.
∀
x
~
Ax
Zał.
1.
~
∀
x
~
Ax
Zał.
2. ~
Aa
∀
Elim 1
2.
XXX
(e)
(f)
1.
∀
x
(
Ax
∨
Bx
)
Zał.
1.
∀
x
Ax
∨
Bb
Zał.
2.
Aa
∨
Ba
∀
Elim 1
2.
XXX
(g)
(h)
1.
∀
x
Ax
∨
∀
xBx
Zał.
1.
~
∀
x
(
Ax
∨
Bx
)
Zał.
2.
XXX
2.
XXX
(i)
(j)
1.
∀
x
~(
Ax
∨
Bx
)
Zał.
1.
∀
x
(~(
Ax
∨
Bx
)
→
Cx
)
Zał.
2.
~(
Aa
∨
Ba
)
∀
Elim 1
2.
(~(
Aa
∨
Ba
)
→
Ca
)
∀
Elim 1
(k)
(l)
1.
∀
x
~(
Ax
∨
Bx
)
→
∀
x
Cx
Zał.
1.
∀
x
((
Ax
∨
Bx
)
∧
Cx
)
∧
Da
Zał.
2.
XXX
2.
XXX
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 17. Dowodzenie
R17-2
Ćwiczenie
Elim.II.
W następujących dowodach brakuje dokładnie jednego kroku, aby dowieść
wniosku znajdującego się w ostatnim wierszu. Należy uzupełnić brakujący krok, uzasadnić go, oraz
uzasadnić krok ostatni:
(a)
∀
(b)
1.
∀
x
(
Cx
→
Bx
)
Zał.
1.
Cd
∨
Bd
Zał.
2.
Ca
Zał.
2.
∀
x
~
Cx
Zał.
3.
Ca
→
Ba
∀
Elim 1
3. ~
Cd
∀
Elim 2
4.
Ba
→
Elim 3, 2
4.
Bd
∀
Elim 1
(c)
(d)
1.
∀
x
Cx
∨
∀
x
Ax
Zał.
1.
Bb
→
Cd
Zał.
2.
~
∀
x
Cx
Zał.
2.
∀
x
Bx
Zał.
3.
∀
x
Ax
∨
Elim 1, 2
3.
Bb
∀
Elim 2
4.
Ab
∀
Elim 3
4.
Cd
→
Elim 2, 3
(e)
(f)
1.
∀
x
Ax
→
∀
x
Cx
Zał.
1.
∀
x
A
x
Zał.
2.
∀
x
Ax
Zał.
2.
∀
x
Bx
Zał.
3.
∀
x
Cx
→
Elim 1, 2
3.
Ad
∀
Elim 1
4.
Cd
∀
Elim 3
4.
Ad
∧
∀
x
Bx
∧
Wpr 3, 2
Elim.III.
W następujących dowodach brakuje dokładnie dwóch kroków, aby dowieść
wniosku znajdującego się w ostatnim wierszu. Należy uzupełnić brakujące kroki, uzasadnić je, oraz
uzasadnić krok ostatni:
(a)
∀
(b)
1.
∀
x
(
Ax
→
Bx
)
Zał.
1.
∀
x
(
Ax
∨
Bx
)
Zał.
2.
Aa
Zał.
2.
∀
x
~
Ax
Zał.
3.
Aa
→
Ba
∀
Elim 1
3. ~
Ad
∀
Elim 2
4.
Ba
→
Elim 3, 2
4.
Ad
∨
Bd
∀
Elim 1
5.
Aa
∧
Ba
∧
Wpr 2, 4
5.
Bd
∨
Elim 4, 3
(c)
(d)
1.
∀
x
[(
Cx
→
Bx
)
≡
Cx
]
Zał.
1.
∀
x
[(
Cx
∨
Bx
)
→
Ax
]
Zał.
2.
Cb
Zał.
2.
Be
Zał.
3.
(
Cb
→
Bb
)
≡
Cb
∀
Elim 1
3.
(
Ce
∨
Be
)
→
Ae
∀
Elim 1
4.
Cb
→
Bb
≡
Elim 3, 2
4.
Ce
∨
Be
∨
Wpr 2
5.
Bb
→
Elim 4, 2
5.
Ae
→
Elim 3, 4
(e)
(f)
1.
∀
x
Ax
Zał.
1.
∀
x
~
Dx
Zał.
2.
∀
x
~
Bx
Zał.
2.
∀
x
Bx
Zał.
3.
Ab
∀
Elim 1
3.
~Da
∀
Elim 1
4.
~Ba
∀
Elim 2
4.
~Da
∨
Db
∨
Wpr 3
5.
Ab
∧
~
Ba
∧
Wpr 3, 4
5.
(
~Da
∨
Db
)
∧
∀
xBx
∧
Wpr 4, 2
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 17. Dowodzenie
R17-3
Ćwiczenie
Ćwiczenie
Ćwiczenie
∀
Elim.IV.
Proszę skonstruować następujące dowody:
(a)
(b)
Dowieść, że:
Ba
→
Ca
Dowieść, że: (
Aa
∧
Ba
)
→
Ca
1.
∀
x
((
Ax
∨
Bx
)
→
Cx
)
Zał.
1.
∀
x
((
Ax
∨
Bx
)
→
Cx
)
Zał.
2.
Ba
Zał. (
→
Wpr)
2.
Aa
∧
Ba
Zał. (
→
Wpr)
3. (
Aa
∨
Ba
)
→
Ca
∀
Elim 1
3.
Aa
∧
Elim 2
4.
Aa
∨
Ba
∨
Wpr 2
4.
(
Aa
∨
Ba
)
→
Ca
∀
Elim 1
5.
Ca
→
Elim 3, 4
5.
Aa
∨
Ba
∨
Wpr 3
6.
Ba
→
Ca
→
Wpr 2–5
6.
Ca
→
Elim 4, 5
7. (
Aa
∧
Ba
)
→
Ca
→
Wpr 2–6
(c)
Dowieść, że: ~
Aa
(d)
Dowieść, że: (
Ab
∧
Bb
)
→
Cb
1.
∀
x
(
Ax
→
Cx
)
Zał.
1.
∀
x
(
Ax
→
Cx
)
Zał.
2.
∀
x
~
Cx
Zał.
3.
Aa
→
Ca
∀
Elim 1
2.
Ab
∧
Bb
Zał. (
→
Wpr)
4. ~Ca
∀
Elim 2
3. Ab
→
Cb
∀
Elim 1
5.
~Aa
M.T. 3, 4
4. Ab
∧
Elim 2
5.
Cb
→
Elim 3,4
6.
(
Ab
∧
Bb
)
→
Cb
→
Wpr 2–5
(e)
Dowieść, że: (
Ab
∨
Bb
)
→
Cb
(f)
Dowieść, że:
Ad
→
Cd
1.
∀
x
(
Ax
→
Cx
)
Zał.
1.
∀
x
(
Ax
→
Bx
)
Zał.
2.
∀
x
(
Bx
→
Cx
)
Zał.
2
∀
x
(
Bx
→
Cx
)
Zał.
3.
Ab
∨
Bb
Zał. (
→
Wpr)
3.
Ad
Zał. (
→
Wpr)
4.
Ad
→
Bd
∀
Elim 1
4.
Ab
Zał. (
∨
Elim)
5.
Bd
→
Cd
∀
Elim 2
5.
Ab
→
Cb
∀
Elim 1
6.
Bd
→
Elim 4,3
6.
Cb
→
Elim 5, 4
7.
Cd
→
Elim 5,6
8.
Ad
→
Cd
→
Wpr 3–7
7.
Bb
Zał. (
∨
Elim)
8.
Bb
→
Cb
∀
Elim 2
9.
Cb
→
Elim 8, 7
10.
Cb
∨
Elim 3, 4-6, 7-9
11.
(
Ab
∨
Bb
)
→
Cb
→
Wpr 2–5
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 17. Dowodzenie
R17-4
Wpr.Ia.
Zdecyduj, w których wypadkach wolno zastosować regułę
∃
∃
Wpr.
(a)
(b)
1.
Aa
Zał.
1. ~
Aa
Zał.
2.
∃
x
Ax
∃
Wpr 1
2.
∃
x
~
Ax
∃
Wpr 1
(c)
(d)
1. ~
Aa
Zał.
1.
Aa
∨
Ba
Zał.
2.
~
∃
x
Ax
XXX
2.
∃
x
(
Ax
∨
Bx
)
∃
Wpr 1
(e)
(f)
1.
Aa
∧
Ba
Zał.
1.
Aa
∨
Ba
Zał.
2.
∃
x
Ax
∧
Ba
XXX
2.
∃
x
Ax
∧
∃
x
Bx
XXX
(g)
(h)
1.
Aa
→
(
Ba
→
Cb
)
Zał.
1.
Aa
→
(
Ba
→
Cb
)
Zał.
2.
Aa
→
(
Ba
→
∃
x
Cx
)
XXX
2.
∃
x
(
Ax
→
(
Bx
→
Cb
))
∃
Wpr 1
(i)
(j)
1.
Aa
→
(
Ba
→
Cb
)
Zał.
1.
~~Aa
Zał.
2.
∃
x
(
Aa
→
(
Ba
→
Cx
))
∃
Wpr 1
2.
~
∃
x ~Ax
XXX
Wpr.Ib.
Uzupełnij brakujące informacje:
∃
(a)
(b)
1.
Aa
Zał.
1.
~Aa
Zał.
2.
∃
x
Ax
∃
Wpr 1
2.
∃
x
~
Ax
∃
Wpr 1
(c)
(d)
1.
Aa
∧
Ba
Zał.
1.
~(
Aa
→
Ba
)
Zał.
2.
∃
x
(
Ax
∧
Bx
)
∃
Wpr 1
2.
∃
x
~(
Ax
→
Bx
)
∃
Wpr 1
(e)
(f)
1.
Aa
∧
Bb
Zał.
1.
~(
Aa
→
Bb
)
Zał.
2.
∃
x
(
Ax
∧
Bb
)
∃
Wpr 1
2.
∃
x
~(
Ax
→
Bb
)
∃
Wpr 1
3.
∃
x
(
Aa
∧
Bx
)
∃
Wpr 1
3.
∃
x
~(
Aa
→
Bx
)
∃
Wpr 1
Ćwiczenie
∃
Wpr.Ic.
1.
Aa
∧
Bc
Zał.
2.
∃
x
Ax
∧
Bc
∃
Wpr 1
Ani krok 2, ani krok 3 nie jest uprawniony. Rezultatem wprowadzenia partykularyzacji może być tylko
partykularyzacja, a zdanie w kroku 2 jest koniunkcją. Regułę
3.
∃
x
Ax
∧
∃
x
Bx
∃
Wpr 2
∃
Wpr można zastosować do zdania
Aa
∧
Bc
, ale rezultatem będzie wówczas
∃
x
(
Ax
∧
Bc
) lub
∃
x
(
Aa
∧
Bx
). Analogicznie sprawa się
przedstawia z krokiem 3.
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 17. Dowodzenie
R17-5
Ćwiczenie
Ćwiczenie
[ Pobierz całość w formacie PDF ]