13 Førstordens språk

Question 1

signatur

Answer 1

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

⟨ a, b, c, … ; f, g, h, … ; R, S, T, … ⟩

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

Question 2

førsteordens språk

Answer 2

Ethvert førsteordens språk (eng: first-order language) består av følgende logiske symboler (eng: logical symbols): de logiske konnektivene, kvantorene (eng: euqntifiers) ∀ og ∃, og en uendelig, tellbar mengde av variabler, samt paranteser og kommaer.

Et førsteordens språk består også av følgende ikke-logiske symboler (eng: non-logical symbols): en mengde av konstantsymboler (eng: constant symbols), en mengde av funksjonssymboler (eng: function symbols) og en mengde av relasjonssymboler (eng: relation symbols).

Mengdene av variabler, konstant-, funksjons- og relasjonssymboler må være disjunkte. Ethvert funksjons- og relasjonssymbol er assosiert med et naturlig tall, kalt ariteten (eng: arity) til symbolet.

Question 3

førsteordens termer

Answer 3

Anta at et førsteordens språk er gitt. Mengden av førsteordens termer (eng: first-order terms), 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 t1, …, tn er termer, er f(t1, …, tn) en term.

Question 4

atomær formel

Answer 4

Hvis R er et relasjonssymbol med aritet n > 0 og t1, …, tn er termer, så er R(t1, …, tn) en atomær formel (eng: atomær formula). Hvis n = 0, er R en atomær formel.

Question 5

førsteordens formler

Answer 5

Anta at førsteordens språk er gitt. Mengden av førsteordens formler (eng: first-order formulas), 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 (eng: bound) i formlene ∀xφ og ∃xφ og innenfor skopet (eng: scope) til den gjeldende kvantoren.