13 Førsteordens språk

Question 1

13.1 Førsteordens språk

Answer 1

Ethvert førsteordens språk består av følgende logiske symboler: de logiske konnektivene, ∧, ∨, →, kvantorene, ∀ og ∃ og en uendelig, tellbar mengde av variabler, samt parenteser og kommaer. Et førsteordens språk består også av følgende ikke-logiske symboler: en mengde av konstantsymboler, en mengde av funksjonssymboler og en mengde av relasjonssymboler. Mengdene av variabler, konstant-, funksjons- og relasjonssymboler må være disjunkte. Ethvert funksjons- og relasjonssymbol er assosiert med et naturlig tall, kalt ariteten til symbolet.

Question 2

13.2 Signatur

Answer 2

De ikke-logiske symbolene utgjør det som kalles en signatur. En signatur angis som et tuppel av tre mengder på følgende måte:

〈 a, b, c, … ; f, g, h, … ; R, S, T, … 〉

Her er konstant-, funksjons- og relasjonssymbolene adskilt med semikolon.

Question 3

13.3 Førsteordens termer

Answer 3

Anta at et førsteordens språk er gitt. Mengden av førsteordens termer, eller bare termer, er induktivt definert som den minste mengden slik at enhver variabel og konstant er en term, og hvis f er et funksjonssymbol med aritet n og t₁, …, t_n er termer, er f(t₁, …, t_n) en term.

Question 4

13.4 Atomær formel

Answer 4

Hvis R er et relasjonssymbol med aritet n > 0 og t₁, …, t_n er termer, så er R(t₁, …, t_n) en atomær formel. Hvis n = 0, er R en atomær formel.

Question 5

13.5 Førsteordens formler

Answer 5

Anta at førsteordens språk er gitt. Mengden av førsteordens formler, eller bare formler, er den minste mengden slik at:

• Alle atomære formler er formler.
• Hvis φ og ψ er formler, er ¬φ, (φ ∧ ψ), (φ ∨ ψ) og (φ → ψ) formler.
• Hvis φ er en formel og x er en variabel, er ∀xφ og ∃xφ formler.

Alle forekomster av en variabel x i φ sies å vøre bundet i formlene ∀xφ og ∃xφ og innenfor skopet til den gjeldende kvantoren.