[ Pobierz całość w formacie PDF ]
.Przykładowo struktury, o których była mowa wyżej, możemy zapisać następująco:U1 = )#U = zbiór ludzi; P(x) a" x ma 200 lat*#U2 = )#U = zbiór drzew; P(x) a" x ma 200 lat*#Inne struktury, w których możemy rozpatrywać formułę "x P(x), to na przykład:U3 = )#U = zbiór ludzi; P(x) a" x jest studentem*#U4 = )#U = zbiór drzew; P(x) a" x jest studentem*#,W U3 nasza formuła reprezentować będzie zdanie prawdziwe, natomiast w U4 fałszywe.Strukturę, w której formuła rachunku predykatów jest prawdziwa, nazywamy modelemtej formuły, natomiast strukturę, w której jest fałszywa kontrmodelem.Tak więc możemypowiedzieć, że dla formuły "x P(x), U2 oraz U3 stanowią modele, natomiast U1 i U4 kontrmodele.143 Przejdzmy teraz do zdefiniowania pojęcia tautologii w rachunku predykatów.Jakpamiętamy z rachunku zdań, tautologia, to formuła, która jest zawsze prawdziwa.Skoro wrachunku predykatów prawdziwość formuły zależy od struktury, w jakiej formułęinterpretujemy, możemy powiedzieć, iż tautologia KRP to formuła, która jest prawdziwa wkażdej strukturze.Patrząc na to samo z drugiej strony możemy powiedzieć również, iż wprzypadku tautologii nie istnieje struktura, w której formuła ta byłaby fałszywa.Mówiąckrótko, tautologia nie ma kontrmodelu.Podobnie określić możemy kontratutologię.Jest to formuła fałszywa w każdej strukturzeMówiąc inaczej, nie istnieje struktura, w której formuła będąca kontrtautologią byłabyprawdziwa; kontrtautologia nie ma modelu.3.3.2.PRAKTYKA: WYKAZYWANIE, %7łE FORMUAA NIE JEST TAUTOLOGILUB KONTRTAUTOLOGI.Wykazanie, że dana formuła nie jest tautologią, teoretycznie jest bardzo proste.Skorotautologia musi być prawdziwa w każdej strukturze, to aby udowodnić, że formuła tautologiąnie jest, wystarczy wskazać strukturę, w której jest ona fałszywa (zbudować kontrmodel dlatej formuły).Analogicznie, aby wykazać, że formuła nie jest kontrtautologią, trzeba pokazaćstrukturę, w której jest ona prawdziwa (zbudować model formuły).W praktyce trudność może czasem sprawić wymyślenie odpowiedniej struktury.Nie mabowiem na to jakiejś jednej, sprawdzającej się zawsze, metodyPrzykład:Wykażemy, że formuła "x (P(x) �! Q(x)) nie jest tautologią ani kontrtatologią.Najpierw zbudujemy kontrmodel formuły, a więc strukturę, w której jest ona fałszywa.Wten sposób wykażemy, że nie jest ona tautologią.Aby zbudować odpowiednią strukturę,zacząć musimy od odczytania tego, co mówi nasza formuła.Otóż stwierdza ona, że każdyobiekt, który ma własność P, ma również własność Q.Aby zbudować kontrmodel, musimywięc dobrać własności P i Q w taki sposób, aby w jakimś zbiorze nie było to prawdą.Wezmyprzykładowo zbiór ludzi jako uniwersum i własność bycia kobietą jako odpowiednikpredykatu P oraz bycia matką jako odpowiednik Q.Formalnie:U1 = )#U = zbiór ludzi; P(x) a" x jest kobietą, Q(x) a" x jest matką*#144 W strukturze U1, nasza formuła stwierdza, że dla każdego człowieka, jeśli człowiek tenjest kobietą, to jest również matką, czyli w skrócie każda kobieta jest matką, co jestoczywiście zdaniem fałszywym.U1 jest zatem kontrmodelem dla formuły "x (P(x) �! Q(x))Aby zbudować model, musimy dobrać własności P i Q tak, aby otrzymać zdanieprawdziwe.W powyższym przykładzie możemy to łatwo uczynić zamieniając własnościmiejscami, czyli:U2 = )#U = zbiór ludzi; P(x) a" x jest matką, Q(x) a" x jest kobietą*#W strukturze U2, nasza formuła stwierdza, że każda matka jest kobietą, co jest oczywiściezdaniem prawdziwym.U2 jest zatem modelem dla formuły "x (P(x) �! Q(x)).Skoro zbudowaliśmy dla formuły kontrmodel i model, oznacza to, że nie jest onatautologią ani kontrtautologią.Podane wyżej rozwiązanie jest oczywiście jednym z nieskończonej ilości właściwychodpowiedzi.Ktoś mógłby przykładowo zbudować takie struktury:U3 = )#U = zbiór polityków; P(x) a" x jest posłem, Q(x) a" x jest uczciwy*#, orazU4 = )#U = zbiór liczb; P(x) a" x jest podzielne przez 4, Q(x) a" x jest parzyste*#.Struktura U3 stanowiłaby wtedy kontrmodel, gdyż umieszczona w niej formułastwierdzałaby, że każdy polityk, który jest posłem, jest uczciwy, natomiast U4 byłabymodelem, ponieważ umieszczona w tej strukturze formuła głosiłaby, iż każda liczbapodzielna przez 4, jest liczbą parzystą.To, jaki model i kontrmodel zostanie stworzony, zależy tylko od wyobraznibudowniczego.Przykład:Wykażemy, że tautologią ani kontrtautologią nie jest formuła: "x R(x,x)Formuła powyższa stwierdza, że każdy obiekt jest w pewnej relacji do samego siebie [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl centka.pev.pl
.Przykładowo struktury, o których była mowa wyżej, możemy zapisać następująco:U1 = )#U = zbiór ludzi; P(x) a" x ma 200 lat*#U2 = )#U = zbiór drzew; P(x) a" x ma 200 lat*#Inne struktury, w których możemy rozpatrywać formułę "x P(x), to na przykład:U3 = )#U = zbiór ludzi; P(x) a" x jest studentem*#U4 = )#U = zbiór drzew; P(x) a" x jest studentem*#,W U3 nasza formuła reprezentować będzie zdanie prawdziwe, natomiast w U4 fałszywe.Strukturę, w której formuła rachunku predykatów jest prawdziwa, nazywamy modelemtej formuły, natomiast strukturę, w której jest fałszywa kontrmodelem.Tak więc możemypowiedzieć, że dla formuły "x P(x), U2 oraz U3 stanowią modele, natomiast U1 i U4 kontrmodele.143 Przejdzmy teraz do zdefiniowania pojęcia tautologii w rachunku predykatów.Jakpamiętamy z rachunku zdań, tautologia, to formuła, która jest zawsze prawdziwa.Skoro wrachunku predykatów prawdziwość formuły zależy od struktury, w jakiej formułęinterpretujemy, możemy powiedzieć, iż tautologia KRP to formuła, która jest prawdziwa wkażdej strukturze.Patrząc na to samo z drugiej strony możemy powiedzieć również, iż wprzypadku tautologii nie istnieje struktura, w której formuła ta byłaby fałszywa.Mówiąckrótko, tautologia nie ma kontrmodelu.Podobnie określić możemy kontratutologię.Jest to formuła fałszywa w każdej strukturzeMówiąc inaczej, nie istnieje struktura, w której formuła będąca kontrtautologią byłabyprawdziwa; kontrtautologia nie ma modelu.3.3.2.PRAKTYKA: WYKAZYWANIE, %7łE FORMUAA NIE JEST TAUTOLOGILUB KONTRTAUTOLOGI.Wykazanie, że dana formuła nie jest tautologią, teoretycznie jest bardzo proste.Skorotautologia musi być prawdziwa w każdej strukturze, to aby udowodnić, że formuła tautologiąnie jest, wystarczy wskazać strukturę, w której jest ona fałszywa (zbudować kontrmodel dlatej formuły).Analogicznie, aby wykazać, że formuła nie jest kontrtautologią, trzeba pokazaćstrukturę, w której jest ona prawdziwa (zbudować model formuły).W praktyce trudność może czasem sprawić wymyślenie odpowiedniej struktury.Nie mabowiem na to jakiejś jednej, sprawdzającej się zawsze, metodyPrzykład:Wykażemy, że formuła "x (P(x) �! Q(x)) nie jest tautologią ani kontrtatologią.Najpierw zbudujemy kontrmodel formuły, a więc strukturę, w której jest ona fałszywa.Wten sposób wykażemy, że nie jest ona tautologią.Aby zbudować odpowiednią strukturę,zacząć musimy od odczytania tego, co mówi nasza formuła.Otóż stwierdza ona, że każdyobiekt, który ma własność P, ma również własność Q.Aby zbudować kontrmodel, musimywięc dobrać własności P i Q w taki sposób, aby w jakimś zbiorze nie było to prawdą.Wezmyprzykładowo zbiór ludzi jako uniwersum i własność bycia kobietą jako odpowiednikpredykatu P oraz bycia matką jako odpowiednik Q.Formalnie:U1 = )#U = zbiór ludzi; P(x) a" x jest kobietą, Q(x) a" x jest matką*#144 W strukturze U1, nasza formuła stwierdza, że dla każdego człowieka, jeśli człowiek tenjest kobietą, to jest również matką, czyli w skrócie każda kobieta jest matką, co jestoczywiście zdaniem fałszywym.U1 jest zatem kontrmodelem dla formuły "x (P(x) �! Q(x))Aby zbudować model, musimy dobrać własności P i Q tak, aby otrzymać zdanieprawdziwe.W powyższym przykładzie możemy to łatwo uczynić zamieniając własnościmiejscami, czyli:U2 = )#U = zbiór ludzi; P(x) a" x jest matką, Q(x) a" x jest kobietą*#W strukturze U2, nasza formuła stwierdza, że każda matka jest kobietą, co jest oczywiściezdaniem prawdziwym.U2 jest zatem modelem dla formuły "x (P(x) �! Q(x)).Skoro zbudowaliśmy dla formuły kontrmodel i model, oznacza to, że nie jest onatautologią ani kontrtautologią.Podane wyżej rozwiązanie jest oczywiście jednym z nieskończonej ilości właściwychodpowiedzi.Ktoś mógłby przykładowo zbudować takie struktury:U3 = )#U = zbiór polityków; P(x) a" x jest posłem, Q(x) a" x jest uczciwy*#, orazU4 = )#U = zbiór liczb; P(x) a" x jest podzielne przez 4, Q(x) a" x jest parzyste*#.Struktura U3 stanowiłaby wtedy kontrmodel, gdyż umieszczona w niej formułastwierdzałaby, że każdy polityk, który jest posłem, jest uczciwy, natomiast U4 byłabymodelem, ponieważ umieszczona w tej strukturze formuła głosiłaby, iż każda liczbapodzielna przez 4, jest liczbą parzystą.To, jaki model i kontrmodel zostanie stworzony, zależy tylko od wyobraznibudowniczego.Przykład:Wykażemy, że tautologią ani kontrtautologią nie jest formuła: "x R(x,x)Formuła powyższa stwierdza, że każdy obiekt jest w pewnej relacji do samego siebie [ Pobierz całość w formacie PDF ]