Kijelentéslogika, normálformák
Ennek a témakörnek a képletei
Letöltöm az egész kurzus összes képletét:
LetöltömLetöltöm ennek a témakörnek a képleteit:
LetöltömVálogass kedvedre a témakör képletei között:
Univerzális kvantor
Az univerzális kvantor egy jelölése a "minden" kifejezésnek.
Jele: $\forall$
Egzisztenciális kvantor
Az egzisztenciális kvantor egy jelölése a "létezik" vagy "van olyan" kifejezésnek.
Jele: $\exists$
Logikai műveletek | Negáció
Az állítás negációja (vagy tagadása) egy egyváltozós művelet. Egy $A$ kijelentés negációja az a kijelentés, amely akkor igaz, ha $A$ hamis és akkor hamis, ha $A$ igaz.
Állítás
Az állítás (vagy kijelentés) olyan kijelentő mondat, amelyről egyértelműen eldönthetjük, hogy az igaz vagy hamis.
Logikai műveletek | Konjunkció
A konjunkció két állítás közti logikai művelet. Két kijelentés konjunkciója pontosan akkor igaz, ha mindkét kijelentés igaz, különben hamis.
Jele: $ A \land B$
Logikai műveletek | Diszjunkció
A diszjunkció két állítás közti logikai művelet. Két kijelentés diszjunkciója pontosan akkor igaz, ha legalább az egyik kijelentés igaz, különben hamis.
Jele: $ A \lor B$
Logikai műveletek | Implikáció
A "ha $A$, akkor $B$" kapcsolatnak megfelelő logikai műveletet nevezzük implikációnak. Az implikáció akkor hamis, ha $A$ igaz és $B$ hamis, minden más esetben igaz.
Jele: $A \Rightarrow B$
Logikai műveletek | Ekvivalencia
Az ekvivalencia egy olyan logikai művelet, amikor $A \Rightarrow B$ és $A \Leftarrow B$. Az ekvivalencia akkor igaz, ha $A$ és $B$ logikai értéke azonos, különben hamis.
Jele: $A \Leftrightarrow B$
Logikai De Morgan azonosságok
\( \neg \left( A \land B \right ) = \neg A \lor \neg B \)
\( \neg \left( A \lor B \right ) = \neg A \land \neg B \)
\( \neg \left( A \Rightarrow B \right ) = A \land \neg B \)
\( \neg \left( A \Leftrightarrow B \right ) = A \Leftrightarrow \neg B \)
Diszjunktív normálforma
A diszjunktív normálforma, röviden DNF egy olyan alakja egy logikai formuláknak, ahol a művelet a változóinak vagy negáltjainak konjunkcióinak diszjunkciója.
Ennek a témakörnek a feladatai
Letöltöm az egész kurzus összes feladatát:
LetöltömLetöltöm ennek a témakörnek a feladatait:
LetöltömVálogass kedvedre a témakör feladatai között:
Van itt ez az állítás: "Minden mamut sárga."
Válasszuk ki innen azokat, amik az állítás tagadása:
Egyik mamut sem sárga.
Van olyan mamut, ami sárga.
Van olyan mamut, ami nem sárga.
A legtöbb mamut nem sárga.
Nem minden mamut sárga.
Dontsük el az alábbi állításokról, hogy igazak, vagy hamisak.
a) Esik az eső és a mamut piros.
b) Esik az eső vagy a mamut piros.
c) Ha esik az eső, akkor a mamut piros.
Készítsük el az alábbi állítások igazságtábláit.
a) \( \neg A \wedge \neg B \)
b) \( A \wedge \neg B \)
c) \( \left( A \lor B \right) \Rightarrow \left( A \wedge B \right) \)
d) \( \neg A \Rightarrow \left( A \wedge B \right) \)
e) \( \neg A \wedge \left( A \lor B \right) \)
a) Van itt két láda. Az egyikben arany van, a másik üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is. Anélkül, hogy hozzárénénk a ládákhoz, meg tudjuk-e mondani, hogy melyikben van az arany?
A ládák feliratai: "Ha a másik ládában van az arany, akkor mindkét ládában hamis felirat van." és "Az arany nem ebben a ládában van."
b) Ezúttal már három láda van. Az egyikben arany van, a másik kettő üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is.
A ládák feliratai:
"A másodikon ládán a felirat igaz."
"Az arany ebben a ládában van és az első ládán a felirat hamis."
"Az arany olyan ládában van, amin a felirat hamis."
c) Most pedig tegyünk egy kört a lovagok és lókötők szigetén. Ezen a szigeten kétféle ember él, akik külsejük alapján teljesen egyformák. Csak éppen a lovagok mindig igazat mondanak, a lókötők pedig mindig hazudnak. Találkozunk két szigetlakóval.
X azt mondja: "Ha Y lovag, akkor én lókötő vagyok.". Y nem mond semmit. Milyen típusú X és Y?
d) Egy másik alkalommal három szigetlakóval találkozunk, akik ezt mondják:
X: "Y lókötő és Z lovag."
Y: "Lókötő vagyok és Z lovag."
Milyen típusú X, Y és Z?
e) Végü legy újabb esetben ismét három szigetlakóval találkozunk, akik ezt mondják:
X: Y lovag.
Y: X lókötő és Z lovag.
Milyen típusú X, Y és Z?
Tagadjuk a következő állítást:
"Az áldozat a szobában van, és ha nem találják meg, akkor holnap is ott lesz."
Mi a teljes diszjunktív normálformája?
a) \( A \Rightarrow \left( B \wedge C \right) \)
b) \( \left( A \Leftrightarrow B \right) \wedge \neg A \)
c) \( \left( A \Rightarrow B \right) \wedge \left( A \vee B \right) \)
A kvantorok. Hogy mik?
Minden ember utálja a matekot…
Azért ez így nem teljesen igaz, itt van ugyanis például Bob.
És Bob szereti a matekot.
Ez az állítás, hogy „Minden ember utálja a matekot.” tehát hamis.
Azért hamis, mert „Van olyan ember, aki szereti”.
Az egészből elég annyit megjegyezni, hogy Bobnak nehéz gyerekkora volt.
Nem, valójában ne ezt jegyezzük meg.
Hanem azt, hogy ez a két állítás egymás tagadása.
Nézzünk erre még egy példát és rögtön minden érthető lesz.
Itt van például ez az állítás:
Minden mamut piros.
Ennek az állításnak a tagadása:
Nem minden mamut piros.
Van olyan mamut, ami nem piros.
Tehát annak a tagadása, hogy „minden”…
így szól, hogy „van olyan, ami nem”.
A matematikában ezek a kifejezések meglehetősen gyakran előfordulnak.
Így aztán külön jelölés van rájuk forgalomban.
Ezt a jelet úgy hívják, hogy univerzális kvantor.
Ezt a másikat pedig úgy, hogy egzisztenciális kvantor.
Ezeknek a jeleknek a segítségével komplett kis titkosírásokat hozhatunk létre.
Ez például azt jelenti, hogy minden x-re létezik olyan y, hogy x+y=1.
A dolog igaznak tűnik, tényleg mindig létezik ilyen y.
Vagy itt van például egy másik:
Ami azt jelenti, hogy létezik olyan x, hogy minden y-ra x+y=1.
Na, ez már sajnos nem igaz.
Nem létezik olyan x szám, ami azt tudná, hogy bármilyen y-t adunk hozzá 1-et kapunk.
De visszatérve egy kicsit a mamutokra…
Van itt ez az állítás:
Minden mamut sárga.
Válasszuk ki innen azokat, amik az állítás tagadása:
Egyik mamut sem sárga.
Van olyan mamut, ami sárga.
Van olyan mamut, ami nem sárga.
A legtöbb mamut nem sárga.
Nem minden mamut sárga.
Hogyha még emlékszünk Bobra…
akkor talán rémlik valami, hogy a „minden” tagadása így szól: „van olyan, ami nem”.
Ez tehát biztosan jó.
Ez a másik pedig csak megtévesztésből van itt…
Hiányzik belőle a „nem” szócska.
Ócska kis trükk…
Aztán nyilván ez is az eredeti állítás tagadása…
Hiszen a mágikus „nem” szócskát őseink éppen a tagadás kifejezésére fejlesztették ki.
Ezek pedig nem tagadásai az eredeti állításnak, csak rá kell nézni itt lent a mamutokra és kiderül.
Próbáljuk meg eldönteni, hogy vajon igaz vagy hamis a következő állítás:
Esik az eső és a mamut piros.
Hát, eléggé hamisnak tűnik.
gy néz ki egyáltalán nem.
A mondat első fele sem igaz…
és a másik fele sem.
Ha mondjuk az eső legalább esne…
Az állítás ettől továbbra is hamis maradna.
Egyetlen egy esetben lenne igaz…
Ha mindkét fele igaz.
Készítsünk ebből egy kis táblázatot.
igaz
hamis
Végülis a mamutokra és az esőre nincs is szükség.
Az „és”-re pedig bevezetünk egy jelölést.
Itt jön aztán egy másik állítás:
Esik az eső vagy a mamut piros.
Készítsünk erről is egy táblázatot.
Hogyha mindkét rész hamis…
akkor az egész állítás is hamis.
Ha a két rész közül valamelyik igaz…
akkor az egész állítás is igaz.
Hogyha pedig mindkét rész igaz…
Ilyen esetekben az emberek hétköznapi logikája nem nagyon tudja értelmezni a „vagy” szócskát.
A matematika viszont igen, és az állítás ebben az esetben is igaz.
A „vagy”-ra is létezik egy matematikai jelölés…
Éppen itt is van.
Egy ősi népi megfigyelés szerint:
Ha esik az eső, akkor a mamut piros.
Nézzük, mikor lesz ez az állítás igaz.
Nos, olyankor, amikor süt a nap…
teljesen mindegy, hogy milyen színű a mamut.
Hiszen csak olyankor kell pirosnak lennie, ha esik.
Ezt az állítást matematikailag így jelöljük:
Olyankor, amikor a kiinduló feltevés hamis, már bármi történhet…
Maga az állítás igaz lesz.
És olyankor is igaz lesz, ha mindkét rész igaz.
Egyetlen egy esetben lesz az állítás hamis.
Amikor esik az eső, de a mamut mégsem piros.
Ezek itt valójában ugyanolyan műveletek, mint az algebrában az összeadás vagy a szorzás.
És ugyanúgy nevük is van.
KONJUNKCIÓ
DISZJUNKCIÓ
IMPLIKÁCIÓ
Vannak aztán még további műveletek is.
Az egyik az ekvivalencia.
Az ekvivalencia jeléből is látszik, hogy ez egy olyan művelet, amikor
Tehát A-ból következik B és B-ből is következik A.
A dolog valójában még ennél is egyszerűbb, az egész azt jelenti, hogy A pontosan akkor igaz, amikor B.
Ezek a műveletek mind kétváltozós műveletek, vagyis kell hozzá egy A és egy B is.
Itt jön aztán egy olyan logikai művelet is, ami egyváltozós.
Ez a művelet a tagadás, vagyis a „nem A”.
Olyan, mint az algebrában az ellentett…
A művelet neve negáció.
Jók ezek a táblázatok, csak hát rémesen sok helyet foglalnak.
Kénytelenek leszünk egy kicsit egyszerűsíteni őket:
Na, így már sokkal jobb.
Most nézzünk egy izgalmas feladványt, ami azt tesztelte, hogy a hétköznapi emberek mennyire fogékonyak a matematikai logika iránt.
A teszt során az derült ki, hogy nem különösebben…
De lássuk a feladványt.
Van itt ez a négy darab kártya. Az egyik oldalán mindegyiknek egy szám áll, a másik oldalon pedig egy betű.
És van itt ez az állítás:
Ha a kártya egyik oldalán magánhangzó van, akkor a másik oldalán páros szám áll.
A kérdés az, legfeljebb hány kártyát kell megfordítanunk ahhoz, hogy kiderüljön igaz-e az állítás?
A tipikus rossz válaszokat bárki megtudhatja, hogyha elmondja ezt a kis feladványt ismerőseinek…
És most lássuk a jó választ.
Ez az állítás tulajdonképpen mindig igaz, kivéve egyetlen esetben.
Egyedül az okozza a bajt, amikor A igaz, de B hamis.
Ez megtörténhet itt, ha a túloldalon páratlan szám van…
És itt, ha a másik oldalon magánhangzó van.
A többi esetben vagy eleve A hamis, és akkor már mindegy…
vagy B igaz és akkor is mindegy.
Ezt a két kártyát kell tehát megfordítani.
Itt jön néhány állítás, és fogalmazzuk meg ezek tagadását.
Az ég kék és a fű zöld.
Az állítás tagadásának a táblázata úgy kell, hogy kinézzen…
hogy itt mindenhol 0 helyett 1 és 1 helyett pedig 0 van.
Hát, ilyen éppen van…
Csak A-t és B-t is tagadni kellene.
Ha esetleg elsőre ez kicsit zavarosnak tűnik, az teljesen normális...
Nézzük meg szépen lépésről lépésre, és minden ki fog derülni.
Az állítás tagadásában tehát „vagy”-nak kell lennie…
És úgy fog stimmelni a táblázat, ha külön-külön A-t és B-t is tagadjuk.
Valahogy így:
Az ég nem kék vagy a fű nem zöld.
Lássuk a táblázatot.
Úgy tűnik ez meg is van.
A táblázat utolsó oszlopában minden épp a fordítottja lett annak, ami eredetileg volt.
Ez tehát valóban az eredeti állítás tagadása.
Végül nézzünk meg még egyet.
Ha az ég kék, akkor a fű zöld.
Megint megnézzük a táblázatot…
és keresünk egy ezzel ellentéteset.
Ami itt 0 volt…
az ebben 1.
Most hasonlítsuk össze ezt a két sort.
Csak a B-nél van változás, így most csak a B-t kell tagadni.
Az eredeti állítás tagadásában tehát „és” fog szerepelni és 
.
Az ég kék és a fű nem zöld.
Az utolsó oszlop épp a fordítottja annak, mint ami eredetileg volt.
Ez tehát az állítás tagadása.
Most pedig őrülten izgalmas dolgokat fogunk csinálni.
Elkészítjük néhány állítás igazságtáblázatát.
Épp itt is van az első:
edu10
Hát, ez kész is.
És ami azt illeti, élénken emlékeztet az A vagy B tagadására.
Sőt ez maga az A vagy B tagadása.
Hogyha most elkészítenénk az igazságtáblázatát…
akkor az derülne ki, hogy az pedig A és B tagadása.
Lássuk aztán, mi a helyzet ezzel:
Már jön is az igazságtáblázat…
A jelek szerint ez éppen az tagadása.
Az ekvivalencia tagadása pedig ez volna…
Most pedig lássuk, mi a tagadása ennek a nagyon egyszerű mondatnak:
Ha az ég kék, akkor a fű zöld és a mamut piros.
Beazonosítjuk a szereplőket.
És íme, az állítás:
Ez pedig a tagadása…
Hát ez megvolna.
Az ég kék, és a fű nem zöld vagy a mamut nem piros.
Végül vannak itt ezek az állítások:
És készítsük el az igazságtáblázatukat.
Ez a táblázat élénken emlékeztet az ekvivalencia igazságtáblázatára…
Annyira emlékeztet, hogy az is.
A jelek szerint ez éppen A.
Ez leginkább erre emlékeztet…
Egy kis módosítással.
Csodás.
Van itt ez a két láda. Az egyikben arany van, a másik üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is.
Anélkül, hogy hozzáérnénk a ládákhoz, meg tudjuk-e mondani, hogy melyikben van az arany?
Ha a másik ládában van az arany, akkor mindkét ládán hamis felirat van.
Az arany nem ebben a ládában van.
Kezdjük az első ládán szereplő felirattal.
Ez a felirat csak abban az esetben hamis…
ha az arany a másik ládában van…
és nem mindkét ládán van hamis felirat.
Mivel ez a felirat hamis, így a másik ládán lévőnek kell igaznak lennie.
De ez lehetetlen, hiszen az arany abban a ládában van.
Az első ládán lévő felirat tehát nem lehet hamis.
Lássuk, mi van akkor, ha az első ládán a felirat igaz.
Ha az arany mégis a másik ládában van…
akkor ennek a résznek is igaznak kéne lennie.
De ez lehetetlen.
Csak úgy lehet az első ládán igaz felirat, hogy az állítás első fele hamis.
És ekkor a másik láda üres ugyan, de a rajta lévő felirat igaz.
Ezúttal már három láda van. Az egyikben arany van, a másik kettő üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is.
Anélkül, hogy hozzáérnénk a ládákhoz, meg tudjuk-e mondani, hogy melyikben van az arany?
A második ládán a felirat igaz.
Az arany ebben a ládában van és az első ládán a felirat hamis.
Az arany olyan ládában van, amin a felirat hamis.
Az első két láda felirata egy kicsit ellentmond egymásnak.
Az első ládán a felirat biztosan nem lehet igaz.
Így aztán a második ládán is hamis felirat van.
De ennek a második fele igaz…
tehát az első felének mindenképp hamisnak kell lennie.
Most nézzük a harmadik ládát.
Ha ez a felirat hamis, akkor az aranynak olyan ládában kell lennie, amin a felirat igaz.
Csakhogy nincs ilyen láda, mert ebben az esetben mindegyik felirat hamis.
A harmadik láda felirata csak igaz lehet.
És az arany nem lehet ebben a ládában.
Az arany az első ládában van.
Hát, ennyit a ládákról. Most pedig tegyünk egy kört a lovagok és lókötők szigetén.
Ezen a szigeten kétféle ember él, akik külsejük alapján teljesen egyformák.
Csak éppen a lovagok mindig igazat mondanak, a lókötők pedig mindig hazudnak.
Találkozunk két szigetlakóval.
X azt mondja:
Ha Y lovag, akkor én lókötő vagyok.
Y nem mond semmit.
Milyen típusú X és Y?
Kezdjük azzal, hogy mi van akkor, ha X hazudik.
Ez csak úgy lehetséges, ha Y lovag…
és X is lovag.
De ez lehetetlen, hiszen akkor X nem hazudhat.
X-nek mindenképpen igazat kell mondania.
X tehát lovag.
És Y nem lehet lovag…
mert akkor X-nek lókötőnek kéne lennie.
Vagyis Y lókötő.
Egy másik alkalommal három szigetlakóval találkozunk, akik ezt mondják:
X: Y lókötő és Z lovag.
Y: Lókötő vagyok és Z lovag.
Milyen típusú X, Y és Z?
Kezdjük azzal, hogy lovag ilyet nem mondhat…
Y tehát biztosan lókötő, mivel pedig az állítás első fele igaz…
a második felének mindenképpen hamisnak kell lennie.
Eddig tehát ott tartunk, hogy Y és Z is lókötő.
Ez azt jelenti, hogy X hazudik.
Így aztán X is lókötő.
Egy újabb esetben ismét három szigetlakóval találkozunk, akik ezt mondják:
Kezdjük azzal a lehetőséggel, hogy Y hazudik.
Ekkor annak a résznek is hazugságnak kell lenni, hogy lókötő vagyok.
De az a rész éppen igaz, ez tehát ellentmondás.
Y csak lovag lehet, és így ez a rész biztosan igaz.
És a jelek szerint X is igazat mond.
Vagyis mindhárman lovagok.
Végül egy újabb esetben ismét három szigetlakóval találkozunk, akik ezt mondják:
Ha X igazat mond és Y lovag…
akkor X-nek lókötőnek kéne lennie.
Ez ellentmondás.
X tehát hazudik, így X és Y is lókötő.
Hogyha Y lókötő, akkor neki is hazudnia kell, de mivel az állítás első fele igaz…
a második fele nem lehet igaz.
Tehát Z-nek lókötőnek kell lennie.
Van itt ez az állítás:
Az áldozat a szobában van, és ha nem találják meg, akkor holnap is ott lesz.
Lássuk, mi lesz ennek a tagadása.
Ehhez egy kicsit formalizáljuk:
A tagadás pedig a mi kis képleteink segítségével…
Ez valahogy így szól, hogy:
Az áldozat nincs a szobában, vagy nem találják meg és holnap nem lesz ott.
Ezeket a képleteket De Morgan azonosságoknak hívják.
Voltak már ilyenek a halmazoknál is…
De ezek most a logikai De Morgan azonosságok.
Azon kívül, hogy segítenek nekünk leírni egy állítás tagadását még rengeteg mágikus dolgot tudnak.
Nézzük meg például ezt:
Ha most ezt újra tagadjuk…
A dupla tagadás éppen kiejti egymást.
Itt pedig használhatjuk ezt.
És ezzel egy „Ha akkor” típusú állítást le tudtunk írni egy tagadás és egy „vagy” segítségével.
Ezzel az új kis képletünkkel az eredeti állítás egész jól átalakítható…
Az állítás pedig így szól…
Az áldozat a szobában van, és megtalálják vagy holnap is ott lesz.
De nem csak a „Ha akkor” típusú állításokat tudjuk lecserélni…
A De Morgan azonosságokkal ugyanis képesek vagyunk az „és”-t átalakítani „vagy”-ra és fordítva.
Nézzük meg például, hogyan nézne ki egy olyan világ, amiben csak tagadás meg „vagy” létezik:
Itt túl sok dolgunk nincsen…
És az ekvivalencia…
Na, itt még szükség van egy kis trükkre.
Az ekvivalencia azt jelenti, hogy A és B is egyszerre igaz…
vagy egyszerre hamis.
Ezzel fogjuk folytatni.
Egy ügyes kis trükk segítségével minden kifejezés feldarabolható teljesen különálló részekre.
Itt van például az ekvivalencia, ami azt jelenti, hogy A és B is egyszerre igaz…
vagy egyszerre hamis.
Az implikációnál pedig…
Vagy A és B is egyszerre igaz…
vagy A hamis és B igaz…
vagy A hamis és B is hamis.
A „vagy”-gyal elválasztott részek csak tagadást meg „és”-t tartalmaznak, így mindegyik ilyen rész pontosan egyféleképpen lehet igaz.
Az eredeti kifejezésnek ezt a felírását úgy hívjuk, hogy teljes diszjunktív normálforma.
Nézzük meg, hogy mi lesz például a teljes diszjunktív normálformája ennek:
Azzal kezdjük, hogy elkészítjük a szokásos igazságtáblázatot.
Aztán kiválogatjuk azokat az eseteket, amikor az egész kifejezés igaz.
Ezeket felírjuk szépen egymás után…
És hopp, már kész is a teljes diszjunkt normálforma.
Minden nem azonosan hamis kifejezésnek van teljes diszjunktív normálformája.
És éppen így kell elkészíteni, ahogy az előbb csináltuk.
Nézzük, mi lesz a teljes diszjunktív normálformája ennek itt:
Na, itt túl sok dolgunk nem lesz…
Lássunk még egyet.
Pompás.
Teljes
diszjunktív
normálformák
