Fromulák

Formulák igazságtáblája

Egy formula igazhalmaza azon \(\mathbb{I}\) interpretációk halmaza amelyre a helyettesítési érték igaz

Egy formula hamishalmaza azon \(\mathbb{I}\) interpretációk halmaza amelyre a helyettesítési érték hamis

Példában az X, Y, Z bázis esetén az igazsághalmaz {(i,i,i),(i,i,h),(i,h,i),(...)}

Implikáció iránya

$ X \supset Y$

$ X \rightarrow Y$

Igazságértékelés függvény

Egy formula igaz/hamishalmazának előállításához keressük a formula bázisának interpretációira azokat a feltételeket, amelyek biztosítják, hogy az igaz és hamishalmaznak eleme legyen

Halmazok előállításának eszköze a \(\varphi A^{\alpha}\) igazsságértékelés fügvénye (\(\alpha = i \lor h\)) amely A formula esetén az igazságtábla felírása nélkül megadja a közvetlen részformulán keresztül az A interpretációira vonatkozó $\varphi A^{i} \land \varphi A ^{h} $ értéket.

Definíció szerkezeti rekurzióvan

• Ha A prímformula (ítéletváltozó), akkor \(\varphi A^{i}\) feltételt pontosan azon \(\mathbb{i}\)
• A $ \varphi (\neg A)^{i} $ feltételek pontosan akkor teljesülnek

Igazságértékelés fügvény

$ \varphi (X \supset Y \land Z \lor \neg X)^{i} $

Formulák szemnatikus tulajdonságai

Interpretáció kielégít egy formulát

Egy I interpretáció kielégít egy B formulát

\(( I =_{0} B )\) i az I interpretációban. A formul´at kiel´eg´ıt˝o I interpretációt a formula modelljének is szokás nevezni.

Kielégíthetőség/kielégíthetelenség/tautológia formulákra

• Egy B formula kielégíthető ha legalább egy interpretációja kielégíti
• Egy B formula kielégíthetetlen, ha egyetlen interpretáció sem elégíti ki.
• Egy B formula tautológia (\(\models_0\)), ha minden interpretáció kielégíti. A tautologiát ítéletlogikai törvénynek is nevezik.

Kielégíthetőség kiterjeszthető formula halmazokra

Akkor elégíti ki ha legalább egy interpretációja kielégíti

Kielégíthetetlen, ha bármely interpretációban legalább egy formulája hamis (nincs olyan interpretáció, ami kielégítené)

Szemantikus következmény

Fogalom

Egy G formula szemantikus vagy taulogikus következménye az $ \digamma = {\digamma_{1},\digamma_{2},...,\digamma_{n}}$ formulahalmaznak

Ha \(\digamma\)- nek következménye \(G_{1} (\digamma \models_{0} G_{1})\) és \(\digamma\)- nek következménye \(G_{2} (\digamma \models_{0} G_{2})\) valamint \(\{G_{1},G_{2}\}\)-nek következménye \(A (\{G_{1},G_{2}\}\models_{0} A)\), akkor \(\digamma\)- nek következménye \(A(\digamma \models A)\).

Eldöntésprobléma

Definíció

Eldöntésproblémának nevezik a logikában annak eldöntését, hogy egy (F, G) pár a szemntikus következményfogalom szerint helyes gondolkodásforma-e.

Tétel

F-nek akkor és csak akkor következménye a G ha az $ \digamma \cup \neg G $ formulahalmaz vagy () formula kielégíthetelen.

Az egyik szemantikus eldöntésprobléma: tetszőleges ítéletlogikai formuláról eldőnteni, hogy kielégíthetelen-e.

A másik szemnatikus eldöntésprobléma: tetszőleges ítéletlogikai formulárol eldönteni hogy tautológia-e.

Taulogikus ekvivalens

Definíció - 1

Két vagy több formula igazségtébléja lehet azonos, ekkor azt mondjuk, hogy a formulák taulogikusan ekvivalensek.

Jelölése a \(\sim_{0}\)

Definíció - 2

A z A és B formulák tautologikusan ekvivalensek,
ha \(A \models_{0} B\) és \(B \models0 A\).

Ekkor \(\models_{0} (A \supset B) \land (B \supset A)\).

Átalakítási szabályok

• $ X \supset Y \sim_{0} \neg X \lor Y $
• $ \neg \neg X \sim_0 X $

De Morgan szabályok

• $ \neg (X \land Y) \sim_0 \neg X \lor \neg Y $
• $ \neg (X \lor Y) \sim_0 \neg X \land \neg Y $

Egyszerűsítési szabályok

• \((X \lor d) \land (\neg X \lor d) \sim_{0} d\)
• \((X \land k) \lor (\neg X \land k) \sim_{0} k\)

Következtetési módok

Következtetési módok - Definíció

Legyen a F feltételhalmazban szerelpő változók száma n. Ekkor a legszűkebb következmény az az \(\{i,h\}^{n} \rightarrow \{i,h\}\) leképezés, amely pontosan azokhoz az interpretációkhoz rendel i értéket, amelyek kielégítik F-et

Következtetési módok - Előrekövetkeztetés

Ismert F feltételhalmaz, keresük a lehetséges következményeit. Megkeressük F legszűkebb következményét R-t.
Következmény az amire igaz: \(R \supset G\) tautologia azaz R igazhalmaz része G igazhalamzának.

Következtetési módok - Visszakövetkeztetés

A következményformula ismeretében döntjük el hogy valamilyen következmény fent áll-e.
B pontosan akkor következménye F-nek ha minden olyan interpretációban, ahol B hamos, az F kielégíthetetlen.

Formalizálás