Lause- ja predikaatarvutuse valemid ning interpretatsioon

Lausearvutuse valemid ja reeglid

Lausearvutuse valemid on parajasti need avaldised, mida saab koostada järgmiste reeglite abil:

1. Iga lausemuutuja on lausearvutuse valem.
2. Kui F on lausearvutuse valem, siis ka ¬F on lausearvutuse valem.
3. Kui F ja G on lausearvutuse valemid, siis ka (F & G), (F ∨ G), (F ⇒ G) ja (F ⇔ G) on lausearvutuse valemid.

Valemi tõeväärtuse määramine

Olgu fikseeritud lausearvutuse valemis F leiduvate lausemuutujate mingi väärtustus. Kui F on lausemuutuja, siis valemi F tõeväärtuseks loetakse sellele muutujale antud tõeväärtus. Kui F sisaldab vähemalt ühte lausearvutuse tehet, siis valemi F tõeväärtus leitakse järgmiste reeglite abil:

1. Kui F = ¬G, siis F = 1 parajasti siis, kui G = 0.
2. Kui F = G & H, siis F = 1 parajasti siis, kui G = 1 ja H = 1.
3. Kui F = G ∨ H, siis F = 1 parajasti siis, kui G = 1 või H = 1.
4. Kui F = G ⇒ H, siis F = 1 parajasti siis, kui G = 0 või H = 1.
5. Kui F = G ⇔ H, siis F = 1 parajasti siis, kui (G = 1 ja H = 1) või (G = 0 ja H = 0).

Predikaadid, kvantorid ja mudelid

Predikaadi P : Mⁿ → {1, 0} tõesuspiirkonnaks nimetatakse hulka TP = {(a₁, ..., a_n) ∈ Mⁿ | P(a₁, ..., a_n) = 1}.

Üldisuskvantor on tõene parajasti siis, kui argumentide x₁, ..., x_i−1, x_i+1, ..., x_n väärtused on sellised, et hulga M iga elemendi m korral on P(x₁, ..., m, ..., x_n) tõene.

Tõene mudel ja valemite hulga mudel

Tõene mudel: valemi F mudeliks nimetatakse sellist interpretatsiooni α, milles valem F on tõene oma vabade muutujate kõikidel väärtustel. Sel juhul öeldakse ka, et valem F on tõene mudelis α.

Mudel: interpretatsiooni α nimetatakse valemite hulga {F₁, ..., F_n} mudeliks, kui see interpretatsioon on iga üksiku valemi mudel.

Interpretatsioon ja termi väärtus

Termi t väärtus t^α interpretatsioonis α indiviidmuutujate fikseeritud väärtustel leitakse järgmiste reeglite abil:

1. Kui t = x, kus x on indiviidmuutuja, siis t^α on muutuja x väärtus.
2. Kui t = c, kus c on konstantsümbol, siis t^α = c^α.
3. Kui t = f(t₁, ..., t_n), kus f on n-kohaline funktsionaalsümbol ja t₁, ..., t_n on termid, siis t^α = f^α(t₁^α, ..., t_n^α).

Signatuuri interpretatsiooni struktuur

Signatuuri σ = ⟨C; F; P⟩ interpretatsioon on järjestatud paar α = ⟨M^α; I^α⟩, kus M^α on mingi mittetühi hulk, mida nimetatakse põhihulgaks ehk interpretatsiooni kandjaks, ja I^α on interpreteeriv kujutus, mis teisendab:

1. iga konstantsümboli c ∈ C hulga M^α mingiks elemendiks c^α;
2. iga n-kohalise funktsionaalsümboli f ∈ F mingiks n-kohaliseks funktsiooniks f^α : (M^α)ⁿ → M^α;
3. iga n-kohalise predikaatsümboli P mingiks n-kohaliseks predikaadiks P^α : (M^α)ⁿ → {1, 0}.

Predikaatarvutuse valemid

Predikaatarvutuse valemid on parajasti need avaldised, mis on moodustatud järgmiste reeglite abil:

1. Kui P on n-kohaline predikaatsümbol ja t₁, ..., t_n on termid, siis P(t₁, ..., t_n) on predikaatarvutuse valem.
2. Kui F on predikaatarvutuse valem, siis ¬F on predikaatarvutuse valem.
3. Kui F ja G on predikaatarvutuse valemid, siis (F & G), (F ∨ G), (F ⇒ G) ja (F ⇔ G) on predikaatarvutuse valemid.
4. Kui x on indiviidmuutuja ja F on predikaatarvutuse valem, siis ∀x F ja ∃x F on predikaatarvutuse valemid.