====== Matematikai logika ====== A matematikai logika a matematika egyik fejezete, mely a matematikai rendszereket, bizonyításokat vizsgálja, pontosabban ezek számára nyújt alapot: következtetési sémákat, szabályokat, definíciókat ad. A naív halmazelmélet paradoxonainak felfedezése késztette a matematikusokat (ld. David Hilbert programja) arra, hogy a matematika minden területét axiómarendszerekre alapozzák, majd ezekből helyes következtetések sorával vezessék le az egyes állításokat. Ehhez a bizonyítások formalizálására volt szükség (formális nyelvek). A matematikai logika a //kétértékű// logikára épül. Másképp fogalmazva az //{igaz, hamis}// logikai halmaz és a rajta értelmezett logikai függvények, műveletek világában mozog. ===== Kijelentés ===== A kijelentés (ítélet vagy állítás) olyan jól meghatározott dologra vonatkozó kijelentő mondat, amely vagy igaz, vagy hamis, de nem lehet egyidőben igaz is és hamis is (ellentmondástalanság törvénye), illetve nem lehet ezektől különböző érték sem (kizárt harmadik törvénye). A matematikai logika ezen ágát ezért nevezzük **kétértékű logikának**. **Jelölés:** p, q, r, ..., x, y, z, ..., ezeket kijelentésváltozóknak nevezzük. A kijelentés **logikai értéke** igaz, vagy hamis lehet, de gyakran ezek helyett az 1 (//i// - igaz), illetve 0 (//h// - hamis) jeleket használjuk. A //p// kijelentés logikai értékét //|p|// jelöli. Néhány megjegyzés: * A kijelentés és a kijelentés logikai értéke fenti megadása nem matematikai definíció * Annak eldöntése, hogy egy kijelentő mondat kijelentés-e, és hogy ez esetben mi a logikai értéke, nem a logika feladata. Ez konkrét tapasztalattal, vagy valamely szaktudomány eredményeivel dönthető el, vagy bizonyos esetekben megállapodás kérdése. * A kijelentésekre vonatkozó alapvető törvényeket (ellentmondástalanság, illetve kizárt harmadik törvénye) Arisztotelész görög filozófus fogalmazta meg. * Léteznek az un. többértékű logikák is, ezekkel mi nem foglalkozunk. ===== Logikai műveletek ===== Kijelentésekből logikai műveletek segítségével újabb összetett kijelentéseket rakhatunk össze. A logikai műveletek tulajdonképpen egy- vagy többváltozós logikai (az //{igaz, hamis}// halmazon értelmezett) függvények. Könnyen belátható, hogy négy egyváltozós (konstans hamis, konstans igaz, identitás, [[#negáció]]) és 16 kétváltozós logikai művelet van. Ezek közül néhányat gyakran használunk, külön névvel és jelöléssel látjuk el. ==== Negáció ==== A //p// kijelentés negációja (tagadása) a "nem //p//" kijelentés, ami igaz, ha //p// hamis, és hamis, ha //p// igaz. **Jelölés:** overline{p}, vagy //¬p// **Megjegyzés:** |overline{p}| = 1 + |//p//| (mod 2) ==== Konjunkció ==== Konjunkció vagy logikai "és" művelet. A //p// és //q// kijelentések konjunkciója a "//p// és //q//" kijelentés, mely akkor, és csak akkor igaz, ha //p// és //q// is igaz. **Jelölés:** p logicaland q **Megjegyzés:** |p logicaland q| = |//p//|cdot|//q//| (mod 2) ==== Diszjunkció ==== Diszjunkció vagy logikai "vagy" művelet. A //p// és //q// kijelentések diszjunkciója a "//p// vagy //q//" kijelentés, mely akkor, és csak akkor igaz, ha //p// és //q// közül legalább az egyik igaz. (azaz akkor, és csak akkor hamis, ha //p// és //q// is hamis.) **Jelölés:** p logicalor q **Megjegyzés:** |p logicalor q| = |//p//| + |//q//| + |//p//|cdot|//q//| (mod 2) ==== Implikáció ==== Implikáció vagy következtetés. A //p// és //q// kijelentések implikációja a "//p//-ből következik //q//" kijelentés, mely pontosan akkor hamis, ha //p// igaz és //q// hamis. Olvashatjuk így is: "ha //p//, akkor //q//", "//p// elégséges feltétele //q//-nak" **Jelölés:** p right q **Megjegyzés:** |p right q| = 1 + |//p//| + |//p//|cdot|//q//| (mod 2) ==== Ekvivalencia ==== Ekvivalencia vagy egyenértékűség. A //p// és //q// kijelentések ekvivalenciája a "//p// egyenértékű //q//-val" kijelentés, mely pontosan akkor igaz, ha //p// és //q// egyszerre igaz, vagy hamis, tehát //|p|=|q|//, és hamis, ha //p// és //q// különböző értékű (egyik igaz, másik hamis). Olvashatjuk így is: "//p// akkor, és csak akkor, ha //q//", "//p// szükséges és elégséges feltétele //q//-nak". **Jelölés:** p leftright q **Megjegyzés:** |p leftright q| = |//p//| + |//q//| + 1 (mod 2) ==== Antivalencia ==== Antivalencia, kizáró vagy, XOR, Birkhoff-féle művelet. A //p// és //q// kijelentések antivalenciája a "//p// kizárja //q//-t" kijelentés, mely akkor igaz, ha //p// és //q// közül pontosan az egyik igaz. **Jelölés:** //p// ∇ //q// ==== Scheffer-féle művelet ==== Összeférhetetlenséget kifejező diszjunkció, Scheffer-művelet, összeférhetetlenség, NAND. A //p// és //q// kijelentések összeférhetetlensége a "//p// összeférhetetlen //q//-val" kijelentés, ami akkor és csak akkor igaz, ha //p// és //q// közül legfeljebb az egyik igaz. **Jelölés:** p | q ==== Web-féle művelet ==== Sem-sem művelet, Web-féle művelet, NOR. A //p// és //q// kijelentések "sem-sem" kapcsolata a "sem //p//, sem //q//" kijelentés, ami akkor és csak akkor igaz, ha //p// és //q// közül egyik sem igaz. **Jelölés:** p || q ==== Bool algebra ==== Az igazságértékek //{igaz, hamis}// halmaza a logikai és (logicaland, vagy (logicalor) valamint negáció műveletekkel [[matematika:algebra:bool_algebra| Bool algebrát]] alkot. ===== Műveleti tulajdonságok ===== Az alábbi műveleti szabályok könnyen bizonyíthatók egyszerű ellenőrzéssel (egy változó esetén két esetet, két változó esetén négy esetet kell ellenőriznünk), igazság-táblázattal. ==== Kettős tagadás elve ==== Ha //p// kijelentés, akkor delim{|}{overline{overline{p}}}{|}=delim{|}{p}{|}. ==== Asszociativitás ==== A diszjunkció és a konjunkció [[matematika:algebra:asszociatív]] művelet, azaz ha //p//, //q// és //r// tetszőleges kijelentés, akkor: delim{|}{(p logicaland q) logicaland r}{|} = delim{|}{p logicaland (q logicaland r)}{|}, illetve delim{|}{(p logicalor q) logicalor r}{|} = delim{|}{p logicalor (q logicalor r)}{|}. ==== Kommutativitás ==== A diszjunkció és a konjunkció [[matematika:algebra:kommutatív]] művelet, azaz ha //p//, és //q// tetszőleges kijelentés, akkor: delim{|}{p logicaland q}{|} = delim{|}{q logicaland p}{|}, illetve delim{|}{p logicalor q}{|} = delim{|}{q logicalor p}{|}. ==== Abszorbció ==== A diszjunkció és a konjunkció [[matematika:algebra:abszorbtív]] művelet egymásra nézve, azaz ha //p//, és //q// tetszőleges kijelentés, akkor: delim{|}{p logicaland (p logicalor q)}{|} = delim{|}{p}{|}, illetve delim{|}{p logicalor (p logicaland q)}{|} = delim{|}{p}{|}. ==== Idempotencia ==== A diszjunkció és a konjunkció [[matematika:algebra:idempotens]] művelet, azaz ha //p// tetszőleges kijelentés, akkor: delim{|}{p logicaland p}{|} = delim{|}{p}{|}, illetve delim{|}{p logicalor p}{|} = delim{|}{p}{|}. ==== Disztributivitás ==== A diszjunkció és a konjunkció [[matematika:algebra:disztributív]] művelet egymásra nézve, azaz ha //p//, //q// és //r// tetszőleges kijelentés, akkor: delim{|}{p logicaland (q logicalor r)}{|} = delim{|}{(p logicaland q) logicalor (p logicaland r)}{|}, illetve delim{|}{p logicalor (q logicaland r)}{|} = delim{|}{(p logicalor q) logicaland (p logicalor r)}{|}. ==== de Morgan azonosságok ==== delim{|}{overline{p logicalor q}}{|} = delim{|}{overline{p} logicaland overline{q}}{|}, illetve delim{|}{overline{p logicaland q}}{|} = delim{|}{overline{p} logicalor overline{q}}{|} ==== A negáció tulajdonságai ==== delim{|}{p logicalor overline{p}}{|} = 1 delim{|}{p logicaland overline{p}}{|} = 0 ==== Ekvivalencia és implikáció ==== delim{|}{p leftright q}{|} = delim{|}{(p right q) logicaland (q right p)}{|} delim{|}{p right q}{|} = delim{|}{overline{p} logicalor q}{|} ===== Kijelentéslogikai formulák ===== A kijelentéslogikai formulákban a következő szimbólumokat használhatjuk: - kijelentésváltozók jelei: //p//, //q//, //r//... - logikai műveletek jelei: ¬, logicalor, logicaland, right, leftright - zárójelpárok: (, ) Ezek után definiálhatjuk a kijelentéslogikai formula fogalmát: - A kijelentésváltozók formulák. - Ha //A// és //B// formulák, akkor ¬A, (A logicalor B), (A logicaland B), (A right B), (A leftright B) is formula. - Minden formula előáll véges sok lépésben az (1) és (2) segítségével. ==== Helyettesítés ==== **Helyettesítés**ről beszélünk, ha egy //A// formulában valamely //p// kijelentésváltozó vagy //R// részformula helyére egy //C// formulát írunk. ==== Szöveges interpretáció ==== Különböző kijelentéseknek lehet azonos szerkezete. Egy-egy ilyen kijelentést a szerkezetet leíró formula **szöveges interpretációjának** nevezzük. Például a következő kijelentések a (t logicalor s) right overline{d} formula szöveges interpretációi: * "Ha TV-t nézek vagy strandolok, akkor nem dolgozom." * "Ha egy szám osztható 4-gyel, vagy 6-tal, akkor nem páratlan." ==== Formula interpretációi ==== Ha egy formulában megadjuk a kijeletésváltozók logikai értékét, akkor ezt a formula egy **interpretáció**jának nevezzük. Egy //n// változós formulának 2n interpretációja van. Ha egy formulát minden interpretációja igazzá tesz, akkor azt **azonosan igaz formulának** vagy **tautológiá**nak nevezzük. Az //A// formula azonosan hamis vagy **kontradikció**, ha minden interpretációja hamissá teszi. Ha egy formulának van olyan interpretációja, ami igazzá teszi, akkor **kielégíthető**nek nevezzük, ellenkező esetben **kielégíthetetlen**nek. //A// pontosan akkor tautológia, ha negáltja kontradikció. ==== Kijelentéslogikai formulák ekvivalenciája ==== Az //A// és //B// formulák **egyenértékűek** vagy **ekvivalensek**, ha //A// <-> //B// tautológia, azaz az //A//-ban és //B//-ben szereplő összes kijelentésváltozó minden interpretációjára |//A//| = |//B//|. Ezt sokszor úgy mondjuk, hogy: * "//A// szükséges és elégséges feltétele //B//-nek" * "//A// akkor és csak akkor, ha //B//" * "//A// pontosan akkor, ha //B//" * "//A// és //B// ekvivalensek" **Jelölés:** //A// <=> //B// A formulák körében értelmezett <=> [[matematika:halmazok:reláció#ekvivalencia reláció]], azaz * reflexív (//A// <=> //A//) * szimmetrikus (//A// <=> //B//, akkor //B// <=> //A//) * tranzitív (//A <=> B//, //B// <=> //C//, akkor //A// <=> //C//) **Megjegyzés:** Az "//A// egyenértékű //B//-vel" (<=>) tehát egy a formulák halmazán értelmezett reláció, míg az implikáció (<->) egy kijelentéslogikai művelet, mely kijelentésekből, vagy formulákból újabb kijelentést, illetve formulát állít elő. Ha logikailag ekvivalens formulákban a kijelentésváltozókat tetszőleges formulákkal helyettesítjük, akkor ismét logikailag ekvivalens formulákhoz jutunk. ==== Kijelentéslogikai következtetések ==== A logikai következtetés egy vagy több feltételből, más néven **premisszá**ból, és egy állításból (következmény, vagy **konklúzió**) áll. Abban az esetben, ha egy premissza van, akkor azt mondjuk, hogy //A// formulából következik //B//, ha //A// -> //B// tautológia. **Jelölés:** //A// ⊨ //B//, esetleg //A// => //B// A kijelentéslogikai formulák körében értelmezett ⊨ reláció * reflexív * tranzitív * nem szimmetrikus (//A// ⊨ //B// esetén általában nem következik, hogy //B// ⊨ //A//) * //A// ⊨ //B// és //B// ⊨ //A//, akkor //A// <=> //B// ==== Következtetési sémák ==== * Leválasztási szabály (modus ponens): //A// -> //B//, //A// ⊨ //B// * Indirekt bizonyítás (modus tollens): //A// -> //B//, ¬//B// ⊨ ¬//A// * Lehetetlenre való visszavezetés (redukció ad abszurdum): //A// -> //B//, //A// -> ¬//B// ⊨ ¬//A// * Kontrapozíció: //A// -> //B// ⊨ ¬//B// -> ¬//A// * Diszjunktív szillogizmus (modus tollendo ponens): //A// logicalor //B//, ¬//B// ⊨ //A// * Láncszabály (feltételes szillogizmus): //A// -> //B//, //B// -> //C// ⊨ //A// -> //C// ==== Levezetések ==== Kijelentésloggikai levezetésnek, vagy dedukciónak nevezzük következtetési szabályok olyan rendszerét, melynek alapján eldöntehető, hogy teljesül-e az //A1//, ..., //An// ⊨ //B//. Pontosabban: Legyenek //A1//, ..., //An//, //B// (n>=0) adott kijelentéslogikai formulák és legyen //T// tautológiák egy halmaza. Az //E1//, //E2//, ..., //Ek// formulasorozatot a //B// formulának az //A1//, ..., //An// premisszákból a //T// segítségével történő **levezetésének** nevezzük, ha * //Ek// = //B// * minden i in \{1, 2, ..., k\} esetén * //Ei// egy premissza, vagy * //Ei// valamely //T//-beli tautilógiából helyettesítéssel keletkezik, vagy * vannak az //E1//, //E2//, ..., //Ek// sorozatban az //Ei//-t megelőző formulák, hogy (E_{i_1} logicaland E_{i_2} logicaland cdots logicaland E_{i_s}) right E_i egy //T//-beli tautológiából helyettesítéssel áll elő. Belátható (teljes indukcióval), hogy ha //B// kijelentéslogikai formula levezethető //A1//,...,//An// premisszákból //T// segítségével, akkor //A1//, ..., //An// ⊨ //B//, tehát //B// következménye //A1//, ..., //An//-nek. G. Frege (német matematikus) bizonyította, hogy megadható tautológiák olyan //T// halmaza, hogy tetszőleges formulák esetén, ha //A1//, ..., //An// ⊨ //B//, akkor //B// levezethető az //A1//, ..., //An// premisszákból //T// segítségével. J. Lukasiewicz (lengyel matematikus) adott meg egy ilyen, alkalmas //T// halmazt: * //A// -> (//B// -> //A//) * (//A// -> (//B// -> //C//)) -> ( (//A// ->//B//) -> (//A// -> //C//)) * (¬//B// -> ¬//A//) -> (//A// -> //B//) * //A//, //A// -> //B// => //B// (Modus Ponens) ===== Normálformák ===== A normálformák olyan szerepet töltenek be a kijelentéslogikában, mint a polinomok az algebrában. A polinomoknál megszokot összeadás és szorzás helyett itt konjunkciót és diszjunkciót használunk. ==== Teljes diszjunktív normál forma ==== Minden kijelentéslogikai formula felírható konjunkciók diszjunkciójaként. Az ilyen alakot **diszjunktív normál formának** nevezzük. Ha a konjunkciós tagokban minden kijelentésváltozó szerepel (negálva vagy negálatlanul), akkor **teljes diszjunktív normál formáról** beszélünk. **Példa:** (p logicaland q logicaland ¬r) logicalor (p logicaland ¬q logicaland r) logicalor (¬p logicaland q logicaland r) ==== Teljes konjunktív normál forma ==== Minden kijelentéslogikai formula felírható diszjunkciók konjunkciójaként. Az ilyen alakot **konjunktív normál formának** nevezzük. Ha a diszjunkciós tagokban minden kijelentésváltozó szerepel (negálva vagy negálatlanul), akkor **teljes konjunktív normál formáról** beszélünk. **Példa:** (¬p logicalor ¬q logicalor r) logicaland (¬p logicalor q logicalor ¬r) logicaland (p logicalor ¬q logicalor ¬r) ===== Predikátum ===== Predikátumoknak nevezzük az olyan kijelentő mondatokat, amelyek egy vagy több változótól függenek és amelyek ezen változók minden megengedett rögzített értékeire egy kijelentést adnak. A változok valamilyen halmaz elemei, például számok lehetnek. **Jelölés:** P(x), P(x,y), P(x_1,x_2, ..., x_n) ahol //x//, //y//, //x1//, ..., //xn// **individumváltozók** Ha egy predikátum nulla változós, akkor az [[#kijelentés]]. Az egy és több változós predikátumokat szokás **nyitott mondat**oknak is nevezni. ==== Predikátumok és kijelentések ==== Tekintsük az alábbi következtetést: //A1//: A paralelogrammák átlói felezik egymást\\ //A2//: A négyzet paralelogramma\\ ---- //B//: A négyzet átlói felezik egymást. Ha fel akarjuk írni ennek a következtetésnek a sémáját, akkor azt tapasztaljuk, hogy egyiket sem tudjuk felbontani kijelentéslogikai műveletekkel, így a séma a következő: //A1//: //p//\\ //A2//: //q//\\ ---- //B//: //r// Ebben a sémában //p//, //q//, //r// egymástól független kijelentések, így az ezek közti összefüggést nem képes kifejezni a séma, holott a következtetést jogosnak érezzük. A kijelentéslogika ugyanis nem alkalmas az ilyen és ehhez hasonló következtetések vizsgálatára, csak az állítások **durvaszerkezetét** tárja fel. Nézzük ugyanezt predikátumlogikai formulákkal: Vegyük a következő predikátumokat a sikbeli négyszögek halmazán:\\ //P(x)//: //x// paralelogramma\\ //F(x)//: //x// átlói felezik egymást\\ //N(x)//: //x// négyzet Ekkor a fenti következtetés sémája: //A1//: forall x(P(x) right F(x))\\ //A2//: forall x(N(x) right P(x))\\ ---- //B//: forall x(N(x) right F(x)) ==== Műveletek predikátumokkal ==== A kijelentésekre vonatkozó műveletek segítségével értelmezhetünk műveleteket predikátumok között is: * overline{P}(x_1, ..., x_n) = overline(P(x_1, ..., x_n)) * (P logicaland Q)(x_1, ..., x_n) = P(x_1, ..., x_n) logicaland Q(x_1, ..., x_n) * (P logicalor Q)(x_1, ..., x_n) = P(x_1, ..., x_n) logicalor Q(x_1, ..., x_n) * (P right Q)(x_1, ..., x_n) = P(x_1, ..., x_n) right Q(x_1, ..., x_n) * (P leftright Q)(x_1, ..., x_n) = P(x_1, ..., x_n) leftright Q(x_1, ..., x_n) Ha //P// és //Q// predikátumok és minden megengedett helyettesítés esetén P(x_1, ..., x_n) right Q(x_1, ..., x_n) igaz, akkor azt mondjuk, hogy //P//-ből **következik** //Q//. **Jelölés:** P doubleright Q Ha //P// és //Q// predikátumok és minden megengedett helyettesítés esetén P(x_1, ..., x_n) leftright Q(x_1, ..., x_n) igaz, akkor azt mondjuk, hogy //P// és //Q// **egyenértékű**ek, vagy **ekvivalens**ek. **Jelölés:** P doubleleftright Q ==== Predikátum igazsághalamaz ==== Az //n// változós A=A_1 * cdots * A_n halmazon értelmezett //P(x_1, ..., x_n)// predikátum **igazsághalmaza** azon (a_1, ..., a_n) in A elemek halmaza, melyekre //P// igaz. **Jelölés:** //I(P)// Minden predikátumot egyértelműen meghatároz az igazsághalmaza. A predikátumokkal végzett műveletek is átfogalmazhatók az igazsághalmazok segítségével: * I(overline{P}) = A backslash I(P) = overline{I(P)} * I(P logicaland Q) = I(P) inter I(Q) * I(P logicalor Q) = I(P) union I(Q) * I(P right Q) = (A backslash I(P)) union I(Q) * I(P leftright Q) = A backslash (I(P) Delta I(Q)) Továbbá P doubleright Q átfogalmazása I(P) subset I(Q), illetve P doubleleftright Q pontosan akkor teljesül, ha I(P) = I(Q). ===== Kvantorok ===== ==== Univerzális kvantor ==== A "minden //x//-re" kifejezést **univerzális kvantor**nak nevezzük. Jele: forall x. Ha //P// az //A// halmazon értelmezett predikátum, akkor forall x P(x) egy kijelentés, melynek értéke\\ delim{|}{forall x P(x)}{|} = delim{lbrace}{matrix{2}{1}{{1, ha minden a in A esetén delim{|}{P(a)}{|}=1} {0, ha van olyan a in A, melyre delim{|}{P(a)}{|}=0}}}{} ==== Egzisztenciális kvantor ==== A "van olyan //x//, melyre" kifejezést **egzisztenciális kvantor**nak nevezzük. Jele: exists x. Ha //P// az //A// halmazon értelmezett predikátum, akkor exists x P(x) egy kijelentés, melynek értéke\\ delim{|}{exists x P(x)}{|} = delim{lbrace}{matrix{2}{1}{{0, ha minden a in A esetén delim{|}{P(a)}{|}=0} {1, ha van olyan a in A, melyre delim{|}{P(a)}{|}=1 }}}{} ==== Műveletek kvantorokkal ==== * delim{|}{overline{forall x P(x)}}{|} = delim{|}{exists overline{P(x)}}{|} * delim{|}{overline{exists x P(x)}}{|} = delim{|}{forall overline{P(x)}}{|} * delim{|}{forall x P(x) logicaland forall x Q(x)}{|} = delim{|}{forall x (P(x) logicaland Q(x))}{|} * delim{|}{exists x P(x) logicalor exists x Q(x)}{|} = delim{|}{exists x(P(x) logicalor Q(x))}{|} * delim{|}{(forall x P(x) logicalor forall x Q(x)) doubleright (forall x (P(x) logicalor Q(x)))}{|} = 1 * delim{|}{(exists x(P(x) logicaland Q(x))) doubleright (exists x P(x) logicaland exists x Q(x))}{|} = 1 ===== Predikátumlogikai formulák ===== Predikátum változók a következő képp adhatók meg: - A kijelentésválltozók formulák - Ha //P// egy //n// változós predikátum és //x1//,...,//xn// individumváltozók, vagy individumnevek, akkor //P x1...xn// és //x1// ≡ //x2// formulák. - Ha //A// és //B// formulák, akkor ¬A, (A logicalor B), (A logicaland B), (A right B), (A leftright B) is formula. - Ha //A// formula és //x// egy individum változó, akkor forall x A és exists x A is formulák. - más jelsorozat nem formula Az ≡ ("azonosság") predikátum egy kitüntetett szerepű. kétváltozós predikátum. Észrevehető, hogy a 2. és 4. pontot elhagyva a [[#kijelentéslogikai formulák]] definíciójához jutunk. ===== Hivatkozások ===== [[http://www.ttk.pte.hu/matek/ltoth/A%20matematikai%20logika%20alapjai,%202005.pdf]]