Definisjon: Førsteordens formler
Test deg selv
Gitt det enkle språket med signatur $\langle a; f,g; P,R \rangle$ der funksjonssymbolet $f$ og relasjonssymbolet $P$ har aritet 1 og funksjonssymbolet $g$ og relasjonssymbolet $R$ har aritet 2. Vi bruker her variablene $x$, $y$ og $z$.
Hvilke av disse formlene er sammensatte førsteordens formler i dette språket, altså førsteordens formler som ikke er atomære formler?
Dette er en atomær formel.
Dette er en sammensatt formel. Siden $P(x)$ er en formel og $x$ er en variabel, er $\forall x P(x)$ en formel.
Dette er en sammensatt formel. Siden $P \big( g(y, a) \big)$ er en formel og $y$ er en variabel, er $\exists y P\big(g(y, a)\big)$ en formel.
Dette er en sammensatt formel. Siden $P \big( f(y) \big)$ er en formel og $z$ er en variabel, er $\forall z P \big( f(y) \big)$ en formel.
Dette er en atomær formel.
Dette er en sammensatt formel. Siden $P(x)$ og $R(y, z)$ er formler, er $P(x) \lor R(y, z)$ en formel.
Dette er en sammensatt formel. $R(x, y)$ er en formel, så $\neg R(x, y)$ er en formel. Siden $\neg R(x, y)$ er en formel og $y$ er en variabel, så er $\forall y \neg R(x, y)$ en formel. Siden $\forall y \neg R(x, y)$ er en formel og $x$ er en variabel, så er $\forall x \forall y \neg R(x, y)$ en formel.
Dette er en sammensatt formel. Siden $P(z)$ er en formel og $z$ er en variabel, så er $\exists z P(z)$ en formel. Siden $P(x)$ er en formel, er $\neg P(x)$ en formel, og siden $R(x, a)$ og $\neg P(x)$ er formler, er $R(x, a) \rightarrow \neg P(x)$ en formel, og siden $R(x, a) \rightarrow \neg P(x)$ er en formel og $x$ er en variabel, er $\forall x \big( R(x, a) \rightarrow \neg P(x) \big)$ en formel. Og siden $\exists z P(z)$ og $\forall x \big( R(x, a) \rightarrow \neg P(x) \big)$ er formler, er $\exists z P(z) \lor \forall x \big( R(x, a) \rightarrow \neg P(x) \big)$ en formel.