Rozdział Logika pierwszego rzędu



Pobieranie 386,8 Kb.
Data24.02.2019
Rozmiar386,8 Kb.

Rozdział 1. Logika pierwszego rzędu


Niniejszy rozdział poświęcony jest logice pierwszego rzędu. Z formalnego punktu widzenia, każda logika postrzegana jest jako para obiektów: jednym z nich jest formalny język, drugim – relacja wynikania zdefiniowana na tym języku. Na dowolny język formalny składają się pewne skończone ciągi symboli zwane wyrażeniami (tego języka), wśród których zawsze, tzn. niezależnie od rodzaju języka, wyróżnia się wyrażenia typu zdaniowego, zwane czasem formułami zdaniowymi lub krótko – formułami. Języki formalne służą różnorakim celom (na przykład języki programowania - zapisywaniu programu komputerowego). Ten język formalny, który jest elementem jakiejś logiki, ściśle reprezentuje pewien, mniej lub bardziej obszerny, fragment języka etnicznego. Relacja wynikania zdefiniowana na takim języku jest pewnym stosunkiem w jakim pozostają do siebie pary obiektów: zbiór formuł oraz formuła (wówczas gdy mówimy prawdziwie, że formuła ta wynika z tego zbioru formuł), stosunkiem, który przenosi się na pary obiektów innego typu: zbiór zdań i zdanie z języka etnicznego (reprezentowane odpowiednio przez poprzednie pary - tzn. zdania są reprezentowane przez formuły) wtedy, gdy wnioskujemy to zdanie uznając zdania z tego zbioru za przesłanki tego wnioskowania.

Zatem logika pierwszego rzędu może być traktowana jako para obiektów, pierwszym z nich jest język pierwszego rzędu, drugim – relacja wynikania zdefiniowana na tym języku. Najpierw, w §1 i §2 omawiamy pojęcie języka pierwszego rzędu: definiujemy słownik, zbiór termów nazwowych oraz zbiór formuł. Podajemy sposoby reprezentowania niektórych zdań z języka etnicznego w języku pierwszego rzędu.

W §3 podajemy tzw. semantykę dla języka pierwszego rzędu, czyli rzeczywistość, do której odnoszą się wyrażenia tego języka, umożliwiającą zdefiniowanie relacji wynikania oraz innych pomocniczych pojęć. Centralnym obiektem tej semantyki jest interpretacja języka pierwszego rzędu. Ponadto, definiujemy tu pomocnicze pojecie waluacji (termów domkniętych) dla danej interpretacji. W §4 podajemy istotne dla określenia relacji wynikania, pojęcie prawdziwości formuły domkniętej w danej interpretacji. Z przedstawionych warunków prawdziwości formuł w danej interpretacji wynikają reguły wykazywania prawdziwości formuł oraz reguły wykorzystania informacji o prawdziwości formuł w danej interpretacji (§5).

§6 zawiera kluczową definicję relacji wynikania, §7 oraz §8 inne istotne pojęcia: tautologii oraz sprzecznego zbioru formuł, z relacją wynikania związane. Ponadto w §9 omawiamy istotne dla dalszych rozważań pojęcie teorii pierwszego rzędu (jako teorii logiki pierwszego rzędu). Wszystkie teorie prezentowane w tym kursie: teoria mnogości Zermelo-Fraenkla (ZF), naiwna teoria mnogości w wersji aksjomatycznej oraz teoria algebr Boole’a – są teoriami pierwszego rzędu.

§1. Słowniki języków pierwszego rzędu


Według najogólniejszej ze spotykanych w literaturze definicji, przez język sformalizowany rozumie się dowolny niepusty zbiór skończonych ciągów, których wyrazami są symbole proste składające się na tzw. słownik tego języka. Aby więc zdefiniować język sformalizowany, należy najpierw podać jego słownik, następnie określić jakie skończone sekwencje elementów słownika (czyli symboli prostych) traktuje się jako elementy języka.

Język polski, nie będąc wszakże językiem sformalizowanym, daje się w myśl powyższej definicji ujmować – jako pewien zbiór skończonych ciągów, których wyrazami są pojedyncze słowa języka polskiego oraz znaki interpunkcyjne. Język polski jest więc takim językiem, którego słownik jest zbiorem wszystkich pojedynczych słów oraz znaków interpunkcyjnych (nie odróżnia tu się słowa czy znaku interpunkcyjnego fonetycznego od napisu).

Różnorodne języki programowania są naturalnie językami sformalizowanymi. Ich słowniki zawierają zazwyczaj tzw. słowa kluczowe (np. begin, end, let, if then itp.), zmienne różnych typów, stałe różnych typów, symbole operacji, symbole relacji, symbole logiczne, nawiasy różnych typów itp.


Na słownik języka pierwszego rzędu składają się następujące symbole proste:


  • zmienne nazwowe: x1, x2, ..., xn, ...

  • spójniki: , , , , ,

reprezentujące odpowiednio wyrażenia: nieprawda, że..., ... i ..., ... lub ..., jeżeli ..., to ..., ... wtedy i tylko wtedy, gdy ... oraz nazywane odpowiednio spójnikiem negacji, koniunkcji, alternatywy, implikacji oraz równoważności

  • kwantyfikatory: , ,

reprezentujące odpowiednio wyrażenia: dla każdego ..., dla pewnego ... oraz nazywane odpowiednio kwantyfikatorem dużym (ogólnym lub uniwersalnym), małym (szczegółowym lub egzystencjalnym)

  • 2-agumentowy predykat identyczności: =,

reprezentujący wyrażenie: ... równa się ... (... jest identyczne z ...)

  • stałe nazwowe: c1, c2, ..., ck , k  0 (gdy k = 0, to w słowniku nie występują stałe nazwowe)

  • symbole funkcyjne 1- lub 2-argumentowe: f1, f2, ..., fm , m  0

  • predykaty (lub symbole relacyjne) 1- lub 2-argumentowe: P1, P2, ..., Pn , n  0

  • nawiasy: (, ).

Spójniki, kwantyfikatory oraz predykat identyczności nazywane są symbolami logicznymi lub stałymi logicznymi. Stałe nazwowe, symbole funkcyjne oraz predykaty (bez predykatu identyczności) to symbole pozalogiczne.

Każdemu symbolowi funkcyjnemu oraz relacyjnemu przyporządkowana jest jedna z dwóch liczb: 1, 2, nazywana liczbą argumentów (jest to liczba tzw. termów nazwowych, z którymi symbol się łączy tworząc wyrażenia złożone – por. dalej).
Dowolny skończony ciąg symboli ze słownika zapisujemy jako sekwencję wyłącznie symboli, tzn. ani nie oddzielamy przecinkami jego wyrazów, ani nie zaznaczamy nawiasów zewnętrznych: skończony ciąg zazwyczaj zapisywany w postaci (a1,a2,...,ak) zapisujemy jako a1a2...ak, gdzie a1, a2, ..., ak są symbolami ze słownika. Ponadto każdy z symboli prostych traktujemy jako jednowyrazowy ciąg.

Jeżeli ,  są ciągami symboli odpowiednio postaci: a1a2...am, b1b2...bn, to znakiem  oznaczamy tzw. konkatenację tych ciągów, tzn. (n+m)-wyrazowy ciąg postaci: a1a2...amb1b2...bn. Łatwo zauważyć, że operacja konkatenacji, czyli przyporządkowanie dwuwyrazowej sekwencji (,) ciągów ,  ich konkatenacji , jest działaniem łącznym, tzn. dla dowolnych skończonych ciągów , ,  symboli ze słownika zachodzi: () = () (konkatenacja dwóch ciągów:  oraz , jest tym samym ciągiem co konkatenacja ciągów  oraz ). Dlatego konkatenację (...((12)3)...)k oznaczamy jako 123...k.




§2. Termy oraz formuły pierwszego rzędu

Języki pierwszego rzędu różnią się swoimi słownikami, a dokładniej, symbolami pozalogicznymi. Z ustalonym zestawem symboli pozalogicznych (stałych nazwowych oraz symboli funkcyjnych i relacyjnych) jest jednoznacznie związany dokładnie jeden język pierwszego rzędu. W każdym języku pierwszego rzędu występują te same zmienne nazwowe oraz stałe logiczne. Dowolny język pierwszego rzędu jest sumą dwóch zbiorów: zbioru termów nazwowych (krótko – termów) oraz zbioru formuł.



Definicja. (zbioru termów).

  1. Dowolna zmienna lub stała nazwowa jest termem,

  2. jeżeli f jest 1-argumentowym symbolem funkcyjnym oraz ciąg t symboli prostych jest termem, to ciąg postaci: ft, jest termem (ciąg ft jest konkatenacją 1-wyrazowego ciągu f oraz ciągu t),

  3. jeżeli f jest 2-argumentowym symbolem funkcyjnym oraz ciągi t, s są termami, to ciąg postaci: (tfs) jest termem,

  4. jeżeli ciąg t symboli prostych jest termem, to t jest bądź zmienną nazwową, bądź stałą nazwową, bądź ma postać określoną w (2) lub w (3).

Warunek (1) podaje najprostsze typy termów nazwowych, zaś warunki (2), (3) określają sposoby generowania termów złożonych z mniej złożonych (w szczególności z tych najprostszych), wreszcie warunek (4) dookreśla zbiór termów jako taki zbiór skończonych ciągów symboli ze słownika, które mają wyłącznie postać podaną w warunkach (1), (2), (3).



Definicja. (zbioru formuł).

  1. Jeżeli ciągi t, s symboli ze słownika są termami, to ciąg postaci: t = s jest formułą,

  2. jeżeli P jest 1-argumentowym predykatem oraz ciąg t jest termem, to ciąg postaci: Pt jest formułą,

  3. jeżeli P jest 2-argumentowym predykatem oraz t, s są termami, to ciąg tPs jest formułą,

  4. jeżeli ciąg  jest formułą, to ciąg  również jest formułą,

  5. jeżeli ,  są formułami, to następujące cztery ciągi: (  ), (  ), (  ), (  ) są formułami,

  6. jeżeli x jest zmienna nazwową oraz  jest formułą, to ciągi: x, x są formułami,

  7. jeżeli ciąg  jest formułą, to  ma jedną z postaci podanych w warunkach (1) – (6).

Formuły o najprostszej postaci, a więc te określone warunkami (1), (2), (3), to tzw. formuły atomowe. Warunki (4), (5), (6) podają sposoby generowania formuł złożonych z mniej złożonych. Te bardziej złożone postacie formuł podane w tych warunkach, nazywane są identycznie jak nazywane są stałe logiczne w tych postaciach występujące. Tak więc warunek (4) podaje postać formuły negacyjnej, w (5) wymieniono postacie formuł koniunkcji, alternatywy, implikacji oraz równoważności, wreszcie w (6) podano dwa typy formuł: ogólną (uniwersalną) oraz szczegółową (egzystencjalną). Rola warunku (7) jest identyczna do tej, która odgrywa warunek (4) definicji zbioru termów.


W dalszym ciągu, dla uzyskania większej przejrzystości w zapisie formuł i termów, zamiast używać symboli x1, x2, ..., x6, będziemy odpowiednio pisać zmienne: x, y, z, u, v, w. Jednocześnie symbolu x będziemy jak dotychczas używać jako metazmiennej przebiegającej zbiór zmiennych nazwowych. Jest jasne, że symbole zwane pozalogicznymi w definicji słownika języka pierwszego rzędu: c1, c2, ..., ck, f1, f2, ..., fm, P1, P2, ..., Pn, są jedynie nazwami konkretnych symboli pozalogicznych danego słownika i w tej postaci w jakiej są zapisane, nie pojawiają się ani w termach, ani w formułach. Na przykład, jako stałe nazwowe będziemy między innymi używać symboli: a, b, c, jako predykaty 1-argumentowe będziemy używać wielkich liter alfabetu łacińskiego, zaś jako predykaty 2-argumentowe - symboli takich jak: ,  lub również wielkich liter tego alfabetu (to czy predykat jest 1- czy 2-argumentowy odczytuje się łatwo – wystarczy spojrzeć na formułę atomową, która predykat współtworzy). Rezerwujemy jednocześnie użycie litery P jako metazmiennej przebiegającej zbiór wszystkich predykatów (różnych od predykatu identyczności). Ponadto, będziemy pomijać nawiasy zewnętrzne tak termu jak i formuły (nawiasy zewnętrzne występujące w termie w warunku (3) definicji zbioru termów oraz w formułach w warunku (5) definicji zbioru formuł są niezbędne do tego, aby według tych warunków można było jednoznacznie generować termy oraz formuły złożone – nawiasów tych nie pomija się, gdy są one częścią zewnętrzną podformuły danej formuły, czyli w całej formule nie są nawiasami zewnętrznymi).

Przykład. Rozważmy język pierwszego rzędu wyznaczony przez następujące symbole pozalogiczne: stałą nazwową 1, dwa 2-argumentowe symbole funkcyjne +,  oraz 2-argumentowy predykat  . Na mocy warunków (1), (3) definicji zbioru termów, ciągi symboli: x + y, 1 + (x y) są termami tego języka. Zatem według warunków (1) oraz (3) definicji zbioru formuł, ciągi: x + y = 1 + (x y), x + y 1 + (x y), są formułami atomowymi. Zatem formułami są również ciągi:  x + y = x y (co zazwyczaj zapisywane jest w postaci: x + y x y), x + y = x yx + y x y (por. warunki (4), (5) definicji zbioru formuł). Dlatego, na mocy warunku (6), formułami są ciągi: x x + y x y, x(x + y = x yx + y x y) (nawiasy nie zostały tu pominięte, bo nie są na zewnątrz całej formuły; są natomiast na zewnątrz formuły: (x + y = x yx + y x y), i dlatego wcześniej przy jej zapisywaniu zostały pominięte). Również na mocy warunku (6) formułami są ciągi: yx x + y x y, yx(x + y = x yx + y x y).

Definicje. Dowolny term nazywamy domkniętym, gdy nie występuje w nim zmienna nazwowa.

Mówimy, że w formule x, formuła  jest zasięgiem kwantyfikatora  oraz że kwantyfikator ten wiąże zmienną x (tzn. wiąże zmienną nazwową, która przy nim występuje). Analogicznie dla formuły x.

Przez występowanie danej zmiennej nazwowej w danej formule rozumiemy każde takie pojawienie się egzemplarza tej zmiennej w tej formule, które nie następuje bezpośrednio po kwantyfikatorze  lub  (innymi słowy, jest to takie pojawienie się egzemplarza zmiennej w danej formule, które jest składnikiem jakiejś formuły atomowej).

Przez wolne występowanie danej zmiennej w danej formule rozumiemy każde takie występowanie tej zmiennej w tej formule, które jest poza zasięgiem kwantyfikatora wiążącego tę zmienną.

Mówimy, że dana zmienna jest wolna w danej formule, gdy w tej formule ma ona przynajmniej jedno wolne występowanie.

Formułę nazywamy domkniętą lub zdaniem, gdy żadna zmienna nie jest w niej wolna.



Przykład. W formule koniunkcyjnej: xxPyQx (nawiasy zewnętrzne tej formuły zostały pominięte), zmienne x, y są wolne, ponieważ drugie, licząc od lewej do prawej, występowanie zmiennej x w tej formule jest wolne oraz jedyne występowanie zmiennej y w tej formule jest wolne. Lecz w formule ogólnej: x(xPy  Qx), jak również w formule xxPy, tylko zmienna y jest wolna. Formuła yxxPy jest zdaniem.

Formuły domknięte danego języka pierwszego rzędu są schematami niektórych zdań oznajmujących języka etnicznego. To znaczy, pewne zdania oznajmujące są przekładalne na formuły domknięte języka pierwszego rzędu, oddające ich logiczną strukturę.

Stałe nazwowe pojawiające się w schemacie danego zdania reprezentują nazwy indywidualne (własne) występujące w tym zdaniu. Nazwy generalne (pospolite) występujące w zdaniu nie mają swoich bezpośrednich odpowiedników w jego schemacie. Z nazwy generalnej tworzymy orzeczenie przez dodanie do niej słowa „jest” (otrzymujemy więc orzeczenie, w którym owa nazwa jest orzecznikiem) i to orzeczenie reprezentujemy w schemacie zdania, w postaci 1-argumentowego predykatu. Wszelkie predykaty pojawiające się w schemacie zdania reprezentują orzeczenia, 1-argumentowe predykaty reprezentują 1-argumentowe orzeczenia (takie jak na przykład: jest studentem, jest informatykiem, jest wysoki), 2-argumentowe predykaty reprezentują 2-argumentowe orzeczenia (takie jak na przykład: kocha, lubi, bije, jest przyjacielem, jest dobrego zdania o). Orzeczenie jest n-argumentowe, n = 1,2, gdy wraz z n nazwami tworzy zdanie. W zdaniu: Jaś bije Małgosię, występują dwie nazwy (indywidualne): Jaś, Małgosia, dlatego orzeczenie: bije, jest 2-argumentowe. W zdaniu: Jaś jest studentem, orzeczenie: jest studentem, łączy się z jedną nazwą: Jaś, dlatego jest orzeczeniem 1-argumentowym. Pojawiające się w zdaniu słowa kwantyfikujące, tzn. odnoszące się do ilości, takie jak na przykład: każda, żaden, wszystkie, pewne, niektóre, nikt, ktoś, reprezentowane są w schemacie zdania w postaci kwantyfikatorów: , . Podobnie, wyrażenia takie jak: nieprawda, że, i, lub, jeżeli, to, wtedy i tylko wtedy, gdy, są w schemacie reprezentowane przez odpowiadające im spójniki. W schemacie zdania z języka etnicznego mogą pojawić się spójniki również wtedy, gdy reprezentowane przez nie wyrażenia nie występują w tym zdaniu – wówczas, gdy wykorzystujemy spójniki dla zapisu logicznej struktury zdania, mając na uwadze nie tyle przekład wyrażeń prostych występujących w zdaniu na ich odpowiedniki w języku pierwszego rzędu (czyli mając na uwadze przekład dosłowny), ile prezentację sensu (sposobu rozumienia) tego zdania. Dla danego zdania z języka etnicznego, istnieje wiele równie dobrych schematów w języku pierwszego rzędu.

Przykład. Schematami zdań: Jaś kocha Małgosię (lub Małgosia jest kochana przez Jasia – zdanie mające ten sam sens), Małgosia kocha Jasia (Jaś jest kochany przez Małgosię), są odpowiednio formuły atomowe: aKb, bKa, gdzie a,b są stałymi nazwowymi reprezentującymi odpowiednio nazwy indywidualne: Jaś, Małgosia, oraz K jest predykatem 2-argumentowym reprezentującym orzeczenie: kocha.

Formuły: aKx, xKa (gdzie x jest zmienną nazwową) reprezentują odpowiednio wyrażenia: Jaś kocha x, x kocha Jasia, nie będące zdaniami, lecz tzw. funkcjami zdaniowymi.

Schematami zdań: Jaś kocha wszystkich ludzi, Jaś kogoś kocha, są odpowiednio formuły domknięte: x(CxaKx), x(Cx aKx), gdzie C jest predykatem reprezentującym 1-argumentowe orzeczenie: jest człowiekiem, powstałe przez dodanie słowa jest do nazwy generalnej człowiek występującej jawnie w pierwszym i domyślnie w drugim zdaniu. Schematy te czytamy odpowiednio w postaci: dla każdego obiektu x, jeżeli x jest człowiekiem, to Jaś kocha x (lub bez uwzględniania zmiennej x: dla każdego obiektu, jeżeli jest on człowiekiem, to Jaś go kocha), istnieje obiekt x taki, że x jest człowiekiem i Jaś kocha x (istnieje obiekt taki, że jest on człowiekiem i Jaś go kocha). Jest oczywiste, że owe formuły domknięte są dosłownymi przekładami tych właśnie zdań z języka polskiego służących do odczytania tych formuł. Zdania te mają odpowiednio ten sam sens co zdania wyjściowe.

Ponadto, równie wartościowymi schematami dla tych zdań są formuły: xaKx, xaKx, w których jawnie nie pojawia się odpowiednik orzeczenia: jest człowiekiem, czytane odpowiednio: dla każdego człowieka x, Jaś kocha x, istnieje człowiek x taki, że Jaś kocha x. Możliwość uproszczenia schematu przez nieuwzględnienie w nim orzeczenia 1-argumentowego, pojawia się jedynie wówczas, gdy orzeczenie to powstało przez dołączenie „jest” do nazwy generalnej występującej w zdaniu oraz wszystkie słowa kwantyfikujące występujące w tym zdaniu i reprezentowane w schemacie przez kwantyfikatory, odnoszą się, czy dotyczą wyłącznie tylko tych obiektów, które są tą nazwą nazywane. Zatem schematu: x(CxSx)  x(Sx  Cx), dla zdania: Wszyscy ludzie są studentami, lecz niektórzy studenci nie są ludźmi, (predykat S reprezentuje tu orzeczenie: jest studentem) nie można w powyższym sensie uprościć.

Zdanie: Nikt nie jest niczyim przyjacielem, ma równie wartościowe (bo logicznie równoważne – por. dalej) następujące schematy: xyxPy, xyxPy, w których predykat 2-argumentowy P reprezentuje orzeczenie: jest przyjacielem. W schematach tych nie uwzględniono orzeczenia 1-argumentowego: jest człowiekiem, domyślnie występującego w zdaniu (założono, że słowa kwantyfikujące: nikt, niczyj odnoszą się do ludzi).

§3. Interpretacja oraz waluacja dla języka pierwszego rzędu




Definicje. Niech D będzie dowolnym niepustym zbiorem. Przez 1-argumentowa operację na zbiorze D rozumiemy dowolne przyporządkowanie każdemu elementowi zbioru D dokładnie jednego elementu z tego zbioru.

Przez 2-argumentową operację na zbiorze D rozumiemy przyporządkowanie każdej dwuwyrazowej sekwencji elementów z D dokładnie jednego elementu z tego zbioru.

Dowolny zbiór, którego każdy element należy do zbioru D nazywamy podzbiorem zbioru D.

Dowolny zbiór dwuwyrazowych ciągów elementów ze zbioru D nazywamy relacją binarną określoną na D.



Definicja. Ustalmy dowolny język pierwszego rzędu L przez wybór stałych nazwowych: c1, c2, ..., ck , k  0, symboli funkcyjnych: f1, f2, ..., fm , m  0, oraz predykatów: P1, P2, ..., Pn , n  0. Przez interpretację języka L rozumiemy następujący układ:
I = (D,f1*,f2*, ...,fm*,c1*,c2*, ...,ck*,P1*,P2*, ...,Pn*), gdzie


  1. D jest dowolnym niepustym zbiorem, zwanym dziedziną interpretacji,

  2. dla każdego j = 1,2,...,m, fj* jest operacją na zbiorze D (której nazwą jest symbol funkcyjny fj), 1-argumentową, gdy symbol fj jest 1-argumentowy, lub 2 –argumentową, gdy fj jest 2-argumentowy,

  3. dla każdego j = 1,2,...,k, cj* jest wyróżnionym elementem zbioru D (nazywanym w tej interpretacji stałą cj),

  4. dla każdego j = 1,2,...,n, Pj* jest albo podzbiorem zbioru D, gdy Pj jest 1-argumentowy, albo relacją binarną na D, gdy Pj jest 2-argumentowy.

W celu zdefiniowania pojęcia prawdziwości formuły domkniętej z języka L w interpretacji I, rozszerzamy zbiór stałych nazwowych {c1,c2, ...,ck} o nowe stałe ad, dD, d  {c1*,c2*, ...,ck*}. Zmieniamy zatem wyjściowy język L na nowy język pierwszego rzędu L(D), w którym każdy z elementów dziedziny interpretacji I ma nazwę. Niech Const(D) będzie zbiorem wszystkich stałych nazwowych nowego języka L(D).


Każda interpretacja I dla wyjściowego języka pierwszego rzędu L wyznacza waluację zbioru termów domkniętych nowego (rozszerzonego) języka L(D). Waluacja jest przyporządkowaniem każdemu termowi domkniętemu t dokładnie jednego obiektu: |t|, ze zbioru D, interpretowanego nieformalnie jako obiekt nazwany termem t w interpretacji I.

Definicja. Przez waluację dla danej interpretacji I rozumiemy przyporządkowanie | | każdemu termowi domkniętemu t języka L(D) dokładnie jednego elementu |t| z dziedziny D interpretacji I, jak następuje:


  1. |cj| = cj*, j = 1,2,...,k,

  2. |ad| = d, d D, d c1*, dc2*, ..., d ck*,

  3. |f(t)| = f*(|t|), f jest symbolem funkcyjnym 1-argumentowym (ze zbioru { f1, f2, ..., fm}), t jest termem domkniętym języka L(D) oraz f*(|t|) jest wartością 1-argumentowej operacji f* na argumencie |t|, tzn. obiektem przyporządkowanym przez operację f* obiektowi |t|,

  4. |tfs| = f*(|t|,|s|), f jest symbolem funkcyjnym 2-argumentowym, t,s są termami domkniętymi oraz f*(|t|,|s|) jest wartością 2-argumentowej operacji f* na sekwencji (|t|,|s|).


§4. Prawdziwość zdania w interpretacji

Dysponując pojęciem waluacji dla danej interpretacji I, można sformułować pojęcie prawdziwości formuły domkniętej języka L w interpretacji I, formułując definicję prawdziwości dla każdej formuły domkniętej z języka rozszerzonego L(D) w interpretacji I (wśród zdań języka L(D) są wszystkie zdania języka L). Zdanie jest fałszywe w interpretacji I, gdy nie jest ono w I prawdziwe. Prawdziwość, fałszywość zdania w danej interpretacji - to jego wartości logiczne w tej interpretacji.

Poniższa definicja podaje warunki prawdziwości dla dowolnej formuły domkniętej języka L(D) w zależności od jej postaci (w dalszym ciągu symbol „wtw” znaczy tyle co „wtedy i tylko wtedy, gdy”):

Definicja.




  1. zdanie t = s jest prawdziwe w I wtw |t|, |s| są tym samym obiektem,

  2. zdanie Pt jest prawdziwe w I wtw |t|  P*, dla dowolnego 1-argumentowego predykatu P  {P1,P2, ...,Pn},

  3. zdanie tPs jest prawdziwe w I wtw (|t|,|s|)  P*, dla dowolnego 2-argumentowego predykatu P  {P1,P2, ...,Pn},

dla dowolnych zdań , języka L(D):

  1. zdanie  jest prawdziwe w I wtw  jest falszywe w I,

  2. zdanie    jest prawdziwe w I wtw oba zdania: ,  są prawdziwe w I,

  3. zdanie    jest prawdziwe w I wtw co najmniej jedno ze zdań: , , jest prawdziwe w I,

  4. zdanie    jest prawdziwe w I wtw  jest fałszywe w I lub  jest prawdziwe w I,

  5. zdanie    jest prawdziwe w I wtw oba zdania: , są prawdziwe w I, bądź oba te zdania są fałszywe w I,

dla dowolnej formuły  z dokładnie jedną zmienną wolną x:

  1. zdanie xjest prawdziwe w I wtw dla każdej stałej nazwowej cConst(D), zdanie: [x/c] jest prawdziwe w I,

  2. zdanie xjest prawdziwe w I wtw dla pewnej stałej nazwowej cConst(D), zdanie: [x/c] jest prawdziwe w I,

gdzie [x/c] jest formułą uzyskaną z formuły  przez zastąpienie w niej każdego wolnego występowania zmiennej x stałą c.

Przykład. Rozważmy język pierwszego rzędu wyznaczony przez stałą nazwową: 1, dwa 2-argumentowe symbole funkcyjne: +, , oraz predykat 2-argumentowy: . Niech I1 = (N,+*,*,1*,*) będzie interpretacją dla tego języka, w której dziedziną jest zbiór N liczb naturalnych, +*,* są odpowiednio operacjami dodawania i mnożenia na zbiorze liczb naturalnych, 1* jest liczba naturalną jeden oraz * jest relacją niewiększości określoną na zbiorze liczb naturalnych. Niech ponadto druga interpretacja ma postać: I2 = ({0*,1*},+*,*,1*,*), gdzie 0*,1*są dowolnymi różnymi od siebie obiektami, zaś operacje +*, * zdefiniowane są następująco (zamiast, zgodnie z ustaloną wcześniej konwencją, oznaczać wartość operacji +* na sekwencji (u,v) elementów ze zbioru {0*,1*} w postaci: +*(u,v), piszemy: u +* v; analogicznie dla operacji *):

0* +* 0* = 0*,

0* +* 1* = 1* +* 0* = 1* +* 1*= 1*,

1* *1* = 1*,

0* * 1* = 1* * 0* = 0* * 0*= 0*.

Ponadto, * = {(0*,0*), (1*,1*), (0*,1*)}.

Weźmy pod uwagę formułę: xy x + yx  1 . Jest ona prawdziwa w I1, gdy dla pewnej stałej a Const(N) (nazywającej jakąś liczbę naturalną) oraz dla każdej stałej b Const(N), prawdziwa w I1 jest formuła atomowa: a + b a  1. To zaś zachodzi, gdy (|a + b|,|a  1|)  *, tzn., gdy (|a| +* |b|, |a| * 1*)  *. Ostatecznie, wyjściowa formuła jest prawdziwa w I1, gdy dla pewnej stałej a oraz dla każdej stałej b, suma liczb naturalnych |a|, |b| jest mniejsza lub równa liczbie |a|. Ponieważ (|a| +* |b|, |a|)  *, wtedy i tylko wtedy, gdy |b| jest liczbą zero, więc nasza formuła jest fałszywa w I1. Zauważmy, że dla danej interpretacji formalnej I1, można nieformalnie zinterpretować tę formułę jako następujące zdanie z języka polskiego: dla pewnej liczby naturalnej x oraz każdej liczby naturalnej y, suma liczb x, y jest mniejsza lub równa od iloczynu liczb: x, 1.

W interpretacji I2, nasza formuła jest prawdziwa, gdy dla pewnej stałej a Const({0*,1*}) oraz dla każdej stałej b Const({0*,1*}), zachodzi: (|a| +* |b|, |a|)  * (tutaj mamy: |a| * 1* = |a|, bo |a|  {0*,1*}). Lecz właśnie tak jest, bowiem istnieje taki obiekt w dziedzinie interpretacji I2, mianowicie ten oznaczony stałą 1, że (|1| +* |0|, |1|)  * oraz (|1| +* |1|, |1|)  * (zwróćmy uwagę, że Const({0*,1*}) = {0,1}). Ostatecznie, nasza formuła jest prawdziwa w I2.

Jak na to wskazuje powyższy przykład, aby obliczyć wartość logiczną danej formuły domkniętej w danej interpretacji formalnej I, wygodnie jest nieformalnie interpretować tę formułę domkniętą - otrzymując w efekcie, w zależności od interpretacji I, odpowiednie zdanie z języka etnicznego, którego wartość logiczną łatwo ocenić. Oczywiście wartość logiczna formuły w interpretacji I jest tożsama z wartością logiczną tego zdania.


§5. Reguły wykazywania oraz korzystania z prawdziwości zdań

Na podstawie definicji prawdziwości formuły domkniętej w danej interpretacji, można sformułować następujące reguły dowodzenia (D) (wykazywania) wprost prawdziwości formuł oraz reguły korzystania (K) z prawdziwości formuł:


(K) dysponując prawdziwym w danej interpretacji I zdaniem , stwierdzamy, że  jest fałszywe,
(D) aby wykazać prawdziwość w I zdania  należy wykazać, że zdanie  jest fałszywe,
(K) wiedząc, że prawdziwa w I jest koniunkcja:   , stwierdzamy, że obie formuły: , , są prawdziwe w I,
(D) aby wykazać prawdziwość koniunkcji:   , należy wykazać po kolei, że  jest prawdziwa oraz, że  jest prawdziwa w I,
(K) gdy prawdziwa jest alternatywa:   , to przynajmniej jedna z formuł: , , jest prawdziwa. Nie wiedząc, która z tych formuł jest prawdziwa, korzysta się z prawdziwości alternatywy w sposób rozgałęziony. To znaczy, czyni się założenie, że prawdziwa jest formuła  i prowadzi rozumowanie, aż osiągnie się zamierzony cel (którym zazwyczaj jest wykazanie prawdziwości jakiejś formuły w danej interpretacji). Następnie zakłada się, że prawdziwa jest formuła  i kontynuuje rozumowanie, aż osiągnie się ten sam cel. Ostatecznie, ów cel jest osiągnięty, na podstawie informacji, że    jest prawdziwa,

(D) aby dowieść, że w danej interpretacji I prawdziwa jest alternatywa   , należy wykazać, że przynajmniej jedna z formuł: ,  jest w I prawdziwa. Zazwyczaj w tym celu zakłada się, ze jedna z tych formuł, np. , jest fałszywa, tzn., że formuła  jest w I prawdziwa i prowadzi rozumowanie wykazujące, że formuła  jest w I prawdziwa,


(K) gdy prawdziwa jest implikacja:   , zachodzi co najmniej jedno z dwojga: jej poprzednik  jest fałszywy, jej następnik  jest prawdziwy. Jeśli więc dodatkowo dysponujemy informacją, że poprzednik jest prawdziwy, to wnioskujemy, ze następnik jest również prawdziwy; jeśli zaś wiemy, iż następnik jest fałszywy, to wnioskujemy, że poprzednik jest również fałszywy,
(D) aby dowieść prawdziwości implikacji    w danej interpretacji I, zakłada się, że jej poprzednik  jest w I prawdziwy i prowadzi rozumowanie tak, aby wykazać prawdziwość następnika . Inny sposób polega na założeniu fałszywości następnika, tzn. prawdziwości formuły: , i prowadzeniu rozumowania tak, aby wykazać, że fałszywy jest poprzednik, tzn. prawdziwa jest formuła: ,
(K) gdy prawdziwa w danej interpretacji I jest równoważność:   , to prawdziwe są dwie implikacje:   ,    (bo    ma w danej interpretacji tę samą wartość logiczną, co koniunkcja: (  )  (  )),
(D) aby dowieść, że równoważność    jest prawdziwa, wykazujemy, że koniunkcja (  )  (  ) jest prawdziwa, tzn. wykazujemy, że prawdziwe są dwie implikacje:    oraz   ,
(K) gdy w interpretacji I prawdziwa jest formuła ogólna: x, to prawdziwe są wszystkie formuły postaci: [x/a], gdzie a jest stała nazwową nazywającą jakiś obiekt z dziedziny interpretacji I,
(D) aby wykazać, że formuła ogólna: x, jest prawdziwa w I, wybiera się w dowolny sposób obiekt z dziedziny interpretacji I, nazywa się go stałą a, zakładając, że a Const(D), gdzie D jest dziedzina interpretacji I, oraz dowodzi prawdziwości formuły [x/a],
(K) wiedząc, że w I prawdziwa jest formuła egzystencjalna: x, stwierdzamy, że prawdziwa jest w I formuła: [x/a], dla pewnej stałej a Const(D) (nie wiadomo którego to obiektu istnienie jest prawdziwie stwierdzane formułą x, w szczególności nie ma pewności, czy jest to obiekt nazywany jedną ze stałych c1, c2, ..., ck, dlatego a w prawdziwej formule [x/a] jest jakąś stałą ze zbioru Const(D), o której nic więcej nie wiadomo,
(D) aby dowieść, że formuła x jest prawdziwa w I, trzeba wykazać, że prawdziwa jest formuła [x/a], gdzie a jest jakąkolwiek stałą ze zbioru Const(D).

Znany sposób dowodzenia nie wprost prawdziwości zdania  w danej interpretacji I polega na założeniu, iż zdanie  nie jest w I prawdziwe, wyciągnięciu z tego założenia konsekwencji na podstawie definicji prawdziwości formuły w interpretacji oraz dojściu do absurdu (w ogólności wykazać nie wprost, że dany fakt zachodzi, to założyć, że fakt ten nie zachodzi i na tej podstawie, stosując jakieś rozumowanie dojść do absurdu).


§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}









©operacji.org 2019
wyślij wiadomość

    Strona główna