15 Tolkning i modeller

Question 1

15.1 Modell

Answer 1

En modell M for et gitt førsteordens språk består av en ikke-tom mengde D, kalt domenet til modellen, og en funksjon som tolker alle ikke-logiske symboler på følgende måte:

• Hvis k er et konstantsymbol, er k^M ∈ D.
• Hvis f er et funksjonsymbol med aritet n, er f^M en funksjon fra Dⁿ til D.
• Hvis R er et relasjonssymbol med aritet n, er R^M en n-ær relasjon på D, det vil si en delmengde av Dⁿ.

Vi skriver |M| for domenet D til modellen M.

Question 2

15.2 Lukket term

Answer 2

En term kalles lukket hvis den ikke inneholder noen variabler.

Question 3

15.3 Tolkning av termer

Answer 3

La et førsteordens språk være gitt, og la M være en modell for dette språket. Da tolker vi en lukket term f(t₁, …, t_n) på følgende måte:

f(t₁, …, t_n)^M = f^M(t₁^M, …, t_n^M).

Question 4

15.4 Tolkning av en lukket atomær formel

Answer 4

Anta at M er en modell for et førsteordens språk, og la R(t₁, …, t_n) være en lukket atomær formel. Vi sier at formelen R(t₁, …, t_n​) er sann i M og skriver M |= R(t₁, …, t_n​) hvis følgende holder:

〈t₁^M, …, t_n^M〉 ∈ R^M

Question 5

15.5 Substitusjon i termer

Answer 5

La s og t være termer og x en variabel. Da er s[x/t] resultatet av å erstatte, eller substituere, alle forekomster av x i s med t.

Question 6

15.6 Substitusjon i formler

Answer 6

Hvis φ er en formel, t en term og x en variabel, er φ[x/t] resultatet av å erstatte, eller substituere, alle frie forekomster av x i φ med t.

Question 7

15.7 Tolkning av lukkede formler

Answer 7

Anta at M er en modell for et gitt førsteordens språk. Vi definerer rekursivt hva det vil si at en lukket formel φ er sann i M. Skrivemåten M |= φ betyr at φ er sann i modellen M. Basissteget, for atomære formler, er allerede definert. Det sier at M |= R(t₁, …, t_n) hvis 〈t₁^M, …, t_n^M〉 ∈ R^M. Her er rekursjonsstegene:

M |= ¬φ hvis det ikke er tilfellet at M |= φ
M |= φ ∧ ψ hvis M |= φ og M |= ψ
M |= φ ∨ ψ hvis M |= φ eller M |= ψ
M |= φ → ψ hvis M |= φ impliserer M |= ψ
M |= ∀xφ hvis M |= φ[x/ā] for alle a i |M|
M |= ∃xφ hvis M |= φ[x/ā] for minst én a i |M|

Når φ er sann i M, sier vi også at M er en modell for φ, at M gjør φ sann og at M oppfyller φ. Alt dette betyr det samme.

Question 8

15.8 Oppfyllbar, kontradiktorisk, gyldig og falsifiserbar

Answer 8

En lukket formel er oppfylbar hvis det finnes en modell som gjør den sann, ellers er den kontradiktorisk. En lukket formel er gyldig hvis alle modeller gjør den sanne, ellers er den falsifiserbar. En mengde lukkede formler er oppfyllbar/falsifiserbar hvis det finnes en modell som gjør alle formlene sanne/usanne.