Nulladrendű logika

Szintaxis ¹

A leírott kifejezés helyességét határozza meg.

Jelkészlet

• betűk (ítéletváltozók) - atomok
• I(gaz), H(amis) (konstansok) - atomok
• $\neg ,\vee ,\wedge ,⟹$ - műveleti szimbólumok
• zárójelek

Formulaképzés

• minden atom formula Például: $\alpha ,\beta$ formula, akkor $\neg \alpha$, $\alpha ⟹\beta$… is formulák
• az itéletváltozók és műveleti szimbólumok alkalmazásával összetett formulákat tudunk képezni (magyar betűkkel jelöljük az atomi formukákat, görög betűkkel az összetett formulákkal)

Szemantika ¹

A helyes kifejezés jelentését határozza meg.

Interpretáció ²

Egy függvény változóihoz hozzárendeljük a lehetséges igazságértékek valamelyikét.

• $n$ változó esetén a lehetőségek száma: $n^2$

Modell

Olyan [[Nulladrendű logika#Interpretáció [ 2]|interpretáció]], amiben a formula igaz.

Tautológia

Minden interpretációban igaz.

Kontradikció

Ellentmondás, a tautológia ellenpárja. Minden interpretációban hamis.

Logikai műveletek

Konjunkció - metszet - és

Jele: $\wedge$

$A$	$B$	$A\wedge B$
0	0	0
1	0	0
0	1	0
1	1	1

Diszjunkció - unió - vagy

Jele: $\vee$

$A$	$B$	$A\vee B$
0	0	0
1	0	1
0	1	1
1	1	1

Komplementer

Jele: $\neg$

$A$	$\neg A$
0	1
1	0

Implikáció

Jele: $⟹$

$A$	$B$	$A⟹B$
0	0	1
0	1	1
1	0	0
1	1	1

Ekvivalencia

Jele: $\equiv$

$A$	$B$	$A\equiv B$
0	0	1
1	0	0
0	1	0
1	1	1

Formulák ekvivalenciája

Két formula ekvivalens amennyibe az igazságértékük minden interpretációban megegyezik.

Formalizálás

A formalizálás során a kijelentéseket matematikai nyelvre fogalmazzuk meg.

Normálformák

Az adott műveleteket úgy alakítjuk át, hogy azokat adott sorrendben végezzük el.

Diszjunktív normálforma

Konjunktív normálforma

Utoljára éselünk. Ehhez a következő átalakításokra lesz szükségünk:

• $A\oplus B$: $(A\vee B)\wedge (\neg A\vee \neg B)$
• $A\equiv B$: $(A⟹B)\wedge (B⟹A)$
• $A⟹B$: $\neg A\vee B$
• $A\vee (B\wedge C)$: $(A\vee B)\wedge (A\vee C)$

Klóz

Konjunktív és diszjunktív normálformák esetén is amiket összeéselünk (konjunktív normálformák esetén), vagy összevagyolunk (diszjunktív normálforma esetén) klózoknak hívunk.

Rezolúció

Rezolúciót akkor használunk, amikor azt szeretnénk belátni, hogy egy kifejezés minden interpretációban igaz, vagyis tautológia. Ilyenkor a kifejezés megfordítására próbálunk igaz példát hozni, indirekt bizonyítást alkalmazunk. Mivel a tautológia megfordítása a kontradikció, amennyiben az eredeti állításunk igaz, nem fogunk tudni modellt találni a megfordítására.

Gyakorlati lépések

1. Formalizáció
2. Premisszák (feltételek) felírása egymás alá
3. Következmény tagadása
4. Tagadott következmény konjunktív normálformára hozása
5. Klózok egymás alá írása
6. Kiejtegetés
7. Üres klóz

Következmény

Jele: $\models$

• Kontradikció következménye bármi
• Tautológia következménye tautológia $\alpha \models \beta \iff \alpha ⟹\beta \equiv 1\iff \alpha \wedge \neg \beta \equiv 0$

Következtetési sémák bizonyítása

Modus Ponens

$A$	$B$	$A⟹B$
0	0	1
1	0	0
0	1	0
1	1	1
A negyedik sorban igazak a feltételek, itt igaz a következmény is.

Modus Tollens

$A$	$B$	$A⟹B$	$\neg A$	$\neg B$
0	0	1	1	1
1	0	0	0	1
0	1	0	1	0
1	1	1	0	0
Az első sorban igazak a feltételek, itt igaz a következmény is.

Diszjunktív szillogizmus

$A$	$B$	$A\vee B$	$\neg A$
0	0	0	1
0	1	1	1
1	0	1	0
1	1	1	0
A második sorban igazak a feltételek, itt igaz a következmény is.

Hipotetikus szillogizmus

$A$	$B$	$C$	$A⟹B$	$B⟹C$	$A⟹C$
0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	0	1	1
1	0	1	0	1	1
1	1	0	1	0	0
1	1	1	1	1	1
Minden sorban amiben a feltételek igazak igaz a következmény is.

Feladatok

• Lineáris Algebra Feladatgyűjtemény 11. oldal.
• 06 Gyakorlat feladatsor
• 07-08 Gyakorlat feladatsor
• 09 Gyakorlat feladatsor

Megoldások

• 06 Gyakorlat feladatsor megoldás
• 07-08 Gyakorlat feladatsor megoldás
• 09 Gyakorlat feladatsor megoldás

Hasznos dokumentumok

• Matematikai Logika.pdf

Footnotes

1. Diszkrét Matematika tankönyv: 32. oldal ↩ ↩²

2. Diszkrét Matematika tankönyv: 33. oldal ↩