Semantiek

Structuur

Een structuur D is een drietal < D, R, O > bestaande uit een niet-lege verzameling D (het domein), een verzameling R van relaties op D en een verzameling O van operaties op D.

Structuur: Bestaat uit een domein waarop mogelijk relaties of operaties gedefinieerd zijn. Een structuur kan zowel eindig als oneindig zijn.
Relationele structuur: Bestaat uit een domein D van objecten met daarop één of meer relaties.
Operationele structuur: Bestaat uit een domein D met daarop één of meer operaties (functies).

Interpretatiefunctie

Laat D = < D, R, O > een structuur zijn. Een interpretatiefunctie I kent aan elke individuele constante c uit predikaatlogische taal een speciaal object I(c) ∊ O toe,

Model: een paar (D, I ). Een (on)eindig model is een model met een (on)eindig domein.
Bedeling: Een bedeling b is een functie die aan elke variabele x een object b(x) ∊ D toekent.

Waardering van termen

Laat M = (D, I) een model zijn en b een bedeling. De semantische waarden van termen zijn als volgt inductief gedefinieerd:

1. V_M,b(x) = b(x), voor variabelen x
          (Lees: de interpretatie - waard, value - van variabele x in model M onder bedeling b is b(x))
2. V_M,b(a) = I(a), voor individuele constanten a.
3. V_M,b( f (t₁ , ... , t_k) ) = I (f )(V_M,b(t₁ ), ... , V_M,b(t_k) )

Bv.: V_M,b( f (a, x) ) = I(f )(I(a), b(x)) = +(0,1) = 1
Als de waarde 1 is, is het gebruikelijker om M, b ⊨ φ te schrijven dan om V_M,b(φ) = 1 te schrijven.

Waardering van formules

Laat M = (D, I) een model zijn en b een bedeling. M, b ⊨ φ wordt uitgesproken als 'φ is waar in M onder b'.
M, b ⊨ φ ⇔ V_M,b(φ) = 1 , en M, b ⊭ φ ⇔ V_M,b(φ) = 0.
De waarheidswaarden van formules ontstaan als volgt:

1. M, b ⊨ P(t₁ , ..., t_m ) ⇔ I (P)(V_M,b(t₁ ), ... , V_M,b(t_m) )
2. M, b ⊨ ¬ φ ⇔ ⊭ φ
3. M, b ⊨ ∃ x ⇔ er is een d ∊ D zodat M, b[x↦ d] ⊨ φ
4. M, b ⊨ ∀ x ⇔ voor alle d ∊ D geldt M, b[x↦ d] ⊨ φ