Syntax a sémantika predikátové logiky

Syntax predikátové logiky

• Predikátová logika oproti výrokové pracuje s tvrzeními na jemnější úrovni
• Obecně umožňuje používat proměnné, relační symboly, funkční symboly kvantifikátory a predikáty

Definice

Jazyk PL obsahuje:

• proměnné $x,y,z,...,x_1,...$
• relační symboly $p,q,r,...,p_1,...$ (ke každému relačnímu symbolu $r$ je dáno nezáporné číslo $\sigma (r)$ nazývané arita symbolu $r$)
• funkční symboly $f,g,h,...,f_1,...$ (ke každému relačnímu symbolu $f$ je dáno nezáporné číslo $\sigma (f)$ nazývané arita symbolu $f$)
• symboly pro logické spojky: $\neg$ a $\Rightarrow$
• symbol pro univerzální kvantifikátor $\forall$
• pomocné symboly jako závorky a čárka

• Množina všech relačních symbolů jazyka se značí $R$
• Množina všech funkčních symbolů jazyka se značí $F$
• Je-li $r\in R$ a $\sigma (r)=n$, pak řekneme že $r$ je n-ární (ekvivalentně pro $f$ a $F$)
• Trojici $<R,F,\sigma >$ nazýváme jako typ jazyka (jednoznačně to určí jazyk)
  • Platí $R\cap F=\varnothing$ (musí být disjunktní)
• Základní jednotky jazyka jsou termy a formule

Definice

Term jazyka typu $<R,F,\sigma >$ je definován takto

• každá proměnná $x$ je term
• pokud $f\in F$ je n-ární a jsou $t_1,...,t_n$ termy, pak $f(t_1,...,t_n)$ je term

• Pro zápis používáme infixovou notaci
  • $xfy$ místo $f(x,y)$ … $2+3$ místo $+(2,3)$

Definice

Formule jazyka typu $<R,F,\sigma >$ je definován takto

• je-li $r\in R$ je n-ární a jsou $t_1,...,t_n$ termy, pak $r(t_1,...,t_n)$ je (atomická) formule
• jsou-li $\phi$ a $\psi$ formule, pak $\neg \phi ,(\phi \Rightarrow \psi )$ jsou také formule
• je-li $\phi$ formule a $x$ proměnná, pak $(\forall x)\phi$ je formule

• I v PL můžeme provádět důkazy strukturální indukcí jako ve VL

Sémantika predikátové logiky

• Přiřazuje význam (nemá smysl uvažovat $x+0$)

Definice

Struktura pro jazyk typu $<R,F,\sigma >$ je trojice $M=<M,R^M,F^M>$, která sestává z:

• neprázdné množiny $M$
• $R^M=\{r^M\subseteq M^n\mid r\in R,\sigma (r)=n\}$
• $F^M=\{f^M:M^n\to M\mid f\in F,\sigma (f)=n\}$

Pokud $\approx \in R$, pak $\approx$ interpretujeme jako relaci identity (${\approx }^M={\omega }_M=\{<u,u>\mid u\in M\}$)

• Jedná se tedy o systém relací a funkcí pro daný jazyk

M-ohodnocení

• Zobrazení přiřazující každé proměnné $x$ prvek $v(x)\in M$

Definice

Nechť $v$ je M-ohodnocení. Hodnota $\mid \mid t\mid |mi{d}_{M,v}$ termu $t$ v $M$ při $v$ je definována takto

1. $v(x)$ - je-li $t$ proměnná $x$
2. $f^M(\mid \mid t_1\mid {\mid }_{M,v},...,\mid \mid t_k\mid {\mid }_{M,v})$ - je-li tvaru $f(t_1,...,t_k)$

Definice

Pravdivostní hodnota $\Vert \phi {\Vert }_{M,v}$ formule $\phi$ při M-ohodncení $v$ je definována takto:

1. pro atomické forumule: $\Vert r(t_1,\dots ,t_n){\Vert }_{M,v}=\{\begin{array}{ll}1,& \text{je-li }⟨\Vert t_1{\Vert }_{M,v},\dots ,\Vert t_n{\Vert }_{M,v}⟩\in r^M\\ 0,& \text{jinak}\end{array}$
2. pro formule $(\phi )$ ve tvaru $(\neg \alpha )$ a $(\alpha \Rightarrow \beta )$: $\neg \alpha {\Vert }_{M,v}=\{\begin{array}{ll}1,& \text{pokud }\Vert \alpha {\Vert }_{M,v}=0\\ 0,& \text{pokud }\Vert \alpha {\Vert }_{M,v}=1\end{array}$ $\alpha \Rightarrow \beta {\Vert }_{M,v}=\{\begin{array}{ll}1,& \text{pokud }\Vert \alpha {\Vert }_{M,v}=0\text{ nebo }\Vert \beta {\Vert }_{M,v}=1\\ 0,& \text{jinak}\end{array}$
3. pro kvantifikovanou formuli $\phi$: $|(\forall x)\phi {\Vert }_{M,v}=\{\begin{array}{ll}1,& \text{pokud pro kazˇdeˊ }{v}^{\prime }\text{ takoveˊ, zˇe }{v}^{\prime }{=}_{x}v\text{ je }\Vert \phi {\Vert }_{M,v^{\prime }}=1\\ 0,& \text{jinak}\end{array}$

Je-li $\Vert \phi {\Vert }_{M,v}=1(\Vert \phi {\Vert }_{M,v}=0)$, říkáme, že formule $\phi$ je pravdivá (nepravdivá) ve struktuře $M$ při ohodnocení $v$.

• tautologie ve struktuře jestliže $\Vert \phi {\Vert }_{M,v}=1$ platí pro každé M-ohodnocení
• tautologie pokud je $\phi$ tautologií v každé struktuře $M$
  • Prostě pro libovolnou strukturu a libovolné ohodnocení musí být pravdivá

Definice

Teorie v jazyku PL typu $<R,F,\sigma >$ je libovolná množina $T$ formulí jazyka tohoto typu. Struktura $M$ jazyka typu $<R,F,\sigma >$ se nazývá model teorie $T$ (zápis: $M\models T$ či $\Vert T{\Vert }_M=1$), jestliže každá formule z $T$ je pravdivá v $M$.

• Teorie má stejný význam jako v přirozeném jazyce (“Nesouhlasím s tvojí teorií”). Přičemž teorií myslíme soubor tvrzení (v PL je to množina formulí)

Definice

Množina $S$ formulí sémanticky plyne z množiny $T$ formulí (píšeme $T\models S$; píšeme také $T\models \phi$), jestliže $S=\{\phi \}$, podobně když $T=\{\psi \}$, jestliže každý model $T$ je modelem $S$).

Slovy: Tedy $S$ sémanticky plyne z $T$ právě když v každé struktuře, ve které jsou pravdivé všechny formule z $T$, jsou také pravdivé všechny z $S$.

Věta

Platí, že $\phi$ je tautologie, právě když $\models \phi$.

Příklady