Az informatika logikai alapjaikimaradt

Modell, kielégíthetőség, érvényesség

Mikor modellje egy interpretáció egy formulának vagy formulahalmaznak, mi a kielégíthető, kielégíthetetlen, érvényes és cáfolható formula, és hogyan viselkednek a formulahalmazok.

Forrás: eloadas03-2026.pdf, eloadas04-2026.pdf

Modell

Definíció

Legyen adott egy $L^{(1)}$ nyelv és egy $\langle U, \varrho \rangle$ interpretáció.

$\langle U, \varrho \rangle$ az $A$ formula modellje, ha $|A|^{\langle U, \varrho \rangle} = 1$ .
$\langle U, \varrho \rangle$ a $\Gamma$ formulahalmaz modellje, ha $\Gamma$ minden elemére $|A|^{\langle U, \varrho \rangle} = 1$ .

Ítéletlogikában egy modell egyszerűen az igazságtábla egy olyan sora, ahol a formula 1.

A négy fogalom

Definíció

Kielégíthető: van modellje (lehet igaz).
Kielégíthetetlen: nincs modellje, minden interpretációban hamis. Más néven ellentmondás.
Érvényes: minden interpretációban igaz. Más néven logikai törvény vagy tautológia. Jele: $\models A$ .
Cáfolható: van olyan interpretáció, amelyben hamis.

Minden formula a következő három csoport egyikébe esik:

érvényes	kielégíthető és cáfolható	kielégíthetetlen
mindig 1	néha 1, néha 0	mindig 0
$p \vee \neg p$	$p \supset q$	$p \wedge \neg p$

Az első kettő együtt a kielégíthető formulák, az utolsó kettő együtt a cáfolható formulák. Tehát minden érvényes formula kielégíthető, de fordítva nem.

Melyik igaz? Ha A nem érvényes, akkor…

A pontosan akkor érvényes, ha ¬A …

Formulahalmazok

Egy $\Gamma$ formulahalmaz kielégíthető, ha van közös modellje: egy interpretáció, amelyben minden eleme egyszerre igaz. Ha nincs, $\Gamma$ kielégíthetetlen: van benne logikai ellentmondás.

Tétel

Ha $\Gamma$ kielégíthető és $\Delta \subseteq \Gamma$ , akkor $\Delta$ is kielégíthető.

Bizonyítás. Legyen $\langle U, \varrho \rangle$ a $\Gamma$ egy modellje. Ha $A \in \Delta$ , akkor $A \in \Gamma$ is, tehát $|A|^{\langle U, \varrho \rangle} = 1$ . Így $\langle U, \varrho \rangle$ a $\Delta$ modellje is.

Tétel

Ha $\Gamma$ kielégíthetetlen és $\Gamma \subseteq \Delta$ , akkor $\Delta$ is kielégíthetetlen.

Bizonyítás. Indirekt: ha $\Delta$ kielégíthető volna, az előző tétel szerint a részhalmaza, $\Gamma$ is az lenne. Ellentmondás.

Figyelem

Elemenként nem lehet dönteni: a $\{p, \neg p\}$ halmaz minden eleme külön-külön kielégíthető, a halmaz mégsem. Egy formulahalmaz úgy viselkedik, mint az elemei konjunkciója: $\{A_1, \dots, A_n\}$ kielégíthető $\iff$ $A_1 \wedge \dots \wedge A_n$ kielégíthető.

Próbáld ki

Interaktív

Formulaműhely

Írj be egy ítéletlogikai formulát. ASCII is jó: ~ = ¬, & = ∧, | = ∨, -> = ⊃, <-> = ≡.

Példák:

teljesen zárójelezve: (((p ⊃ q) ∧ p) ∧ ¬q)
fő logikai jel: ∧
közvetlen részformulák: ((p ⊃ q) ∧ p) és ¬q
összetettség: 4

kielégíthetetlen (ellentmondás) minden sorban hamis

p	q	(p ⊃ q)	((p ⊃ q) ∧ p)	¬q
0	0	1	0	1
0	1	1	0	0
1	0	0	0	1
1	1	1	1	0