M. Nowak, Materialy do wykladu z logiki na kierunkach humanistycznych
Poj znaku
ecie
Definicja znaku Ch. S. Peirce a:
Znak jest to coś, co komuś zast coś innego pod pewnym wzgl lub
epuje edem
w pewien sposób.
Owo coś innego , czyli to, co jest zast
epowane przez znak, nazywane jest
przedmiotem odniesienia dla tego znaku lub przedmiotem, do którego znak si
e
odnosi.
Znaki dzieli si m.in. na naturalne i konwencjonalne. Wedlug jednego
e
z kryteriów podzialu, znaki naturalne to te, które nie s wytworem ludzkiej
a
cywilizacji; konwencjonalne znaki to te, które nie s naturalne. Wedlug
a
drugiego kryterium podzialu, znak naturalny to taki znak, iż mi nim a
edzy
jego przedmiotem odniesienia wyst naturalny zwiazek, tzn. nie ustalony
epuje
na mocy konwencji. Znak konwencjonalny to znak, którego zwiazek z przed-
miotem odniesienia ustalony jest na podstawie jakiejś umowy (niekoniecznie
spisanej czy uświadamianej). Na przyklad, ból po prawej dolnej stronie brzucha
jest, wedlug pierwszego jak i drugiego kryterium znakiem naturalnym (objawem,
symptomem) zapalenia wyrostka robaczkowego. Wyrażenie kot jest wedlug
obu kryteriów znakiem konwencjonalnym.
Znaki konwencjonalne zwane s symbolami.
a
Definicja znaczenia znaku K. Ajdukiewicza.
Znaczenie znaku to, wedlug K. Ajdukiewicza, sposób rozumienia znaku,
zależny od m.in. nast czynników:
epujacych
(1) typu przedmiotów odniesienia dla znaku,
(2) sposobu kojarzenia przedmiotów odniesienia ze znakiem,
(3) nastawienia uczuciowego do przedmiotów odniesienia.
Dysponuj poj znaku można definiować specjalne systemy znaków
ac eciem
jakimi s j
a ezyki.
Poj j
ecie ezyka
J wedlug lingwistyki matematycznej:
ezyk
Przez j o slowniku Ł rozumiemy dowolny niepusty zbiór skończonych
ezyk
ciagów symboli z Ł. Dowolny ciag symboli należ do j nazywamy wyra-
acy ezyka
żeniem tego j
ezyka.
Slownik jest to dowolny niepusty zbiór symboli.
J polski jest pewnym zbiorem skończonych ciagów symboli. Symbolem
ezyk
jest tu pojedyńczy wyraz lub znak interpunkcyjny, zaś slownikiem zbiór wszys-
tkich wyrazów oraz znaków interpunkcyjnych.
1
Kategorie syntaktyczne w j naturalnym (etnicznym)
ezyku
W literaturze istnieje precyzyjna, lecz nieoperacyjna (tzn. niestosowalna
w pewnych przypadkach) definicja kategorii (typu syntaktycznego) wedug K.
Ajdukiewicza:
Definicja kategorii syntaktycznej
Mówimy, że wyrażenia A i B danego j należ do tej samej kategorii syn-
ezyka a
taktycznej (lub s tego samego typu syntaktycznego), gdy z dowolnego wyrażenia
a
W (A), którego wlaściwym skladnikiem jest A, po zamianie wyrażenia A na
wyrażenie B, otrzymujemy ciag symboli W (B) b acy wyrażeniem tego j
ed ezyka.
Przyklad. Wyrażenia j polskiego: lub , czlowiek nie s tego samego
ezyka a
typu. Np. wyrażenie W (czlowiek) postaci: Jan Kowalski jest czlowiekiem
staje si po zamianie wyrażenia czlowiek na wyrażenie lub ciagiem W (lub):
e
Jan Kowalski jest lub , który nie jest wyrażeniem j polskiego.
ezyka
Definicja kategorii syntaktycznej pozwala, jak widać, na ustalenie, że dane
dwa wyrażenia nie należ do tej samej kategorii. Nie pozwala jednak na ustale-
a
nie, czy dwa wyrażenia należ do tej sanej kategorii, w przypadku gdy poslugujac
a
si wielokrotnie t definicj nie wykazujemy, że nie należ do tej samej kategorii.
e a a, a
W j etnicznym wyróżnia si dwie podstawowe kategorie syntaktyczne:
ezyku e
nazwy i zdania oraz kategorie pochodne: funktorowe i operatorowe.
Nazwy
Z powodu nieoperacyjności definicji typu syntaktycznego wprowadza si
e,
niezależnie od niej, definicj typu wyrażeń zwanych nazwami.
e
Definicje nazwy, desygnatu nazwy, jej zakresu i treści
Nazwa jest w to wyrażenie mog pelnić funkcj podmiotu lub orzecznika
ace e
w zdaniu podmiotowo-orzecznikowym.
Desygnat nazwy jest to przedmiot, do którego nazwa ta si odnosi lub inaczej
e
przedmiot oznaczany przez nazw
e.
Zakres nazwy to zbiór wszystkich jej desygnatów.
Treść nazwy to jakikolwiek zbiór cech desygnatów tej nazwy taki, że wszys-
tkie cechy z tego zbioru przysluguja każdemu desygnatowi nazwy oraz jeżeli
wszystkie cechy z tego zbioru przysluguja jakiemuś obiektowi, to obiekt ten jest
desygnatem tej nazwy.
Wielkość zakresu nazwy jest odwrotnie proporcjonalna do wielkości treści
nazwy, w takim oto sensie: jeżeli treść jednej nazwy jest podzbiorem treści
drugiej, to zakres drugiej nazwy jest podzbiorem zakresu tej pierwszej.
Bowiem, przy zalożeniu inkluzji treści pierwszej nazwy w treści drugiej nazwy,
dowolnemu desygnatowi drugiej nazwy przysluguj wszystkie cechy należ do
a ace
treści pierwszej nazwy, zatem z definicji poj treści, musi on być desygnatem
ecia
pierwszej nazwy; dowodzi to inkluzji zakresu drugiej nazwy w zakresie pierwszej.
2
Ze wzgl na ilość desygnatów, nazwy dzielimy na ogólne, jednostkowe,
edu
puste. Nazwa majaca wi niż jeden desygnat nazywana jest ogóln ta, która
ecej a,
ma dokladnie jeden desygnat nazywana jest jednostkow wreszcie ta, która nie
a,
ma desygnatów nazywana jest pust
a.
Ze wzgl na wielkość treści, nazwy dzielimy na indywidualne majace
edu
treść pust oraz generalne których treść jest niepustym zbiorem. Np. nazwa
a,
Wisla jest w każdym ze swoich znaczeń nazw indywidualn tymczasem
a a,
nazwa najdluższa rzeka w Polsce jest generalna, choć również jak Wisla
jednostkowa.
Logika nazw
Slownik j logiki nazw zawiera nast symbole:
ezyka epujace
S, M, P, S1, M1, P1, S2, M2, P2, . . . - zmienne nazwowe
a, e, i, o - funktory zdaniotwórcze od dwóch argumentów nazwowych
J
ezyk:
Każdy ciag symboli ze slownika postaci: XuY , gdzie X, Y s zmiennymi
a
nazwowymi, a u jest jednym z czterech funktorów ze slownika, jest formula
j logiki nazw i tylko takie ciagi s formulami tego j
ezyka a ezyka.
Zmienne nazwowe reprezentuj dowolne nazwy ogólne z j etnicznego.
a ezyka
Formula: SaP , reprezentuje funkcj zdaniow każde S jest P, b ac sche-
e a: ed a
matem tzw. zdania ogólnotwierdz (np. każda ryba jest drapieżnikiem )
acego
Formula: SeP , reprezentuje funkcj zdaniow żadne S nie jest P,
e a:
b ac schematem tzw. zdania ogólnoprzecz (np. żadna ryba nie jest
ed a acego
drapieżnikiem )
Formula: SiP , reprezentuje funkcj zdaniow niektóre S s P, b ac
e a: a ed a
schematem tzw. zdania szczególowotwierdz (np. niektóre ryby s drapież-
acego a
nikami )
Formula: SoP , reprezentuje funkcj zdaniow niektre S nie s P ,
e a: a
b ac schematem tzw. zdania szczególowoprzecz (np. niektóre ryby
ed a acego
nie s drapieżnikami ).
a
Semantyka:
Niech V b przyporz
edzie adkowaniem każdej zmiennej nazwowej X dokladnie
jednego, lecz dowolnego zbioru wi niż 1-elementowego, oznaczanego tu w
ecej
postaci V (X). (Domyślnie, jeśli zmienna X reprezentuje dan nazw to V (X)
a e,
jest zakresem tej nazwy.) Przyporz
adkowanie V nazwiemy wartościowaniem.
Aby określić sposób przyporz
adkowania wartości logicznych prawdy lub fal-
szu dowolnej formule j logiki nazw, zdefiniujmy dwa znane stosunki mi
ezyka edzy
zbiorami:
3
Zbiór A jest podzbiorem zbioru B (A ą" B), gdy dla dowolnego obiektu b,
jeżeli b jest elementem zbioru A (b " A), to b jest elementem zbioru B (b " B).
Zbiory A, B s rozlaczne, gdy nie istnieje obiekt b taki, że b " A oraz b " B,
a
czyli, gdy zbiory te nie maja wspólnego elementu.
Dla dowolnego wartościowania V , dla dowolnych zmiennych nazwowych X, Y ,
powiemy, że
formula XaY jest prawdziwa przy wartościowaniu V , gdy V (X) jest pod-
zbiorem zbioru V (Y ),
formula XeY jest prawdziwa przy wartościowaniu V , gdy zbiory V (X), V (Y )
s rozlaczne,
a
formula XiY jest prawdziwa przy wartościowaniu V , gdy zbiory V (X), V (Y )
nie s rozlaczne,
a
formula XoY jest prawdziwa przy wartościowaniu V , gdy V (X) nie jest
podzbiorem zbioru V (Y ).
Zauważmy, że zachodzi prosty zwiazek:
dla dowolnego wartościowania V , XaY jest prawdziwa przy V wtw XoY
jest falszywa (tzn. nie jest prawdziwa) przy V ,
XeY jest prawdziwa przy V wtw XiY jest falszywa przy V .
Centralnym poj jest wynikanie logiczne:
eciem
Definicja wynikania logicznego
Mówimy, że ze zbioru formul Z wynika logicznie formula ą (Z |= ą), gdy dla
każdego wartościowania V , przy którym wszystkie formuly z Z s prawdziwe, ą
a
jest również prawdziwa.
Przyklady. (1) Formula SaP wynika logicznie ze zbioru formul {SaM, MaP }.
Aby tego dowieść, zakladamy, że przy jakimś, dowolnie wybranym wartościowa-
niu V prawdziwe s formuly SaM, MaP , co zapisujemy w postaci pierwszych
a
wyrażeń dowodu:
rozważmy dowolne wartościowanie V ,
(1) SaM jest prawdziwa przy V (zalożenie),
(2) MaP jest prawdziwa przy V (zalożenie).
Po tych zalożeniach celem dowodu jest wykazanie, iż
(cel1) formula SaP jest prawdziwa przy wartościowaniu V .
Korzystaj z warunku prawdziwości dla formuly ogólnotwierdz specy-
ac acej
fikujemy ów cel w postaci:
(cel2) V (S) ą" V (P ).
Aby go osiagnć stosujemy definicj stosunku bycia podzbiorem, zatem wyka-
a e
zujemy, że
(cel3) dla dowolnego obiektu b, jeżeli b " V (S), to b " V (P ).
4
Aby go zrealizować zalóżmy, że dowolnie wybrany obiekt b jest elementem
zbioru V (S):
rozważmy dowolny obiekt b,
(3) b " V (S) (zalożenie).
Teraz celem dowodu staje si wykazanie, że
e
(cel4) b " V (P ).
Dalsza specyfikacja celw dowodu nie nast bowiem bycie elementem (")
api,
zbioru jest terminem pierwotnym, tzn. nie istnieje jego definicja wyrazna, z
której można by korzystać, aby specyfikować dalej cel. Dlatego aby osiagnć
a
(cel4) korzystamy z informacji (1), (2), (3) w sposób nast acy. Na podstawie
epuj
warunku prawdziwości dla formuly ogólnotwierdz V (S) jest podzbiorem
acej,
V (M) oraz V (M) jest podzbiorem zbioru V (P ):
(4) V (S) ą" V (M) z (1),
(5) V (M) ą" V (P ) z (2)
Korzystaj z definicji bycia podzbiorem, wyrażenia (4), (5) zamieniamy na
ac
(6) dla dowolnego obiektu x, jeżeli x " V (S), to x " V (M) z (4),
(7) dla dowolnego obiektu x, jeżeli x " V (M), to x " V (P ) z (5).
Ostatecznie otrzymujemy:
(8) b " V (M) z (3), (6),
(9) b " V (P ) z (8), (7),
co kończy dowód.
(2) Wykażemy, że {MaP, MaS} |= SiP .
rozważmy dowolne wartościowanie V ,
(1) MaP jest prawdziwa przy V (zalożenie),
(2) MaS jest prawdziwa przy V (zalożenie),
(3) V (M) ą" V (P ) z (1),
(4) V (M) ą" V (S) z (2),
(5) V (M) jest niepustym zbiorem - z warunku semantycznego, wedlug którego
zbiór V (X) jest wi niż 1-elementowy,
ecej
istnieje obiekt b taki, że
(6) b " V (M) z (5),
(7) b " V (P ) z (3), (6),
(8) b " V (S) z (4), (6),
(9) zbiory V (S), V (P ) nie s rozlaczne - z (8),
a
SiP jest prawdziwa przy V - z (9).
(3) Wykazujemy, że formula SeP wynika logicznie ze zbioru formul {SaM, MeP },
metod nie wprost.
a
5
Dowieść danego zdania (twierdzenia) nie wprost, to zalożyć, że jest ono
falszywe, czyli zalożyć, że zaprzeczenie tego zdania jest prawdziwe i na tej
podstawie, stosuj definicje wyrażeń wyst acych w zdaniu, jak również
ac epuj
być może znane twierdzenia, dojść do absurdu. Polega on na wyprowadzeniu
(wywnioskowaniu) dowolnej pary zdań, w której jedno zdanie jest zaprzeczeniem
drugiego.
(1) {SaM, MeP } |= SeP (zalożenie)
istnieje wartościowanie V takie, że
(2) SaM jest prawdziwa przy V z (1),
(3) MeP jest prawdziwa przy V z (1),
(4) SeP jest falszywa przy V z (1),
(5) V (S) ą" V (M) z (2),
(6) V (M), V (P ) s rozlaczne - z (3),
a
(7) zbiory V (S), V (P ) nie s rozlaczne - z (4),
a
istnieje obiekt b taki, że
(8) b " V (S) z (7),
(9) b " V (P ) z (7),
(10) b " V (M) z (8), (5),
(11) zbiory V (M), V (P ) nie s rozlaczne z (9), (10),
a
absurd (6), (11).
(4) Aby wykazać, że {MaP, SoM} |= SoP należy wskazać takie wartościowanie
V , przy ktrym formuly MaP, SoM s prawdziwe, zaś formula SoP jest falszywa.
a
Na przyklad, V (S) = zbiór miast zamieszkalych przez co najmniej 1 mln miesz-
kańców, V (M) = zbiór stolic krajów, V (P ) = zbiór miast.
Definicja prawa logicznego (logicznej prawdziwości lub tautologii)
Formula ą jest prawem logicznym (jest logicznie prawdziwa lub jest tau-
tologi logiki nazw, gdy ą jest prawdziwa przy każdym wartościowaniu V .
a)
Przyklad. Formuly SaS, SiS s logicznie prawdziwe. Dowód pierwszego faktu
a
przebiega nast
epujaco:
rozważmy dwolne wartościowanie V ,
(1) V (S) ą" V (S) (na podstawie latwo dowodliwego z definicji bycia podzbio-
rem, twierdzenia: A ą" A),
(2) SaS jest prawdziwa przy V z (1).
Definicja sprzecznego zbioru formul
Zbiór formul Z nazywamy niesprzecznym wedlug logiki nazw, gdy istnieje
wartościowanie V , przy którym każda formula ze zbioru Z jest prawdziwa. Zbiór
formul jest sprzeczny, gdy nie jest niesprzeczny.
Przyklady (1) Zbiory formul {SaP, SoP }, {SeP, SiP }, {SoS} s sprzeczne.
a
Dowód nie wprost pierwszego faktu przebiega nast
epujaco:
(1) zbiór formul {SaP, SoP } jest niesprzeczny (zalożenie),
istnieje wartościowanie V takie, że
(2) formula SaP jest prawdziwa przy V z (1),
6
(3) formula SoP jest prawdziwa przy V z (1),
(4) V (S) ą" V (P ) z (2),
(5) V (S) ą" V (P ) z (3),
absurd (4),(5).
(2) Aby wykazać, że zbiór formul {SeM, MaP, SiP } jest niesprzeczny, należy
wskazać takie wartościowanie V , przy którym wszystkie formuly z tego zbioru s
a
prawdziwe, np. V (S) = zbiór krów, V (M) = zbiór koni, V (P ) = zbiór zwierz
at
roślinożernych.
Zdania
Nie każde zdanie z j etnicznego zaliczane jest do kategorii zdań. Należ
ezyka a
do niej wylacznie zdania oznajmuj prawdziwe b falszywe. Kategori zdań
ace, adz e
dzielimy na zdania proste i zlożone, lecz kryterium tego podzialu nie jest liczba
wyst acych w zdaniu orzeczeń (jak w gramatyce), ale wyst
epuj epowanie tzw.
spójnika (funktora zdaniotwórczego od argumentów zdaniowych). Zdanie, w
którym nie wyst spójnik nazywamy prostym, zdanie, które nie jest proste,
epuje
nazywamy zlożonym.
Najważniejszy typ zdań prostych stanowia zdania podmiotowo-orzecznikowe,
tzn. zdania postaci: a jest P , gdzie a jest podmiotem, zaś P orzecznikiem,
np. Jan Kowalski jest studentem .
Wsród zdań zlożonych wyróżnia si m.in.
e
" zdania negacyjne, postaci: nieprawda, że A,
" koniunkcyjne: A i B,
" alternatywne: A lub B,
" implikacyjne: jeżeli A, to B,
" równoważnościowe: A wtedy i tylko wtedy, gdy B,
gdzie A, B s dowolnymi zdaniami.
a
Funktory
Mamy nie jedn lecz wiele tzw. kategorii funktorowych, do ktrych należ
a, a
funktory
Definicja funktora
Funktor jest to wyrażenie sluż do tworzenia wyrażeń zlożonych z mniej
ace
zlożonych.
Wyrażenie zlożone uzyskujemy z wyrażeń mniej zlożonych przez dolaczenie
do nich funktora. Wyrażenia, które dolaczamy do funktora nazywamy jego
argumentami.
Aby wygodnie przedstawić kategorie syntaktyczne funktorowe, przyporz
ad-
kowuje si każdej kategorii syntaktycznej odpowiedni wskaznik. Kategorii nazw
e
przyporz
adkowujemy wskaznik: n, zaś kategorii zdań z.
Wówczas każdej kategorii funktorowej przyporz
adkowany jest wskaznik pos-
taci ulamka, w liczniku którego wyst wskaznik kategorii wyrażenia zlożo-
epuje
7
nego powstalego przez dolaczenie do funktora argumentów, zaś w mianowni-
ku wyst a wskazniki (odzielone przecinkami) kategorii, do których należ
epuj a
argumenty.
Najważniejsze kategorie funktorowe:
n
funktory nazwotwórcze od jednego argumentu nazwowego, czyli wy-
n
rażenia, które dolaczone do jednej nazwy tworz now nazw np. wysoki ,
a a e,
ladny , - ,
n
funktory nazwotwórcze od dwóch argumentów nazwowych, czyli wy-
n,n
rażenia, które dolaczone do dwóch nazw tworz now nazw np. nad , pod ,
a a e,
+ ,
z
funktory zdaniotwórcze od jednego argumentu nazwowego, czyli wy-
n
rażenia, które dolaczone do jednej nazwy tworz zdanie, np. świeci , jest
a
czlowiekiem ,
z
funktory zdaniotwórcze od dwóch argumentów nazwowych, czyli wy-
n,n
rażenia, które dolaczone do dwóch nazw tworz zdanie, np. kocha , lubi
a
d" ,
z
funktory zdaniotwórcze od jednego argumentu zdaniowego, czyli wyra-
z
żenia, które dolaczone do jednego zdania tworz nowe zdanie, np. nieprawda,
a
że , jest konieczne, że ,
z
funktory zdaniotwórcze od dwóch argumentów zdaniowych, czyli wy-
z,z
rażenia, które dolaczone do dwóch zdań tworz nowe zdanie, np. i , lub ,
a
jeżeli,to , wtedy i tylko wtedy, gdy .
Definicje predykatu i spójnika
Funktory zdaniotwórcze od jednego lub wi ilości argumentów naz-
ekszej
wowych nazywamy predykatami.
Funktory zdaniotwórcze od jednego lub wi ilości argumentów zda-
ekszej
niowych nazywamy spójnikami.
Istotn rol w logice klasycznej odgrywaja tzw. spójniki ekstensjonalne
a e
(prawdziwościowe). Aby je przedstawić, dobrze jest wystartować od koncepcji
znaczenia wyrażenia autorstwa Gottloba Fregego.
Znaczenie wyrażenia wedlug Gottloba Fregego
G. Frege (1848-1925) - niemiecki matematyk i filozof, odkrywca aksjomaty-
cznej wersji klasycznej logiki zdaniowej; autor semantycznych rozstrzygnić usta-
e
laj typy odniesień i sensów dla wyrażeń nasyconych, czyli nazw i zdań oraz
ach
nienasyconych, czyli funktorów; twórca koncepcji znaczenia kwantyfikatorów
jako specjalnych wlasności przysluguj innym wlasnościom; zwrócil uwag
acych e
na pewne zjawisko j a;
ezykowe, zwane pózniej intensjonalności twórca tzw. logi-
cyzmu, czyli pogladu, wedlug którego poj matematyczne s sprowadzalne do
ecia a
(definiowalne przez) pojć logiki, a w rezultacie, iż twierdzenia matematyczne
e
8
s wyprowadzalne z zasad logiki.
a
Definicja znaczenia, denotacji i sensu wyrażenia wedlug G. Fregego
Znaczenie dowolnego wyrażenia A jest określone przez dwa komponenty:
denotacj tego wyrażenia: D(A) oraz sens tego wyrażenia: S(A).
e
D(A) jest obiektem, do którego wyrażenie A si odnosi, tzn. jest tym bytem,
e
dla którego A jest znakiem.
S(A) jest sposobem, w jaki denotacja wyrażenia A jest ustalana. Znajomość
sensu wyrażenia jest niezb choć na ogól niewystarczajacym warunkiem
ednym,
ustalenia denotacji tego wyrażenia.
Gdy wyrażenie A jest nazw denotacja D(A) jest jej desygnatem b za-
a, adz
kresem. (Frege przez nazw rozumial takie wyrażenie, które we wspólczesnej
e
literaturze polskiej nazywane jest nazw jednostkow lub nazw pust o in-
a a a a
tencji jednostkowej .) Sens S(A) zazwyczaj jest utożsamiany z treścia nazwy
A.
Gdy wyrażenie A jest zdaniem, denotacja D(A) jest wartościa logiczn tego
a
zdania, czyli Prawd (1), b Falszem (0). Wedlug Fregego zdania oznajmuj
a adz ace
odnosz si do Prawdy b Falszu. Sens S(A) zdania A jest myśla w zdaniu
a e adz
A wyrażon zwan inaczej s w sensie logicznym.
a, a adem
Zasada kompozycyjności denotacji G. Fregego
Denotacja wyrażenia zlożonego jest jednoznacznie określona przez denotacje
wyrażeń skladowych tego wyrażenia.
Innymi slowy, jeżeli W (A) jest wyrażeniem zlożonym, w którym wyrażenie A
jest skladnikiem oraz B jest wyrażeniem o tej samej denotacji co wyrażenie A, to
wyrażenie W (B), powstale przez zast wyrażenia A w W (A) wyrażeniem
apienie
B, ma t sam denotacj co wyrażenie W (A).
e a e
Przyklady (1) W (A) := Warszawa jest stolic Polski
a
D(W (A)) = 1
A := Warszawa
B := najwi miasto w Polsce
eksze
D(A) = D(B)
W (B) := Najwi miasto w Polsce jest stolic Polski,
eksze a
D(W (B)) = 1
D(W1(A1)) = D(W1(B1)).
(2) W1(A1) := Jest konieczne, że Warszawa jest stolic Polski
a
D(W1(A1)) = 0
A1 := Warszawa jest stolic Polski
a
B1 := Każdy kwadrat jest prostok
atem
D(A1) = D(B1) = 1
W1(B1) := Jest konieczne, że każdy kwadrat jest prostok
atem
D(W1(B1)) = 1
D(W1(A1)) = D(W1(B1))
9
Definicja funktora ekstensjonalnego i intensjonalnego
Funktor n-argumentowy F nazywamy ekstensjonalnym, gdy dla dowolnych
jego argumentów A1, A2, . . . , An, denotacja D(F (A1, A2, . . . , An)) wyrażenia
zlożonego F (A1, A2, . . . , An), powstalego przez dolaczenie funktora F do ar-
gumentów A1, A2, . . . , An, jest jednoznacznie określona przez denotacje D(A1),
D(A2), . . . , D(An) tych argumentów.
Funktor nazywamy intensjonalnym, gdy nie jest on ekstensjonalny.
Zatem funktor n-argumentowy F jest intensjonalny, gdy istnieja jego argu-
menty A1, A2, . . . , An oraz argument B tego samego typu co argument Ai dla
pewnego i = 1, 2, . . . , n takie, że D(B) = D(Ai) oraz D(F (A1, A2, . . . , Ai, . . . ,
An)) = D(F (A1, A2, . . . , B, . . . , An))
n
Przyklady. Funktor dawny typu jest intensjonalny:
n
F := dawny
A := senator Rzeczypospolitej
F (A) := dawny senator Rzeczypospolitej
B := kolega marszalka Bogdana Borusewicza, przy czym D(A) = D(B)
F (B) := dawny kolega marszalka Bogdana Borusewicza
D(F (A)) = D(F (B))
z
Funktor jest konieczne, że typu jest intensjonalny:
z
F := jest konieczne, że
A := Warszawa jest stolic Polski
a
F (A) := Jest konieczne, że Warszawa jest stolic Polski
a
B := Każdy kwadrat jest prostok
atem
D(A) = D(B) = 1
F (B) := Jest konieczne, że każdy kwadrat jest prostok
atem
D(F (A)) = D(F (B)).
Z ogólnej definicji funktora ekstensjonalnego otrzymujemy:
Definicj spójnika ekstensjonalnego
e
Spójnik n-argumentowy F jest ekstensjonalny, gdy dla dowolnych jego argu-
mentów A1, A2, . . . , An, wartość logiczna zdania F (A1, A2, . . . , An) jest jednoz-
nacznie określona przez wartości logiczne argumentów A1, A2, . . . , An.
Najważniejsze spójniki ekstensjonalne:
negacja: nieprawda, że . . . (<"),
koniunkcja: . . . i . . . ('"),
alternatywa: . . . lub . . . (co najmniej jedno z dwojga . . . , . . .) ((")
implikacja: jeżeli . . ., to . . . ()
równoważność: . . . wtedy i tylko wtedy, gdy . . . ("!)
alternatywa rozlaczna: . . . albo . . . (dokladnie jedno z dwojga . . . , . . .) ()
10
alternatywa Sheffera: co najwyżej jedno z dwojga . . . , . . . (/)
binegacja: ani nie . . . , ani nie . . . (\)
Sposoby jednoznacznego wyznaczania wartości logicznej zdań, w których
funktorami glównymi s niektóre wymienione spójniki, w zależności od wartości
a
logicznych argumentów tych funktorów, podane s w postaci nast
a epujacych
tabelek:
A <" A
0 1
1 0
A B A '" B A B A (" B
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
A B A B A B A "! B
0 0 1 0 0 1
0 1 1 0 1 0
1 0 0 1 0 0
1 1 1 1 1 1
A B A/B A B A\B
0 0 1 0 0 1
0 1 1 0 1 0
1 0 1 1 0 0
1 1 0 1 1 0
W dalszym ciagu, wartości logiczne b przyporz
edziemy adkowywać formulom
standardowego j zdaniowego.
ezyka
J klasycznej logiki zdaniowej (standardowy j zdaniowy)
ezyk ezyk
Slownik jest tu zbiorem nast symboli:
epujacych
zmiennych zdaniowych: p0, p1, p2, . . .,
spójników: <", '", (", , "!,
nawiasów: (, ) .
Definicja standardowego j zdaniowego podaje, jakie skończone ciagi
ezyka
symboli ze slownika s wyrażeniami tego j wyrażenie tego j nazywane
a ezyka; ezyka
jest formula:
(1) każda zmienna zdaniowa (traktowana jako 1-wyrazowy ciag) jest formula,
(2) jeżeli skończony ciag symboli ą jest formula, to ciag postaci: <" ą, również
jest formula,
(3) jeżeli ciagi ą, s formulami, to ciagi postaci: (ą '" ), (ą (" ), (ą
a
), (ą "! ), również s formulami,
a
11
(4) jeżeli ciag ą jest formula, to ą jest b zmienn zdaniow b ciagiem
adz a a, adz
symboli uzyskanym z prostszych formul na postawie zastosowania przynajmniej
jednej z regul (2), (3).
Przyklad. Nast ace ciagi symboli s formulami: (((p0 p2) '" p0)
epuj a
p2), ((p0 (p2 '" p0)) p2). Zazwyczaj nawiasy zewn pomijamy. Zatem
etrzne
powyższe dwie formuly zapisujemy w postaci: ((p0 p2) '" p0) p2, (p0
(p2 '" p0)) p2.
Klasyczna logika zdaniowa
Centralnymi poj s tu wynikanie logiczne, tautologia (prawo logiczne),
eciami a
sprzeczny zbiór formul .
Definicja wartościowania logicznego
Dowolne przyporz
adkowanie każdej zmiennej zdaniowej p dokladnie jednej z
dwu wartości logicznych: 0, 1, nazywamy wartościowaniem logicznym.
Dane wartościowanie można rozszerzyć do przyporz
adkowania dokladnie jed-
nej z dwu wartości logicznych każdej formule j zdaniowego, w zależności od
ezyka
ksztaltu tej formuly, post ac wedlug tabelek określaj wartość logiczn
epuj acych a
formuly zlożonej w zależności od wartości logicznych jej podformul.
Tak wi formule negacyjnej <" ą dowolne wartościowanie przyporz
ec, adkowuje
wartość 1 dokladnie wówczas, gdy przyporz
adkowuje ono formule ą wartość 0.
Formule koniunkcyjnej ą '" każde wartościowanie przyporz
adkowuje war-
tość 1 dokladnie wówczas, gdy obu formulom ą, wartościowanie to przyporz
ad-
kowuje wartość 1.
Formule postaci ą (" dowolne wartościowanie przyporz
adkowuje wartość 0
dokladnie wtedy, gdy obu formulom ą, przyporz
adkowuje ono wartość 0.
Formule implikacyjnej ą dowolne wartościowanie przyporz
adkowuje
wartość 0 dokladnie wtedy, gdy formule ą wartościowanie to przyporz
adkowuje
wartość 1 oraz formule wartość 0.
Formule równoważnościowej ą "! każde wartościowanie przyporz
adkowuje
wartość 1 dokladnie wówczas, gdy przyporz e
adkowuje ono obu formulom ą, t
sam wartość logiczn
a a.
Wówczas, gdy dane wartościowanie przyporz
adkowuje danej formule wartość
1 (0) mówimy, że jest ona prawdziwa (falszywa) przy tym wartościowaniu.
Definicje wynikania logicznego, tautologii oraz sprzecznego zbioru formul
Mówimy, że formula ą wynika logicznie ze zbioru formul Z (Z |= ą), gdy ą
jest prawdziwa przy każdym wartościowaniu, przy którym prawdziwe s wszys-
a
tkie formuly ze zbioru Z.
Mówimy, że formula ą jest tautologi (jest prawem logicznym lub jest lo-
a
gicznie oprawdziwa), gdy każde wartościowanie przyporz
adkowuje jej wartość
12
1.
Zbiór formul nazywamy niesprzecznym, gdy istnieje wartościowanie, które
każdej formule z tego zbioru przyporz
adkowuje wartość 1. Zbiór formul, który
nie jest niesprzeczny nazywamy sprzecznym.
Przy sprawdzaniu wynikania logicznego, logicznej prawdziwości lub sprzecz-
ności zbioru formul wykonujemy czynności dwóch typów: korzystamy z informa-
cji o wartości logicznej formuly przy danym wartościowaniu, b wykazujemy,
adz
że formula jest prawdziwa lub falszywa przy danym wartościowaniu. Zgodnie
z warunkami prawdziwości formul przy danym wartościowaniu (czyli zgodnie z
tabelkami określajacymi znaczenia standardowych spójników) wyróżnić można
nast ace sposoby (reguly) korzystania z prawdziwości (K1) lub falszywości
epuj
(K0) formul przy danym wartościowaniu (nad poziom linia podawana jest
a
dana informacja, z której si korzysta, pod t linia wyst wyrażenie (lub
e a epuje
wyrażenia), które dzi tej informacji można do dowodu wpisać):
eki
(K1 <") (K0 <")
<" ą jest 1 przy v <" ą jest 0 przy v
ą jest 0 przy v ą jest 1 przy v
(K1'") (K0(")
ą '" jest 1 przy v ą (" jest 0 przy v
ą jest 1 przy v ą jest 0 przy v
jest 1 przy v jest 0 przy v
(K0 '" (a)) (K1 (" (a))
ą '" jest 0 przy v ą (" jest 1 przy v
ą jest 0 przy v (zalożenie) ą jest 1 przy v (zalożenie)
. .
. .
. .
cel cel
jest 0 przy v (zalożenie) jest 1 przy v (zalożenie)
. .
. .
. .
cel cel
(K0 '" (b)) (K1 (" (b))
ą '" jest 0 przy v ą (" jest 1 przy v
ą jest 1 przy v ą jest 0 przy v
jest 0 przy v jest 1 przy v
13
(K0 '" (c)) (K1 (" (c))
ą '" jest 0 przy v ą (" jest 1 przy v
jest 1 przy v jest 0 przy v
ą jest 0 przy v ą jest 1 przy v
(K1 (a))
ą jest 1 przy v
ą jest 1 przy v
jest 1 przy v
(K1 (b))
ą jest 1 przy v
jest 0 przy v
ą jest 0 przy v
(K1 (c))
ą jest 1 przy v
<" ą (" jest 1 przy v
(K0 )
ą jest 0 przy v
ą jest 1 przy v
jest 0 przy v
(K1 "!)
ą "! jest 1 przy v
ą jest 1 przy v
ą jest 1 przy v
(K0 "!)
ą "! jest 0 przy v
(ą ) '" ( ą) jest 0 przy v
Z kolei wyróżniamy nast ace sposoby wykazywania prawdziwości (W 1)
epuj
lub falszywości (W 0) formul przy danym wartościowaniu:
(W 1 <") (W 0 <")
wykaż: ą jest 0 przy v wykaż: ą jest 1 przy v
cel: <" ą jest 1 przy v cel: <" ą jest 0 przy v
14
(W 1'") (W 0(")
wykaż: ą jest 1 przy v wykaż: ą jest 0 przy v
wykaż: jest 1 przy v wykaż: jest 0 przy v
cel: ą '" jest 1 przy v cel: ą (" jest 0 przy v
(W 0 '" (a)) (W 1(")(a)
wykaż: ą jest 0 przy v wykaż: ą jest 1 przy v
cel: ą '" jest 0 przy v cel: ą (" jest 1 przy v
(W 0 '" (b)) (W 1(")(b)
wykaż: jest 0 przy v wykaż: jest 1 przy v
cel: ą '" jest 0 przy v cel: ą (" jest 1 przy v
(W 0 '" (c)) (W 1(")(c)
wykaż: ą <" jest 1 przy v wykaż: <"ą jest 1 przy v
cel: ą '" jest 0 przy v cel: ą (" jest 1 przy v
(W 1 (a))
zalóż: ą jest 1 przy v
i wykaż: jest 1 przy v
cel: ą jest 1 przy v
(W 1 (b))
zalóż: jest 0 przy v
i wykaż: ą jest 0 przy v
cel: ą jest 1 przy v
(W 1 (c))
wykaż: <"ą (" jest 1 przy v
cel: ą jest 1 przy v
(W 0 )
wykaż: ą jest 1 przy v
wykaż: jest 0 przy v
cel: ą jest 0 przy v
15
(W 1 "!)
wykaż: ą jest 1 przy v
wykaż: ą jest 1 przy v
cel: ą "! jest 1 przy v
(W 0 "!)
wykaż: (ą ) '" ( ą) jest 0 przy v
cel: ą "! jest 0 przy v
Przyklady (1) Wykazujemy, że {<" (p '" q)} |= <" p (" <" q:
rozważmy dowolne wartościowanie v,
(1) <" (p '" q) jest 1 przy v (zalożenie),
(2) p '" q jest 0 przy v z (1), (K1 <"),
teraz stosujemy (K0 '" (a)):
(3) p jest 0 przy v (zalożenie)
(4) <" p jest 1 przy v z (3), (W 1 <"),
(5) <" p (" <" q jest 1 przy v, (W 1 (" (a))
(6) q jest 0 przy v (zalożenie)
(7) <" q jest 1 przy v z (6), (W 1 <")
(8) <" p (" <" q jest 1 przy v z (7), (W 1 (" (b))
(2) Wykazujemy nie wprost, że {<" p (" <" q} |= <" (p '" q):
(1) {<" p (" <" q} |= <" (p '" q) (zalożenie),
istnieje wartościowanie v takie, że
(2) <" p (" <" q jest 1 przy v z (1),
(3) <" (p '" q) jest 0 przy v z (1),
(4) p '" q jest 1 przy v z (3), (K0 <"),
(5) p jest 1 przy v z (4), (K1'"),
(6) q jest 1 przy v z (4), (K1'"),
(7) <" p jest 0 przy v z (5), (W 0 <"),
(8) <" q jest 1 przy v z (2), (7), (K1 (" (b)),
(9) q jest 0 przy v z (8), (K1 <"),
absurd (6), (9).
(3) Wykazujemy, że {p q, <" q} |= p w taki sposób, jak chcielibyśmy dowieść
nie wprost, iż {p q, <" q} |= p. Naszym celem jest wskazanie takiego
wartościowania v, przy którym formuly p q, <" q s prawdziwe, zaś formula p
a
jest falszywa.
(1) {p q, <" q} |= p (zalożenie)
istnieje wartościowanie v takie, że
(2) p q jest 1 przy v z (1),
(3) <" q jest 1 przy v z (1),
16
(4) p jest 0 przy v z (1),
(5) q jest 0 przy v z (3), (K1 <").
W ten sposób wykazaliśmy, iż jeżeli wynikania tu nie ma, tzn. jeżeli dla
pewnego wartościowania v wszystkie formuly w naszym zbiorze s prawdziwe,
a
zaś formula, która nie wynika logicznie jest przy v falszywa, to wartościowanie
to ma postać: v(p) = 0, v(q) = 0. Latwo sprawdzić (przy użyciu tabelek), iż
na odwrót, przy tak określonym wartościowaniu v, obie formuly w zbiorze s
a
prawdziwe, zaś formula nie wynikaj jest falszywa.
aca
(4) Formula ((p r) (" (q r)) ((p '" q) r) jest tautologia:
rozważmy dowolne wartościowanie v,
aby wykazać prawdziwość tej formuly przy wartościowaniu v stosujemy dwukrot-
nie (W 1 (a)):
(1) (p r) (" (q r) jest 1 przy v (zalożenie),
obecnie celem dowodu jest wykazanie, iż formula (p '" q) r jest prawdziwa
przy v. Stosujemy wi drugi raz (W 1 (a)):
ec
(2) p '" q jest 1 przy v (zalożenie),
teraz celem dowodu jest wykazanie prawdziwości r przy v:
(3) p jest 1 przy v z (2), (K1'")
(4) q jest 1 przy v z (2), (K1'"),
stosujemy (K1 (" (a)):
(5) p r jest 1 przy v (zalożenie)
(6) r jest 1 przy v z (5), (3), (K1 (a)),
(7) q r jest 1 przy v (zalożenie)
(8) r jest 1 przy v z (7), (4), (K1 (a)).
(5) Wykazujemy niewprost, że formula ((p '" q) r) ((p r) (" (q r))
jest tautologia:
(1) ((p '" q) r) ((p r) (" (q r)) nie jest tautologia (zalożenie)
istnieje wartościowanie v takie, że
(2) ((p '" q) r) ((p r) (" (q r)) jest 0 przy v z (1)
(3) (p '" q) r jest (1) przy v z (2), (K0 )
(4) (p r) (" (q r) jest 0 przy v z (2) (K0 )
(5) p r jest 0 przy v z (4), (K0("),
(6) q r jest 0 przy v z (4), (K0("),
(7) p jest 1 przy v z (5), (K0 ),
(8) r jest 0 przy v z (5), (K0 ),
(9) q jest 1 przy v z(6), (K0 ),
(10) p '" q jest 1 przy v z (7),(9), (W 1'"),
17
(11) r jest 1 przy v z (3),(10), (K1 (a)),
absurd (8), (11).
(6) Wykazujemy, że formula ((p r) (" (q r)) ((p '" q) <" r) nie
jest tautologia w taki sposób, jak chcielibyśmy dowieść nie wprost, iż jest ona
tautologia. Naszym celem jest wskazanie takiego wartościowania v, przy którym
formula jest falszywa.
(1) ((p r) (" (q r)) ((p '" q) <"r) nie jest tautologia (zalożenie)
istnieje wartościowanie v takie, że
(2) ((p r) (" (q r)) ((p '" q) <"r) jest 0 przy v z (1),
(3) (p r) (" (q r) jest 1 przy v z (2), (K0 ),
(4) (p '" q) <"r jest 0 przy v z (2), (K0 ),
(5) p '" q jest 1 przy v z (4), (K0 ),
(6) <" r jest 0 przy v z (4), (K0 ),
(7) r jest 1 przy v z (6), (K0 <"),
(8) p jest 1 przy v z (5), (K1'"),
(9) q jest 1 przy v z (5), (K1'"),
W ten sposób wykazaliśmy, że jeżeli formula nie jest tautologia, tzn. przy
pewnym wartościowaniu v jest falszywa, to wartościowanie to ma postać: v(p) =
v(q) = v(r) = 1. Latwo sprawdzić (przy użyciu tabelek), iż na odwrót, przy tak
określonym wartościowaniu v, formula jest falszywa.
(7) Wykazujemy nie wprost, że zbiór formul {p (" <" q, r q, <" (s '" <" r), s '" <"
p} jest sprzeczny.
(1) zbiór {p (" <" q, r q, <" (s '" <" r), s '" <" p} jest niesprzeczny (zalożenie),
istnieje wartościowanie v takie, że
(2) p (" <" q jest 1 przy v z (1),
(3) r q jest 1 przy v z (1),
(4) <" (s '" <" r) jest 1 przy v z (1),
(5) s '" <" p jest 1 przy v z (1),
(6) s '" <" r jest 0 przy v z (4) (K1 <"),
(7) s jest 1 przy v z (5), (K1'"),
(8) <" p jest 1 przy v z (5), (K1'"),
(9) p jest 0 przy v z (8), (K1 <"),
(10) <" q jest 1 przy v z (2),(9), (K1 (" (b)),
(11) q jest 0 przy v z (10), (K1 <"),
(12) r jest 0 przy v z (3),(11), (K1 (b)),
(13) <" r jest 0 przy v z (6),(7), (K0 '" (b)),
(14) r jest 1 przy v z (13), (K0 <"),
absurd (12), (14).
(8) Wykazujemy, że zbiór formul {p q, r p, r <" q} jest niesprzeczny w
taki sposób, jak chcielibyśmy dowieść nie wprost, że jest on sprzeczny. Naszym
celem jest wskazanie takiego wartościowania v, przy którym każda formula z
tego zbioru jest prawdziwa.
18
(1) {p q, r p, r <" q} jest niesprzeczny (zalożenie),
istnieje wartościowanie v takie, że
(2) p q jest 1 przy v z (1),
(3) r p jest 1 przy v z (1),
(4) r <" q jest 1 przy v z (1),
(5) <" p (" q jest 1 przy v z (2), (K1 (c)),
(6) <" p jest 1 przy v (zalożenie)
(7) p jest 0 przy v z (6), (K1 <"),
(8) r jest 0 przy v z (3),(7), (K1 (b)),
W ten sposób wykazaliśmy, że jeżeli zbiór formul jest niesprzeczny, tzn.
przy pewnym wartościowaniu v każda formula z tego zbioru jest prawdziwa, a
ponadto spelnione jest zalożenie (6), to wartościowanie to ma postać: v(p) =
v(r) = 0, pozostalym zmiennym v przyporz
adkowuje dowolne wartości ze zbioru
{0, 1}. Latwo sprawdzić, iż na odwrót, przy tak określonym wartościowaniu v,
wszystkie formuly ze zbioru s prawdziwe.
a
Operatory
Poza zdaniami, nazwami i funktorami, wyróżnia si jeszcze kategorie opera-
e
torowe. Aby zdefiniować poj operatora zacznijmy od nast acych definicji:
ecie epuj
Definicje funkcji zdaniowej i nazwowej
Funkcja zdaniowa [nazwowa] dla j naturalnego, to wyrażenie zawie-
ezyka
raj zmienne określonych typów (np. zmienne przebiegaj zdania, b
ace ace adz
zmienne dla nazw indywidualnych, b zmienne dla nazw generalnych), które
adz
w rezultacie podstawienia w nim w miejsce zmiennych wyrażeń z j natural-
ezyka
nego odpowiednio tych samych typów co typy tych zmiennych, staje si zdaniem
e
(prawdziwym lub falszywym) [nazw
a].
Na przyklad wyrażenie x jest czlowiekiem , jest funkcja zdaniow w której
a,
wyst zmienna x dla nazw indywidualnych; wyrażenie x + x jest funkcja
epuje
nazwow w której wyst zmienna dla nazw indywidualnych; wyrażenie
a, epuje
każde S jest M jest funkcj zdaniow w której S, M s zmiennymi dla nazw
a a, a
generalnych; wyrażenie A i B jest funkcja zdaniow w której A, B s zmien-
a, a
nymi dla zdań.
Wyrażenie: dla każdego x, jeżeli x jest czlowiekiem, to x jest śmiertelny ,
nie jest funkcj zdaniow jeśli x jest zmienn dla nazw indywidualnych. Jest
a a, a
ono zdaniem. Wyrażenie: {x : x jest liczb rzeczywist i x+2 > 4} , mimo, że
a a
wyst w nim zmienna (dla nazw indywidualnych) nie jest funkcja nazwow
epuje a,
lecz jest nazw (zbioru). Podobnie wyrażenie xdx nie jest funkcj nazwow
a a a,
lecz jest nazw (funkcji).
a
Wyrażenia takie jak: dla każdego x , {x : } , dx również nie s ani
a
funkcjami zdaniowymi, ani nazwowymi, choć wyst w nich zmienne. Wy-
epuja
rażenia te nie s jednak ani zdaniami, ani nazwami, ani funktorami. Nazywane
a
s operatorami.
a
19
Definicja operatora
Operator jest to wyrażenie zawierajace zmienn które po dolaczeniu do
a,
funkcji zdaniowej b nazwowej, w której ta zmienna wyst tworzy wraz
adz epuje,
z nia zdanie b nazw
adz e.
Niektóre typy syntaktyczne operatorów:
z
jest wskaznikiem kategorii operatorów zdaniotwórczych, których argu-
|z
mentem jest funkcja zdaniowa,
n
jest wskaznikiem kategorii operatorów nazwotwórczych, których argu-
|n
mentem jest funkcja nazwowa,
n
jest wskaznikiem kategorii operatorów nazwotwórczych, których argu-
|z
mentem jest funkcja zdaniowa.
Przyklady.
z
dla każdego x, dla pewnego x: ,
|z
n
dx: ,
|n
n
{x : }: .
|z
J logiki kwantyfikatorów
ezyk
Slownik:
zmienne nazwowe: x1, x2, . . .,
spójniki: <", '", (", , "!,
kwantyfikatory:
duży, ogólny lub uniwersalny: " (dla każdego),
maly, szczególowy lub egzystencjalny: " (dla pewnego)
predykat identyczności: =, (2-argumentowy)
stale nazwowe: c1, c2, . . . , ck, k e" 0
predykaty: P1, P2, . . . , Pn, n e" 0 (1- i 2-argumentowe)
nawiasy i przecinek: (,) , .
Definicja termu nazwowego
Dowoln zmienn lub stala nazwow nazywamy termem (nazwowym).
a a a
Dysponuj definicja termu można sformulować
ac
Definicj zbioru formul
e
(1) Jeżeli t, s s termami, to ciag symboli: t = s jest formula.
a
(2) Jeżeli t jest termem oraz P jest 1-argumentowym predykatem, to ciag
P (t) jest formula.
(3) Jeżeli t, s s termami oraz P jest 2-argumentowym predykatem, to ciag:
a
P (t, s) jest formula.
(4) Jeżeli ą jest formula, to <" ą jest formula.
20
(5) Jeżeli ą, s formulami, to ciagi: (ą '" ), (ą (" ), (ą ), (ą "! ) s
a a
formulami.
(6) Jeżeli x jest zmienn nazwow oraz ą jest formula, to ciagi: "xą, "xą
a a
s formulami.
a
(7) Jeżeli ciag symboli ą jest formula, to ą jest jednej z postaci podanych w
warunkach (1) - (6).
Formuly, których postacie zostaly wymienione w (1), (2), (3) nazywane s
a
formulami atomowymi.
Definicje
Mówimy, że w formule "xą kwantyfikator " wiże zmienn x, zaś formul ą
a a e
nazywamy zasi tego kwantyfikatora. Analogicznie dla formuly "xą.
egiem
Każde pojawienie si nie bezpośrednio po kwantyfikatorze danej zmiennej x
e
w danej formule ą nazywamy wyst
epowaniem zmiennej x w ą.
Wyst
epowanie zmiennej x w formule nazywamy wolnym, gdy nie jest ono
w zasi żadnego kwantyfikatora wiaż t zmienn
egu acego e a.
Mówimy, że zmienna x jest wolna w formule , gdy zmienna ta ma w tej
formule przynajmniej jedno wolne wyst
epowanie.
Formul nazywamy domkni a (lub zdaniem), gdy nie wyst w niej
e et epuje
zmienna wolna.
Przyklad. W formule: "xP1(x, y)'"P2(x), zmienne x, y s wolne, natomiast
a
w formule "xP1(x, y) tylko zmienna y jest wolna. Formula "y"xP1(x, y) jest
zdaniem.
Zasady zapisu schematów w j logiki kwantyfikatorów dla zdań
ezyku
z j naturalnego
ezyka
Niech A b dowolnym zdaniem oznajmuj z j polskiego. Na-
edzie acym ezyka
szym celem jest zapisanie formuly domkni w j logiki kwantyfikatorów,
etej ezyku
ukazujacej struktur logiczn zdania A, nazywanej z tego powodu, schematem
e a
zdania A.
1) Każdej nazwie indywidualnej wyst acej w zdaniu A odpowiada w jego
epuj
schemacie stala nazwowa (różnym nazwom odpowiadaja różne stale).
2) Żadna nazwa generalna S wyst aca w zdaniu A nie ma odpowiednika w
epuj
jego schemacie, lecz 1-argumentowemu predykatowi postaci jest S, powstalemu
przez dolaczenie do nazwy S wyrażenia jest, odpowiada w schemacie zdania A
1-argumentowy predykat ze slownika j logiki kwantyfikatorów.
ezyka
3) Każdemu 1- i 2-argumentowemu predykatowi wyst acemu w zdaniu
epuj
A odpowiada w schemacie tego zdania odpowiednio 1- b 2-argumentowy
adz
predykat ze slownika (różnym predykatom z j polskiego odpowiadaj różne
ezyka a
predykaty ze slownika)
21
4) Jeżeli w A wyst a kwantyfikatory (każdy, żaden, wszystkie, pewne,
epuj
niektóre, to dokonujemy jego rozkladu na glówny kwantyfikator i funkcj zda-
e
niow która jest jego argumentem, nast rozkladamy t funkcj zdaniow
a, epnie e e a
na jej glówny kwantyfikator i jego argument itd., aż oznaczymy wszystkie funkcje
zdaniowe, w których już nie wyst kwantyfikator.
epuje
5) Funkcjom zdaniowym, w których nie wyst a kwantyfikatory, otrzy-
epuj
manym wedlug zasady 4), odpowiadaj w schemacie zdania A, formuly ato-
a
mowe.
Przyklady. Schematami zdań: Jaś kocha Malgosi Malgosia kocha Jasia s
e, a
odpowiednio formuly atomowe: K(j, m), K(m, j), gdzie K jest predykatem ze
slownika odpowiadajacym predykatowi kocha oraz j, m s stalymi nazwowymi
a
odpowiadaj odpowiednio nazwom indywidualnym Jaś, Malgosia.
acymi
Schematami zdań Jaś kocha wszystkich ludzi, Jaś kogoś kocha, s odpowied-
a
nio formuly: "x(C(x) K(j, x)), "x(C(x) '" K(j, x)), gdzie C jest predykatem
ze slownika odpowiadajacym predykatowi: jest czlowiekiem.
Semantyka dla j I rz (kwantyfikatorowego
ezyka edu
Naszym celem jest obecnie zdefiniowanie dwóch pojć: interpretacji j
e ezyka
kwantyfikatorowego oraz prawdziwości, wzgl falszywości zdania w danej
ednie
interpretacji. Dysponuj poj prawdziwości zdania w danej interpretacji
ac eciem
można b wprowadzić centralne poj wynikania logicznego, a nast
edzie ecie epnie
tautologii oraz sprzecznego zbioru zdań.
Definicje
Niech D b dowolnym niepustym zbiorem (klas mnogościa) obiektów.
edzie a,
Przypominany, że dowolny zbiór, którego każdy element należy do zbioru D
nazywamy podzbiorem zbioru D.
Dowolny zbiór dwuwyrazowych ciagów elementów zbioru D nazywamy re-
lacj binarn na zbiorze D.
a a
Na formaln semantyk dla j kwantyfikatorowego skladaja si jego in-
a e ezyka e
terpretacje:
Definicja interpretacji
Przez interpretacj j I rz wyznaczonego przez stale nazwowe: c1, . . . ,
e ezyka edu
ck, oraz predykaty P1, . . . , Pn, rozumiemy nast uklad:
epujacy
" "
I = (D, c", . . . , c", P1 , . . . , Pn), gdzie
1 k
(1) D jest dowolnym niepustym zbiorem, zwanym dziedzin interpretacji,
a
(2) dla każdego j = 1, . . . , k : c" " D jest wyróżnionym elementem zbioru
j
D (którego nazw w definiowanej interpretacji jest stala cj),
a
"
(3) dla każdego j = 1, . . . , n : Pj jest albo podzbiorem zbioru D, gdy
nazywajacy go predykat Pj jest 1-argumentowy, albo jest relacja binarn na
a
zbiorze D, gdy Pj jest 2-argumentowy.
22
Aby zdefiniować poj prawdziwości formuly domkni w interpretacji I
ecie etej
rozszerzamy przy ustalonej interpretacji I zbiór stalych nazwowych {c1, . . . , ck}
o nowe stale ad, d " D. W ten sposób dla danej interpretacji I ulega rozszerzeniu
zbiór formul tego j I rz którego I jest interpretacj w szczególności
ezyka edu, a,
jego zbiór zdań. B definiować prawdziwość w interpretacji I dla zdań z
edziemy
tego szerszego zbioru.
Każda interpretacja wyznacza tzw. waluacj termów domkni czyli
e etych,
przyporz etemu
adkowanie każdemu termowi domkni pewnego elementu z dzie-
dziny tej interpretacji (nieformalnie: elementu nazywanego tym termem w tej
interpretacji), jak nast
epuje:
(a) |cj| = c", j = 1, . . . , k,
j
(b) |ad| = d, d " D.
Definicja prawdziwości formuly domkni w interpretacji I
etej
Dla dowolnych stalych a, b rozszerzonego j oraz dowolnych 1-argumen-
ezyka
towego predykatu P i 2-argumentowego predykatu Q:
(1) a = b jest prawdziwa w I wtw |a|, |b| s jednym i tym samym obiektem,
a
"
(2) P (a) jest prawdziwa w I wtw |a| " P ,
(3) Q(a, b) jest prawdziwa w I wtw (|a|, |b|) " Q",
dla dowolnych formul domkni ą, :
etych
(4) <" ą jest prawdziwa w I wtw ą nie jest prawdziwa w I,
(5) ą '" jest prawdziwa w I wtw obie formuly: ą, , s prawdziwe w I,
a
(6) ą (" jest prawdziwa w I wtw przynajmniej jedna z formul: ą, , jest
prawdziwa w I,
(7) ą jest prawdziwa w I wtw ą nie jest prawdziwa w I lub jest
prawdziwa w I,
(8) ą "! jest prawdziwa w I wtw obie formuly: ą, , s prawdziwe w I,
a
b obie te formuly nie s prawdziwe w I
adz a
dla dowolnej formuly ą z co najwyżej jedn zmienn woln któr jest
a a a, a
zmienna x:
(9) "xą jest prawdziwa w I wtw dla każdego elementu d " D: formula
ą[x/ad] jest prawdziwa w I,
(10) "xą jest prawdziwa w I wtw dla pewnego elementu d " D: formula
ą[x/ad] jest prawdziwa w I,
gdzie ą[x/ad] jest formula uzyskan z formuly ą przez zast w niej
a apienie
każdego wolnego wyst
epowania zmiennej x stala ad.
Na podstawie definicji prawdziwości formul ogólnych i szczególowych w danej
23
interpretacji, można sformulować nast ace reguly (sposoby) korzystania z
epuj
informacji o prawdziwości lub falszywości w danej interpretacji tych formul:
(K1") (K0")
"xą jest 1 w I "xą jest 0 w I
ą[x/a] jest 1 w I ą[x/a] jest 0 w I
gdzie a jest dowoln stala nazwow spośród c1, . . . , ck, b stalych ad, d " D
a a adz
(K0") (K1")
"xą jest 0 w I "xą jest 1 w I
ą[x/a] jest 0 w I dla pewnego a ą[x/a] jest 1 w I dla pewnego a
a jest tu niewyspecyfikowan stala nazwow spośród stalych ad, d " D i tak
a a a,
która wcześniej w dowodzie nie pojawila si
e
Sposoby wykazywania prawdziwości lub falszywości w danej interpretacji
formul ogólnych i szczególowych:
(W 1") (W 0")
rozważmy dowolne a rozważmy dowolne a
wykaż: ą[x/a] jest 1 w I wykaż: ą[x/a] jest 0 w I
cel: "xą jest 1 w I cel: "xą jest 0 w I
a jest tu dowoln niewyspecyfikowan stala nazwow (tzn. nie wiemy jaki
a a a
obiekt z dziedziny interpretacji I jest przez nia nazywany) spośród stalych
ad, d " D
(W 0") (W 1")
wykaż: ą[x/a] jest 0 w I wykaż: ą[x/a] jest 1 w I
cel: "xą jest 0 w I cel: "xą jest 1 w I
a jest tu jak a adz
akolwiek stala nazwow spośród c1, . . . , ck, b stalych ad, d " D
Wynikanie loguiczne, tautologia, sprzeczny zbiór zdań w logice
kwantyfikatorów
Centralnym poj semantycznym jest tu wynikanie logiczne lub inaczej
eciem
relacja konsekwencji logicznej.
Definicja wynikania logicznego
Mówimy, że zdanie ą wynika logicznie ze zbioru zdań Z ustalonego j
ezyka
kwantyfikatorowego (Z |= ą), gdy ą jest prawdziwe w każdej interpretacji, w
której prawdziwe jest każde zdanie ze zbioru Z.
Przyklady (1) Zdanie "xQ(x, c) wynika logicznie ze zbioru zdań:
{"x"y(P (y, x) Q(x, y)), "xP (c, x)}.
24
"
Rozważmy bowiem dowoln interpretacj I = (D, c", P , Q") i zalóżmy, że
a e
(1) "x"y(P (y, x) Q(x, y)) jest 1 w I,
(2) "xP (c, x) jest 1 w I,
Wówczas:
(3) "y(P (y, a) Q(a, y)) jest 1 w I dla pewnej stalej a z (1), (K1"),
(4) P (c, a) Q(a, c) jest 1 w I z (3), (K1"),
(5) P (c, a) jest 1 w I z (2), (K1"),
(6) Q(a, c) jest 1 w I z (4),(5), (K1 )(a),
"xQ(x, c) jest 1 w I z (6), (W 1").
(2) Zdanie (1) "x(P1(x)'" <" Q(x, x)) nie wynika logicznie ze zbioru zdań:
{(2) "x(P2(x) '" "y(P1(y) <" Q(x, y))), (3) "x(P1(x) P2(x))}.
" "
Aby to wykazać, należy wskazać tak interpretacj I = (D, P1 , P2 , Q"), w
a e
której zdania (2), (3) s prawdziwe, natomiast zdanie (1) jest falszywe. Polóżmy:
a
D = zbiór liczb naturalnych N,
"
P1 = zbiór liczb naturalnych parzystych,
"
P2 = N, Q" = {(i, i) : i " N} (relacja identyczności na N).
W I zdanie (1) jest falszywe: nie istnieje liczba naturalna, która jest parzysta
i różna od siebie samej. Ponieważ np. liczba 1 jest naturalna i każda liczba
parzysta naturalna jest od niej różna, wi prawdziwe w I jest zdanie (2).
ec
Oczywiście każda liczba naturalna parzysta jest liczb naturaln dlatego praw-
a a,
dziwe w I jest zdanie (3).
Definicja tautologii
Zdanie ą danego j I rz nazywamy tautologi gdy ą jest prawdziwe
ezyka edu a,
w każdej interpretacji dla tego j
ezyka.
Przyklady (1) Zdanie: "x"yQ(x, y) "y"xQ(x, y), jest tautologia.
Rozważmy bowiem dowoln interpretacj I = (D, Q"). Naszym celem jest
a e
wykazanie prawdziwości tego zdania w I. Na podstawie (W 1 )(a) zalóżmy,
że
(1) "x"yQ(x, y) jest 1 w I.
Na mocy (W 1") niech a b stala nazywaj a dowolnie wybrany obiekt
edzie ac
z dziedziny D. Wówczas:
(2) "yQ(b, y) jest prawdziwa w I dla pewnej stalej b z (1), (K1"),
(3) Q(b, a) jest 1 w I z (2) (K1"),
"xQ(x, a) jest 1 w I z (3), (W 1"),
co, na mocy (W 1"), dowodzi prawdziwości zdania: "y"xQ(x, y). Zatem,
wedlug (W 1 (a)), nasze zdanie jest prawdziwe w I.
(2) Implikacja: "y"xQ(x, y) "x"yQ(x, y) nie jest tautologia.
25
Aby to wykazać, należy wskazać tak interpretacj I = (D, Q"), w której
a e
zdanie to jest falszywe. Niech wi np.
ec
D = N oraz
Q" = {(i, j) : i, j " N : i e" j}.
W tej interpretacji poprzednik: "y"xQ(x, y) jest prawdziwy, lecz nast
epnik:
"x"yQ(x, y) jest falszywy. Zatem nasza implikacja jest w tej interpretacji
falszywa.
Definicja sprzecznego zbioru zdań
Zbiór zdań X nazywamy niesprzecznym, gdy istnieje interpretacja, w której
każde zdanie z X jest prawdziwe. Zbiór zdań jest sprzeczny, gdy nie jest on
niesprzeczny.
Przyklady (1) Zbiór zdań:
{"x"y((P1(x)'"P2(y)) Q(x, y)), "x(P1(x)'"P2(x)), "x(P1(x) <" Q(x, x))},
jest sprzeczny.
Aby tego dowieść, zalóżmy nie wprost, że jest niesprzeczny. Wówczas istnieje
" "
interpretacja I = (D, P1 , P2 , Q"), w której prawdziwe s formuly:
a
(1) "x"y((P1(x) '" P2(y)) Q(x, y)),
(2) "x(P1(x) '" P2(x)),
(3) "x(P1(x) <" Q(x, x)).
Zatem
(4) P1(a) '" P2(a) jest 1 w I dla pewnego a z (2), (K1"),
(5) "y((P1(a) '" P2(y)) Q(a, y)) jest 1 w I z (1), (K1"),
(6) (P1(a) '" P2(a)) Q(a, a) jest 1 w I z (5), (K1"),
(7) Q(a, a) jest 1 w I z (6), (4), (K1 )(a),
(8) P1(a) jest 1 w I z (4), (K1'"),
(9) P1(a) <" Q(a, a) jest 1 w I z (3), (K1"),
(10) <" Q(a, a) jest 1 w I z (9), (8), (K1 (a)),
(11) Q(a, a) jest 0 w I z (10), (K1 <"),
absurd (11), (7).
(2) Zbiór zdań: {"x(Q(c, x) Q(x, c)), <" Q(c, c)} jest niesprzeczny.
Aby to wykazać, wystarcza wskazać jak interpretacj w której każda
akolwiek e,
formula z tego zbioru jest prawdziwa. Np. niech dziedzin interpretacji b
a edzie
jakikolwiek niepusty zbiór D oraz niech
Q" = {(u, v) : u, v " D, u = v}.
Poj klasyfikacji
ecie
Przypominamy, iż przez relacj binarn określon na danym zbiorze A rozu-
e a a
miemy dowolny (w tym również pusty) zbiór 2-wyrazowych ciagów elementów
zbioru A. Zbiór wszystkich 2-wyrazowych ciagów elementów zbioru A nazy-
wamy relacja peln na A i oznaczamy A2.
a
26
Niech R b dowoln relacj binarn określon na ustalonym zbiorze
edzie a a a a
A. Zamiast pisać: ciag (x, y) elementów zbioru A jest elementem relacji R
piszemy: xRy .
Definicja najważniejszych formalnych wlasności relacji binarnych określonych
na danym zbiorze
Mówimy, że
R jest zwrotna na A wtw dla dowolnego elementu x zbioru A zachodzi
xRx,
R jest przeciwzwrotna na A wtw dla żadnego elementu x zbioru A nie
zachodzi: xRx,
R jest symetryczna na A wtw dla dowolnych elementów x, y zbioru A
(niekoniecznie różnych), jeżeli xRy, to yRx,
R jest przeciwsymetryczna na A wtw dla dowolnych elementów x, y zbioru
A, jeżeli xRy, to nie zachodzi yRx,
R jest antysymetryczna na A wtw dla dowolnych elementów x, y zbioru
A, jeżeli xRy oraz yRx, to x = y,
R jest przechodnia na A wtw dla dowolnych elementów x, y, z zbioru A,
jeżeli xRy oraz yRz, to xRz,
R jest spójna na A wtw dla dowolnych elementów x, y zbioru A, jeżeli
x = y, to xRy lub yRx.
Jeden z najważniejszych typów relacji binarnych określonych na danym zbiorze
stanowia relacje równoważnościowe.
Definicja relacji równoważności
Mówimy, że R jest równoważnościowa lub że jest relacja równoważności na
zbiorze A, gdy R jest zwrotna, symetryczna i przechodnia na A.
Przyklady (1) Relacja pelna A2 oraz tzw. relacja identycznościowa id(A)
określona na A nast aco: dla dowolnych elementów x, y zbioru A,
epuj
x(id(A))y wtw x = y,
s relacjami równoważności na zbiorze A.
a
(2) Na zbiorze trójelementowym A = {a, b, c} mamy pić relacji równoważności:
e
id(A) = {(a, a), (b, b), (c, c)},
R1 = {(a, a), (b, b), (c, c), (a, b), (b, a)},
R2 = {(a, a), (b, b), (c, c), (a, c), (c, a)},
R3 = {(a, a), (b, b), (c, c), (b, c), (c, b)},
27
A2 = {(a, a), (b, b), (c, c), (a, b), (b, a), (a, c), (c, a), (b, c), (c, b)}.
Definicja klasy abstrakcji wzgl danej relacji równoważności
edem
Dla dowolnej relacji równoważności R określonej na danym zbiorze A oraz
dowolnego elementu a zbioru A, zbiór wszystkich elementów x zbioru A ta-
kich, że aRx nazywamy klas abstrakcji b reprezentacji elementu a wzgl
a adz edem
relacji R i oznaczamy w postaci: [a]R.
Przyklady (1) Dla dowolnego elementu a danego zbioru A, [a]id(A) = {a}
oraz [a]A2 = A,
(2) Dla relacji równoważności R1, R2, R3 z poprzedniego przykladu, określonych
na zbiorze {a, b, c} mamy:
[a]R = {a, b}, [b]R = {a, b} = [a]R , [c]R = {c},
1 1 1 1
[a]R = {a, c}, [b]R = {b}, [c]R = {a, c} = [a]R ,
2 2 2 2
[a]R = {a}, [b]R = {b, c}, [c]R = {b, c} = [b]R .
3 3 3 3
Niech R b relacja równoważności na A. Ponieważ dla dowolnego ele-
edzie
mentu a zbioru A zachodzi: aRa, wi a jest elementem swojej klasy abstrakcji,
ec
zatem
dowolna klasa abstrakcji jest niepustym zbiorem.
Interesuj dla zastosowań s kolejne dwie wlasności klas abstrakcji:
ace a
Druga istotna wlasność klas abstrakcji ma postać:
dla dowolnych elementów x, y zbioru A : xRy wtw [x] = [y].
Dowód: (!): Zalóżmy, że xRy. Aby wykazać równość zbiorów dowodzimy,
iż maj one te same elementy. Niech wi a b elementem klasy abstrakcji
a ec edzie
[x]. Zatem xRa. Ponieważ z zalożenia na mocy symetrii relacji R mamy: yRx,
wi w konsekwencji na podstawie przechodniości R otrzymujemy: yRa, co oz-
ec
nacza, iż a jest elementem zbioru [y]. W ten sposób wykazaliśmy, że każdy
element zbioru [x] jest elementem zbioru [y]. Na odwrót przypuśćmy, iż a jest
elementem klasy abstrakcji [y]. Zatem yRa. St na mocy zalożenia i przechod-
ad
niości relacji R mamy: xRa, dlatego a jest elementem zbioru [x].
(!): Zalóżmy, że [x] = [y]. Ponieważ y jest elementem klasy abstrakcji [y],
wi na mocy zalożenia otrzymujemy: y jest elementem zbioru [x], zatem xRy.
ec
Trzecia wlasność klas abstrakcji:
dla dowolnych elementów x, y zbioru A: jeżeli klasy abstrakcji [x], [y] nie s
a
rozlaczne, to s równe.
a
Dowód: Zalóżmy, że a jest elementem obu klas abstrakcji [x], [y]. Wówczas
xRa oraz yRa. Zatem z symetrii relacji R mamy: aRy, co z przechodniości
relacji R implikuje: xRy i w konsekwencji na mocy drugiej wlasności klas ab-
strakcji otrzymujemy: [x] = [y].
28
Definicja podzialu danego zbioru
Przez podzial danego zbioru A rozumiemy dowolny zbiór niepustych
podzbiorów zbioru A spelniaj nast ace dwa warunki:
acy epuj
(1) dowolne dwa różne elementy zbioru s rozlaczne,
a
(2) dla każdego elementu a zbioru A istnieje element X zbioru taki że a
należy do X.
Przyklady (1) Zbiór 1-elementowy {A} jest podzialem zbioru A.
(2) Zbiór zlożony ze wszystkich jednoelementowych podzbiorów {a} dowolnego
zbioru A jest podzialem zbioru A.
(3) Istnieje pić podzialów trójelementowego zbioru A = {a, b, c}:
e
{{a}, {b}, {c}},
{{a, b}, {c}},
{{a, c}, {b}},
{{b, c}, {a}},
{{a, b, c}}.
Jednym z podstawowych twierdzeń dotycz podzialów jest
acych
Zasada abstrakcji
Dla dowolnej relacji równoważności R określonej na zbiorze A zbiór wszyst-
kich klas abstrakcji elementów zbioru A wzgl relacji R jest podzialem tego
edem
zbioru.
Dowód: Zauważmy najpierw, iż dowolna klasa abstrakcji [x] wzgl R
edem
jest niepustym podzbiorem zbioru A (pierwsza wlasność klas abstrakcji). Po
drugie, na mocy trzeciej wlasności klas abstrakcji zachodzi warunek (1) definicji
podzialu dla zbioru wszystkich klas abstrakcji wzgl R. Warunek (2) tej
edem
definicji jest spelniony, bo dowolny element a zbioru A jest elementem klasy
abstrakcji [a].
Twierdzenie 1. Dla dowolnego podzialu zbioru A relacja R określona na
A nast dla dowolnych elementów x, y zbioru A : xRy wtw istnieje
epujaco:
element X podzialu taki, że x, y s elementami X, jest relacj równoważności
a a
na zbiorze A.
Dowód: Zwrotność relacji R wynika z warunku (2) definicji podzialu, syme-
tria wprost z określenia relacji R, natomiast jej przechodniość jest konsekwencj
a
warunku (1) definicji podzialu: przypuśćmy bowiem, że xRy oraz yRz. Zatem
x, y s elementami pewnego zbioru X należ do oraz y, z s elementami
a acego a
pewnego zbioru Y należ do podzialu . St X, Y nie s rozlaczne. Zatem,
acego ad a
wedlug warunku (1) definicji podzialu: X = Y . Dlatego x, z s elementami tej
a
samej czści podzialu . Na mocy definicji relacji R otrzymujemy ostatecznie:
e
xRz.
29
Na mocy zasady abstrakcji, każda relacja równoważności określona na danym
zbiorze wyznacza podzial tego zbioru. Natomiast zgodnie z Tw.1, dowolny
podzial danego zbioru wyznacza relacj równoważności określon na tym zbiorze.
e a
Można wykazać nieco wi relacja równoważności wyznaczona przez podzial,
ecej:
który sam wyznaczony jest przez dan relacj równoważności, jest tożsama z t
a e a
dan relacj Ponadto, podzial wyznaczony przez relacj równoważności, która
a a. e
sama jest wyznaczona przez dany podzial, jest tożsamy z tym danym podzialem.
Przyklad. Przyporz
adkowanie: relacja równoważności ! podzial, dla zbioru
A = {a, b, c} przedstawia si nast aco:
e epuj
{(a, a), (b, b), (c, c)} ! {{a}, {b}, {c}} ,
{(a, a), (b, b), (c, c), (a, b), (b, a)} ! {{a, b}, {c}},
{(a, a), (b, b), (c, c), (a, c), (c, a)} ! {{a, c}, {b}},
{(a, a), (b, b), (c, c), (b, c), (c, b)} ! {{b, c}, {a}},
{(a, a), (b, b), (c, c), (a, b), (b, a), (a, c), (c, a), (b, c), (c, b)} ! {{a, b, c}}.
Definicja relacji bycia drobniejszym
Niech , Ł b a dowolnymi podzialami danego zbioru A. Mówimy, że podzial
ed
jest drobniejszy niż podzial Ł, gdy dla każdego elementu X podzialu istnieje
element Y podzialu Ł taki, że X jest podzbiorem zbioru Y .
Wlasności formalne relacji bycia drobniejszym podaje nast
epujace
Twierdzenie 2. Relacja bycia drobniejszym, tzn relacja dr określona na zbiorze
wszystkich podzialów zbioru A nast aco: drŁ wtw jest drobniejszy niż
epuj
Ł, jest relacj zwrotn antysymetryczn i przechodni
a a, a a.
Dowód: Oczywiście dla dowolnego podzialu danego zbioru A : dr ,
bowiem dla każdego elementu X podzialu : X jest podzbiorem X.
W celu wykazania przechodniości przypuśćmy, że (1) drŁ oraz (2) ŁdrŚ
dla jakichś podzialów , Ł, Ś zbioru A. Aby wykazać, że drŚ zalóżmy, że X
jest elementem podzialu . Wówczas z zalożenia (1) istnieje taki element Y
podzialu Ł, że X jest jego podzbiorem. Analogicznie, na mocy zalożenia (2)
istnieje element Z podzialu Ś taki, że Y jest podzbiorem Z. Zatem X jest
podzbiorem Z (bo relacja bycia podzbiorem jest przechodnia), co dowodzi, iż
drŚ. Aby dowieść antysymetrii relacji dr zalóżmy, że (3) drŁ oraz (4) Łdr .
Celem jest wykazanie równości: = Ł, tzn. tego, że podzialy , Ł maj te same
a
elementy. Niech wi X b elementem podzialu . Wówczas z zalożenia (3)
ec edzie
istnieje element Y podzialu Ł taki, że (5) X jest podzbiorem Y . Z zalożenia
(4) istnieje element Z podzialu taki, że (6) Y jest podzbiorem Z. Wobec
tego z (5) i (6) mamy: X jest podzbiorem Z, a ponieważ X jest niepusty, wi
ec
elementy X, Z podzialu nie s rozlaczne. Zatem X = Z na mocy warunku
a
(1) definicji podzialu. Oznacza to wraz z (6), że Y jest podzbiorem X. St i
ad
z (5) wnosimy, że zbiory X, Y maj te same elementy, tzn. , że X = Y . Lecz
a
30
Y to element podzialu Ł, Zatem X jest elementem podzialu Ł. W ten sposób
wykazano, że każdy element podzialu jest elementem podzialu Ł. Należy
jeszcze dowieść, że każdy element podzialu Ł jest elementem podzialu , co
czyni si analogicznie.
e
Definicja klasyfikacji
Przez klasyfikacj zbioru A rozumie si dowolny niepusty zbiór podzialów
e e
zbioru A taki, że dla dowolnych podzialów , Ł z tego zbioru, jest drobniejszy
niż Ł lub Ł jest drobniejszy niż .
Przyklad. Zbiór podzialów: {{a, b, c}}, {{a, b}, {c}}, {{a}, {b}, {c}} zbioru
A = {a, b, c} jest klasyfikacja tego zbioru.
31
Wyszukiwarka
Podobne podstrony:
J Dyczkowska Logistyka zaopatrzenia i produkcji wpływ na log dystrybucjizestawy cwiczen przygotowane na podstawie programu Mistrz Klawia 6PKC pytania na egzaminPrezentacja ekonomia instytucjonalna na MoodleSerwetka z ukośnymi kieszonkami na sztućceMUZYKA POP NA TLE ZJAWISKA KULTURY MASOWEJlogpzabawki na choinkeLasy mieszane i bory na wydmach nadmorskichAnaliza?N Ocena dzialan na rzecz?zpieczenstwa energetycznego dostawy gazu listopad 09Sposob na wlasny pradtworzenie aplikacji w jezyku java na platforme androidwięcej podobnych podstron