Logika. Zadania z tematu 9.
Klasyczny rachunek predykatów  część II
Zadanie 1.Wykazać, że podana formuła nie jest tautologią ani kontrtautologią:
a) "x ( P(x) '" Q(x) ), b) "x"y R(x,y),
c) "x"y (R(x,y) (" R(y,x) ), d) "x"y (R(x,y) Ò! ~ R(y,x) ),
e) "x"y R(x,y) Ò! "x R(x,x), f) [ "x P(x) '" "x Q(x) ]Ò! "x [ P(x) '" Q(x) ],
g) [ "x P(x) Ò! "x Q(x) ] Ò! "x [ P(x) Ò! Q(x) ], h) "x"y R(x,y) Ò! "x R(x,x),
i) "x R(x,x) Ò! "x"y R(x,y), j) "x"y (R(x,y) Ò! R(y,x) ) Ò! "x R(x,x),
k) "x [ "y R(x,y) Ò! P(x) ], l) "x"y"z [ (R(x,y) '" R(y,z) ) Ò! R(x,z) ].
Zadanie 2. Wykazać, że reguła nie jest dedukcyjna:
"x P(x) "x [P(x) Ò! Q(x)] "x <" [P(x) '" Q(x)]
a) , b) , c) ~,
"x P(x) "x [<" P(x) Ò!<" Q(x)] "x <" P(x)
"x R(x, x) "x"y [ R(x, y) Ò! R(y, x)]
d) , e) .
"x"y R(x, y) "x R(x, x)
Odpowiedzi
Zadanie 1. W każdym z rozwiązań U1 stanowi kontrmodel formuły, tzn. taką interpretację, przy której formuła staje się
zdaniem fałszywym, a U2 - model, czyli taką interpretację, która formule nadaje postać zdania prawdziwego.
a) U1 = U  zbiór liczb, R(x, y)  x jest małżonkiem y .
Jeżeli dla każdych dwóch ludzi jest tak, że jeden jest małżonkiem drugiego, to drugi jest małżonkiem pierwszego, to
istnieje ktoś, kto jest swoim własnym małżonkiem. (fałsz)
U2 = U  zbiór ludzi, R(x, y)  x ma tyle samo lat co y .
Jeżeli dla każdych dwóch ludzi jest tak, że jeden ma tyle samo lat co drugi, to drugi ma tyle samo lat co pierwszy, to
istnieje ktoÅ›, kto ma tyle samo lat, co on sam. (prawda)
b) U1 = U  zbiór liczb, , P(x)  x jest parzyste, Q(x)  x jest nieparzyste .
Istnieje liczba będąca jednocześnie parzysta i nieparzysta. (fałsz)
U2 = U  zbiór ludzi, P(x)  x jest kobietą, Q(x)  x ma 20 lat .
Istnieje kobieta majÄ…ca 20 lat. (prawda)
c) U1 = U  zbiór ludzi, R(x, y)  x jest rodzicem y .
Każdy człowiek jest czyimś rodzicem. (fałsz)
U2 = U  zbiór ludzi, R(x, y)  x jest dzieckiem y .
Każdy człowiek jest czyimś dzieckiem. (prawda)
d) U1 = U  zbiór ludzi, R(x, y)  x kocha y
Dla każdych dwóch ludzi jest tak, że jeden kocha drugiego lub drugi pierwszego. (fałsz)
U2 = U  zbiór ludzi, R(x, y)  x jest nie niższy od y
Dla każdych dwóch ludzi jest tak, że jeden jest nie niższy od drugiego lub drugi od pierwszego. (prawda)
e) U1 = U  zbiór ludzi, R(x, y)  x kocha y
Dla każdych dwóch ludzi jest tak, że jeśli jeden kocha drugiego, to drugi nie kocha pierwszego. (fałsz)
U2 = U  zbiór ludzi, R(x, y)  x jest starszy od y
Dla każdych dwóch ludzi jest tak, że jeśli jeden jest starszy od drugiego, to drugi nie jest starszy od pierwszego. (prawda)
f) U1 = U  zbiór ludzi, R(x, y)  x jest starszy od y
Jeżeli istnieje dwoje ludzi, takich że jeden jest starszy od drugiego, to istnieje ktoś, kto jest starszy od samego siebie.
(fałsz)
U2 = U  zbiór ludzi, R(x, y)  x jest w tym samym wieku co y
Jeżeli istnieje dwoje ludzi, takich że jeden jest w tym samym wieku co drugi, to istnieje ktoś, kto jest w tym samym wieku,
co on sam. (prawda)
Logika. Zadania z tematu 9.
2
g) U1 = U  zbiór ludzi, P(x)  x ma 20 lat, Q(x)  x ma 35 lat .
Jeśli istnieje ktoś, kto ma 20 lat i istnieje ktoś, kto ma 35 lat, to istnieje ktoś, kto ma jednocześnie 20 lat i 35 lat. (fałsz)
U2 = U  zbiór ludzi, P(x)  x urodził się w lipcu, Q(x)  x ma 20 lat .
Jeśli istnieje ktoś, kto urodził się w lipcu i istnieje ktoś, kto ma 20 lat, to istnieje ktoś, kto urodził się w lipcu i ma
jednocześnie 20 lat. (prawda)
h) U1 = U  zbiór ludzi, P(x)  x jest kobietą, Q(x)  x jest nauczycielem .
Jeśli jest tak, że jeśli każdy człowiek jest kobietą, to każdy człowiek jest nauczycielem, to każda kobieta jest nauczycielem.
(fałsz)
U2 = U  zbiór liczb, P(x)  x jest podzielne przez 4, Q(x)  x jest parzyste .
Jeśli jest tak, że jeśli każda liczba jest podzielna przez 4, to każda liczba jest parzysta, to każda liczba podzielna przez 4
jest parzysta. (prawda)
i) U1 = U  zbiór liczb, R(x, y)  x jest mniejsza niż y .
Jeśli każda liczba jest mniejsza od jakiejś liczby, to istnieje liczba mniejsza od siebie samej. (fałsz)
U2 = U  zbiór liczb, R(x, y)  x jest mniejsza lub równa y .
Jeśli każda liczba jest mniejsza lub równa w stosunku do jakiejś liczby, to istnieje liczba mniejsza lub równa w stosunku
do siebie samej. (prawda)
j) U1 = U  zbiór liczb, R(x, y)  x jest równa y .
Jeśli istnieje liczba równa sobie samej, to każde dwie liczby są sobie równe. (fałsz)
U2 = U  zbiór ludzi, R(x, y)  x jest starszy od y .
Jeśli istnieje ktoś, kto jest starszy od samego siebie, to dla każdych dwóch ludzi jeden jest starszy od drugiego. (prawda)
k) U1 = U  zbiór ludzi, R(x, y)  x jest małżonkiem y .
Jeżeli dla każdych dwóch ludzi jest tak, że jeden jest małżonkiem drugiego, to drugi jest małżonkiem pierwszego, to
istnieje ktoś, kto jest swoim własnym małżonkiem. (fałsz)
U2 = U  zbiór ludzi, R(x, y)  x ma tyle samo lat co y .
Jeżeli dla każdych dwóch ludzi jest tak, że jeden ma tyle samo lat co drugi, to drugi ma tyle samo lat co pierwszy, to
istnieje ktoÅ›, kto ma tyle samo lat, co on sam. (prawda)
l) U1 = U  zbiór ludzi, R(x, y)  x jest małżonkiem y, P(x)  x jest mężczyzną .
Każdy człowiek, który ma rówieśnika, jest mężczyzną. (fałsz)
U2 = U  zbiór ludzi, R(x, y)  x jest matką y, P(x)  x jest kobietą .
Każdy człowiek, który jest czyjąś matką, jest kobietą. (prawda)
m) U1 = U  zbiór ludzi, R(x, y)  x kocha y .
Dla każdych trzech ludzi jest tak, że jeśli pierwszy kocha drugiego, drugi trzeciego, to pierwszy kocha trzeciego. (fałsz)
U2 = U  zbiór ludzi, R(x, y)  x jest starszy od y .
Dla każdych trzech ludzi jest tak, że jeśli pierwszy jest starszy od drugiego, a drugi od trzeciego, to pierwszy jest starszy
od trzeciego. (prawda)
Zadanie 2. W każdym przypadku należy znalez
ć strukturę, w której przesłanka jest prawdziwa, a wniosek fałszywy.
a) U = U  zbiór ludzi, P(x)  x jest kobietą .
Przesłanka: Niektórzy ludzie są kobietami. (prawda) Wniosek: Każdy człowiek jest kobietą. (fałsz)
b) U = U  zbiór liczb, P(x)  x jest podzielna przez 4, Q(x)  x jest parzyste .
Przesłanka: Każda liczba podzielna przez 4 jest parzysta. (prawda) Wniosek: Każda liczba, która nie jest podzielna przez 4,
nie jest parzysta. (fałsz)
c) U = U  zbiór liczb, P(x)  x jest parzyste, Q(x)  x jest nieparzyste .
Przesłanka: Żadna liczba nie jest jednocześnie parzysta i nieparzysta. (prawda) Wniosek: Żadna liczba nie jest parzysta.
(fałsz)
d) U = U  zbiór ludzi, R(x, y)  x ma tyle samo lat co y .
Przesłanka: Każdy człowiek ma tyle samo lat co on sam. (prawda) Wniosek: Każdych dwoje ludzi ma tyle samo lat. (fałsz)
e) U = U  zbiór mężczyzn, R(x, y)  x jest bratem y .
Przesłanka: Dla każdych dwóch mężczyzn, jeśli jeden jest bratem drugiego, to drugi jest bratem pierwszego (prawda)
Wniosek: Każdy mężczyzna jest swoim własnym bratem (fałsz)