Ítéletlogika

Bevezetés

Formalizálás: adott problémát formális elemekkel megfogalmazni

• Az ég kék
• 2 az egy páros szám
• 5 az egy páros szám

Egyszerű, konkrét állítások, amelyek az egyedről mondanak valamit. Ilyeneket tudunk ítéletlogikában megfogalmazni.

• Minden nyúl rágcsáló
• Van olyan hal, ami kék

Egyszerű, konkrét állítások, amelyek az egyedekből álló csoportról mondanak valamit. Ilyeneket tudunk elsőrendű logikában megfogalmazni.

Ilyen típusú állításokhoz egyértelműen tudunk igazságértéket rendelni. (Hogy igaz, vag hamis, egyértelműen megállapítható)

Alapfogalmak

Halmazok direktszorzata

A és B tetszőleges halmazok direkt szorzata \(A \times B\) az összes olyan (a,b) párok halmaza, ahol \(a \in A\) és \(b \in B\)

Függvény

Legyen D és R (nem feltétlen különböző) halmazok.

Függvény fajtái

D legyen a domain, és R a range ebben az esetben

• $ D = U $ a függvény egyváltozós
• $ D = U^n (n > 1) $, n változós
• $ R = \N$, egészértékű

Rekurzió

Szerkezeti rekurzió

• Definíciós módszer
• Alaplépés + rekurzív lépés

Szerkezeti indukció

• Bizonyítási módszer rekurzívan definiált struktúrák tulajdonságáról
• Alaplépés + indukciós lépés
  • Speciális példa: teljes indukció
  • példa: logikai formulák bizonyítása

Következtetésforma

Egy $ F = {A_{1},A_{2},A_{3}}$ állításhalmazból egy A állításból álló (F,A) pár.

Helyes következtetésforma

Egy $ F = {A_{1},A_{2},A_{3}}$ állításhalmazból egy A állításból álló (F,A) pár helyes következtetésforma, ha létezik olyan eset, hogy az F állításhalmazban szereplő mindegyik állítás igaz és minden ilyen esetben az A állítás igaz.

Nyelvdefiníció

Nyelv: Alapfogalmak + Szintaxis + Szemantika

Ítéletlogika vagy állításlogika

Egyszerű állítás

Egy olyan kijelentés, amelynek tartalmából eldönthető, hogy igaz-e vagy sem. Egy állításhoz hozzárendeljük az igazságértékét

Összetett állítás

To be continued

Ítéletlogika ábécéje

• Ítéletváltozók \((V_{v}): X,Y,Z,\dots\)
• Unér logikai műveleti jel:
  • negáció \(\neg\)
• Binér logikai műveleti jelek:
  • konjukció \(\land\)
  • diszjunkció \(\lor\)
  • implikáció \(\supset\)
• Elválasztójelek ()
  • {},[] használható, csupán olvashatóság miatt, egyébként egyenértékű

Ítéletlogikai Formula

• (alaplépés) Minden ítéletváltozó ítéletlogikai formula (prímformula)
• (rekurzív lépés)
  • Ha A ítáletlogikai formula, akkor \(\neg A\) is igaz
  • Ha A és B ítéletlogikai formulák, akkor \(\left(A \circ B\right)\) is ítéletlogikai formula
  • "\(\circ\)" a három binér művelet bármelyike
• Minden ítéletlogikai formula az előző 2 szabályok véges sokszori alkalmazásával áll elő

Formulaszerkezet

• To be continued

Formulaszerkezet vizsgálata

Közvetlen részformula

• Prímformulának nincs közvetlen részformulája
• \(\neg A\) közvetlen részformulája A
• Az \(\left(A \circ B\right)\) közvetlen részformulája az A és a B (bal és jobboldali)

Szerkezeti fa

Egy adott formulához tartozó szerkezeti fa egy olyan fa, melynek gyökere a formula, minden csúcs gyerekei a csúcshoz tartozó formula közvetlen részformulái, a fa levelei pedig az ítéletváltozók.

Szintaxis fa

Egy adott formulához tartozó szintaxis fa egy olyan fa, melynek gyökere a formula fő logikai összekötöjele, minden csúcs gyerekei a csúcshoz tartozó formula közvetlen részformuláinak fő logikai összekötője, a fa levelei pedig az ítéletváltozók.

Zárójelelhagyás

A teljesen zárójelezett formulákat kevesebb zárójellel írhatjuk fel, ha bevezetjük a műveletek prioritását.

Prioritás csökkenően:

1.1-es ábra

A zárójelelhagyás célja egy formulából a legtöbb zárójel elhagyása a formula szerkezetének megtartása mellett

Lépések:

• A formula külső elhagyható (ha még van)
• Ha a kötési szabályoknak megfelel, akkor elhagyható (tehát a zárójel nélkül is balra kötne a formula)

Tetszőleges formuláknál

• Konjunkció tetszólegesen zárójelezhető
• Diszjunkció tetszólegesen zárójelezhető
• Implikációnál a zárójelés jobbról balra történik (bal oldalt nem elhagyható)

Láncformulák

• Literál
  • Ha X ítéletváltozü, akkor az X ls a nemX formulákat literálnak nevezzük.
  • Az ítéletváltozó a literál alapja
• Elemi konjunkció és Elemi diszjunkció
  • Különböző literálokon végrehajtott konjunkció és diszjunkció

Logikai összetettség

• Ha A ítéletváltozó, akkor l(A) = 0
• Ha \(l(\neg A) : l(A) = 1\)
• \(l(A \circ B): l(A) + l(B) +1\)

Lényegében az alkalmazott lépések száma (az ítéletváltozók és zárójelek nem befolyásolnak)

Logikai műveletek hatásköre

A formula részformulái közül a legkissebb logikai összetettségű, amelyben az adott logikai összekötőjel előfordul.

Logikai műveletek Fő összekötöjele

Az az összekötőjel, amelynek a hatásköre maga a formula

kb. az utolsónak elvégzendő művelet

Interpretáció

A formula interpretációja az a lépés, ahol az ítéletváltozók megkapják az értéküket, és így a formula elvégezhető

\(I = V_{v}\supset\{i,h\}\)

Az ítéletváltozók értékek megadhatók:

• Felsorolással
• Szemantikus fával

szemantius fánál a csúcsok az adott műveletet, a szárak pedig a változók

1.2-es ábra

Egy n-változós szemantikus fa egy n-szintű bináris fa, ahol a szintek a bázisbeli --To be continued...--

Igazságtábla

Egy n-változós formula igazságtáblájával megadott \(\{i,h\}^{n} \supset \{i,h\}\) n-változós logikai műveletet ír le.

Ebből következik a formula igazhalmaza és hamishalmaza.