Wykład dziewiąty

Temat X

Klasyczny

rachunek

logiczny

Klasyczny rachunek logiczny

Teoria predykatów (Rachunek kwantyfikatorów)

Terminologia

- zmienne nazwowe (indywiduowe): x, y, z … - reprezentują nazwy jednostkowe

- stałe indywiduowe (nazwy jednostkowe): a, b, c …

- symbole klasycznego rachunku zdań:

zmienne zdaniowe: p, q, r …

funktory: ∼,
, ∨, ∧, ≡

∀, Λ - kwantyfikator ogólny, duży, czytamy: dla każdego

∃, V - kwantyfikator szczegółowy, egzystencjalny, czytamy: dla pewnego, istnieje takie … że

- Zmienna związana przez kwantyfikator - zmienna, która występuje i przy kwantyfikatorze i w wyrażeniu zdaniowym po kwantyfikatorze. Np. ∀x x ≤ y; x - zmienna związana

- Zmienna wolna - zmienna, która nie jest związana przez żaden kwantyfikator, tj. taka, która występuje tylko w wyrażeniu zdaniowym po kwantyfikatorze. Np. ∀x x ≤ y; y - zmienna wolna

- Zasięg kwantyfikatora - wszystkie zmienne wyrażenia zdaniowego, które są przez kwan- tyfikator związane. Np. W pierwszym wyrażeniu ∀x [A(x) → B(x)] zasięgiem kwantyfikatora jest: [A(x) → B(x)], w wyrażeniu ∃x A(x) → B(x) zasięgiem kwantyfikatora jest A(x).

- predykaty pierwszego rzędu: A(x), B(x)… - zmienne (A, B …) reprezentują funktory zdaniotwórcze o argumentach nazwowych

- predykaty wyższych rzędów: P(x, y), Q(x, y, z) … - zmienne (P, Q …) reprezentują predykaty dwu, trójargumentowe itd.

Predykat drugiego rzędu - funktor zdaniotwórczy o argumentach należących do kategorii składniowej nazw indywidualnych lub predykatów pierwszego rzędu (do tej kategorii musi należeć przynajmniej jeden argument).

Predykat n-go rzędu - funktor zdaniotwórczy o argumentach należących do kategorii składniowej nazw indywidualnych lub predykatów niższych od n, przy czym przynajmniej jeden argument musi należeć do kategorii składniowej predykatów rzędu n −1.

Rachunek predykatów pierwszego rzędu (węższy rachunek predykatów)

W wyrażeniach tego rachunku występują tylko predykaty pierwszego rzędu a kwantyfikator wiąże tylko zmienne.

Wyrażenie molekularne (atomiczne) rachunku predykatów pierwszego rzędu to najprostsze wyrażenia zdaniowe tego rachunku: zmienne zdaniowe lub wyrażenia zbudowane ze zmiennej reprezentującej predykaty pierwszego rzędu i jej argumentów, np. A(x), B(x), P(x, y),

R(x, y … z). Rodzaje wyrażeń molekularnych:

Predykaty jednoargumentowe pierwszego rzędu denotują cechy (własności) przedmiotów indywidualnych: A(x) - x ma cechę (własność) A.

Predykaty dwu- i wieloargumentowe pierwszego rzędu denotują dwu- i wieloargumentowe relacje (stosunki) zachodzące między przedmiotami indywidualnymi. Np.

P(x, y) - x pozostaje w relacji P do y (xPy)

Q(x, y, z) - relacja Q zachodzi między przedmiotami x, y i z.

R (x₁, x₂, … , x_n) - relacja R zachodzi między przedmiotami x₁, x₂, … , x_n.

Przykłady predykatów

Predykaty jednoargumentowe:

A(x) - x jest liczbą parzystą

B(x) - x jest człowiekiem

B(a) - a jest człowiekiem

a - Sokrates, x/a: B(a) - Sokrates jest człowiekiem

Predykaty dwuargumentowe:

P(x, y) - x jest wyższy od y.

Q(x, y) - x jest uczniem y.

Q(a, b) - a jest uczniem b.

a - Arystoteles, b - Platon; x/a, y/b - Platon: Q(a, b) - Arystoteles jest uczniem Platona

Predykaty trójargumentowe:

R(x, y, z) - x leży między y i z.

R(a, b, c) - a leży między b i c.

a - Warszawa, b - Kraków, c - Gdańsk; x/a, y/b, z/c

R(a, b, c) - Warszawa leży między Krakowem a Gdańskiem.

Przykłady formuł zdaniowych z predykatami

A(x) - x jest mężczyzną

B(x) - x jest człowiekiem

A(x)
B(x)

Jeżeli x jest mężczyzną, to x jest człowiekiem.

A(x) - x jest żonaty

P(x, y) - x pozostaje w związku małżeńskim z y.

A(x)
P(x, y)

Jeżeli x jest żonaty, to x pozostaje w związku małżeńskim z y.

P(x, y) - x jest równoległe do y.

Q(x, y) - x jest prostopadłe do y.

P(x, y)
∼ Q(x, y)

Jeżeli x jest równoległe do y, to x nie jest prostopadłe do y.

A(x) - x jest Polakiem

P(x, y) - x jest ojcem y.

[A(x) ∧ P(x, y)]
A(y)

Jeżeli x jest Polakiem i x jest ojcem y, to y jest Polakiem.

Wyrażenia zdaniowe węższego rachunku predykatów

Rachunek predykatów pierwszego rzędu (węższy rachunek predykatów zawiera:

a) wyrażenie molekularne (atomiczne)

b) wyrażenia zbudowane z wyrażeń molekularnych za pomocą funktorów klasycznego rachunku zdań

c) wyrażenia zbudowane z kwantyfikatora ogólnego lub szczegółowego, występującej po nim zmiennej indywidualnej i wyrażenia zdaniowego.

d) dowolne wyrażenia zdaniowe zbudowane poprawnie z wyrażeń typu a), b) i c).

Przykłady formuł zdaniowych z predykatami i kwantyfikatorami

Predykaty jednoargumentowe

1) ∀x A(x)

A(x) - x jest śmiertelny, X - ludzie; Każdy człowiek jest śmiertelny.

A(x) - x jest omylny, X - ludzie; Wszyscy są omylni.

2) ∼∀x A(x)

A(x) - x jest szczery, X - ludzie; Nie każdy jest szczery.

A(x) - x jest odważny; X - ludzie; Nieprawda, że wszyscy ludzie są odważni.

3) ∀x ∼A(x)

A(x) - x jest doskonały, X - ludzie; Nikt nie jest doskonały.

A(x) - x jest altruistą, X - ludzie; Nie ma altruistów.

4) ∃x A(x)

A(x) - x jest hojny, X - ludzie; Niektórzy ludzie są hojni.

A(x) - x jest optymistą; X - ludzie; Istnieją optymiści.

5) ∼∃x A(x)

A(x) - x jest doskonały, X - ludzie; Nie istnieje nikt, kto jest doskonały.

A(x) - x jest altruistą, X - ludzie; Nie istnieje nikt, kto jest altruistą.

6) ∃x ∼A(x)

A(x) - x jest bezinteresowny, X - ludzie; Są tacy, którzy nie są bezinteresowni.

A(x) - x jest odważny; X - ludzie; Niektórzy nie są odważni.

Predykaty dwuargumentowe

1) ∀x ∀y P(x, y)

P(x, y) - x jest związany z y, X - przedmioty; Każda rzecz jest powiązana ze wszystkimi innymi.

P(x, y) - x krytykuje y, X - ludzie; Wszyscy wszystkich x krytykują.

2) ∃x ∃y P(x, y)

P(x, y) - x naśladuje y, X - ludzie; Są tacy, którzy naśladują innych.

P(x, y) - x zna y, X - ludzie; Y- politycy. Niektórzy znają ludzi władzy (polityków).

3) ∀x ∃y P(x, y)

P(x, y) - x lubi y, X - ludzie; Każdy kogoś lubi.

P(x, y) - x jest potomkiem y, X - ludzie; Każdy jest czyimś potomkiem.

4) ∃x ∀y P(x, y)

P(x, y) - x wynosi się nad y, X - ludzie; Niektórzy wynoszą się nad wszystkich.

P(x, y) - x zazdrości y, X - ludzie; Są tacy, którzy każdemu zazdroszczą.

A(x) - x jest studentem

B (x) - y jest podręcznikiem

P(x, y) - x przeczytał y

∀x A(x) →∃y [B(y) ∧ P(x, y)]

Każdy student przeczytał jakiś podręcznik.

∃x A(x) ∧ ∀y [P(x, y) →B(y)]

Niektórzy studenci czytają tylko podręczniki.

Przykłady z matematyki

- Definicja Heinego granicy funkcji f w punkcie x₀:

dla x→ x₀ i dla n →

lim f(x) = g Λ (x_n) {[Λ n ∈ N (x_n ∈ D_f ∧ x_n ≠ x₀ ∧ lim x_n = x₀] → lim f(x_n) = g}

- Definicja Cauchy'ego granicy funkcji f w punkcie x_0, dla x→ x₀:

lim f(x) = g Λ ( > 0) V (δ > 0) Λ ( x ∈ D_f 0 < |x - x₀ |< δ → | f(x) - f(x₀₎ |< 

Prawa rachunku kwantyfikatorów

(dla predykatów jedno i dwuargumentowych)

A(x), B(x) - predykaty jednoargumentowe

P(x, y) - predykat dwuargumentowy

p - zmienna zdaniowa

1) Prawo opuszczania kwantyfikatora ogólnego (dictum de omni)

∀x A(x) → A(x)

∀x A(x) → A(a)

Stąd, że każdy przedmiot ma pewną własność A wynika, że dowolny/pewien określony przedmiot ma tę własność.

Przykład: Jeśli każdy jest omylny, to Arystoteles jest omylny.

1*) Nie zachodzi:

A(x) → ∀x A(x)

A(a) → ∀x A(x)

2) Prawo dołączania kwantyfikatora szczegółowego (dictum de singulo)

A(x) → ∃x A(x)

A(a) → ∃x A(x)

Stąd, że dowolny/pewien określony przedmiot ma daną własność, wynika, że istnieje przedmiot mający tę własność.

Przykład: Jeśli N. jest mieszkańcem Krakowa, to istnieje takie x, że x jest mieszkańcem Krakowa.

2*) Nie zachodzi:

∃x A(x) → A(x)

∃x A(x) → A(a)

2.1) ∀A(x) → ∃x A(x) - prawo subalternacji

Prawo 2. 1 wynika z 1), 2) i z prawa przechodniości implikacji.

3) Prawa zmiany zmiennych związanych

∀x A(x) ≡ ∀x A(x)

∃x A(x) ≡ ∃x A(x)

4) Pierwsze prawo de Morgana dla rachunku predykatów, inaczej prawo negowania kwantyfikatora ogólnego:

∼∀x A(x) ≡ ∃x ∼A(x)

Nie każdy przedmiot ma własność A wtedy i tylko wtedy, gdy istnieją przedmioty niemające własności A.

Przykład. Nie każdy człowiek jest długowieczny wtedy i tylko wtedy, gdy istnieją ludzie, którzy nie są długowieczni.

5) Drugie prawo de Morgana dla rachunku predykatów, inaczej prawo negowania kwantyfikatora szczegółowego

∼∃x A(x) ≡ ∀x ∼A(x)

Nie istnieją przedmioty o własności A wtedy i tylko wtedy, gdy żaden przedmiot nie ma własności A (każdy przedmiot ma własność nie-A).

Przykład. Nie istnieją ludzie nieśmiertelni wtedy i tylko wtedy, gdy każdy człowiek jest śmiertelny (żaden człowiek nie jest nieśmiertelny).

6.1) Prawo zastępowania kwantyfikatora ogólnego przez kwantyfikator szczegółowy i negację

∀x A(x) ≡ ∼∃x ∼A(x)

6.2) Prawo zastępowania kwantyfikatora szczegółowego przez kwantyfikator ogólny i negację

∃x A(x) ≡ ∼∀x ∼A(x)

Prawa 6.1) i 6.2) wynikają z praw de Morgana i prawa podwójnej negacji.

7) Prawo rozkładania kwantyfikatora ogólnego na implikację

a) ∀x [A(x) → B(x)] → [∀x A(x) → ∀x B(x)]

b)∀x [A(x) → B(x)] → [∃x A(x) → ∃x B(x)]

7*) Nie zachodzi:

[∀x A(x) → ∀x B(x)] → ∀x [A(x) → B(x)]

8) Prawo rozkładania kwantyfikatora ogólnego na równoważność

a) ∀x [A(x) ≡ B(x)] → [∀x A(x) ≡ ∀x B(x)]

b)∀x [A(x) ≡ B(x)] → [∃x A(x) ≡ ∃x B(x)]

9) Prawo rozkładania kwantyfikatora ogólnego na koniunkcję

∀x [A(x) ∧ B(x)] ≡ [∀x A(x) ∧ ∀x B(x)]

10) Prawo rozkładania kwantyfikatora szczegółowego na koniunkcję

∃x [A(x) ∧ B(x)] → [∃x A(x) ∧ ∃x B(x)]

Przykład. Jeżeli istnieje taki x, że x jest aktorem i tancerzem, to istnieje taki x, że x jest aktorem i istnieje taki x, że x jest tancerzem.

10*) Nie zachodzi:

[∃x A(x) ∧ ∃x B(x)] → ∃x [A(x) ∧ B(x)]

Przykład:

A(x) - x jest psem

B(x) - x jest kotem

Z tego, że istnieją psy i istnieją koty nie wynika, że istnieje zwierzę, które jest jednocześnie psem i kotem.

11) Nie zachodzi:

∃x [A(x) → B(x)] → [∃x A(x) → ∃x B(x)]

12) Prawo wyciągania kwantyfikatora ogólnego przed alternatywę

[∀x A(x) ∨ ∀x B(x)] → ∀x [A(x) ∨ B(x)]

Przykład:

Ze zdania: Dla każdego x, x zdał egzamin z socjologii lub dla każdego x, x zdał egzamin z logiki, wynika zdanie: Dla każdego x, x zdał egzamin z socjologii x zdał egzamin z logiki.

12*) Nie zachodzi:

∀x [A(x) ∨ B(x)] → [∀x A(x) ∨ ∀x B(x)]

Przykład:

A(x) - x jest kobietą

B(x) - x jest mężczyzną

Z tego, że każdy człowiek jest kobietą lub mężczyzną nie wynika, że albo każdy człowiek jest kobietą albo każdy człowiek jest mężczyzną.

13) Prawo rozkładania kwantyfikatora szczegółowego na alternatywę

∃x [A(x) ∨ B(x)] → [∃x A(x) ∨ ∃x B(x)]

14) Prawo przestawiania kwantyfikatorów ogólnych

∀x ∀y P(x, y) ≡ ∀y∀x P(x, y)

15) Prawo przestawiania kwantyfikatorów szczegółowych

∃x ∃y P(x, y) ≡ ∃y ∃x P(x, y)

16) Prawo przestawiania kwantyfikatorów szczegółowego i ogólnego

∃x ∀y P(x, y) → ∀y ∃x P(x, y)

Jeśli istnieje takie państwo x, że każdy y jest jego obywatelem, to dla każdego y istnieje takie państwo x, którego y jest obywatelem.

16*) Nie zachodzi:

∀x ∃y P(x, y) → ∃y∀x P(x, y)

Przykłady. Jeśli dla każdego żubra istnieje taki las, w którym on przebywa (zamieszkuje), to z tego nie wynika, że istnieje taki las, że każdy żubr jego mieszkańcem.

N - zbiór liczb naturalnych; m, n ∈ N

Nie zachodzi: ∀n ∃ m (n < m) → ∃m ∀n (n < m)

Z tego, że dla każdej liczby naturalnej n istnieje liczba większa od niej liczba naturalna m (np. m = n + 1) nie wynika, że istnieje taka liczba naturalna, która jest większa od wszystkich innych liczb naturalnych.

Inne prawa rachunku kwantyfikatorów

Prawami rachunku kwantyfikatorów są wszystkie podstawienia tautologii krz.

Przykłady podstawień:

a) prawa wyłączonego środka p ∨ ∼p, przy: p/∀x A(x)

∀x A(x) ∨ ∼ ∀x A(x)

b) prawa symplifikacji dla alternatywy: p → (p ∨ q), przy: p/ ∃x A(x), q/ ∀y A(y)

∃x A(x) → (∀y A(y) ∨ ∃x A(x))

c) charakterystyki prawdy q → (p → q), przy: p/∀x ∃y P(x, y), q/∃x A(x)

∃x A(x) → [∀x ∃y P(x, y) → ∃x A(x)]

Kwantyfikatory o ograniczonym zakresie

A(x), B(x) - predykaty jednoargumentowe

∀_A(x) B(x) - kwantyfikator ogólny o ograniczonym zakresie

∀_A(x) B(x) czytamy: każdy x posiadający własności A ma własność B; inaczej, własność B, która przysługuje każdemu x o własności A

∃_A(x) B(x) - kwantyfikator szczegółowy o ograniczonym zakresie

∃_A(x) B(x) czytamy: istnieje taki - posiadający własność A - x który ma własność B; inaczej, istnieje taki x o własności A, który ma własność B

Kwantyfikatory o ograniczonym zakresie ograniczają zakres predykatu B do pewnego A. Są to operatory od dwóch argumentów zdaniowych (z/z, z)

Zachodzą równoważności:

∀_A(x) B(x) ≡ ∀x [A(x) →B(x)]

∃_A(x) B(x) ≡ ∃x [A(x) ∧ B(x)]

Teoria predykatów - pełnym systemem logicznym

Rozwój logiki doprowadził do powstania takiego systemu logiki, który zawiera wszelkie schematy logicznie poprawnego wnioskowania na do­wolny temat. System, który posiada taką właściwość nazywamy systemem pełnym. Teoria predykatów jest pełnym systemem logicznym, dlatego nazywana jest po prostu (klasycznym) rachunkiem logicznym (krl). Każde intuicyjnie poprawne rozumowanie daje się mianowicie w tym rachunku logicznym całkowicie sformalizować. Wyciągane spontanicznie wnioski logika rozbija na elementarne etapy, sprowadzając wszelkie poprawne rozumowanie do stosowania aksjomatów krl i re­guł pierwotnych krl. Środki te są całkowicie dostateczne do odtworzenia wszelkiego intuicyjnie poprawnego dedukcyjnego dowodu.

Klasyczny, aksjomatyczny rachunek logiczny zawiera dokładnie wszystkie zdania, które są prawdziwe w każdej dziedzinie, czyli zawiera wszystkie tauto­logie logiczne i tylko tautologie logiczne.

Przy czym krl, będąc teorią pełną, zawiera bowiem pełny zbiór logicznych twierdzeń prawdziwych we wszystkich dziedzinach, nie jest jednak teorią zupełną.

Definicje funktorów tworzących zdania kategoryczne

A(x) - x jest A

B(x) - x jest B

1) Każde A jest B
∀_A(x) B(x)

2) Żadne A nie jest B
∀_A(x) ∼ B(x)

3) Niektóre A są B
∃_A(x) B(x)

4) Niektóre A nie są B
∃_A(x) ∼B(x)

Zachodzą równoważności:

1) ∀_A(x) B(x) ≡ ∀x [A(x) →B(x)]

Każde A jest B ≡ Dla każdego x, jeśli x jest A, to x jest B

2) ∀_A(x) ∼B(x) ≡ ∀x [A(x) → ∼B(x)]

Żadne A nie jest B ≡ Dla każdego x, jeśli x jest A, to x nie jest B

3) ∃_A(x) B(x) ≡ ∃x [A(x) ∧ B(x)]

Niektóre A są B≡ Istnieje taki x, że x jest A i x jest B

4) ∃_A(x) ∼B(x) ≡ ∃x [A(x) ∧ ∼B(x)]

Niektóre A nie są B ≡ Istnieje taki x, że x jest A i x nie jest B

Warunek niepustości zakresu nazwy - istnienia odpowiednich przedmiotów:

∃x A(x)

czytamy: Istnieją A ≡ Istnieją x, że x jest A

Definicje zdań kategorycznych w krl

S(x) - x jest S

P(x) - x jest P

M(x) - x jest M

S'(x) - x jest nie-S

P'(x) - x jest nie-P

1) S a P
∀_S(x) P(x)

Każde S jest P ≡ Dla każdego x, jeśli x jest S, to x jest P

2) S e P
∀_S(x) ∼ P(x)

Żadne S nie jest P ≡ Dla każdego x, jeśli x jest S, to x nie jest P

3) S i P
∃_S(x) P(x)

Niektóre S są P ≡ Istnieje taki x, że x jest S i x jest P

4) S o P
∃_S(x) ∼P(x)

Niektóre S nie są P ≡ Istnieje taki x, że x jest S i x nie jest P

Zdania kategoryczne w krl - zapis teoriomnogościowy

S, P - nazwy niepuste

S a P
∀x (x∈S → x∈P) ∧ ∃x (x∈S)

S e P
∀x (x∈S → ∼x∈P) ∧ ∃x (x∈S) ∧ ∃x (x∈P)

S i P
∃x (x∈S ∧ x∈P)

S o P
∃x (x∈S ∧ ∼x∈P) ∧ ∃x (x∈P

Krl a wnioskowanie bezpośrednie

W krl (węższym rachunku predykatów) można, na podstawie podanych wyżej definicji sformułować i udowodnić prawa wnioskowania bezpośredniego.

Przykłady. Prawo konwersji dla zdań szczegółowo-twierdzących:

S i P

P i S

ma postać: ∃_S(x)P(x) → ∃_p(x)S(x)

prawo obwersji zdań ogólno-przeczących:

S e P

S a P'

∀_S(x) ∼ P(x) →∀_S(x) P'(x)

Krl a sylogistyka

W krl można też, na podstawie podanych wyżej definicji sformułować i udowodnić prawa sylogistyki. Przykłady:

BARBARA (I, 1)

M a P

S a M

S a P

[∀_S(x) M (x)∧ ∀_M(x) P(x)] → ∀_S(x) P(x)

FERISON (III, 6)

M e P M i S S o P

[∃_M(x) S(x) ∧ ∀_M(x) ∼ P(x)]→ ∃_S(x) ∼P(x)

Krl i klasyczny rachunek zdań

Krz jest częścią składową krl.

Addenda

Rachunek predykatów

G. Malinowski Logiki wielowartościowe , ss. 5 - 6

Logiczna analiza wewnętrznej struktury zdań prostych (nie zawierających spójników zdaniowych) prowadzi do rachunku predykatów, który jest rozszerzeniem rachunku zdań. W najprostszej wersji takiego rachunku obok dotychczas używanych symboli wprowadza się dodatkowo:

zmienne nazwowe: x, y, z, x₁, y₁, z₁, ...

predykaty: P, Q, R, P₁, Q₁, R₁ ...

kwantyfikatory:
(ogólny),
(egzystencjalny).

Zmienne nazwowe reprezentują nazwy indywidualne, a predykaty funkcje zdaniotwórcze o argumentach nazwowych. Z każdym predykatem związana jest jednoznacznie liczba naturalna ustalająca jego kategorię składniową: predykaty jednoargumentowe reprezentują własności (obiektów) pozostałe zaś - relacje. Jeśli P jest predykatem n -argumentowym, to wyrażenie postaci

„P(x₁, x₂, ... , x_n)” nazywane będzie formułą atomową. Kwantyfikatory są odpowiednikami zwrotów: dla każdego (ogólny), dla pewnego (egzystencjalny), i współwystępują ze zmiennymi nazwowymi, tworząc wyrażenia
(dla każdego x) i
(dla pewnego x).

Zbiór formuł For* rachunku predykatów definiuje się podobnie jak zbiór formuł kla­sycznego rachunku zdań, traktując formuły atomowe tak jak zmienne zdaniowe oraz do­dając warunek:

(*) Jeśli
For* i x jest zmienną nazwową, to
(α)
For*.

Prawdziwościowy opis rachunku predykatów można uzyskać przy użyciu inter­pretacji pełniących w tym przypadku rolę podobną do wartościowań zero-jedynkowych.

Interpretacja f (f_D) zbioru For* w niepustej dziedzinie D (D ≠ ∅) jest funkcją przy­porządkowującą dowolnej zmiennej nazwowej element zbioru Dla, każdemu predykatowi n -argumentowemu pewną n-argumentową relację w D i dowolnej formule wartość logicz­ną (0 lub 1). Zakłada się, że:

(1) Dla dowolnego n -argumentowego predykatu P: f (P(x₁, x₂, …x_n))
f (P(x₁), P(x₂), …, P(x_n))

(2) f jest wartościowaniem logicznym zbioru For*.

(3) f (
) = l wtedy i tylko wtedy, gdy f'
= l dla wszystkich interpretacji f' różniących się od f co najwyżej na x.

f (
) = l wtedy i tylko wtedy, gdy f'
= l dla pewnej interpretacji f' różniącej się od f co najwyżej na x.

Formuła

For* jest tautologią rachunku predykatów wtedy i tylko wtedy, gdy f
= 1 dla dowolnej interpretacji f (f_D).

Rachunek predykatów utożsamiany z teorią wszystkich tautologii jest nierozstrzygalny (zob. Church (1956)), tj. nie można podać efektywnej metody, która zastosowana w odnie­sieniu do dowolnej formuły pozwalałaby uzyskać odpowiedź na pytanie o tautologiczność. Tym większa rola przypada aksjomatyzacji. Aksjomatyzację rachunku predykatów uzy­skuje się wzbogacając zbiór schematów aksjomatów rachunku zdań schematami formuł i reguł charakteryzujących kwantyfikatory. Wzajemna definiowalność kwantyfikatorów:

(D)

∼(

upraszcza to zadanie. Ostatecznie, w celu zaksjomatyzowania tego rachunku wystarczy do aksjomatów KRZ:

A1. (p → q) → [(q → r) → (p → r)]

A2. p → (q → p)

A3. [p → (p → q)] → (p → q)

A4. p → ∼∼ p

A5. ∼∼ p → p

A6. (p → q) → (∼q → ∼p)

A7. (p ∧ q) → p

A8. (p ∧ q) → q

A9. (p → q) → {(p → r) → [p → (q ∧ r)]}

A10. p → (p ∨ q)

A11. q → (p ∨ q)

A12. (p → r) → {(q → r) → [(p ∨ q) → r)]}

A13. (p ≡ q) → (p → q)

A14. (p ≡ q) → (q → p)

A15. (p → q) → [(q → p) → (p ≡ q)]

dodać schematy:

A16.
)] przy założeniu, że x nie jest zmienną wolną w

A17.
o ile podstawienie y/x jest dopuszczalne

i jako reguły przyjąć (RO) oraz tzw. regułę generalizacji:

(GN)

.

Pierwszy dowód pełności systemu klasycznego rachunku predykatów podany został przez K. Gödla (1930). Badania rachunku predykatów mają bogatą tradycję, a teoria jego interpretacji, tzw. teoria modeli, wyodrębniła się, przybierając postać samodzielnej dyscypliny (por. Chang, Keisler (1973), Hodges (1993)).

------------------------------------------

7

---