KIF02

0) /\x[P(x)-¹Q{x)aR(x.})). (m) A Ar[/>0-)-»/?(x.    z).

71. Tautologią rachunku kwantyfikatorów nazywamy każde i tylko takie wyrażenie języka tego rachunku, które jest tche¹ matem wyłącznie prawdziwych zdań, lub funkcji zdaniowych' Tak więc, na przykład, schemat:

A xP(x)-> ~ \/ x~P(x)

jest tautologią, gdyż każde zdanie zbudowane według tego schematu jest prawdziwe; nic ma bowiem takiego rodzaju przedmiotów i takiej własności przysługującej przedmiotom tego rodzaju, aby było prawdą, że każdy przedmiot własno# tę posiada, fałszem zaś — że nie istnieje przedmiot nie mający tej własności. Podobnie, tautologiczny jest schemat:

V¹A y¹(^x- y)-+Ay\/    y).

nie ma bowiem takiego rodzaju przedmiotów i takiej relacj zachodzącej między przedmiotami tego rodzaju, aby było prawdą, że istnieje przedmiot pozostający w tej relacji do każdego przedmiotu, fałszem zaś — że dla każdego przedmiotu istnieje taki, który pozostaje doń w owej relacji.

Nic jest natomiast tautologią schemat:

A v &¹)]-¹( A v A ¹QM\

istnieje bowiem taki rodzaj przedmiotów i takie dwie whaofd przysługujące przedmiotom tego rodzaju, iż jest prawdą, te każdy przedmiot posiada pierwszą lub drugą z tych'własności, fałszem zaś — iż każdy posiada pierwszą lub każdy posiadł drugą. Przykładem takiego rodzaju przedmiotów jest zbiór liczb naturalnych, z których każda jest parzysta (P) lub nieparzysta (0, podczas gdy nic jest prawdą ani to. że kałd.-. liczba naturalna jest parzysta, ani to, że każda jest nieparzysta.

Dla każdego z podanych niżej schematów wskaż taką dziedzinę (tj. taki rodzaj przedmiotów i takie własności i relacje tych przedmiotów)⁷, której istnienie dowodzi nictautologicz* ności tego schematu.

(*)\JxP(x)-./\_xP(x).

(b)    V xP(x)-+ V

(c)    ~ A xP(x)^ A X~P(x).

(d)    /\x[P(x)-Q(x)]* f\x[P(x)A. &x)].

(e)    V x[P(x)-+ CWl- V a Q(x)l

(0 [ A xP(x)A V V *!/*(*) A Q(x)].

(*) A ■* V >^R<^X- y)- V y A ^xR(^x- >)•

(h) A ^xR(^x> *)-* A * A p*(*. >■)■

(0 A*A->i*(*.p)-*0^)l.

0) A*Ay[^R(^x->)-*-*(>'.*)]•

(k) A^xApA^zl^R(.^x‘ >•)^A *0’- z)-* A*. z)].

0> A * A p V    *) a    >•)]-*

-»A * V * A    z) a *(*. >)]•

(*> />(*)-» A **(*)•

(m) V xP(x)-*P(x).

72.    Dla każdego ze schematów (a)-(m) podanych w zadaniu 71 wskaż taką dziedzinę, której istnienie dowodzi, że schemat ten nie jest kontrtautologią.

73.    Weź pod uwagę dziedzinę, którą stanowią liczby naturalne wraz z przysługującymi im własnościami parzystości

’ Pojecie dziedziny można zdefiniować Scrile w terminołoeii teorii mnogedci (xoh. zndnnie I6J częki II).

59

1

Ponieważ język rachunku kwantyfikatorów zawiera w tobie jpyt rachunku zdać, więc każda tautologia rachunku zdań jest też uui> logią rachunku kwantyfikatorów. Pojęcie tautologii rachunku kwamyftU-torów jest równoznaczne z pojęciem tautologii klasytitorgo isehakn bfientgo.