wyk cz1 , Uczelnia
[ Pobierz całość w formacie PDF ]
AnalizaMatematyczna
Antoni Miczko
2004/2005
1 Wiadomo±ci przygotowawcze
1.1 Elementy rachunku zda« i kwantyfikatorów
1.1.1 Intuicyjny model rachunku zda«
Zdania proste i zło»one
Poj¦ciami pierwotnymi rachunku zda« logiki dwuwarto±ciowej s¡ zdania orzekaj¡ce i przy-
sługuj¡ce tym zdaniom przeciwstawne własno±ci prawdy albo fałszu. Niech L
2
b¦dzie klas¡
wszystkich zda« orzekaj¡cych p,q,r,... w logice dwuwarto±ciowej. Zatem zapis p 2 L
2
ozna-
cza,»epjestzdaniemorzekaj¡cym.Je»eliwzapisiep2L
2
niewi¡»emyzpokre±lonegozdania,
to mówimy, »e p jest zmienn¡ zdaniow¡.
Funkcj¦ warto±ciuj¡c¡ definiujemy nast¦puj¡co:
v : L
2
! {0,1}
p
7! v(p).
Funkcja ta przypisuje zdaniom ich warto±¢ logiczn¡ 0 lub 1, tzn. fałsz lub prawd¦. B¦dziemy
dalej pisa¢ krótko p=0 zamiast v(p)=0 i p=1 zamiast v(p)=1.
Oznaczamy symbolem _,^,),,,
odpowiednio spójnik „lub” - zwany alternatyw¡, „i” -
zwany koniunkcj¡, „je±li ...to ” - zwany implikacj¡, wtedy i tylko wtedy, gdy” - zwany równo-
wa»no±ci¡oraz„nieprawda,»e”-zwanynegacj¡.Ztychspójników(funktorówzdaniotwórczych)
i zda« orzekaj¡cych mo»emy budowa¢ zdania zło»one.
W logice matematycznej powy»sze spójniki nazywa si¦ funktorami zdaniotwórczymi i defi-
1
niuje si¦ je przy u»yciu funkcji warto±ciuj¡cej nast¦puj¡co:
p q p
_
q p
^
q p
)
q p
,
q
p
1 1 1
1
1
1
0
1 0 1
0
0
0
0
0 1 1
0
1
0
1
0 0 0
0
1
1
1
W oparciu o powy»sze spójniki i zdania proste p,q,r,... budujemy zdania zło»one.
W zdaniach
p
_
q
(
p
^
q
) poszczególne zdania
p
i
q
nazywamy
członami
alternatywy (koniunkcji).
W implikacji
p
)
q
zdanie
p
nazywamy
poprzednikiem
, a
q
nast¦pnikiem
.
Mówi si¦ te» o
członach
p
i
q
równowa»no±ci
p
,
q
.
Przykład 1.1 Oto przykład zdania zło»onego orzekaj¡cego: „Je»eli Janek jest studentem, to
je»eli nie jest prawd¡, »e Janek jest studentem, to Janek jest spadochroniarzem.” Przyjmuj¡c:
p - Janek jest studentem,
q - Janek jest spadochroniarzem,
mo»na powy»sze zdanie zapisa¢ krótko:
(Sc) p)(
p)q).
Podobnieprzyjmuj¡cpiq jakwy»ej,zdanie„Je»elizfaktu,»eJanekniejeststudentem,wynika,
»e Janek jest studentem, to Janek jest studentem” mo»na zapisa¢ krócej:
(Cl)
(
p)p))p.
Tautologie rachunku zda«
Zdanie, które staje si¦ zdaniem prawdziwym bez wzgl¦du na to, jakie warto±ci logiczne
przyjmuj¡ zdania składowe, nazywamy tautologiami albo prawami rachunku zda«.
Przykład 1.2 W zastosowaniach logiki matematycznej pierwszorz¦dn¡ rol¦ odgrywaj¡ prawa
de Morgana:
(M
1
)
(p
_
q)
,
p
^
q (M
2
)
(p
^
q)
,
p
_
q
Prawdziwo±ci tych tautologii dowiedziemy tzw. metod¡
zero - jedynkow¡
: wyka»emy zatem, »e
powy»sze zdania (
M
1
)
,
(
M
2
) pozostaj¡ prawdziwe przy dowolnym układzie zer i jedynek jakie funkcja
warto±ciuj¡ca mo»e przypisa¢ zdaniom
p
i
q
. Najwygodniej posłu»y¢ si¦ tutaj tabelk¡:
p q p
_
q
(p
_
q)
p
q
p
^
q ...
,
...
1 1 1
0
0 0
0
1
(M
1
)
1 0 1
0
0 1
0
1
0 1 1
0
1 0
0
1
0 0 0
1
1 1
1
1
Analogicznie dowodzimy prawdziwo±ci drugiego prawa de Morgana:
p q p
_
q
(p
^
q)
p
q
p
_
q ...
,
...
1 1 1
0
0 0
0
1
(M
2
)
1 0 0
1
0 1
1
1
0 1 0
1
1 0
1
1
0 0 0
1
1 1
1
1
2
Przykład 1.3 Identyczn¡ metod¡ (zero - jedynkow¡) mo»na wykaza¢, »e zdania z Przykładu 1
s¡ prawdziwe, bo zdania (Sc),(Cl) s¡ tautologiami rachunku zda« i nosz¡ odpowiednio nazwy:
prawo Scotusa
i
prawo Claviusa
.
Reguła podstawiania i reguła odrywania
Zokre±leniaspójnikówlogicznychwynikaszeregregułdowodzenia.Wyró»nimydwieznich:
Reguła podstawiania. Głosi ona, »e ze zdania prawdziwego wolno wywie±¢ nowe zdanie (praw-
dziwe), które powstaje z tego pierwszego przez konsekwentne zast¡pienie wszystkich zda« skła-
dowych zdaniami prawdziwymi.
Przykład 1.4 Poniewa» zdanie
(Ws)
p_
p
(prawo wył¡czonego ±rodka) jest tautologi¡ wi¦c słuszne jest np. zdanie
p)(q )p)_
(p)(q )p)).
Reguła odrywania. Reguła ta wynika z okre±lenia implikacji: Je»eli implikacja
)
jest
zdaniem prawdziwym i
jest zdaniem prawdziwym, to
jest równie» zdaniem prawdziwym.
Przykład 1.5 Przyjmuj¡c za prawdziwe zdanie „Je»eli Janek uko«czył 18 lat, to Janek jest
człowiekem dorosłym” oraz wiedz¡c, »e Janek ulo«czył 18 lat stwierdzamy, »e „Janek jest czło-
wiekiem dorosłym”.
Funkcje zdaniowe
Niech dany b¦dzie zbiór X 6=;. Wyra»enie '(·), które staje si¦ albo zdaniem prawdziwym
albo fałszywym dla ka»dego x2X nazywamy funkcj¡ zdaniow¡ jednej zmiennej:
' : X ! L
2
x 7! '(x).
Zbiórtychwszystkichx2X,dlaktórychzdanie'(x)jestprawdziwe(w('(x))=1)oznaczamy
{x2X :'(x)}.
* Analogicznie okre±lamy funkcj¦ zdaniow¡ 2 - zmiennych:
'
:
X
×
Y
! L
2
(
x,y
)
7!
'
(
x,y
)
oraz funkcj¦ zdaniow¡
n
- zmiennych:
'
:
X
1
×
X
2
×
...
×
X
n
!
L
2
(
x
1
,x
2
,...,x
n
)
7!
'
(
x
1
,x
2
,...,x
n
)
3
Kilka wa»niejszych praw rachunku zda«
1. p)(q )p) prawo symplifikacji
2. (p)(q )r)))((p)q))(p)r)) prawo Fregego
3. p)(
p)q)
prawo Scotusa
4. (
p)p))p
prawo Claviusa
5.
(
p),p
pr. podwójnego przeczenia
6. p_
p
pr. wył¡czonego ±rodka
7.
(p^
p)
pr. sprzeczno±ci
8. p)p
pr. to»samo±ci implikacji
9. p,p
pr. to»samo±ci równowa»no±ci
10.
(p_q),
p^
q
pr. de Morgana
11.
(p^q),
p_
q
pr. de Morgana
12. w((
p)p))p)=1
pr. sprowadzania do niedorzeczno±ci
13. p_(q_r),(p_q)_r
ł¡czno±¢ alternatywy
14. p^(q^r),(p^q)^r
ł¡czno±¢ koniunkcji
15. p^(q_r),(p^q)_(p^r)
rozdzielno±¢ kon. wzgl. altern.
16. p_(q^r),(p_q)^(p_r)
rozdzielno±¢ alternatywy wzgl. kon.
17. p_p,p, p^p,p
pr. tautologii
18. p_0,p, p^0,0
19. p_1,p, p^1,1
pr. pochłaniania
20. p_q ,q_p
przemienno±¢ alternatywy
21. p^q ,q^p
przemienno±¢ koniunkcji
22. (p)q),
q )
p
pr. kontrapozycji
23.
(p)q),p^
q
pr. negacji implikacji
24. [(p)q)^(q )r)])(p)r)
pr. sylogizmu
1.2 Klasyczny rachunek kwantyfikatorów
Kwantyfikator ogólny i szczegółowy
Wlogice opróczfunktorówzdaniotwórczychwa»n¡rol¦odgrywaj¡kwantyfikatoryalboina-
czej predykaty.
Funkcji zdaniowej '(x),x2X mo»na przyporz¡dkowa¢ zdania:
1
o
Istnieje x2X, które spełnia funkcj¦ zdaniow¡ ', tzn prawdziwe jest zdanie '(x).
2
o
Ka»dy element x 2 X spełnia funkcj¦ ', tzn. zdanie '(x) jest prawdziwe dla ka»dego
x2X.
Słowo istnieje identyfikujemy z kwantyfikatorem szczegółowym a zwrot dla ka»dego - uto»-
samiamy z kwantyfikatorem ogólnym.
Je»eli'jestfunkcj¡zdaniow¡jednejzmiennejx2X,topodstawowezdaniabudowaneprzy
u»yciu tej funkcji zdaniowej oraz kwantyfikatorów maj¡ posta¢:
Zdanie z kwantyfikatorem
Nazwa
Symbolika polska Symbolika anglosaska Czyta si¦
W
szczegółowym
x
'(x)
9
x
'(x)
„istnieje x, »e '(x)”.
V
ogólnym
x
'(x)
8
x
'(x)
„dla ka»dego x, '(x)”.
4
Zdanie „istn.
x
,
'
(
x
)” czytamy „istnieje
x
takie, »e
'
(
x
)” i rozumiemy, »e zdanie
'
(
x
) jest wtedy
prawdziwe. Podobnie, zdanie „dla ka»dego
x
,
'
(
x
) ” rozumiemy, »e „dla ka»dego
x
zdanie
'
(
x
)
jest prawdziwe.
Jestoczywiste,»ezdanie:„Istnieje
x
X
,»e
'
(
x
)”jestzdaniemprawdziwymw.it.w.,gdy{
x
:
'
(
x
)}6=;
2
i analogicznie zdanie : „dla ka»dego
x,'
(
x
) ” jest zdaniem prawdziwym w. i t. w., gdy {
x
:
'
(
x
)}=
X
.
Je»eli µ jest funkcj¡ zdaniow¡ (jednej zmiennej) x 2 X, to mo»na budowa¢ zdania przy
u»yciu funktorów i kwantyfikatorów o ograniczonym zakresie, przyjmuj¡c
8
µ(x)
'(x),8
x
(µ(x))'(x)),
9
µ(x)
'(x),9
x
(µ(x)^'(x)].
Działania 9 i 8 mo»na uwa»a¢ za uogólnienie alternatywy i koniunkcji zda«. Je±li bowiem
zakres zmienno±ci
x
jest sko«czony i
X
={
x
1
,x
2
,...,x
n
}, to
9
x2X
f
(
x
),
f
(
x
1
)_
f
(
x
2
)_
...
_
f
(
x
n
)
,
1)
8
x2X
f
(
x
),
f
(
x
1
)^
f
(
x
2
)^
...
^
f
(
x
n
)
,
1)
Poj¦cie kwantyfikatora uogólnia si¦ w naturalny sposób na przypadek funkcji zdaniowych
dwu i wi¦cej zmiennych.
Przykład 1.6 Oto przykłady zda« zbudowanych przy u»yciu funkcji dwu zmiennych i kwanty-
fikatorów:
8
x2X
9
y2Y
'(x,y), 9
x2X
8
y2Y
'(x,y),
8
x2X,y2Y
'(x,y),...
Wybrane prawa rachunku kwantyfikatorów
Dla funkcji ' jednej zmiennej x mamy:
Prawo Nazwa
8
x
'(x)
,9
x
'(x) Pr. de Morgana
9
x
'(x)
,8
x
'(x) Pr. de Morgana
8
x2X
'(x))9
x2X
'(x)
Dla funkcji ' dwu zmiennych x,y mamy np. prawa:
1 8
x
8
y
'(x,y)),9
y
8
x
'(x,y)
2 9
x
9
y
,9
y
,9
x
'(x,y)
3 9
y
8
x
'(x,y)))8
x
9
y
'(x,y)
Przykład 1.7 Niech x,y 2N. Wtedy ma miejsce równowa»no±¢:
a)
9
y
8
x
y ¬x,8
x
9
y
y ¬x.
Jest te» prawdziwa (zgodnie z prawem 3)) implikacja:
b)
9
y
8
x
x¬y )8
x
9
y
x¬y.
Jednak nieprawdziwe jest wnioskowanie:
c)
8
x
9
y
x¬y )9
y
8
x
x¬y.
5
[ Pobierz całość w formacie PDF ]