1) Uvedte zneni vety o kompaktnosti. (viz skripta)
2) Syntakticky oduvednete,
, kde
je generalni uzaver
. Vysvetlete, co je generalni uzaver.
(Jedna se o formuli po
-"okvantifikani" vsech volnych promennych puvodni formule. Implikace
: pravidlo modus ponens; Implikace
: axiom substituce, konkr.
)
3) Vhodnym protiprikladem dokazte
. Jakou vetu k tomu vyuzivate?
(Veta o koreknosti. Kontrabeispiel:
, kde P, R jsou relacni unarni symboly a
a navic
. Pak
, neboli
, tedy tvrzeni neni dokazatelne.)
1) Uvedte zneni vety o kompaktnosti. (viz skripta)
2) Syntakticky oduvednete, [latex]T\vdash\varphi\Leftrightarrow T\vdash\varphi'[/latex], kde [latex]\varphi'[/latex] je generalni uzaver [latex]\varphi[/latex]. Vysvetlete, co je generalni uzaver.
(Jedna se o formuli po [latex]\forall[/latex]-"okvantifikani" vsech volnych promennych puvodni formule. Implikace [latex]\Rightarrow[/latex]: pravidlo modus ponens; Implikace [latex]\Leftarrow[/latex]: axiom substituce, konkr. [latex](\forall x)\varphi\rightarrow\varphi(x/x)[/latex])
3) Vhodnym protiprikladem dokazte [latex]
vdash (\varphi\rightarrow(\forall x)\psi) \rightarrow (\forall x)(\varphi\rightarrow\psi)[/latex]. Jakou vetu k tomu vyuzivate?
(Veta o koreknosti. Kontrabeispiel: [latex]\mathcal{A} = <A, P^{\mathcal{A}}, R^{\mathcal{A}}>[/latex], kde P, R jsou relacni unarni symboly a [latex]P^{\mathcal{A}}
subseteq R^{\mathcal{A}[/latex] a navic [latex]\exists a\in A\setminus P^{\mathcal{A}}[/latex]. Pak [latex]\mathcal{A}\models (P^{\mathcal{A}}(x) \rightarrow(\forall x)R^{\mathcal{A}}(x))[a] \; \& \; \mathcal{A}
ot\models(\forall x)(P^{\mathcal{A}}(x)\rightarrow R^{\mathcal{A}}(x))[/latex], neboli [latex]\mathcal{A}
ot\models (P^{\mathcal{A}}(x) \rightarrow(\forall x)R^{\mathcal{A}}(x)) \rightarrow (\forall x)(P^{\mathcal{A}}(x)\rightarrow R^{\mathcal{A}}(x))[/latex], tedy tvrzeni neni dokazatelne.)