4   Čtvrté cvičení
4.1 Véty o úplnosti a korektnosti
£0 Příklad 4.1 Mejme odvozovací systém s jedním schématem axiomu A1: p — p as pravidlem modus ponens. Necht' p je formule systemu L(—, —). Rozhodnete a dokazte, zda platí nasledující tvrzení.
a) Pokud h p, pak = p.
b) Pokud = p, pak h p.
4.2 Véta o kompaktnosti
$ Příklad 4.2 Mejme n G N a vyrokove promenne Xi,... , Xn. Pro slovo w G {0,1}n znacíme
symbolem vw valuaci takovou, ze pro 1 < i < n máme vw(Xi) = w(i), kde w(i) je i-ty znak slova w, a vw (Y) = 0 pro vsechna ostatní Y.
Necht' S je jazyk nad abecedou {0,1}. Zadejte formuli pn takovou, ze pro kazde slovo w G {0,1}n platí, ze pn je pravdiví pri valuaci vw, prave kdyz w je prefixem nejakeho slova z S.
Příklad 4.3 Necht' S je nekonecní jazyk nad abecedou {0,1}. Dokazte, ze existuje posloupnost &i,&2,&3,.. .takoví, ze kazde bi se nerovna bi+1, je prefixem bi+1 a je prefixem nejakeho prvku z
S.
00       Příklad 4.4 Necht' A, B jsou spocetne mnoziny a R C A x B je relace takova, ze pro kazde a G A je Ba = {b | (a, b) G R} konecní neprázdní soubor. Dokazte, ze pokud pro kazdou konečnou cast A' C A existuje injektivní funkce f a' : A' — B takova, ze f a C R (zde funkci /a' chapeme jako relaci), pak existuje take injektivní funkce f : A — B takoví, ze f C R. (Take zadaní muzete drápat jako bipartitní graf zadaní pomocí (A, B, R) s parovaním f ci /a' .)
4.3 Zúklady predikútové logiky
i^i Příklad 4.5 Mejme jazyk L = {•} s rovností, kde • je binarní funkcní symbol a realizaci M
jazyka L. Dejte príklad uzavřené formule p predikatoveho poctu jazyka L takove, ze M = p prave tehdy, kdyz
a) (M, •m) je pologrupa
b) (M, •m) je monoid
c) (M, •m) je grupa
$ Příklad 4.6 Mejme jazyk L = {^} s rovností, kde ~ je binarní predikatovy symbol a realizaci
M jazyka L. Dejte príklad uzavřené formule p predikatoveho poctu jazyka L takove, ze M = p prave tehdy, kdyz
a) ^M je relace ekvivalence na M
b) ^M je relace usporádíní na M
Příklad 4.7 Mejme jazyk L = {P, Q} bez rovnosti, kde P a Q jsou uránií predikatove symboly. Rozhodnete a dokazte, zda pro kazdou realizaci M jazyka L platí
a) M = Vx (P (x) <->■ Q(x)) — (Vx P (x) <->■ Vx Q(x))
b) M = (P (x) ^ Q(x)) — (Vx P (x) ^ Vx Q(x))
1^10 Příklad 4.8 Mejme jazyk L = {•} s rovností, kde • je binarní funkcní symboly. Mejme formuli p = Vx Vy (x • y = y • x). Rozhodnete a dokazte, zda
a) pro kazdou realizaci M jazyka L platí M = p,
b) existuje realizace M jazyka L takova, ze M = p.
Příklad 4.9 Rozhodnete, zda platí nasledující tvrzení: Mejme nejakí jazyk L, realizaci M jazyka L a formuli p predikítoveho poctu jazyka L. Pak
M = p prave tehdy, kdyz M = —p
1