Řešení příkladu 4.7 a) ze sady na 4. cvičeních
Zadání
Mejme jazyk L = {P, Q} bez rovnosti, kde P a Q jsou unární predikátové symboly. Rozhodněte a dokaZte, zda pro kaZdou realizaci M jazyka L platí
M = Vx (P (x) — Q(x)) — (Vx P (x) — Vx Q(x))
Řešení
Platí. Mejme libovolnou realizaci M a ohodnocení e takove, ze M = Vx (P(x) — Q(x)) [e]. Pro kazde a G M tedy platí M = P (x) — Q(x) [e(x/a)]. Tedy pro kazde a G M platí e[x/a](x) G PM, prave kdyz e[x/a](x) G QM, a tedy platí a G PM, prave kdyz a G QM (protoze e[x/a](x) je a).
Predpokladejme, ze M = Vx P (x) [e]. Tedy obdobnou argumentací jako vySe dostávame, ze pro vsechna a G M platí a G PM. Pak pro vsechna a G M take platí a G QM, tedy M = Vx Q(x) [e]. Ze symetrie plyne i opacna implikace, tedy celkove dostaváme M = (Vx P (x) —
Vx Q(x)) [e].
Zcela formální řešení
Pozn.: takto formální resení nejsou pozadována u zkousky, zde je uvedeno pouze pro ukazku, jak by bylo mozne postupovat. U zkousky skutecne plne dostacuje resení uvedene váse.
Mejme libovolnou realizaci M a libovolne ohodnocení e. Vyraz
M = Vx (P (x) — Q(x)) — (Vx P (x) — Vx Q(x)) [e]. z definice platí pokud
M = Vx (P(x) — Q(x)) [e] nebo M = Vx P (x) — Vx Q (x) [e]
Predpokláadejme, ze
M = Vx (P(x) — Q(x)) [e], pot rebujeme dokáazat, ze
M = Vx P(x) — Vx Q(x) [e]
coz dle definice platí, pokud
M = Vx P(x)[e],   práave kdyz  M = Vx Q(x) [e]. Úpravou predpokladu dle definice mame
M = (P(x) — Q(x)) [e(x/a)]   pro vsechna a G M, a tedy pro kazdáe a G M platáí
M= P (x) [e(x/a)],   práve kdyz   M= Q(x) [e(x/a)]. (1) Nyní muzeme dokázat pozadovanou ekvivalenci. Predpokládejme její levou stranu, tedy, ze platí
M = Vx P(x) [e],
to je z definice prave kdyz
M = P(x) [e(x/a)] pro v sechna a G M, coz s pomocáí tvrzenáí (1) platáí, práave kdyz
M = Q(x) [e(x/a)] pro vsechna a G M, coz je z definice prave kdyz
M = VxQ(x) [e].
Dostali jsme pravou stranu dokazovane ekvivalence. Celkove tedy pro libovolne e platí M = Vx (P (x) — Q(x)) — (Vx P (x) — Vx Q(x)) [e].
Protoze jsme zvolili e libovolne (platáí to pro kazdáe e), dostáavaáme
M = Vx (P (x) — Q(x)) — (Vx P (x) — Vx Q(x)).