Logice pierwszego rzędu




Pobierz 128.04 Kb.
NazwaLogice pierwszego rzędu
strona3/3
Data konwersji18.12.2012
Rozmiar128.04 Kb.
TypDokumentacja
1   2   3

§6. Wynikanie w logice pierwszego rzędu




Wszystkie prezentowane w tym temacie pojęcia i fakty dotyczą dowolnego ustalonego języka pierwszego rzędu. Zakłada się, że wszystkie pojawiające się w przykładach symbole proste należą do słownika tego języka oraz że używane w wielu miejscach wyrażenie „interpretacja” rozumie się zawsze jako „interpretacja dla tego języka”.


Definicja. Mówimy, że zdanie  wynika (logicznie) ze zbioru zdań X (co zapisujemy w postaci: X ), gdy  jest prawdziwe w każdej interpretacji, w której prawdziwe są wszystkie zdania z X.


Interpretacja I, w której prawdziwe jest każde zdanie z jakiegoś zbioru zdań X nazywana jest modelem dla X. Model dla jednoelementowego zbioru zdań {} nazywany jest modelem dla zdania . Zatem definicję wynikania można sformułować również w takiej formie: zdanie  wynika ze zbioru zdań X, gdy każdy model dla X jest modelem dla .


Przykład. Zdanie xxRc wynika ze zbioru zdań: {xy(ySx xRy), xcSx}. Rozważmy bowiem dowolną interpretację I = (D,c*,R*,S*) i załóżmy, że

  1. xy(ySx xRy) jest prawdziwa w I,

  2. xcSx jest prawdziwa w I.

Wówczas

  1. y(ySa aRy) jest prawdziwa w I, dla pewnej stałej a, (K) z (1),

  2. cSa aRc jest prawdziwa w I, (K) z (3),

  3. cSa jest prawdziwa w I, (K) z (2),

  4. aRc jest prawdziwa w I, (K) z (4),(5),

  5. xxRc jest prawdziwa w I, (D) z (6).


Zdanie (1) x(Px   xRx) nie wynika ze zbioru zdań: {(2) x(Qx  y(Py  xRy)), (3) x(Px Qx)}. Aby to wykazać, należy wskazać taką interpretację I = (D,P*,Q*,R*), w której zdania (2), (3) są prawdziwe, natomiast zdanie (1) jest fałszywe. Połóżmy, D = zbiór liczb naturalnych, P* = zbiór liczb naturalnych parzystych, Q* = D oraz R* = {(i,i): i D}. Wówczas w I zdanie (1) nieformalnie interpretujemy jako: istnieje liczba naturalna parzysta i różna od siebie samej, co jest fałszem. Ponieważ na przykład 1 jest liczbą naturalną oraz każda liczba parzysta jest od niej różna, więc prawdziwe w I jest zdanie (2) (istnieje liczba naturalna różna od każdej liczby naturalnej parzystej). Oczywiście każda liczba naturalna parzysta jest liczbą naturalną, zatem prawdziwe w I jest zdanie (3).


§7. Tautologia


Definicja. Zdanie  nazywamy tautologią, gdy  jest prawdziwe w każdej interpretacji (każda interpretacja jest modelem dla ). Zdania ,  są logicznie równoważne, gdy    jest tautologią.


Przykład. Zdanie: xyxRy  yxxRy, jest tautologią. Rozważmy bowiem dowolną interpretację I = (D,R*). Naszym celem jest wykazanie prawdziwości tego zdania w I. Na podstawie (D) załóżmy, że

  1. xyxRy jest prawdziwa w I.

Postępując według (D) nazwijmy stałą a dowolnie wybrany ustalony obiekt z dziedziny D. Wówczas

  1. ybRy jest prawdziwa w I dla pewnej stałej b, (K) z (1),

bRa jest prawdziwa w I, (K) z (2),

xxRa jest prawdziwa w I, (D) z (3),

co na mocy (D), dowodzi prawdziwości zdania: yxxRy. Zatem, według (D), wyjściowe zdanie jest prawdziwe w I.


Implikacja odwrotna: yxxRy  xyxRy, nie jest tautologią. Aby to wykazać, należy wskazać taką interpretację I = (D,R*), w której implikacja ta jest fałszywa. Niech więc na przykład D będzie zbiorem liczb naturalnych oraz R* = {(i,j): i,jD, i j}. W tej interpretacji poprzednik: yxxRy (dla każdej liczby naturalnej istnieje liczba naturalna od niej większa), jest prawdziwy, podczas gdy następnik: xyxRy (istnieje liczba naturalna większa od każdej liczby naturalnej), jest fałszywy. Zatem cała implikacja jest w tej interpretacji fałszywa.


Twierdzenie 1. Zdanie jest tautologią wtwwynika z każdego zbioru zdań.


Dowód: Aby dowieść twierdzenia postaci równoważności wykazujemy prawdziwość dwóch implikacji: prostej: () i odwrotnej: ().

(): Załóżmy, że  jest tautologią. Niech X będzie dowolnym zbiorem zdań oraz I – jakąkolwiek interpretacją, w której każde zdanie z X jest prawdziwe. Wtedy z założenia,  jest prawdziwe w I, zatem wynika z X.

(): Załóżmy niewprost, że  wynika z każdego zbioru zdań, ale nie jest tautologią. Wówczas istnieje interpretacja I, w której zdanie  jest fałszywe. Zatem zdanie  jest w I prawdziwe. Lecz z założenia,  wynika ze zbioru 1-elementowego {}, dlatego jest prawdziwe w I, co jest niemożliwe. 


Twierdzenie 2. Dla dowolnych zdań ,:  wynika ze zbioru {} wtw zdanie    jest tautologią.


Dowód: Oczywisty, na podstawie definicji wynikania, tautologii i warunku prawdziwości dla implikacji. 


§8. Sprzeczny zbiór zdań


Definicja. 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 niesprzeczny.


Przykład. Zbiór zdań: {xy((Px Qy)  xRy), x(Px Qx), x(Px  xRx)}, jest sprzeczny. Aby tego dowieść, załóżmy niewprost, że jest niesprzeczny. Wówczas istnieje interpretacja I = (D,P*,Q*,R*), w której prawdziwe są formuły:

  1. xy((Px Qy)  xRy),

  2. x(Px Qx),

  3. x(Px  xRx).

Wówczas:

  1. Pa Qa jest prawdziwa w I dla pewnej stałej a, (K) z (2),

  2. y((Pa Qy)  aRy) jest prawdziwa w I, (K) z (1),

  3. (Pa Qa)  aRa jest prawdziwa w I, (K) z (5),

  4. aRa jest prawdziwa w I, (K) z (6),(4),

  5. Pa jest prawdziwa w I, (K) z (4),

  6. Pa  aRa jest prawdziwa w I, (K) z (3),

  7. aRa jest prawdziwa w I, (K) z (9),(8),

  8. aRa nie jest prawdziwa w I, (K) z (10),

absurd: (11), (7).


Zbiór zdań: {x(cRx xRc), cRc} jest niesprzeczny. Aby to wykazać, wystarcza wskazać jakąkolwiek interpretację, w której każda formuła z tego zbioru jest prawdziwa. Na przykład, niech dziedziną interpretacji będzie dowolny niepusty zbiór oraz R* = {(u,v): u,vD, uv}.


Twierdzenie 3. Zbiór zdań X jest sprzeczny wtw każde zdanie wynika ze zbioru X.


Dowód: (): Załóżmy niewprost, że X jest sprzeczny oraz pewne zdanie  z niego nie wynika. Wówczas, z definicji wynikania, istnieje interpretacja, w której  jest fałszywe oraz każde zdanie z X jest prawdziwe. Ten ostatni fakt oznacza, że X jest niesprzeczny, co jest niemożliwe.

(): Załóżmy niewprost, że każda formuła domknięta wynika ze zbioru X oraz że X jest niesprzeczny. Wtedy dla pewnej interpretacji I, każda formuła z X jest w I prawdziwa. Niech  będzie jakimkolwiek zdaniem, na przykład xx = x. Ponieważ na mocy założenia, zarówno  jak i  wynikają z X, więc oba te zdania są prawdziwe w I, co jest niemożliwe. 


Twierdzenie 4. Zbiór zdań X jest sprzeczny wtw istnieje zdanie takie, że zarówno jak  wynikają z X.


Dowód: (): Oczywisty na mocy Tw.3.

(): Analogiczny do dowodu () Tw.3. 


Twierdzenie 5. Zdanie wynika ze zbioru zdań X wtw zbiór zdań: X  {}, jest sprzeczny.


Dowód: (): Załóżmy, że X  {} jest niesprzeczny. Niech więc I będzie interpretacją, w której każde zdanie z X jest prawdziwe oraz zdanie  jest prawdziwe, tzn.  jest fałszywe. Stąd, na mocy definicji wynikania, zdanie  nie wynika z X.

(): Załóżmy, że X  {} jest sprzeczny. Aby wykazać, że  wynika z X, przypuśćmy, że I jest interpretacją, w której każde zdanie z X jest prawdziwe. Z założenia otrzymujemy wtedy, iż  jest fałszywe w I, zatem  jest prawdziwe w I. Ostatecznie, wobec dowolności wyboru interpretacji I, zdanie  wynika z X. 


Pojęcia wynikania i sprzecznego (niesprzecznego) zbioru formuł domkniętych rozszerzamy dla zdań z języka etnicznego. Mówimy więc, że zdanie A wynika ze zbioru zdań X, gdy formuła będąca schematem zdania A wynika ze zbioru schematów zdań należących do zbioru X. Mówimy, że zbiór zdań (z języka etnicznego) jest sprzeczny, gdy zbiór schematów tych zdań jest sprzeczny.


§9. Pojęcie teorii pierwszego rzędu


Definicja. Zbiór zdań X nazywamy teorią (pierwszego rzędu), gdy istnieje taki zbiór zdań Y, że X jest zbiorem wszystkich i tylko tych zdań, które wynikają z Y, tzn. X = {: Y ╞ } dla pewnego zbioru zdań Y. Każdy ze zbiorów Y takich, że X = {: Y ╞ }, nazywany jest zbiorem aksjomatów teorii X (każde zdanie z Y zwane jest aksjomatem teorii X).


Twierdzenie 6. Dla dowolnej teorii X każdy jej aksjomat należy do X.


Dowód: Niech Y będzie zbiorem aksjomatów teorii X. Gdy   Y, to naturalnie Y ╞  (każdy model dla Y jest modelem dla ), zatem   X. 


Twierdzenie 7. Dla dowolnych teorii X oraz interpretacji I, I jest modelem dla X wtw I jest modelem dla jakiegokolwiek zbioru aksjomatów teorii X.


Dowód: (): Oczywisty na podstawie Tw.6.

(): Niech Y będzie zbiorem aksjomatów teorii X oraz niech I będzie interpretacją, w której każdy aksjomat z Y jest prawdziwy. Rozważmy dowolne zdanie   X. Ponieważ Y ╞ , więc  jest w I prawdziwe. Wobec dowolności wyboru zdania  z teorii X, interpretacja I jest modelem dla X. 


Przykładem teorii jest zbiór Ver(K) wszystkich zdań prawdziwych w każdej interpretacji należącej do danej niepustej klasy K interpretacji:


Twierdzenie 8. Dla dowolnej niepustej klasy K interpretacji, Ver(K) = {: Ver(K) ╞ }.


Dowód: Aby dowieść równości zbiorów należy wykazać, że owe zbiory mają te same elementy. W tym celu wykazuje się, że każdy element jednego zbioru należy do drugiego zbioru oraz na odwrót, że każdy element drugiego zbioru należy do tego pierwszego. Załóżmy zatem, że   Ver(K). Ponieważ zbiór {: Ver(K) ╞ } jest teorią taką, że zbiorem jej aksjomatów jest Ver(K) , więc na mocy Tw.6:   {: Ver(K) ╞ }. Na odwrót, załóżmy, że   {: Ver(K) ╞ }, tzn., że Ver(K) ╞ . Aby wykazać, że   Ver(K), rozważmy dowolnie wybraną interpretację I K. Wówczas z definicji zbioru zdań Ver(K) stwierdzamy, że I jest modelem dla Ver(K). Wobec wynikania zdania  ze zbioru Ver(K) otrzymujemy: I jest modelem dla . Na mocy dowolności wyboru I Ver(K) stwierdzamy, że  jest prawdziwe w każdej interpretacji z klasy K, zatem   Ver(K). 


Ćwiczenia





  1. Wykazać, posługując się klasyczną logiką pierwszego rzędu, że zdanie: Jan jest dobrego zdania o sobie samym, nie wynika ze zdania: Każdy, o kim Jan jest dobrego zdania, jest dobrego zdania o Janie.




  1. Wykazać, posługując się klasyczną logiką pierwszego rzędu, że zdanie: Jan jest dobrego zdania o sobie samym, nie wynika ze zdania: Istnieje ktoś, kto jest dobrego zdania o Janie i o kim Jan jest dobrego zdania.




  1. Wykazać, posługując się klasyczną logiką pierwszego rzędu, że zdanie: Niektórzy materialiści są racjonalistami, nie wynika ze zbioru zdań: {Niektórzy filozofowie są materialistami, Niektórzy filozofowie są racjonalistami}.




  1. Wykazać, posługując się klasyczną logiką pierwszego rzędu, że zdanie: Niektórzy filozofowie są uczonymi, nie wynika ze zbioru zdań: {Każdy uczony jest racjonalistą, Niektórzy filozofowie nie są racjonalistami}.




  1. Czy zdanie: Niektórzy ludzie lubią Jana, wynika ze zbioru zdań: {Niektórzy ludzie lubią każdego, kto jest o nich dobrego zdania, Jan jest dobrego zdania o każdym człowieku}? Odpowiedź uzasadnić.




  1. Wykazać, że zdanie: x(Fx  xCx), nie wynika ze zbioru zdań: {x(Ux  y(Fy  xCy)), x(Fx Ux)}.




  1. Wykazać, że następujące zdania nie są tautologiami logiki pierwszego rzędu:

(a) xyxRy  yxxRy,

  1. x(Px Qx)  (xPx  xQx),




  1. Czy następujące zdania są tautologiami logiki pierwszego rzędu? Odpowiedź uzasadnić. (a) xyxRy  yxxRy,

  1. x(Px Qx)  (xPx  xQx),

(c) (xPx  xQx)  x(Px Qx).

(d)x(Px Qx)  (xPx  xQx),

(e) (xPx  xQx)  x(Px Qx),

  1. (xPx  xQx)  x(Px Qx)




  1. Stosując klasyczną logikę pierwszego rzędu wykazać, że następujące zbiory zdań są sprzeczne:

  1. {Żadne zdanie nie wynika ze zdania, które mu przeczy, Każde zdanie przeczy jakiemuś zdaniu, Istnieją zdania, z których wynika każde zdanie},

  2. {Niektórzy ludzie lubią każdego, kto jest o nich dobrego zdania, Jan jest dobrego zdania o każdym człowieku, Nikt nie lubi Jana},

  3. {Istnieją zdania, które wynikają z każdego zdania i z których każde zdanie wynika, Jeśli jakieś zdanie wynika z każdego zdania, to jest ono prawdziwe, Jeśli z jakiegoś zdania wynika każde zdanie, to nie jest ono prawdziwe}.

  4. {Istnieją zdania, które wynikają z każdego zdania, Dla każdego zdania można podać takie, z którego ono nie wynika}




  1. Czy następujące zbiory zdań są sprzeczne? Odpowiedź uzasadnić.

  1. {xy((Px Qy)  xRy), x(Px Qx), x(Px  xRx)},

  2. {x(Px Qx), x(Qx  yxRy), xPx, xyxRy}






1   2   3

Powiązany:

Logice pierwszego rzędu iconSpermatocyty pierwszego rzędu

Logice pierwszego rzędu iconRównanie różniczkowe liniowe rzędu pierwszego. Definicja

Logice pierwszego rzędu iconRÓwnania róŻniczkowe zwyczajne def równaniem różniczkowym zwyczajnym pierwszego rzędu

Logice pierwszego rzędu iconRównania różniczkowe rzędu pierwszego sprowadzone do równań różniczkowych o zmiennych rozdzielonych

Logice pierwszego rzędu iconKompendium Nauki Społecznej Kościoła, Jedność, Kielce 2005, 144 – 148
«pomocą» dla mężczyzny, tak jak mężczyzna jest «pomocą» dla kobiety!”290: w ich spotkaniu urzeczywistnia się koncepcja harmonijnej...

Logice pierwszego rzędu iconMaria Smereczyńska rodzina podstawową wspólnotą Życia społecznego I działalności państwa
«pomocniczości» głosi, że: „ społeczność wyższego rzędu nie powinna ingerować w sprawy społeczności niższego rzędu, pozbawiając ją...

Logice pierwszego rzędu iconRachunek zdań. Definicja w logice zdaniem

Logice pierwszego rzędu iconSystemy produkcji. Fakty I reguły w logice predykatów

Logice pierwszego rzędu iconLogika dla opornych Wszystko co powinniście wiedzieć o logice

Logice pierwszego rzędu iconCharakterystyka owadów chronionych z rzędu ważek. Charakterystyka owadów chronionych z rzędu chrząszczy

Umieść przycisk na swojej stronie:
Rozprawki


Baza danych jest chroniona prawami autorskimi ©pldocs.org 2014
stosuje się do zarządzania
Rozprawki
Dom