2. Logika Flashcards
kijelentés/állítás
A klasszikus logikában kijelentésnek vagy állításnak nevezünk egy nyelvtanilag kijelentő mondatot, melynek tartalmáról eldönthető, hogy igaz vagy hamis.
Feltesszük, hogy minden állítás vagy igaz vagy hamis, továbbá azt is, hogy egy állítás egyszerre nem lehet igaz is és hamis is.
logikai érték
Ha egy A állítás igaz, akkor azt mondjuk, hogy a logikai értéke igaz, ha A hamis, akkor a logikai értéke hamis. Az A állítás logikai értékének a jele |A|, az igaz logikai értékei i-vel vagy 1-gyel, a hamis értéket h-val vagy 0-val jelöljük.
Tagadás
A tagadás egy egyváltozós logikai művelet, mely egy A állításhoz a ¬A-val jelölt tagadását rendeli hozzá. Az A állítás tagadásának a logikai értéke igaz, ha A logikai értéke hamis, és hamis, ha A logikai értéke igaz.
Tetszőleget A állítás esetén |A| = |¬¬A|.
Logikai és
A konjunkció egy kétváltozós művelet, amelyet a ∧ jelöl. Az A ∧ B kijelentés logikai értéke pontosan akkor igaz, ha az A, illetve a B állítások mindegyike igaz.
Logikai vagy
A diszjunkció egy kétváltozós logikai művelet, amelyet a ∨ jelöl. Az A ∨ B kijelentés logikai értéke pontosan akkor igaz, ha A és B állítások közül legalább az egyik igaz.
Implikáció
Az implikáció olyan kétváltozós logikai művelet, melyet → jelöl. Az A → B kijelentést „ha A, akkor B” módon fogalmazzuk meg. Az A → B kijelentés logikai értéke hamis, ha A logikai értéke igaz, B logikai értéke hamis, minden más esetben A → B logikai értéke igaz.
Ekvivalencia
Az ekvivalencia olyan kétváltozós logikai művelet, melyet ↔ jelöl. Az A ↔ B kijelentést „A akkor és csak akkor, ha B” módon fogalmazzuk meg. Az A ↔ B kijelentés logikai értéke pontosan akkor igaz, ha A és B logikai értéke megegyezik. Az A ↔ B kijelentés az (A→B) ∧ ( B→A) kijelentés rövidítése.
Logikai műveletek tulajdonságai
ellentmondásmentesség
harmadik kizárás elve
De-Morgan azonosságok
Ellentmondásmentesség
Egy állítás nem lehet egyszerre igaz is és hamis is. |A ∧ ¬A|=h
Harmadik kizárás elv
Ha egy A kijelentés nem igaz, akkor A hamis. |A ∨ ¬A|=i
De-Mordan azonosságok
|¬(A ∨ B)| = |¬A ∧ ¬B|
|¬(A ∧ B)| = |¬A ∨ ¬B|
Kijelentéslogikai formulák
Kijelentéslogikai formuláknak nevezzük a kijelentésváltozókból, műveleti jelekből és zárójelpárokból álló véges hosszú sorozatot, mely előállítható a következő két szabály véges sokszori alkalmazásával:
- Minden kijelentésváltozó formula.
- Ha F és G formulák, akkor ¬(F), (F) ∧ (G), (F) ∨ (G),(F) → (G), (F) ↔ (G) is formulák.
Formalizálás (kijelentéslogika)
A kijelentéslogika segítségével az állítások igazságértékeit matematikai formalizálással meg tudjuk adni. A formalizálásra azért van szükség, mert a természetes nyelvben többértelműség is előfordulhat, így nehéz az érvek helyességét megállapítani.
Diszjunktív normálforma
Egy F formulát diszjunktív normálformának nevezünk, ha olyan konjunkciók diszjunkciója, melyben minden konjunkcióban a változók mindegyike legfeljebb egyszer fordul elő (negálatlanul, vagy negáltan). Ha egy F diszjunktív normálformulában minden konjunkcióban minden változó pontosan egyszer fordul elő, akkor F-t teljes diszjunktív normálformának nevezzük.
Konjunktív normálforma
Egy F formulát konjunktív normálformának nevezünk, ha olyan diszjunkciók konjunkciója, melyben minden diszjunkcióban a változók mindegyike legfeljebb egyszer fordul elő (negálatlanul, vagy negáltan).
Kijelentéslogikai következtetések
Legyenek F1, F2, F3, …,Fn és G formulák, melye összességében a p1, p2, …,pk kijelentésváltozók fordulnak elő. Azt mondjuk, hogy a G formula logikai következménye az F1, F2, …, Fn formuláknak, ha a p1, p2, …, pk kijelentésváltozók minden olyan interpretációja esetén, amikor az F1, F2, …, Fn formulák mindegyikének igaz a logikai értéke, a G formula logikai értéke is igaz.
Következtetési szabály, konklúzió
Az F1, F2, …, Fn formulák ebben az esetben a következtetési szabály, a G formula pedig a konklúzió.
Tautológia
Azonosan igaz logikai formula, azaz olyan állítás, amely saját értelménél fogva igaz.
Kontradikció
Egy formula kontradikció, vagyis logikailag ellentmondásos, ha minden interpretációban hamis.
Kielégíthetőség
Egy formula kielégíthető, ha létezik olyan interpretáció, amelynél igaz.
Predikátumlogika
A predikátumlogika az ítéletlogika kiegészítése. A predikátumlogika eszközeivel az állítások precízebben formalizálhatóak, logikaileg jobban vizsgálhatók. A változók a predikátumlogikában úgy funkcionálnak, mint a természetes nyelv névmásai. A természetes nyelvi mondatok predikátumlogikai elemzésében a névmásokat vagy névmási szerepet betöltő egyéb kifejezéseket rendszerint változókkal is adjuk vissza.
Predikátum
Egy tulajdonságot, kapcsolatot, relációt predikátumnak nevezünk. Amiről állítunk valamit, azt individuumnak nevezzük. A predikátumokat predikátumváltozókkal (nagybetűk), az individuumokat individuumváltozókkal (kisbetűk) jelöljük. Beszélhetünk egy- vagy többváltozós predikátumokról. A kijelentéseket tekinthetjük nullváltozós predikátumoknak.
Egzisztenciális kvantor
∃, azaz egzisztenciális kvantor: “létezik”, “van olyan”, “található”, “néhány”, “bizonyos”, “valamely”
Univerzális kvantor
∀, azaz univerzális kvantor: “bármely”, “minden”, “tetszőleges”, “az összes”
Predikátumlogikai formulák
- Egy atomi formula a predikátumlogika formulája.
- Ha A és B formula, akkor (A ∧ B), (A ∨ B), (A ⊃ B), ¬A, ¬B is predikátumlogikai formulák.
- Ha A formula, és x individuumváltozó, akkor ∀xA, ∃xA is predikátumlogikai formulák.
Más jelsorozatok nem formulák a predikátumlogikában.
Interpretáció
Predikátumlogikai formula interpretációján azt értjük, hogy helyettesítjük a benne szereplő predikátumváltozókat konkrét predikátumokkal, az individuumneveket konkrét individuumokkal.
Formalizálás
A formalizálás során a nyelvi kijelentéseket matematikai logikai formulákra fordítjuk.
Predikátumlogika tagadás
Predikátumlogikában a tagadás esetén a következő logikai ekvivalenciák teljesülnek:
¬ ((∀x) F) ≡ (∃x) (¬F)
¬ ((∃x) F) ≡ (∀x) (¬F)