Dr Andrzej Kmiecik
Zakład Logiki i Epistemologii
Instytut Filozofii i Socjologii UKW
w Bydgoszczy
ul. Ogińskiego 16
Wykład 13
Węższy rachunek predykatów (3)
Rachunek predykatów wyższych rzędów
Metoda 0-1 dla w.r.p.
Rachunek predykatów wyższych rzędów
Predykat n-tego rzędu jest to funktor zdaniotwórczy od argumentów należących
do kategorii składniowej nazw jednostkowych lub od predykatów rzędów
mniejszych od n, przy czym przynajmniej jeden z nich należy do kategorii
składniowej predykatów rzędu n-1.
Ex. Predykaty drugiego rzędu
Def. Ix(x,A) a" A(x) '" V ! A(x)
x
Def. Rozł(A,B) a" ~Vx (A(x) '" B(x))
gdzie zmienne A, B reprezentujÄ… predykaty
W rachunku predykatów n-tego rzędu kwantyfikatory wiążą zmienne nazwowe i
zmienne predykatowe rzędów od, 1 do n-1. Predykat n-tegp rzędu nie jest
zwiÄ…zany kwantyfikatorem.
W rachunku predykatów n-tego rzędu, n e" 2, przyjmujemy analogicznie jak w
w.r.p., reguły pierwotne dołączania i opuszczania kwantyfikatorów wiążących
zmienne nazwowe i predykatów rzędów 1, ..., n-1.
Ponadto przyjmujemy aksjomaty ekstensjonalności i aksjomaty definicyjne,
które dla predykatów 1-go rzędu, czyli w rachunku predykatów 2-go rzędu mają
postać następującą:
›x (A(x) a" B(x)) A = B
gdzie "=" jest kategorii z/(z/n, z/n).
1
Postać uogólniona
› (P (x , ..., x ) a" P (x , ..., x )) P = P
x1, ..., xn 1 1 n 2 1 n 1 2
Def. V › (A(x) a" Õ(x))
A x
Õ(x) - forma zdaniowa o zmiennej wolnej z, w której to formie nie wystÄ™puje
zmienna wolna A.
Postać uogólniona
Def. V › (P(x , ..., x ) a" Õ(x , ..., x ))
P x1, ..., xn 1 n 1 n
Õ(x , ..., x ) - jest formÄ… zdaniowÄ… o zmiennych wolnych x , ..., x , w
1 n 1 n
której to formie nie występuje zmienna wolna P.
Uwaga 1
W rachunku predykatów n-tego rzędu analogiczne aksjomaty definicyjne i
aksjomaty ekstensjonalności przyjmuje się dla predykatów rzędów, 1, ... , n-1.
Uwaga 2
W rachunku predykatów rzędu 2-go identyczność można zdefiniować
następująco:
x = y a" › (A(x) a" A(y))
A
Dwa przedmioty sÄ… identyczne, gdy majÄ… takie same cechy
Regułą opuszczania kwantyfikatora jednostkowego
OV: ' VÄ… Õ '
' ÕÈ '
--------
' È '
o ile zmienna Ä… nie jest wolna ani w zaÅ‚ożeniach dowodu ani w wyrażeniu È.
Ex. ..........
n. VÄ… Õ z.
1.1 Õ z.d.
..........
1.k È
n+1 ÕÈ n, 1.1 1.k
Jeżeli do dowodu należy wyrażenie ' VÄ… Õ ' i Ä… nie jest zmiennÄ… wolnÄ… ani w
zaÅ‚ożeniach dowodu ani w wyrażeniu È oraz w dowodzie tym z zaÅ‚ożenia
2
dodatkowego Õ wyprowadzimy È , to można doÅ‚Ä…czyć do tego dowodu
wyrażenie È.
Ex. V › xPy › V xPy
x y y x
Dowód (nie ma stałych)
1. V › xPy z.
x y
1.1 › xPy z.d.
y
1.2 xPy O›: 1.1
1.3 V xPy DV: 1.2
x
1.4 › V xPy D›: 1.3
y x
2. › V xPy OV: 1, 1.11.4
y x
Ex. V (A(x) '" B(x)) V A(x) '" V B(x)
x x x
Dowód
1. V (A(x) '" B(x)) z.
x
1.1 A(x) '" B(x) z.d.
1.2 A(x) OK.: 1.1
1.3 B(x) OK.: 1.1
1.4 V A(x) DV: 1.2
x
1.5 V B(x) DV: 1.3
x
1.6 V A(x) '" V B(x) DK: 1.4, 1.5
x x
2. V A(x) '" V B(x) OV: 1, 1.1 1.6
x x
Teorie elementarne
W teoriach elementarnych występuje tylko jeden rodzaj zmiennych  zmienne
indywiduowe.
Ponadto w takich teoriach mogą występować funktory prawdziwościowe i
kwantyfikatory jako stałe logiczne oraz różne stałe specyficzne (pozalogiczne).
Stałych pozalogicznych jest ilośćskończona. Są to stałe predykaty.
Ex. Teoria większości ma predykaty stałe ' < ' oraz '> '.
Metoda 0-1 dla w.r.p.
Dla węższego rachunku predykatów 1-arg. istnieją metody rozstrzygalności.
Sens symboli 0, 1 jest jednak inny niż w rachunku zdań.
Ograniczamy się do sprawdzania wyrażeń w.r.p, w których:
1. nie występują wolne zmienne nazwowe
2. występuje tylko jedna zmienna nazwowa
3
3. żaden kwantyfikator nie występuje w zasięgu innego kwantyfikatora
4. nie występują kwantyfikatory, w których zasięgu nie występowałaby
mzienna wolna zwiÄ…zan przez ten kwantyfkator
Sprawdzanie bardziej złożonych wyrażeń zob. L. Borkowski: Wprowadzenie do
logiki i teorii mnogości, TN KUL, Lublin 1991, s. 114-126.
Klasy rozkładu zbiorów
Przy n predykatach dowolny niepusty zbiór dzieli się na 2n klas. Klasy takie
nazywamy klasami rozkładu danego zbioru.
Zasadą rachunku predykatów jest to, że zmienne indywiduowe przebiegają
dowolny, niepusty zbiór przedmiotów.
Uwaga
Są prawa, które są prawdziwe w zbiorach pustych i niepustych. Są takie, które
sÄ… prawdziwe tylko w zbiorach pustych (zob. Andrzej Grzegorczyk: Zarys logiki
matematycznej).
Ex. › A(x) V A(x)
x x
~ V ~A(x) V A(x)
x x
są fałszywe w dziedzinie pustej, bo jest fałszywy następnik w dziedzinie
pustej
Przypadki
n = 1
A
21 = 2
1 : {x: A(x)}
0 : {x: ~A(x)}
charakterystyka klas rozkładu jest następująca:
1, x " A
ch(A) =
0, x " A
Uwaga
Obie klasy rozkładu nie mogą być puste
4
n =2
IV
22 = 4
A B
III I II
Obszary I, II, III, IV symbolizujÄ… odpowiednie obszary
Klasom tym przyporządkowuje się jako charakterystyki ukłądy zerojedynkowe
I {x : A(x) '" B(x)} 1,1
II {x : A(x) '" ~B(x)} 1,0
III {x : ~A(x) '" B(x)} 0,1
IV {x : ~A(x) '" ~B(x)} 0,0
Rozkład zbioru
1 Rozkład zbioru jest wyznaczony przez ukazanie tego, które klasy
rozkładu zbioru są puste.
2. Puste klasy rozkładu zaznaczamy skreślając wiersz, w którym występuje
jego charakterystyka.
3. Niepustość klas rozkładu zaznaczamy przez podkreślenie przynajmniej
jednego elementu w wierszu zawierajÄ…cym tÄ™ charakterystykÄ™ (nie zawsze to
musi być czynione).
4. Wyrażenie jest prawdziwe wttw, gdy jest prawdziwe przy każdym rozkładzie
dowolnego niepustego zbioru.
Instrukcje dla sprawdzania
1. Sprawdzanie zaczynamy od wypisania pod wyrażeniem w.r.p. układów 0-1,
analogicznie jak w klasycznym rachunku zdań. Wypisywane w ten sposób
układy zer i jedynek stanowią charakterystyki poszczególnych klas rozkładu.
Następnie obliczamy wg tabelek funktorów prawdziwościowych wartości
wyrażeń nie zawierających kwantyfikatorów.
Przeprowadzamy skrócone sprawdzenie całego wyrażenia analogicznie jak w
rachunku zdań.
2. Wyrażenie zaczynające się od kwantyfikatora ogólnego ma wartość 1
wttw, gdy pod jego zasięgiem ani razu nie występuje zero.
Wyrażenie takie ma wartość 0 wttw, gdy pod jego zasięgiem przy najmniej raz
pojawi siÄ™ zero.
5
Wyrażenie zaczynające się od kwantyfikatora szczegółowego ma wartość 1
wttw, gdy pod jego zasięgiem występuje przy najmniej raz wartość jeden.
Wyrażenie takie ma wartość 0 wttw, gdy pod jego zasięgiem nie występuje ani
razu wartość jeden.
3. Zmiennym zdaniowym można przyporządkować jedną i tylko jedną z
wartości: 0, 1.
4. Przeprowadzając sprawdzanie skrócone badamy, czy jest możliwy taki
rozkład niepustego zbioru, przy którym dane wyrażenie jest fałszywe.
Przykłady
prawda
› A(x) V A(x)
x x
1 1
1 1
0 0
1. wypisanie charakterystyki klas rozkładu
2. zakładamy prawdziwość poprzednika tej implikacji
3. wyrażenie › A(x) jest prawdziwe, gdy klasa o charakterystyce 0 jest pusta
x
4. przekreślamy ten wiersz
5. klasa o charakterystyce 1 musi więc być niepusta.
6. wtedy wyrażenie V A(x) jest prawdziwe.
x
7. Tak więc następnik implikacji jest prawdziwy, gdy jej porzednik jest
prawdziwy.
fałsz
V A(x) › A(x)
x x
1 1
1 0 0
0 0
1. Jeśli istnieją przedmioty należące do {x: A(x)} i przedmioty należące do {x:
~A(x)}, to wyrażenia V A(x) jest prawdziwe.
x
2. Wyrażenie › A(x) jest jednak faÅ‚szywe wtedy.
x
3. Zatem implikacja jest fałszywa.
6