5   Páté cvičení
Vzorové řešení většiny těchto příkladů na http://www.fi.muni.cz/~xbrazdil/plogika.ps
5.1 Základy predikátové logiky
£i Příklad 5.1 Mějme jazyk L = {P} bez rovnosti, kde P je binární predikátový symbol. Rozhodněte
a dokaZte, zda platí nýsledující tvrzení:
a) M = Vx Vz (P (x, z) — 3y P (x, y))
b) M = (Vx 3y P (x, y)) — (3y Vx P (x, y))
c) M = (3y Vx P (x, y)) — (Vx 3y P (x, y))
£0 Příklad 5.2 Rozhodnete, zda platí nasledujúci tvrzení: Mejme nejaký jazyk L, realizaci M jazyka L a formuli y predikítoveho poCtu jazyka L. Pak
M = y príve tehdy, kdyz M = —y
000 Příklad 5.3 Rozhodnete, zda platí nýsledující tvrzeni: Mejme jazyk L, realizaci M jazyka L a uzavřenou formuli y predikítoveho poctu jazyka L. Pak
M = y prave tehdy, kdyz M = —y
Příklad 5.4 Mejme jazyk L = {<} s rovností, kde < je binírní predikítovy symbol. Uvazme tri realizace N, Z, Q jazyka L s nosici N, Z, Q (mnoziny porozených, celých a racionalních císel), ktere interpretují symbol < jako standardní ostré usporadaní na príslusne mnozine císel. Dejte príklad uzavrene formule y predikítoveho poctu jazyka L takove, ze
a) N = y, Z = y, Q = y
b) N = y, Z = y, Q = y
c) N = y, Z = y, Q = y
£i0 Příklad 5.5 Mejme jazyk L = {•} s rovností, kde • je binírní funkcní symbol. Uvazme tri realizace Z, Q, R s nosici Z, Q, R (mnoziny celích, racionalních a realnych císel), ktere intepretují symbol • jako standardní nasobení císel. Dejte príklad uzavrene formule y predikatoveho poctu jazyka L takove, ze
a) Z = y, Q = y
b) Q = y, R = y
Příklad 5.6 Necht' y je formule predikítoveho poctu jazyka L takoví, ze x je jedina volna promenna ve y. Rozhodnete, zda pro libovolnou realizaci M jazyka L a libovolnou promennou y substituovatelnou za x ve y platíí
a) M = y — (y(x/y)),
b) M = y — 3y (y(x/y)).
5.2 Teorie
00 Příklad 5.7 Mejme jazyk L = 0 s rovností. Dejte príklad teorie T s jazykem L takove, ze vsechny její modely mají nekonečný nosic.
000 Příklad 5.8 Mejme jazyk L = {S} s rovností, kde S je unarní funkcní symbol. Dejte príklad splnitelné konečné teorie T s jazykem L takove, ze vsechny její modely mají nekonečný nosic.
£1$       Příklad 5.9 Mejme jazyk L = {S} s rovností, kde S je unírní funkcní symbol. Mejme teorii
T = {Vx Vy (S(x) = S(y) — x = y)}.
Rozhodnete a dokazte, zda platí nísledující tvrzení.
a) T = Vx —(S(x) = x)
b) Teorie T je bezesporna.
c) Teorie T je uíplnía.
1