Rachunek Predykatów
LOGIKA
Rachunek Predykatów
Robert Trypuz
Katedra Logiki KUL
7 kwietnia 2011
Rachunek Predykatów
Plan wykładu
1 Język węższego rachunku predykatów (WRP)
Rachunek Predykatów
Plan wykładu
1 Język węższego rachunku predykatów (WRP)
2 Metoda założeniowa
Rachunek Predykatów
Plan wykładu
1 Język węższego rachunku predykatów (WRP)
2 Metoda założeniowa
3 Ważniejsze prawa WRP
Rachunek Predykatów
Plan wykładu
1 Język węższego rachunku predykatów (WRP)
2 Metoda założeniowa
3 Ważniejsze prawa WRP
4 Sprawdzanie poprawności formalnej wnioskowań w WRP
Rachunek Predykatów
Plan wykładu
1 Język węższego rachunku predykatów (WRP)
2 Metoda założeniowa
3 Ważniejsze prawa WRP
4 Sprawdzanie poprawności formalnej wnioskowań w WRP
5 WRP z identycznością
Rachunek Predykatów
Plan wykładu
1 Język węższego rachunku predykatów (WRP)
2 Metoda założeniowa
3 Ważniejsze prawa WRP
4 Sprawdzanie poprawności formalnej wnioskowań w WRP
5 WRP z identycznością
6 Ważniejsze prawa WRP z identycznością
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Ludwig Wittgenstein (Tractatus Logico-Philosophicus)
 Granice języka są granicami mojego świata
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu
Ludwig Wittgenstein (Tractatus Logico-Philosophicus)
 Granice języka są granicami mojego świata
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu
Ludwig Wittgenstein (Tractatus Logico-Philosophicus)
 Granice języka są granicami mojego świata
KRZ traktował o stanach rzeczy (sytuacja) oraz o związkach
pomiędzy nimi.
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu
Ludwig Wittgenstein (Tractatus Logico-Philosophicus)
 Granice języka są granicami mojego świata
KRZ traktował o stanach rzeczy (sytuacja) oraz o związkach
pomiędzy nimi.
Za pomocą KRZ nie mogliśmy bezpośrednio mówić o:
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu
Ludwig Wittgenstein (Tractatus Logico-Philosophicus)
 Granice języka są granicami mojego świata
KRZ traktował o stanach rzeczy (sytuacja) oraz o związkach
pomiędzy nimi.
Za pomocą KRZ nie mogliśmy bezpośrednio mówić o:
relacji pomiędzy obiektami
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu
Ludwig Wittgenstein (Tractatus Logico-Philosophicus)
 Granice języka są granicami mojego świata
KRZ traktował o stanach rzeczy (sytuacja) oraz o związkach
pomiędzy nimi.
Za pomocą KRZ nie mogliśmy bezpośrednio mówić o:
relacji pomiędzy obiektami
własnościach obiektów
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu
Ludwig Wittgenstein (Tractatus Logico-Philosophicus)
 Granice języka są granicami mojego świata
KRZ traktował o stanach rzeczy (sytuacja) oraz o związkach
pomiędzy nimi.
Za pomocą KRZ nie mogliśmy bezpośrednio mówić o:
relacji pomiędzy obiektami
własnościach obiektów
istnieniu obiektów oraz relacji pomiędzy nimi
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu
Ludwig Wittgenstein (Tractatus Logico-Philosophicus)
 Granice języka są granicami mojego świata
KRZ traktował o stanach rzeczy (sytuacja) oraz o związkach
pomiędzy nimi.
Za pomocą KRZ nie mogliśmy bezpośrednio mówić o:
relacji pomiędzy obiektami
własnościach obiektów
istnieniu obiektów oraz relacji pomiędzy nimi
(nie)powszechnym charakterze związków pomiędzy obiektami
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu i inferencji
Pewne wnioskowania dedukcyjne są poza zasięgiem KRZ:
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu i inferencji
Pewne wnioskowania dedukcyjne są poza zasięgiem KRZ:
wnioskowania Å‚atwe, np.:
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu i inferencji
Pewne wnioskowania dedukcyjne są poza zasięgiem KRZ:
wnioskowania Å‚atwe, np.:
1 Każdy informatyk jest szczęśliwy.
                  
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu i inferencji
Pewne wnioskowania dedukcyjne są poza zasięgiem KRZ:
wnioskowania Å‚atwe, np.:
1 Każdy informatyk jest szczęśliwy.
                  
2 Nieprawda, że żaden informatyk nie jest szczęśliwy.
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu i inferencji
Pewne wnioskowania dedukcyjne są poza zasięgiem KRZ:
wnioskowania Å‚atwe, np.:
1 Każdy informatyk jest szczęśliwy.
                  
2 Nieprawda, że żaden informatyk nie jest szczęśliwy.
wnioskowania trudne, np.:
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu i inferencji
Pewne wnioskowania dedukcyjne są poza zasięgiem KRZ:
wnioskowania Å‚atwe, np.:
1 Każdy informatyk jest szczęśliwy.
                  
2 Nieprawda, że żaden informatyk nie jest szczęśliwy.
wnioskowania trudne, np.:
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                    -
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Granice KRZ
Granice wyrazu i inferencji
Pewne wnioskowania dedukcyjne są poza zasięgiem KRZ:
wnioskowania Å‚atwe, np.:
1 Każdy informatyk jest szczęśliwy.
                  
2 Nieprawda, że żaden informatyk nie jest szczęśliwy.
wnioskowania trudne, np.:
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                    -
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Co nowego w WRP?
predykaty:
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Co nowego w WRP?
predykaty:
jednoargumentowe:
. . . umiera
. . . jest ssakiem
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Co nowego w WRP?
predykaty:
jednoargumentowe:
. . . umiera
. . . jest ssakiem
wieloargumentowe:
. . . jest większy od . . .
. . . przynależy do . . .
. . . kocha . . .
. . . leży pomiędzy . . . a . . .
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Co nowego w WRP?
predykaty:
jednoargumentowe:
. . . umiera
. . . jest ssakiem
wieloargumentowe:
. . . jest większy od . . .
. . . przynależy do . . .
. . . kocha . . .
. . . leży pomiędzy . . . a . . .
kwantyfikatory:
dla każdego
dla pewnego (istnieje)
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Alfabet WRP
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Alfabet WRP
Definicja
Alfabet WRP zawiera:
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Alfabet WRP
Definicja
Alfabet WRP zawiera:
1 alfabet KRZ:
zbiór zmiennych zdaniowych: p, q, r, . . .
zbiór funktorów prawdziwościowych: Ź, '", (", , a"
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Alfabet WRP
Definicja
Alfabet WRP zawiera:
1 alfabet KRZ:
zbiór zmiennych zdaniowych: p, q, r, . . .
zbiór funktorów prawdziwościowych: Ź, '", (", , a"
2 nieskończony zbiór zmiennych indywidualnych:
x, y, z, . . . , x1, y1, z1, . . . , x2, . . . ,
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Alfabet WRP
Definicja
Alfabet WRP zawiera:
1 alfabet KRZ:
zbiór zmiennych zdaniowych: p, q, r, . . .
zbiór funktorów prawdziwościowych: Ź, '", (", , a"
2 nieskończony zbiór zmiennych indywidualnych:
x, y, z, . . . , x1, y1, z1, . . . , x2, . . . ,
3 nieskończony zbiór predykatów:
jednoargumentowych: A, B, C, . . . , A1, . . . ,
wieloargumentowych: P, Q, R, . . . , P1, . . . ,
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Alfabet WRP
Definicja
Alfabet WRP zawiera:
1 alfabet KRZ:
zbiór zmiennych zdaniowych: p, q, r, . . .
zbiór funktorów prawdziwościowych: Ź, '", (", , a"
2 nieskończony zbiór zmiennych indywidualnych:
x, y, z, . . . , x1, y1, z1, . . . , x2, . . . ,
3 nieskończony zbiór predykatów:
jednoargumentowych: A, B, C, . . . , A1, . . . ,
wieloargumentowych: P, Q, R, . . . , P1, . . . ,
4 kwantyfikatory: ", ",
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Alfabet WRP
Alfabet WRP
Definicja
Alfabet WRP zawiera:
1 alfabet KRZ:
zbiór zmiennych zdaniowych: p, q, r, . . .
zbiór funktorów prawdziwościowych: Ź, '", (", , a"
2 nieskończony zbiór zmiennych indywidualnych:
x, y, z, . . . , x1, y1, z1, . . . , x2, . . . ,
3 nieskończony zbiór predykatów:
jednoargumentowych: A, B, C, . . . , A1, . . . ,
wieloargumentowych: P, Q, R, . . . , P1, . . . ,
4 kwantyfikatory: ", ",
5 nawiasy: (, ).
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Język WRP
Język WRP
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Język WRP
Język WRP
Definicja
Zbiór poprawnie zbudowanych wyrażeń (formuł) WRP (skrót: PZWWRP)
jest najmniejszym zbiorem napisów spełniającym poniższe warunki:
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Język WRP
Język WRP
Definicja
Zbiór poprawnie zbudowanych wyrażeń (formuł) WRP (skrót: PZWWRP)
jest najmniejszym zbiorem napisów spełniającym poniższe warunki:
1 Każda formuła KRZ jest PZWWRP.
2 Jeżeli ´n jest predykatem n-argumentowym (n e" 1), a Ä…1, Ä…1, . . . , Ä…n
sÄ… zmiennymi indywiduowymi, to
´n(Ä…1, Ä…1, . . . , Ä…n) " PZWWRP.
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Język WRP
Język WRP
Definicja
Zbiór poprawnie zbudowanych wyrażeń (formuł) WRP (skrót: PZWWRP)
jest najmniejszym zbiorem napisów spełniającym poniższe warunki:
1 Każda formuła KRZ jest PZWWRP.
2 Jeżeli ´n jest predykatem n-argumentowym (n e" 1), a Ä…1, Ä…1, . . . , Ä…n
sÄ… zmiennymi indywiduowymi, to
´n(Ä…1, Ä…1, . . . , Ä…n) " PZWWRP.Wyrażenie ´(Ä…1, Ä…1, . . . , Ä…n) jest
wyrażeniem atomicznym WRP.
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Język WRP
Język WRP
Definicja
Zbiór poprawnie zbudowanych wyrażeń (formuł) WRP (skrót: PZWWRP)
jest najmniejszym zbiorem napisów spełniającym poniższe warunki:
1 Każda formuła KRZ jest PZWWRP.
2 Jeżeli ´n jest predykatem n-argumentowym (n e" 1), a Ä…1, Ä…1, . . . , Ä…n
sÄ… zmiennymi indywiduowymi, to
´n(Ä…1, Ä…1, . . . , Ä…n) " PZWWRP.Wyrażenie ´(Ä…1, Ä…1, . . . , Ä…n) jest
wyrażeniem atomicznym WRP.
3 JeÅ›li Õ " PZWWRP, to ŹÕ " PZWWRP.
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Język WRP
Język WRP
Definicja
Zbiór poprawnie zbudowanych wyrażeń (formuł) WRP (skrót: PZWWRP)
jest najmniejszym zbiorem napisów spełniającym poniższe warunki:
1 Każda formuła KRZ jest PZWWRP.
2 Jeżeli ´n jest predykatem n-argumentowym (n e" 1), a Ä…1, Ä…1, . . . , Ä…n
sÄ… zmiennymi indywiduowymi, to
´n(Ä…1, Ä…1, . . . , Ä…n) " PZWWRP.Wyrażenie ´(Ä…1, Ä…1, . . . , Ä…n) jest
wyrażeniem atomicznym WRP.
3 JeÅ›li Õ " PZWWRP, to ŹÕ " PZWWRP.
4 JeÅ›li Õ, È " PZWWRP, to
(Õ '" È), (Õ (" È), (Õ È), (Õ a" È) " PZWWRP.
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Język WRP
Język WRP
Definicja
Zbiór poprawnie zbudowanych wyrażeń (formuł) WRP (skrót: PZWWRP)
jest najmniejszym zbiorem napisów spełniającym poniższe warunki:
1 Każda formuła KRZ jest PZWWRP.
2 Jeżeli ´n jest predykatem n-argumentowym (n e" 1), a Ä…1, Ä…1, . . . , Ä…n
sÄ… zmiennymi indywiduowymi, to
´n(Ä…1, Ä…1, . . . , Ä…n) " PZWWRP.Wyrażenie ´(Ä…1, Ä…1, . . . , Ä…n) jest
wyrażeniem atomicznym WRP.
3 JeÅ›li Õ " PZWWRP, to ŹÕ " PZWWRP.
4 JeÅ›li Õ, È " PZWWRP, to
(Õ '" È), (Õ (" È), (Õ È), (Õ a" È) " PZWWRP.
5 Jeżeli Õ " PZWWRP i Ä… jest zmiennÄ… indywidualnÄ…, to "Ä…(Õ) i
"Ä…(Õ) " PZWWRP.
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Język WRP
Siła wiązania funktorów i kwantyfikatorów w WRP
W ciągu symboli: ", ", Ź, '", (", , a", każdy symbol wiąże silniej niż
symbole występujące po nim.
Rachunek Predykatów
Język węższego rachunku predykatów (WRP)
Język WRP
Język WRP  przykłady
Tabela: Przykłady poprawnie i niepoprawnie zbudowanych PZWWRP
PZWWRP non-PZWWRP
A(x) A(x, x)
P(x, x) P(x)
"x A(x) A("x)
"x"x A(x)
"x"y P(z1, z2)
Rachunek Predykatów
Metoda założeniowa
Metoda założeniowa: od KRZ do WRP
WRP = KRZ + 4 nowe reguły:
Rachunek Predykatów
Metoda założeniowa
Metoda założeniowa: od KRZ do WRP
WRP = KRZ + 4 nowe reguły:
1 reguła dołączania kwantyfikatora ogólnego,
Rachunek Predykatów
Metoda założeniowa
Metoda założeniowa: od KRZ do WRP
WRP = KRZ + 4 nowe reguły:
1 reguła dołączania kwantyfikatora ogólnego,
2 reguła opuszczania kwantyfikatora ogólnego,
Rachunek Predykatów
Metoda założeniowa
Metoda założeniowa: od KRZ do WRP
WRP = KRZ + 4 nowe reguły:
1 reguła dołączania kwantyfikatora ogólnego,
2 reguła opuszczania kwantyfikatora ogólnego,
3 reguła dołączania kwantyfikatora szczegółowego,
Rachunek Predykatów
Metoda założeniowa
Metoda założeniowa: od KRZ do WRP
WRP = KRZ + 4 nowe reguły:
1 reguła dołączania kwantyfikatora ogólnego,
2 reguła opuszczania kwantyfikatora ogólnego,
3 reguła dołączania kwantyfikatora szczegółowego,
4 reguła opuszczania kwantyfikatora ogólnego,
Rachunek Predykatów
Metoda założeniowa
Metoda założeniowa: od KRZ do WRP
WRP = KRZ + 4 nowe reguły:
1 reguła dołączania kwantyfikatora ogólnego,
2 reguła opuszczania kwantyfikatora ogólnego,
3 reguła dołączania kwantyfikatora szczegółowego,
4 reguła opuszczania kwantyfikatora ogólnego,
Rachunek Predykatów
Metoda założeniowa
Ku nowym regułom - krok po kroku
Rachunek Predykatów
Metoda założeniowa
Ku nowym regułom - krok po kroku
zasięg wiązania kwantyfikatorów
wolność i niewola zmiennych
operacja podstawiania
Rachunek Predykatów
Metoda założeniowa
Zasięg kwantyfikatorów
Zasięg kwantyfikatorów
Rachunek Predykatów
Metoda założeniowa
Zasięg kwantyfikatorów
Zasięg kwantyfikatorów
Definicja
W wyrażeniach "Ä… Õ i "Ä… Õ wyrażenie Õ jest zasiÄ™giem kwantyfikatora:
ogólnego i szczegółowego.
Rachunek Predykatów
Metoda założeniowa
Wolność i niewola zmiennych
Wolność i niewola zmiennych
Rachunek Predykatów
Metoda założeniowa
Wolność i niewola zmiennych
Wolność i niewola zmiennych
Definicja
Zmienna Ä… wystÄ™puje w danym miejscu w wyrażeniu Õ jako zmienna
wolna, gdy występuje w tym miejscu, lecz nie bezpośrednio za
kwantyfikatorem ani w zasiÄ™gu kwantyfikatora. Zmienna Ä… jest wolna w Õ
jeżeli wystÄ™puje w Õ w jakimÅ› miejscu jako zmienna wolna.
Rachunek Predykatów
Metoda założeniowa
Wolność i niewola zmiennych
Wolność i niewola zmiennych
Definicja
Zmienna Ä… wystÄ™puje w danym miejscu w wyrażeniu Õ jako zmienna
wolna, gdy występuje w tym miejscu, lecz nie bezpośrednio za
kwantyfikatorem ani w zasiÄ™gu kwantyfikatora. Zmienna Ä… jest wolna w Õ
jeżeli wystÄ™puje w Õ w jakimÅ› miejscu jako zmienna wolna.
Definicja
W wyrażeniach "Ä… Õ i "Ä… Õ kwantyfikator wiąże zmiennÄ… Ä…. Jeżeli Ä… nie
jest wolne w Õ, to kwantyfikator wiąże Ä… nieistotnie.
Rachunek Predykatów
Metoda założeniowa
Wolność i niewola zmiennych
Wolność i niewola zmiennych - przykłady
Tabela: Przykłady wolnych i związanych zmiennych w PZWWRP
PZWKRZ wolne zmienne zwiÄ…zane zmienne
A(x) B(x) x -
"x"y P(x, y, z) z x, y
"x"y P(x, y, z) A(x) x, z y
Rachunek Predykatów
Metoda założeniowa
Operacja podstawiania
Operacja podstawiania
Definicja
Jeżeli zmienna Ä… jest wolna w wyrażeniu Õ, to wyrażenie Õ(Ä…/¾) jest
wyrażeniem uzyskanym z Õ przez prawidÅ‚owe podstawienie za Ä…
wyrażenia ¾ tej samej kategorii skÅ‚adniowej, co Ä…. Przy tym:
Rachunek Predykatów
Metoda założeniowa
Operacja podstawiania
Operacja podstawiania
Definicja
Jeżeli zmienna Ä… jest wolna w wyrażeniu Õ, to wyrażenie Õ(Ä…/¾) jest
wyrażeniem uzyskanym z Õ przez prawidÅ‚owe podstawienie za Ä…
wyrażenia ¾ tej samej kategorii skÅ‚adniowej, co Ä…. Przy tym:
1 W każdym miejscu, w którym Ä… wystÄ™puje w Õ jako zmienna wolna,
podstawiamy to samo wyrażenie ¾,
Rachunek Predykatów
Metoda założeniowa
Operacja podstawiania
Operacja podstawiania
Definicja
Jeżeli zmienna Ä… jest wolna w wyrażeniu Õ, to wyrażenie Õ(Ä…/¾) jest
wyrażeniem uzyskanym z Õ przez prawidÅ‚owe podstawienie za Ä…
wyrażenia ¾ tej samej kategorii skÅ‚adniowej, co Ä…. Przy tym:
1 W każdym miejscu, w którym Ä… wystÄ™puje w Õ jako zmienna wolna,
podstawiamy to samo wyrażenie ¾,
2 żadna zmienna wolna ¾ nie może stać siÄ™ zwiÄ…zanÄ… w wyniku
podstawienia.
Rachunek Predykatów
Metoda założeniowa
Operacja podstawiania
Operacja podstawiania
Definicja
Jeżeli zmienna Ä… jest wolna w wyrażeniu Õ, to wyrażenie Õ(Ä…/¾) jest
wyrażeniem uzyskanym z Õ przez prawidÅ‚owe podstawienie za Ä…
wyrażenia ¾ tej samej kategorii skÅ‚adniowej, co Ä…. Przy tym:
1 W każdym miejscu, w którym Ä… wystÄ™puje w Õ jako zmienna wolna,
podstawiamy to samo wyrażenie ¾,
2 żadna zmienna wolna ¾ nie może stać siÄ™ zwiÄ…zanÄ… w wyniku
podstawienia.
Denotacja ¾:
x, y, z, . . . ,
a, b, c, a1, b1, . . . ,
ax, bx,y , cz, . . . ,
Rachunek Predykatów
Metoda założeniowa
Operacja podstawiania
Operacja podstawiania - przykłady
Tabela: Przykłady podstawiania w PZWWRP
PZWKRZ podstawienie wynik podstawienia
P(x, y) R(y, x) x/y P(y, y) R(y, y)
"x P(x, y) R(y, x) x/y "x P(x, y) R(y, y)
"y P(x, y) x/y -
"y P(x, y) x/z "y P(z, y)
Rachunek Predykatów
Metoda założeniowa
Reguła dołączania kwantyfikatora ogólnego
Reguła dołączania kwantyfikatora ogólnego
Rachunek Predykatów
Metoda założeniowa
Reguła dołączania kwantyfikatora ogólnego
Reguła dołączania kwantyfikatora ogólnego
D" Õ
"Ä… Õ
o ile ą nie jest zmienną wolną w założeniach dowodu.
Rachunek Predykatów
Metoda założeniowa
Reguła dołączania kwantyfikatora ogólnego
Reguła dołączania kwantyfikatora ogólnego - przykłady
Rachunek Predykatów
Metoda założeniowa
Reguła dołączania kwantyfikatora ogólnego
Reguła dołączania kwantyfikatora ogólnego - przykłady
Tabela: Przykłady zastosowania reguły D"
Przed D" Po D"
A(x) "x A(x)
A(x) "y A(x)
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora ogólnego
Reguła opuszczania kwantyfikatora ogólnego
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora ogólnego
Reguła opuszczania kwantyfikatora ogólnego
O" "Ä… Õ
Õ(Ä…/¾)
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora ogólnego
Reguła opuszczania kwantyfikatora ogólnego - przykłady
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora ogólnego
Reguła opuszczania kwantyfikatora ogólnego - przykłady
Tabela: Przykłady zastosowania reguły O"
Przed O" Po O"
"x A(x) A(x)
"x A(x) A(y)
"x A(x) A(a)
"x"y P(x, y) "y P(x, y)
"x"y P(x, y) "y P(x, y)
"x"y P(x, y) "y P(z, y)
Rachunek Predykatów
Metoda założeniowa
Reguła dołączania kwantyfikatora szczegółowego
Reguła dołączania kwantyfikatora szczegółowego
Rachunek Predykatów
Metoda założeniowa
Reguła dołączania kwantyfikatora szczegółowego
Reguła dołączania kwantyfikatora szczegółowego
D" Õ(Ä…/¾)
"Ä… Õ
Rachunek Predykatów
Metoda założeniowa
Reguła dołączania kwantyfikatora szczegółowego
Reguła dołączania kwantyfikatora szczegółowego -
przykłady
Rachunek Predykatów
Metoda założeniowa
Reguła dołączania kwantyfikatora szczegółowego
Reguła dołączania kwantyfikatora szczegółowego -
przykłady
Tabela: Przykłady zastosowania reguły D"
Przed D" Po D"
A(x) "x A(x)
A(a) "y A(y)
A(y) "z A(z)
A(x) '" B(x) "z (A(z) '" B(z))
A(x) '" B(y) "z (A(z) '" B(y))
A(x) '" B(y) "z (A(x) '" B(z))
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego
O" "Ä… Õ
Õ(Ä…/IJ ,²2,...,²n)
1
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego
O" "Ä… Õ
Õ(Ä…/IJ ,²2,...,²n)
1
gdzie:
Ä jest staÅ‚Ä…,
²1, ²2, . . . , ²n sÄ… wszystkimi zmiennymi wolnymi wyrażenia Õ poza
zmiennÄ… Ä….
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia
Każde użycie reguły O" w jednym dowodzie wymaga wprowadzenia
nowej stałej.
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia
Każde użycie reguły O" w jednym dowodzie wymaga wprowadzenia
nowej stałej.
1. "x x + 1 = 1 z.
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia
Każde użycie reguły O" w jednym dowodzie wymaga wprowadzenia
nowej stałej.
1. "x x + 1 = 1 z.
2. "x x + 1 = 2 z.
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia
Każde użycie reguły O" w jednym dowodzie wymaga wprowadzenia
nowej stałej.
1. "x x + 1 = 1 z.
2. "x x + 1 = 2 z.
3. a + 1 = 1 O" : 1
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia
Każde użycie reguły O" w jednym dowodzie wymaga wprowadzenia
nowej stałej.
1. "x x + 1 = 1 z.
2. "x x + 1 = 2 z.
3. a + 1 = 1 O" : 1
4. a + 1 = 2 O" : 2
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia
Każde użycie reguły O" w jednym dowodzie wymaga wprowadzenia
nowej stałej.
1. "x x + 1 = 1 z.
2. "x x + 1 = 2 z.
3. a + 1 = 1 O" : 1
4. a + 1 = 2 O" : 2
5. 1 = 2 ExI : 3, 4
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia
Każde użycie reguły O" w jednym dowodzie wymaga wprowadzenia
nowej stałej.
1. "x x + 1 = 1 z.
2. "x x + 1 = 2 z.
3. a + 1 = 1 O" : 1
4. a + 1 = 2 O" : 2
5. 1 = 2 ExI : 3, 4
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
2. "y y < x O" : 1.
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
2. "y y < x O" : 1.
3. a < x O" : 2
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
2. "y y < x O" : 1.
3. a < x O" : 2
4. "x a < x D" : 3
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
2. "y y < x O" : 1.
3. a < x O" : 2
4. "x a < x D" : 3
5. "y"x y < x D" : 4
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
2. "y y < x O" : 1.
3. a < x O" : 2
4. "x a < x D" : 3
5. "y"x y < x D" : 4
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
2. "y y < x O" : 1.
3. a < x O" : 2
4. "x a < x D" : 3
5. "y"x y < x D" : 4
1. "x"y y < x z.
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
2. "y y < x O" : 1.
3. a < x O" : 2
4. "x a < x D" : 3
5. "y"x y < x D" : 4
1. "x"y y < x z.
2. "y y < x O" : 1.
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
2. "y y < x O" : 1.
3. a < x O" : 2
4. "x a < x D" : 3
5. "y"x y < x D" : 4
1. "x"y y < x z.
2. "y y < x O" : 1.
3. ax < x O" : 2
Rachunek Predykatów
Metoda założeniowa
Reguła opuszczania kwantyfikatora szczegółowego
Reguła opuszczania kwantyfikatora szczegółowego -
ostrzeżenia c.d.
Stała wprowadzona za pomocą reguły O" musi odzwierciedlać wszystkie
zmienne wolne wyrażenia.
1. "x"y y < x z.
2. "y y < x O" : 1.
3. a < x O" : 2
4. "x a < x D" : 3
5. "y"x y < x D" : 4
1. "x"y y < x z.
2. "y y < x O" : 1.
3. ax < x O" : 2
4. "x ax < x D" : 3
Rachunek Predykatów
Ważniejsze prawa WRP
Ważniejsze prawa WRP I
1 "x (A(x) '" B(x)) a" "x A(x) '" "x B(x),
2 "x A(x) (" "x B(x) "x (A(x) (" B(x)),
3 "x (A(x) '" B(x)) "x A(x) '" "x B(x),
4 "x A(x) (" "x B(x) a" "x (A(x) (" B(x)),
5 "x (A(x) B(x)) ("x A(x) "x B(x)),
6 "x (A(x) B(x)) ("x A(x) "x B(x)),
7 ("x A(x) "x B(x)) "x (A(x) B(x)).
Rachunek Predykatów
Ważniejsze prawa WRP
Ważniejsze prawa WRP II
1 "x (A(x) a" B(x)) ("x A(x) a" "x B(x)),
2 "x (A(x) a" B(x)) ("x A(x) a" "x B(x)),
3 "x"y P(x, y) a" "y"x P(x, y),
4 "x"y P(x, y) a" "y"x P(x, y),
5 "x"y P(x, y)"y"x P(x, y),
Rachunek Predykatów
Ważniejsze prawa WRP
Ważniejsze prawa WRP III
1 "x (p (" A(x)) a" p (" "x A(x),
2 "x (p A(x)) a" p "x A(x),
3 "x A(x) "x A(x),
4 "x A(x) a" "y A(y),
5 "x A(x) a" "y A(y),
6 Ź"x A(x) a" "x ŹA(x),
7 Ź"x A(x) a" "x ŹA(x),
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w WRP I
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w WRP I
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w WRP I
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
PoczÄ…tek:
wnioskowanie W
teoria logiczna WRP
W W wyróżnij przesłanki P i wniosek C !
Zapisz P oraz C w języku WRP!
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
1 A(x) - x jest informatykem,
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
2 B(x) - x jest szczęśliwy,
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
1 A(x) - x jest informatykem,
2 B(x) - x jest szczęśliwy,
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
1 A(x) - x jest informatykem,
2 B(x) - x jest szczęśliwy,
1 "x(A(x) B(x)),
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
1 A(x) - x jest informatykem,
2 B(x) - x jest szczęśliwy,
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
1 A(x) - x jest informatykem,
2 B(x) - x jest szczęśliwy,
2 "x(A(x) ŹB(x)),
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
1 A(x) - x jest informatykem,
2 B(x) - x jest szczęśliwy,
2 "x(A(x) ŹB(x)),
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP II
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
1 A(x) - x jest informatykem,
2 B(x) - x jest szczęśliwy,
3 Ź"x(A(x) ŹB(x)).
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP III
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP III
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP III
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
"x(A(x) B(x)).
             
Ź"x(A(x) ŹB(x)).
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP III
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP III
"x(A(x) B(x)).
             
Ź"x(A(x) ŹB(x)).
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP III
"x(A(x) B(x)).
             
Ź"x(A(x) ŹB(x)).
Przesłanki otrzymanego schematu formalnego połącz znakami
koniunkcji. Rezultat wstaw jako poprzednik implikacji, w której
następniku wstaw wniosek schematu!
Czy podstawa wnioskowania W jest prawem WRP?
TAK Ò! w W C wynika z P.
NIE Ò! w W C nie wynika z P.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP IV
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP IV
Czy  "x(A(x) B(x)) Ź"x(A(x) ŹB(x)) jest prawem WRP
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP IV
Czy  "x(A(x) B(x)) Ź"x(A(x) ŹB(x)) jest prawem WRP
NIE - dlaczego?
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP IV
Czy  "x(A(x) B(x)) Ź"x(A(x) ŹB(x)) jest prawem WRP
NIE - dlaczego?
słaba i mocna interpretacja zdań kategorycznych
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Słaba i mocna interpretacja zdań kategorycznych
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Słaba i mocna interpretacja zdań kategorycznych
Zdanie:
Każde A jest B.
żadne A nie jest B.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Słaba i mocna interpretacja zdań kategorycznych
Zdanie: SÅ‚aba interpretacja:
Każde A jest B. "x(A(x) B(x)).
żadne A nie jest B. "x(A(x) ŹB(x)).
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Słaba i mocna interpretacja zdań kategorycznych
Zdanie: SÅ‚aba interpretacja: Mocna interpretacja:
Każde A jest B. "x(A(x) B(x)). "x(A(x) B(x)) '" "x A(x).
żadne A nie jest B. "x(A(x) ŹB(x)). "x(A(x) ŹB(x)) '" "x A(x).
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP V
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP V
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP V
Każdy informatyk jest szczęśliwy.
                   -
Nieprawda, że żaden informatyk nie jest szczęśliwy.
"x(A(x) B(x)) '" "x A(x).
             
Ź("x(A(x) ŹB(x)) '" "x A(x)).
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VI
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VI
Czy
 "x(A(x) B(x)) '" "x A(x) Ź("x(A(x) ŹB(x)) '" "x A(x))
jest prawem WRP?
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VI
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VI
Tak, wyrażenie
 "x(A(x) B(x)) '" "x A(x) Ź("x(A(x) ŹB(x)) '" "x A(x))
jest prawem WRP.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
x jest dłużnikiem y - P(x, y),
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
x jest wierzycielem y - Q(x, y),
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Jeżeli Jan jest moim dłużnikiem i Piotr jest dłużnikiem Jana, to
Piotr jest moim dłużnikiem.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Jeżeli Jan jest moim dłużnikiem i Piotr jest dłużnikiem Jana, to
Piotr jest moim dłużnikiem.
"x"y"z (P(x, y) '" P(y, z) P(x, z)),
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Jeżeli Jan jest moim wierzycielem, to ja jestem dłużnikiem Jana.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Jeżeli Jan jest moim wierzycielem, to ja jestem dłużnikiem Jana.
"x"y (Q(x, y) P(y, x)),
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
"x"y (P(x, y) Q(y, x)),
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VII
1 Dłużnicy naszych dłużników są naszymi dłużnikami.
2 Każdy jest dłużnikiem swego każdego wierzyciela.
3 Każdy jest wierzycielem swego każdego dłużnika.
                       
4 Wierzyciele naszych wierzycieli sÄ… naszymi wierzycielami.
"x"y"z (Q(x, y) '" Q(y, z) Q(x, z)).
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VIII
Podstawa wnioskowania:
"x"y"z (P(x, y) '" P(y, z) P(x, z)) '" "x"y (Q(x, y) P(y, x)) '"
"x"y (P(x, y) Q(y, x)) "x"y"z (Q(x, y) '" Q(y, z) Q(x, z)).
Rachunek Predykatów
Sprawdzanie poprawności formalnej wnioskowań w WRP
Sprawdzanie poprawności formalnej wnioskowań w
WRP VIII
Podstawa wnioskowania:
"x"y"z (P(x, y) '" P(y, z) P(x, z)) '" "x"y (Q(x, y) P(y, x)) '"
"x"y (P(x, y) Q(y, x)) "x"y"z (Q(x, y) '" Q(y, z) Q(x, z)).
Czy podstawa wnioskowania jest prawem WRP?
Rachunek Predykatów
WRP z identycznością
Rachunek Predykatów
WRP z identycznością
Co nowego w języku WRP?
Zmiany w alfabecie WRP
Dodajemy funktor  = do alfabetu WRP.
Zmiany w definicji formuły WRP
Wyrażenie postaci  Ä… = ² jest PZWWRP.
Rachunek Predykatów
WRP z identycznością
Co nowego w języku WRP?
Zmiany w alfabecie WRP
Dodajemy funktor  = do alfabetu WRP.
Zmiany w definicji formuły WRP
Wyrażenie postaci  Ä… = ² jest PZWWRP.
Definicja różności
Przez wyrażenie  Ä… = ² rozumieć bÄ™dziemy wyrażenie  Źą = ² .

Rachunek Predykatów
WRP z identycznością
Reguła ekstensjonalności dla identyczności
Rachunek Predykatów
WRP z identycznością
Reguła ekstensjonalności dla identyczności
Reguła ekstensjonalności dla identyczności
ExI Ä… = ²
Õ
Õ(Ä…//²)
Rachunek Predykatów
WRP z identycznością
Reguła ekstensjonalności dla identyczności
Reguła ekstensjonalności dla identyczności
ExI Ä… = ²
Õ
Õ(Ä…//²)
gdzie Õ(Ä…//²) jest wyrażeniem powstaÅ‚ym z wyrażenia Õ przez
zastąpienie na jakimś miejscu (lub jakiś miejscach) wyrażenia nazwowego
Ä… przez ².
Rachunek Predykatów
WRP z identycznością
Reguła ekstensjonalności dla identyczności
Reguła ekstensjonalności dla identyczności
ExI Ä… = ²
Õ
Õ(Ä…//²)
gdzie Õ(Ä…//²) jest wyrażeniem powstaÅ‚ym z wyrażenia Õ przez
zastąpienie na jakimś miejscu (lub jakiś miejscach) wyrażenia nazwowego
Ä… przez ².
Uwaga! Regułę ExI można zastosować o ile spełnione są następujące
warunki:
Rachunek Predykatów
WRP z identycznością
Reguła ekstensjonalności dla identyczności
Reguła ekstensjonalności dla identyczności
ExI Ä… = ²
Õ
Õ(Ä…//²)
gdzie Õ(Ä…//²) jest wyrażeniem powstaÅ‚ym z wyrażenia Õ przez
zastąpienie na jakimś miejscu (lub jakiś miejscach) wyrażenia nazwowego
Ä… przez ².
Uwaga! Regułę ExI można zastosować o ile spełnione są następujące
warunki:
żadna zmienna wolna indywidualna wyrażenia ą nie jest związana w
wyrażeniu Õ na miejscu zastÄ…pienia.
Rachunek Predykatów
WRP z identycznością
Reguła ekstensjonalności dla identyczności
Reguła ekstensjonalności dla identyczności
ExI Ä… = ²
Õ
Õ(Ä…//²)
gdzie Õ(Ä…//²) jest wyrażeniem powstaÅ‚ym z wyrażenia Õ przez
zastąpienie na jakimś miejscu (lub jakiś miejscach) wyrażenia nazwowego
Ä… przez ².
Uwaga! Regułę ExI można zastosować o ile spełnione są następujące
warunki:
żadna zmienna wolna indywidualna wyrażenia ą nie jest związana w
wyrażeniu Õ na miejscu zastÄ…pienia.
żadna zmienna wolna indywidualna wyrażenia ² nie staje siÄ™
związana na miejscu zastąpienia w wyrażeniu stanowiącym wynik
zastÄ…pienia, tj. w wyrażeniu Õ(Ä…//²).
Rachunek Predykatów
WRP z identycznością
Aksjomat/prawo zwrotności identyczności
Rachunek Predykatów
WRP z identycznością
Aksjomat/prawo zwrotności identyczności
Przyjmujemy jako aksjomat WRP z identycznością:
Prawo zwrotności identyczności
"x x = x
Co to jest aksjomat?
Aksjomatem teorii logicznej nazywamy wyrażenie prawdziwe tej teorii
przyjęte bez dowodu.
Rachunek Predykatów
Ważniejsze prawa WRP z identycznością
Ważniejsze prawa WRP z identycznością
1 "x, y (x = y y = x),
2 "x, y, z (x = y '" y = z x = z),
3 "x, y (A(x) '" x = y A(y)),
4 "x, y (A(x) '" ŹA(y) x = y),

5 "x (A(x) a" "y (y = x '" A(y))),
6 "x (A(x) a" "y (y = x A(y))),
7 "x "y y = x,