Rwracjerr1314, Logika inf, Logika

[ Pobierz całość w formacie PDF ]
Rozdział 1
Relacje
W poprzednim rozdziale wiele uwagi po±wi¦cili±my poj¦ciu
własno±ci
elementu
1
. Za po-
moc¡ własno±ci deﬁniowali±my podzbiory (zło»one z tych elementów, które posiadaj¡ dan¡
własno±¢).
Ale poj¦cie własno±ci mo»na odnie±¢ nie tylko do pojedynczych elementów, ale do par,
trójek, etc. elementów. Dla przykładu:
„x jest »on¡ y”
jest własno±ci¡, przysługuj¡c¡ pewnym
parom
ludzi, wyró»niaj¡c¡ mał-
»e«stwa ze zbioru wszystkich par.
„x jest numerem konta bankowego y”
jest własno±ci¡ przysługuj¡c¡ pewnym parom, w
których pierwszym elementem jest liczba (nr konta), a drugim elementem jest ci¡g liter
j¦zyka polskiego (imi¦ i nazwisko wła±ciciela konta).
Za pomoc¡ „własno±ci par” b¦dziemy opisywali relacje (binarne).
U»ycie słowa „para” a nie „zbiór dwuelementowy” nie jest przypadkowe;
- mówi¡c o zbiorze dwuelementowym nie okre±lamy porz¡dku jego elementów,
- mówi¡c o parze wskazujemy, który element jest pierwszym elementem pary, a który drugim.
Przykład 1.0.1.
Formuła „x jest »on¡ y” opisuje własno±¢ pary, a nie zbioru dwuelementowego gdy» stwier-
dzenie „Anna jest »on¡ Jana” ma sens a „Jan jest »on¡ Anny” nie ma.
W teorii zbiorów poj¦cie pary deﬁniujemy tak:
Deﬁnicja 1.0.1.
Par¡ uporz¡dkowan¡ nazywamy zbiór postaci
(
x,y
) =
{{
x
}
,
{
x,y
}}
Element x nazywamy wówczas pierwszym elementem pary („poprzednikiem”), a y - drugim
(„nast¦pnikiem”).
Zadanie 1.0.1.
Korzystaj¡c z deﬁnicji równo±ci zbiorów poka», »e
(
a,b
) = (
c,d
)
wtw
(
a
=
c
)
^
(
b
=
d
)
(szczególnie ostro»nie rozpatrz przypadek a
=
b !)
Poka», »e je»eli elementy a i b s¡ ró»ne, to
{
a,b
}
=
{
b,a
}
ale
(
a,b
)
6
= (
b,a
)
.
1
„Własno±¢” rozumiemy tu jako „cech¦” (obiektu, kilku obiektów) a nie „co±, co posiadamy”.
1
ROZDZIAŁ 1.
RELACJE
2
Ta deﬁnicja jest... „do szybkiego zapomnienia”. O parze uporz¡dkowanej my±limy raczej jako
o „ci¡gu długo±ci 2” - z elementem pierwszym i drugim. T¦ deﬁnicj¦ podali±my jako przykład
superpoprawnej deﬁnicji matematycznej - odwołali±my si¦ w niej jedynie do wcze±niej zdeﬁnio-
wanego poj¦cia zbioru. Natomiast mówi¡c: „para to ci¡g duwelementowy” odwołujemy si¦ do
intuicyjnie jasnej, lecz dot¡d (w tym wykładzie) wci¡» nieformalnej deﬁnicji „ci¡gu”.
„Mo»emy zapomnie¢” o tej deﬁnicji, je»eli chcemy tylko posługiwa¢ si¦ poj¦ciem pary, ale po-
winni±my pami¦ta¢, je»eli chcemy zachowa¢ matematyczn¡ ±cisło±¢.
Dla dowolnych zbiorów
A
i
B
mo»emy my±le¢ o zbiorze wszystkich takich par, ktorych
pierwszy element (poprzednik) jest ze zbioru
A
i drugi (nast¦pnik) ze zbioru
B
. Taki zbiór
to
iloczyn kartezja«ski
zbiorów
A
i
B
. Formalnie:
Deﬁnicja 1.0.2.
Niech A,B b¦d¡ dowolnymi zbiorami. Iloczynem kartezja«skim zbiorów A i B nazywamy
zbiór oznaczany symbolem A
×
B , który deﬁniujemy nast¦puj¡co:
A
×
B
=
{
(
a,b
) :
a
2
A,b
2
B
}
St¡d
(
)
(
a,b
)
2
A
×
B
,
a
2
A
^
b
2
B
Przykład 1.0.2.
Je»eli A
=
{
a,b,c,d
}
a B
=
{
1
,
2
,
3
}
, to
A
×
B
=
{
(
a,
1)
,
(
a,
2)
,
(
a,
3)
,
(
b,
1)
,
(
b,
2)
,
(
b,
3)
,
(
c,
1)
,
(
c,
2)
,
(
c,
3)
,
(
d,
1)
,
(
d,
2)
,
(
d,
3)
}
ROZDZIAŁ 1.
RELACJE
3
Dlaczego „iloczyn kartezja«ski”?. Kartezjusz
2
był nie tylko wybitnym matematykiem, ale
wszechstronnie wykształconym badaczem, prekursorem nowo»ytnej kultury umysłowej. W trak-
tacie
„Lageometrie”
przedstawił ide¦ badania obiektów geometrycznych za pomoc¡ narz¦dzi
algebraicznych.
Zbiór liczb rzeczywistych
R
przyj¦to reprezentowa¢ jako prost¡ z wyró»nionym punktem 0 -
pozwala to identyﬁkowa¢ punkty tej prostej z liczbami rzeczywistymi. Idea Kartezjusza polegała
na przyporz¡dkowaniu punktom płaszczyzny
pary
liczb - jego „współrz¦dnych” w odpowied-
nim układzie współrz¦dnych. W ten sposób płaszczyzna została uto»samiona z ... iloczynem
kartezja«skim dwóch prostych rzeczywistych:
P
=
R×R
•
(
x,y
)
y
x
Warto te» pami¦ta¢, »e to Kartezjusz zacz¡ł pierwszy u»ywa¢ terminu „funkcja”...
Przykład 1.0.3.
Ekran monitora mo»na opisa¢ jako iloczyn kartezja«ski. Opisuj¡c jako±¢ monitora mówimy
o jego rozdzielczo±ci opisywanej np. symbolem
1920
×
1080
(Full HD). Mo»emy uzna¢, »e
modelem matematycznym takiego monitora jest iloczyn kartezja«ski
{
n
2
N
: 1
¬
1920
}×{
n
2
N
: 1
¬
n
¬
1080
}
Ka»dy element tego iloczynu kartezj«skiego to para wspołrz¦dnych pojedynczego piksela.
Je±li to zbyt skomplikowane to proponuj¦ prostszy przykład. Znana wszystkim gra w
okr¦ty wykorzystuje fakt, »e ka»de pole „obszaru bitwy” (planszy) mo»na zakodowa¢ za
pomoc¡ pary zło»onej z litery i liczby. Np. pozycja „A
1
” (czyli para
(
A,
1)
) to pole w górnym
lewym rogu obszaru bitwy.
A to oznacza, »e plansza zakodowana jest jako iloczyn kartezja«ski. Np. plansz¦-kwadrat
„pi¦¢ na pi¦¢” zakodujemy tak:
{
A,B,C,D,E
}×{
1
,
2
,
3
,
4
,
5
}
Zadanie 1.0.2.
Poka», wybieraj¡c odpowiednie zbiory A i B »e równo±¢ A
×
B
=
B
×
A
nie musi by¢ prawdziwa.
Poka», »e A
×;
=
;
.
Iloczyn kartezja«ski zbiorów mo»e pojawi¢ si¦ - obok symbolu sumy, przekroju, uzupeł-
nienia - w wyra»eniach boolowskich. Np. zapis
A
[
(
C
×
D
) jest wyra»eniem boolowskim.
2
Kartezjusz ( Rene Descartes) (1596 - 1650)– francuski ﬁlozof, matematyk i ﬁzyk.
ROZDZIAŁ 1.
RELACJE
4
Dowodz¡c równo±ci wyra»e« boolowskich w których wyst¦puje symbol iloczynu kartezja«-
skiego, musimy nieco zmodyﬁkowa¢ opisany wcze±niej sposób post¦powania. Przypomnijmy,
»e ogólna metoda polegała na zast¡pieniu równo±ci wyra»e« boolowskich
L
=
R
przez
równowa»no±¢
a
2
L
$
a
2
R
i przekształcaniu jej zgodnie z deﬁnicjami operacji na zbiorach.
Teraz dodamy now¡ reguł¦ do naszej procedury:
je»eli w trakcie przekształcania wyra»enia pojawi si¦ napis a
2
(
A
×
B
)
, to zmien-
n¡ przedmiotow¡ „a” nale»y zast¡pi¢ przez par¦
(
a
1
,a
2
)wewszystkichmiejscachjej
wyst¦powania
, a nast¦pnie dokona¢ przekształcenia zapisu:
a
2
A
×
B
(
a
1
,a
2
)
2
A
×
B
(
a
1
2
A
)
^
(
a
2
2
B
)
Przykład 1.0.4.
Rozwa»my równo±¢ A
×
(
B
[
C
) = (
A
×
B
)
[
(
A
×
C
)
Najpierw zast¦pujemy j¡ równowa»no±ci¡:
a
2
A
×
(
B
[
C
)
$
a
2
(
A
×
B
)
[
(
A
×
C
)
Zgodnie z nowoprzyj¦t¡ reguł¡ zast¦pujemy zmienn¡ a przez par¦
(
a
1
,a
2
)
:
(
a
1
,a
2
)
2
A
×
(
B
[
C
)
$
(
a
1
,a
2
)
2
(
A
×
B
)
[
(
A
×
C
)
Teraz przekształcamy osobno lew¡ i praw¡ stron¦ równowa»no±ci korzystajac z deﬁnicji ope-
racji na zbiorach. Lewa strona:
(
a
1
,a
2
)
2
A
×
(
B
[
C
)
(
a
1
2
A
)
^
(
a
2
2
B
[
C
)
(
a
1
2
A
)
^
((
a
2
2
B
)
_
(
a
2
2
C
))
Prawa strona:
(
a
1
,a
2
)
2
(
A
×
B
)
[
(
A
×
C
)
(
a
1
,a
2
)
2
A
×
B
_
(
a
1
,a
2
)
2
A
×
C
((
a
1
2
A
)
^
(
a
2
2
B
))
_
(
a
1
2
A
)
^
(
a
2
2
C
))
Teraz trzy ró»ne wyra»enia atomowe „a
1
2
A, a
2
2
B, a
2
2
C” zast¡pimy przez trzy ró»ne
zmienne zdaniowe p,q,r i utworzymy formuł¦ zdaniow¡:
(
p
^
(
q
_
r
))
$
((
p
^
q
)
_
(
p
^
r
))
o której łatwo dowie±¢, »e jest tautologi¡. Zatem pierwotna równo±¢
A
×
(
B
[
C
) = (
A
×
B
)
[
(
A
×
C
)
jest prawem rachunku zbiorów.
Przykład 1.0.5.
Rozwa»my równo±¢ A
×
B
=
B
×
A z Zadania 1.0.2 i przeanalizujmy j¡ zgodnie z nasz¡
procedur¡. Otrzymamy równowa»no±¢:
(
a
1
,a
2
)
2
A
×
B
$
(
a
1
,a
2
)
2
B
×
A
czyli
(
a
1
2
A
)
^
(
a
2
2
B
)
$
(
a
1
2
B
)
^
(
a
2
2
A
)
ROZDZIAŁ 1.
RELACJE
5
Teraz wyra»enia atomowe zast¡pimy przez cztery ró»ne zmienne zdaniowe i otrzymamy
formuł¦
(
p
^
q
))
$
(
r
^
s
)
A to oczywi±cie nie jest tautologia.
Udowodnienie drugiej równo±ci z Zadania 1.0.2 polega na pokazaniu, »e
(
x,y
)
2
A
×;
jest zdaniem zawsze fałszywym. Ale to chyba potraﬁsz uzasadni¢ samodzielnie.
Zadanie 1.0.3.
Udowodnij równo±ci zbiorów:
1. A
×
(
B
[
C
) = (
A
×
B
)
[
(
A
×
C
)
2. A
×
(
B
\
C
) = (
A
×
B
)
\
(
A
×
C
)
3.
(
A
×
B
)
\
(
C
×
D
) = (
A
\
C
)
×
(
B
\
D
)
4.
(
A
×
B
)
[
(
C
×
D
)
(
A
[
C
)
×
(
B
[
D
)
Poka», »e odwrotna inkluzja nie musi by¢ prawdziwa.
1.0.1
Relacje binarne
Własno±ci, w których opisie wyst¦puje jedna zmienna przedmiotowa wskazywały cechy („atry-
buty”) pojedynczych elementów. Np.
„x jest liczb¡ parzyst¡”
. Takie własno±ci wykorzysty-
wali±my do deﬁniowania podzbiorów.
2
N
=
{
x
2
N
:
x
jest liczb¡ parzyst¡
}
N
Własno±ci, które opisujemy wykorzystuj¡c dwie zmienne przedmiotowe deﬁniuj¡ podzbiory
iloczynu kartezja«skiego.
Przykład 1.0.6.
1. Własno±¢ „x jest wła±cicielem samochodu marki y” wyró»nia pod-
zbiór iloczynu kartezja«skiego Ludzie
×
Marki samochodów.
2. Zdanie (własno±¢) „x jest wi¦ksze od y ” opisuje podzbiór B
>
N
×
N
.
B
>
=
{
(
x,y
)
2
N
×
N
:
x > y
}
Np. para
(2
,
5)
2
B
>
a
(5
,
3)
2
B
>
.
3. Własno±¢ pary liczb rzeczywistych
(
x,y
)
: „suma kwadratów x i y nie jest wi¦ksza od
1
” opisuje podzbiór płaszczyzny - koło o ±rodku w punkcie
(0
,
0)
i promieniu
1
.
Podzbiory iloczynu kartezja«skiego nazywamy
relacjami
. Formalnie:
Deﬁnicja 1.0.3.
Relacj¡ binarn¡ (dwuargumentow¡) o poprzednikach ze zbioru A i nast¦pnikach ze zbioru B
nazywamy dowolny podzbiór iloczynu kartezja«skiego A
×
B.
Relacj¡ binarn¡ (dwuargumentow¡) na zbiorze A nazywamy dowolny podzbiór iloczynu
kartezja«skiego A
×
A .
Tak wi¦c zamiast mówi¢, »e „własno±ci opisane za pomoc¡ formuł z dwiema zmienny-
mi przedmiotowymi odpowiadaj¡ podzbiorom iloczynu kartezja«skiego” mo»emy mówi¢, »e
takie własno±ci odpowiadaj¡ relacjom binarnym.
[ Pobierz całość w formacie PDF ]

Rwracjerr1314, Logika inf, Logika

Tematy