Matematikai logika Jegyzet
Összeállította: Faludi Anita 2011.
Tartalomjegyzék Bevezetés ............................................................................................................................................. 3 Előzmények .......................................................................................................................................... 3 Augustus de Morgan (1806-1871) ................................................................................................... 3 George Boole(1815-1864) ................................................................................................................ 3 Claude Elwood Shannon(1916-2001) ............................................................................................... 3 Alapfogalmak ....................................................................................................................................... 3 Ítélet (kijelentés)............................................................................................................................... 3 Logikai érték (logikai változó): ......................................................................................................... 3 Egyszerű ítélet: ................................................................................................................................. 3 Összetett ítélet: ................................................................................................................................ 4 Logikai műveletek ................................................................................................................................ 4 Negáció ............................................................................................................................................ 4 Konjukció .......................................................................................................................................... 4 Diszjunkció........................................................................................................................................ 5 Kizáróvagy ........................................................................................................................................ 5 Igazságtáblák ................................................................................................................................... 5 Logikai műveletek tulajdonságai ..................................................................................................... 6 Feladat ............................................................................................................................................. 6 Logikai kifejezések ................................................................................................................................ 7 Kiértékelés ........................................................................................................................................ 7 Igazságtáblák ................................................................................................................................... 7 Logikai kapu.......................................................................................................................................... 9 Logikai kapu-típusok ........................................................................................................................ 9 Összefoglaló elméleti kérdések, feladatok ........................................................................................ 11 Gyakorlati feladatok ........................................................................................................................... 11 Megoldások ........................................................................................................................................ 12 Felhasznált irodalom .......................................................................................................................... 13
Bevezetés Ez a jegyzet elsősorban azoknak a diákoknak készült, akiket tanítok. Nem volt szándékomban a logikai matematikát teljes egészében kitárgyalni, ezért a jegyzet erőteljesen hiányos. Az olvasó egy percig se gondolja azt, hogy a témakörhöz ennyi információ tartozik. A jegyzetben csak azokat a területeket érintettem, amit szükségesnek ítéltem meg, és amiről úgy gondoltam, hogy megfelelő alapot biztosít a továbbfejlődéshez.
Előzmények Augustus de Morgan (1806-1871) Nevéhez fűződik az arisztotelészi logika alapján a logikai műveletek algoritmizálásra tett első kísérlet. 1847-ben publikált „Formális logika” c. műve veti meg a logikai algebra alapjait.
George Boole(1815-1864) A formális logika törvényeit a matematikában alkalmazta, de a maga korában nem talált számottevő visszhangra. Később a számolás gépesítése és a számítógépek kapcsán alapvető fontosságúnak bizonyult munkássága. Az általa bevezetett, azóta róla Boole-algebrának nevezett tudomány-terület célja, hogy egyesítse a matematikát a logikával.
Claude Elwood Shannon(1916-2001) Doktori értekezésében tárgyalta a számítógépek kialakításával, megvalósításával kapcsolatos gyakorlati problémakört, hogy az elektromechanikus relék rendszerével logikai műveletek sorát hogyan lehet megvalósítani. Ezzel elsők között foglalkozott a korábban elméleti jellegű Boole-algebra gyakorlatba való átültetésével.
Alapfogalmak Ítélet (kijelentés) Olyan szavakkal, vagy más szimbólumokkal kifejezett „mondat”, „objektum”, amely egyértelműen igaz, vagy hamis (azaz nem igaz).
Logikai érték (logikai változó): Az ítélethez tartozó „igaz” vagy „hamis” jelző. Jelei: igaz érték:
i,
hamis érték: h,
I,
T, 1
H, F, 0
Egyszerű ítélet: Nem bonthatók fel további ítéletekre. Példa: A tiszta hó fehér. Április 30 napból áll. 3>2 3
Összetett ítélet: Több ítéletet tartalmazó, bonyolult szerkezetű ítélet. Példa: A Hold sajtból van és Kanada Európai ország. a
Logikai műveletek Negáció (NEM, NOT, ¬ , C# megfelelője: ! ) DEF:
¬A logikai értéke igaz, ha A logikai értéke hamis és ¬A logikai értéke hamis, ha A logikai értéke igaz.
Példák:
A: Esik az eső
¬A: Nem esik az eső.
A: a
¬A: a≥b
A: Budapest város. ¬A: Budapest nem város.
Konjukció (ÉS, AND, ˄ , C# megfelelője: && ) DEF:
Az A˄B konjukció logikai értéke akkor és csak akkor igaz, ha mind A, mind B (tehát egyszerre minkettő) logikai értéke igaz.
Példák:
A: Péter okos. B: Péter szép. A˄B: Péter okos is és szép is. A: x>1. B: x<2. A˄B: 1<x<2 A: A 2 páros szám. B: A 2 prím szám. A˄B: A 2 páros és prím szám.
4
Diszjunkció (VAGY, OR, ˅ , C# megfelelője: || ) DEF:
Az AvB diszjunkció logikai értéke akkor és csak akkor igaz, ha A és B közül legalább az egyik logikai értéke igaz.
Példák:
A: Péter okos. B: Péter szerencsés. AvB : Péter okos vagy szerencsés vagy mindkettő. A: 5 osztója 25-nek. B: 3 osztója 25-nek. AvB =i A: 2>3. B: 5>7. AvB =h A: Ma esik a hó. B: Ma esik az eső. AvB: Ma esik a hó vagy esik az eső vagy mindkettő.
Kizáróvagy (XOR, ˅ , C# megfelelője: nincs) DEF:
Az AvB logikai értéke akkor és csak akkor igaz, ha vagy A, vagy B, (de nem mindkettő) logikai értéke igaz.
Példák:
A: Esik az eső. B: Nem esik az eső. AvB =i A: Éjszaka van. B: Nappal van. AvB =i A: A házban vagyok. B: A szobában vagyok. AvB =h
Igazságtáblák NOT A
¬A
i h
h i
AND A
B
A˄B
OR A
B
AvB
i i h h
i h i h
i h h h
i i h h
i h i h
i i i h
5
XOR A
B
AvB
i i h h
i h i h
h i i h
Logikai műveletek tulajdonságai a) Kommutativitás: A˄B = B˄A AvB = BvA AvB = BvA b) Asszociativitás: (A˄B)˄C = A˄(B˄C) (AvB)vC = Av(BvC) (AvB)vC = Av(BvC) c) Disztributivitás: (A˄B)vC = (AvC)˄(BvC) (AvB)˄C = (A˄C)v(B˄C) (AvB)˄C = (A˄C)v(B˄C) AvB = (A˄¬B)v(¬A˄B) d) Tagadás: ¬(¬A) = A ¬(A˄B)=¬Av¬B ¬(AvB)=¬A˄¬B
Feladat Legyen az A és B ítélet a következő: A: Júlia szereti Rómeót. B: Rómeó szereti Júliát. Írjuk fel A, B valamint a logikai műveletek segítségével a következő ítéleteket. a) Rómeó és Júlia kölcsönösen szeretik egymást. b) Rómeó és Júlia közül legfeljebb az egyik szereti a másikat. c) Rómeó és Júlia nem szeretik egymást kölcsönösen. d) Sem Júlia Rómeót, sem Rómeó Júliát nem szereti. e) Júlia szereti ugyan Rómeót, de Rómeó Júliát nem. f) Rómeó és Júlia ugyanúgy éreznek egymás iránt. g) Rómeó és Júlia különbözően éreznek egymás iránt. h) Nem igaz, hogy Rómeó és Júlia közül legalább az egyik szereti a másikat. Megoldások: a) b) c) d) e) f) g) h)
A˄B; AvB; AvB ¬A˄¬B; A˄¬B; (A˄B)v(¬A˄¬B); (A˄¬B)v(¬A˄B); ¬(AvB);
6
Logikai kifejezések DEF:
A logikai műveleti jelek, zárójelek (zárójelpárok) és operandusok (ítéletek) sorozatát logikai kifejezésnek nevezzük.
Példák:
(Pv¬Q)˄(R˄¬S)v(¬PvS) ¬Av(Bv¬C)v(A˄¬C)
Kiértékelés a) Precedencia szabály: 1. negáció 2. konjukció 3. diszjunkció b) „Balról jobbra” szabály: Egyenértékű műveletek esetén a bal oldali számít. A két szabály megtörésére, megváltoztatására szolgálnak a zárójelek.
Igazságtáblák A kifejezések igazságtábláiból minden lehetséges érték leolvasható. Példák: 1. Milyen P értékre lesz a Pv¬Q kifejezés értéke hamis? P
Q
¬Q
i i h h
i h i h
h i h i
Pv¬Q i i h i
A Pv¬Q kifejezés értéke P=h esetén lesz hamis, de csak akkor, ha Q=i. 2. Milyen Q értékre lesz a (PvQ)v¬P kifejezés értéke igaz? P
Q
PvQ
i i h h
i h i h
i i i h
¬P h h i i
(PvQ)v¬P i i i i
A (PvQ)v¬P kifejezés bármilyen Q értékre igaz értéket ad.
7
3. Van e olyan eset, amikor P˄¬P kifejezés értéke igaz? P
¬P
P˄¬P
i h
h i
h h
A P˄¬P kifejezés értéke semmilyen esetben nem lehet igaz. 4. Milyen p és q értékekere adhat igazat a p˄¬q logikai kifejezés? p i i h h
q ¬q pΛ¬q i h h h i i i h h h i h
p=i, q=h esetén
5. Milyen p, q, r értékek esetén lehet a ¬(¬(pv¬q)v¬r) logikai kifejezés igaz?
p i i i i h h h h
q i i h h i i h h
r i h i h i h i h
¬q h h i i h h i i
¬r pv¬q ¬(pv¬q) ¬(pv¬q)v¬r) ¬(¬(pv¬q)v¬r) h i h h i i i h i h h i h h i i i h i h h h i i h i h i i h h i h h i i i h i h
1. eset: p=i, q=i, r=i 2. eset: p=i, q=h, r=i 3. eset: p=h, q=h, r=i
8
Logikai kapu A logikai kapu valamely logikai alapműveletet, vagy ezek kombinációját megvalósító áramkör. A bemeneti és kimeneti értékek logikai értékek (0, vagy 1), amelyeket feszültségszintek képviselnek. A mikroelektronikai berendezések nagy része kétállapotú elemekből áll. Egy logikai kapu egy, vagy több logikai értéket kap bemenetként, melyeken elvégezve az adott műveletet egy kimeneti értékkel tér vissza. Mivel a kimeneti érték is logikai, így az közvetlenül továbbítható egy másik kapu bemenetére, így egyszerű logikai kapukból is igen bonyolult rendszerek épíhetőek.
Logikai kapu-típusok Kapu
jel
művelet
Igazságtábla
A B A AND B 0 0 1 1
AND (és)
0 1 0 1
0 0 0 1
A B A OR B 0 0 1 1
OR (vagy)
NOT (negáció)
0 1 0 1
0 1 1 1
A NOT A
A
0 1
1 0
A B A XOR B 0 0 1 1
XOR kizáró vagy
9
0 1 0 1
0 1 1 0
Példák: (avb)˄c áramköre
(¬B˄¬A)vC áramköre
(a˄¬b)v(¬a˄b) áramköre
10
Összefoglaló elméleti kérdések, feladatok
A matematikai logika fejlődése során milyen nevek merültek fel? Mit tud róluk? Mit jelentenek a következő fogalmak: ítélet, logikai érték, egyszerű ítélet, összetett ítélet? Mondjon rájuk egy-egy példát! Mondjon egy olyan mondatot, ami nem ítélet! Melyik négy logikai művelettel ismerkedtünk meg? Mondja el a definícióit! Írja fel a logikai műveletek igazságtábláit! A logikai műveletek milyen tulajdonságait tanultuk? Csoportosítsa és írja fel őket! Mondja el a logikai kifejezés definícióját! Milyen szabályok érvényesek logikai kifejezés kiértékelésénél? Mikor érdemes a logikai kifejezések igazságtábláit használni? Milyen logikai áramköröket ismertünk meg? Mit jelentenek? Rajzolja fel a megismert logikai kapuk jeleit! Rajzoljon fel egy egyszerű logikai áramkört!
Gyakorlati feladatok 1) Határozzuk meg a következő logikai kifejezések értékét! a) (pvq)˄¬(¬pvq), ha p=i, q=h b) (¬AvB)˄¬C, ha A=i, B=h, C=i c) (A˄¬B)v(¬C˄A), ha A=i, B=i, C=i d) ¬(A˄¬B), ha A=h, B=h 2) Adottak az A=i, B=h, és C=h logikai értékek. Ezek alapján milyen értéket vesznek fel az alábbi logikai kifejezések? a) ¬A˄(BvC)v¬C b) Cv(¬B˄¬A)˄B 3) Bontsuk fel az alábbi összetett ítéletet egyszerű (elemi) ítéletre! Ezután – felhasználva az elemi ítéleteket és a logikai műveleteket – adjuk meg az összetett ítéletnek megfelelő logikai kifejezést! a) K: Az emberi élet véges tartamú és nem független a környezeti behatásoktól. b) K: Vasárnap reggel vagy moziba mégy, vagy kirándulni, de mindenképpen elkészíted a házi feladatokat. 4) Legyen az A, B, C ítélet jelentése: A: Esik az eső. B: Fúj a szél. C: Harangoznak. Mit jelentenek az alábbi kifejezések? a) A˄B˄¬C b) BvC c) (A˄B)v(A˄C) d) (AvB)˄C 11
Megoldások 1. a) (ivh)˄¬(¬ivh) = i˄¬(hvh) = i˄¬h = i˄i = i Megoldás: A kifejezés értéke igaz. b) (¬AvB)˄¬C = (¬ivh)˄¬i = (hvh)˄h = h˄h = h Megoldás: A kifejezés értéke hamis. c) (A˄¬B)v(¬C˄A) = (i˄¬i)v(¬i˄i) = (i˄h)v(h˄i) = hvh = h Megoldás: A kifejezés értéke hamis. d) ¬(h˄¬h) = ¬(h˄i) = ¬h = i Megoldás: A kifejezés értéke igaz. 2. a) ¬i˄(hvh)v¬h = h˄hvi = hvi = i Megoldás: A kifejezés értéke igaz. b) hv(¬h˄¬i)˄h = hv(i˄h)˄h = hvh˄h = h Megoldás: A kifejezés értéke hamis. 3. a) Négy megoldás van, bármelyik megfelelő: A: Az emberi élet véges tartamú. B: Az emberi élet tartama független a környezeti behatásoktól. Logikai kifejezés: K = A˄¬B 2. Elemi ítéletek: A: Az emberi élet végtelen tartamú. B: Az emberi élet tartama független a környezeti behatásoktól. Logikai kifejezés: K = ¬A˄¬B 3. Elemi ítéletek: A: Az emberi élet végtelen tartamú. B: Az emberi élet tartama függ a környezeti behatásoktól. Logikai kifejezés: K = ¬A˄B 4. Elemi ítéletek: A: Az emberi élet véges tartamú. B: Az emberi élet tartama függ a környezeti behatásoktól. Logikai kifejezés: K = A˄B b) Több megoldás is lehetséges. Pl: Elemi ítéletek: A: Vasárnap reggel moziba mégy. B: Vasárnap reggel kirándulni mégy. C: Vasárnap elkészíted a házi feladatokat. Logikai kifejezés: K = (AvB)˄C 1. Elemi ítéletek:
4. a) b) c) d)
Esik az eső és fúj a szél, de nem harangoznak. Esik az eső vagy fúj a szél. Fúj a szél vagy harangoznak, de biztosan esik az eső. Esik az eső vagy fúj a szél, de az biztos, hogy harangoznak.
12
Felhasznált irodalom
Bay-Juhász-Szentlekiné: Matematika analízis példatár I. BGF, Budapest, 2000. Dorozsmai Károly: 60 tétel informatikából (középszint – szóbeli) Maxim Kiadó, Szeged, 2009. Szelezsán János: Matematika 1. (Bevezető fejezetek a matematikából informatikusoknak) LSI Oktatóközpont, Budapest, 2001. Szelezsán János: Matematika példatár LSI oktatóközpont, Budapest, 2001.
13
