Matematikai logika |

Matematikai logika

A matematikai logika az egész matematika alapja. Persze, biztosan tudod, de mielőtt átugranád, egy apró megjegyzés. Szerintem ezt így összeszedve leírva még nem láttad. Az összes áramkör, de igazából a hétköznapi kommunikáció is a matematikai logika alapján működik, és ezt majd példákkal fogom bemutatni. Kezdjük is bele, mert hosszú lesz. Első nagyobb témakör a Haladó Matematikából…

Minden további magyarázat nélkül szerintem néhány logikai alapműveletet már ismersz, sőt naponta használod is:

VAGY
ÉS
NEM

Dehát ezek szavak. Igen és nem. Szavak, mélyebb jelentéssel – és most jöjjön egy kis filozófia

Szívem, majd edzés után menj el a boltba, hozz paradicsomot és rukkolát is a salátához. Ha gondolod, tehetünk még a salátához parmezán sajtot vagy tonhalat is, azzal még finomabb lesz

Sima ügy, gondolhatnánk, pedig nem. Tereljük ezt az üzenetet filozófiai irányba és kezdjünk el kérdéseket feltenni:

Mi van akkor, ha nincs a boltban SE paradicsom, SE rukkola?
Ha nincs SE paradicsom, SE rukkola, akkor vegyek még sajtot VAGY tonhalat?
Ha van paradicsom ÉS rukkola, de NINCS sajt, akkor NE vegyek paradicsomot ÉS rukkolát SE?

Ezt az okfejtést valószínűleg sokáig lehetne folytatni. A SE, VAGY, ÉS szavakat direkt kiemeltem. Szavaknak hívom őket, de ha a filozófiai irányba kívánunk tovább haladni, akkor a jelentésüket ki kell bővíteni. Immáron műveleteknek kell őket tekinteni. AZ ÉS és VAGY, NEM egyértelmű műveleteket fogalmaz meg. A telefonunk képernyőzárjának feloldásához az utolsó ÉS utolsó előtti jelszókarakternek is stimmelnie kell, a matematikát pedig lehet szeretni VAGY utálni, vodka-martinit pedig rázva kérjük, NEM keverve. De ahhoz, hogy Mr. Bond a világ összes talponállójában a megfelelő italt kapja, néhány évszázadnak, sőt évezrednek kellett eltelnie. Ahogy annyi minden, ez is a görögökkel kezdődött.

Történeti visszatekintés – Logika

Az első név akit meg kell említenünk, maga a logika ősapja, Arisztotelész (i.e. 384 – i.e.322) személyesen. Több logikával foglalkozó művet írt, amelyeket a követői i.e 50 körül az $Organon$ (magyarul: eszköz) néven foglaltak össze. Arisztotelész a logikát a legelemibb, legalapvetőbb eszköznek tartotta, enélkül a tudomány és a filozófia művelése nem lehetséges.

Ami most nekünk igazából fontos, az $Organon$ egyik része, az Első Analitika, amely a következtetésekkel ( $szilogizmus$ ), illetve a Második Analitika, amely logikai bizonyításokkal foglalkozik.

Arisztotelész - a logika ősapja — Arisztotelész – a logika ősapja

Az Első és Második Analitikából levezethető az arisztotelészi logika alapvetése, a Hármas Elv:

Minden dolog azonos önmagával
Semmi sem azonos önmaga ellentétével
Egy dolog és tagadása közül csupán az egyik lehet igaz

Szintén meg kell említeni a kettős-következtetés elvét is:

Szókratész ember. Minden ember halandó. Tehát Szókratész halandó

Igaz, hogy mennyire logikus? Persze, ha így van megfogalmazva, akkor könnyű belátni, csak eddig el is kellett jutni. Most ugrunk időben és térben egy nagyot és meg sem állunk a Ködös Albionig…

Egy nagy név következik, George Boole (1815-1864), az autodidakta angol matematikus és filozófus. 1847-ben kiadja a $The \ Laws \ of \ Thought$ (A gondolkodás törvényei) című munkájában a logika algebrai rendszerét.

Boole nem tekintette a logikát a matematika ágának, inkább arra mutatott rá, hogy egyértelmű analógia van az algebrai szimbólumok és a logika leírásában használt szimbólumok között. És ha már van egy leírónyelv, akkor egyenletekké lehet formálni állításokat.

A filozófiai ÉS, VAGY, NEM immáron matematikai hátteret kapott, noha ez abban az időszakban csak keveseket érdekelt – a matematikai logika kiteljesedése érdeklődés hiányában elmaradt…

George Boole - Létrehozza azt az algebrát, ahol látszólag az 1+1=1.. Logika, ugyan... — George Boole – Létrehozza azt az algebrát, ahol látszólag az 1+1=1.. Logika, ugyan…

Boole munkásságát az Indiában született, angol kollégája, Augustus De Morgan (1806-1871) vitte tovább. De Morgan először a $matematikai \ indukcióval$ gurított nagyot (hamarosan), majd a róla elnevezett azonosságokkal lett igazán híres:

1. azonosság: $\displaystyle \overline{A\cap B}=\overline{A}\cup\overline{B}$
2. azonosság: $\displaystyle \overline{A\cup B}=\overline{A}\cap \overline{B}$

Gondolom, ez így most elsőre sokat nem mond:

1. azonosság: A metszet komplementere megegyezik a komplementerek uniójával
2. azonosság: az unió komplementere megegyezik a komplementerek metszetével

Semmi gond, mindjárt meg fogod érteni, miről is van szó…

Augustus de Morgan - Boole munkájára építve két nagyon fontos axiómát fogalmaz meg a matematikai logikához — Augustus de Morgan – Boole munkájára építve két nagyon fontos axiómát fogalmaz meg a matematikai logikához

Boole és De Morgan munkássága az 1800-as évek végén a matematika egy érdekes területe volt, elhanyagolható gyakorlati alkalmazhatósággal. Nagyjából 70 évig nem is történt semmi, majd a Második Világháborút követő technikai fejlődés újra felfedezte magának a matematikai logikát.

1940-es években, az amerikai hiradástechnikai mérnök Claude Elwood Shannon (1916-2001) filozófiai tanulmányai során véletlenül rábukkant Boole munkásságára. Shannon éppen a doktori témáját írta az elektromos áramkörök tervezéséről. Ekkor jött az ötlet, hogy a Boole által lefektetett matematikai alapokra támaszkodva optimalizálni lehet az elektromos relék rendszerét. Sőt, ezen felül elsőként fizikailag – elektronikai alkatrészeket felhasználva megépíti az első logikai áramköröket. Mire nem jó a matematikai logika, nem igaz?

Hölgyek, Urak, ekkor megszületett a modern számítástechnika – de ehhez kellett még néhány rendkívüli képességű magyar is…

A Boole-algebra – a matematikai logika alapjai:

Vagyis a búl-algebra, ahogy magyarul hívjuk. Kezdésnek ismerkedjünk meg néhány alapvető fogalommal:

Igazságtáblázat: Egy olyan áttekintő táblázat, amely tartalmazza egy-egy logikai művelet összes lehetséges bemeneti lehetőségét és az összes kimenti válaszát. Hogy ne kapjunk agyvérzést az első témakörnél, 2 logikai változós modellt fogom bemutatni.

Logikai (bemeneti) változó: Egy logikai művelethez tetszőleges számú logikai változó tartozhat – ezeket tekintjük a bemeneti oldalnak. Tegyük fel, hogy egy bankautomata előtt állunk. A kezelőpulton számok vannak nullától kilencig – plusz még néhány műveleti gomb, amelyekkel jóváhagyni, javítani vagy törölni tudunk. Összesen 13 logikai változó van ezen a kezelőpulton. Adatokat tudunk bevinni, illetve műveleteket tudunk indítani.

Logikai (bemeneti) érték: A logikai érték nem más, mint az az érték, amit egy logikai változó felvehet. Az előző példánál maradva, minden számozott gomb 1 számot tartalmaz, minden műveleti gomb pedig egy-egy előre beprogramozott műveletet indít el a gomb megnyomásakor. Nem csak a nyomógombok alkalmasak bevitelre, szenzorok egész családja áll a rendelkezésünkre, lásd például a fülhallgatód hangerőszabályzója

Magas érték: 1 vagy IGAZ (a matematikai logikában NE számként tekintsünk rá…)

Alacsony érték: 0 vagy HAMIS

Kimeneti érték / Ítélet: A logikai művelet eredménye az adott logikai (bemeneti) értékek esetén. Az ítélet szó is használható, ha állítás vagy állítások igazságtartalmát vizsgáljuk.

Most pedig jöjjön a matematikai rész. Ahogy említettem, itt és most csak a 2 logikai változós modellel fogunk dolgozni. Mit gondolsz, hány lehetséges logikai műveletet lehet 2 logikai változóval összehozni?

Igen, a helyes válasz a 16

Hogy egyszerűbb legyen, adok kettő állítást:

$A \ kijelentés$ – A matek előadás dögunalom
$B \ kijelentés$ – Falra mászom

1. Lehetőség – Ellentmondás

Opciók	A	B	$Y$
1	0	0	0
2	0	1	0
3	1	0	0
4	1	1	0

2. Lehetőség – Tautológia

Opciók	A	B	$Y$
1	0	0	1
2	0	1	1
3	1	0	1
4	1	1	1

3. Lehetőség – Igaz állítás A-ra nézve

Jelölés:

Leíró egyenlet: $\displaystyle Y=A$

Az igaz állítás A-ra nézve ebben a kontextusban az jelenit, hogy a „matematika előadás dögunalom” és ezzel egyetértünk, de kint hideg van, szóval maradunk. Itt meg kell jegyezni, hogy a B állítást nem hívjuk meg – mert ha elkezdenék falra mászni, már nem lenne unalmas az előadás…

Opciók	A	B	$Y$
1	0	0	0
2	0	1	0
3	1	0	1
4	1	1	1

4. Lehetőség – NEM-Igaz állítás A-ra nézve

Jelölés: $\neg$

Leíró egyenlet: $\displaystyle Y=\overline{A}$ vagy $\displaystyle Y=\neg A$

A NEM-igaz állítás A-ra nézve az előző kijelentés tagadása, vagyis a „matematika előadás NEM dögunalom” Ezt a logikai kapcsolatot NEGÁCIÓNAK is nevezik. A továbbiakban én a $\overline{A}$ jelölést használom. Nekem ezt vált be, kevesebb elírási lehetőség van, ami nem hátrány, ha nem a szépírásról vagy híres.. Csak a kettős tagadást fogom $\neg \neg$ jelölni így.

Opciók	A	B	$Y$
1	0	0	1
2	0	1	1
3	1	0	0
4	1	1	0

5. Lehetőség – Igaz állítás B-ra nézve

Jelölés:

Leíró egyenlet: $\displaystyle Y=B$

Az igaz állítás B-re nézve ugyanúgy működik, mint az igaz állítás A-ra nézve, csak most a B állításon van a hangsúly, vagyis „falra mászom” show indul a matematika előadás közben – és most nem számít, hogy a dögunalmi skálán hol van az előadás. Ha egyszer rám jött a mászhatnék, akkor mászni kell…

Opciók	A	B	$Y$
1	0	0	0
2	0	1	1
3	1	0	0
4	1	1	1

6. Lehetőség – NEM-Igaz állítás B-ra nézve

Jelölés: $\neg$

Leíró egyenlet: $\displaystyle Y=\overline{B}$ vagy $\displaystyle Y=\neg B$

A NEM-igaz állítás B-re nézve ugyanúgy működik, mint a NEM-igaz állítás A-ra nézve – micsoda csalafinta véletlen… Akármennyire is vonzó a falra mászás és rólam beszélne mindenki az egyetemen, akkor sem fogok falra mászni, független attól, hogy mennyire unalmas az előadás..

Opciók	A	B	$Y$
1	0	0	1
2	0	1	0
3	1	0	1
4	1	1	0

7. Lehetőség – ÉS kapcsolat

Opciók	A	B	$Y$
1	0	0	0
2	0	1	0
3	1	0	0
4	1	1	1

8. Lehetőség – NEM-ÉS kapcsolat

Opciók	A	B	$Y$
1	0	0	1
2	0	1	1
3	1	0	1
4	1	1	0

9. Lehetőség – VAGY-Kapcsolat

Opciók	A	B	$Y$
1	0	0	0
2	0	1	1
3	1	0	1
4	1	1	1

10. Lehetőség – NEM-VAGY-Kapcsolat

Opciók	A	B	$Y$
1	0	0	1
2	0	1	1
3	1	0	1
4	1	1	0

Szándékosan szedtem így szét a táblázatot, ugyanis most a KÖVETKEZMÉNYEK érkeznek – vagyis szintet lépünk a matematikai logika ösvényén. A következményt hívhatjuk implikációnak is. Ez minden esetben legalább kettő logikai állítással végzett művelet, ahol az első állítás a premissza (előtag), a második a konklúzió (következmény), majd ebből következtetünk. Az A és B állítás még mindig ugyanazt jelenti.

Ezt a részt azért vettem külön, mert a hétköznapi életben itt van a legtöbb félreértés. Nézz meg egy írás-olvasás-szövegértés kompetencia tesztet, hemzseg az ilyen szerkezetektől. Nézzük a maradék 6 esetet…

11. Lehetőség – IMPLIKÁCIÓ

Jelölés: $\displaystyle A\to B$ vagy $\displaystyle A \supset B$ vagy $\displaystyle A \le B$

Leíró egyenlet: $\displaystyle Y=\overline{A} \vee B$ vagy $\displaystyle Y=\overline{A} \ + B$ vagy $\displaystyle Y=\overline{A} \gets\overline{B}$ vagy $\displaystyle Y={A} \uparrow \overline{B}$

Az IMPLIKÁCIÓ a „ha… A, akkor…B” szerű szerkezet. HAMIS állításból (A=0) következhet HAMIS (B=0) vagy IGAZ (B=1) következmény. IGAZ állításból (A=1) nem következhet HAMIS (B=0) következmény, csak IGAZ (B=1) következmény lehet.
„Ha majd unalmas lesz a matematika előadás, akkor fogok falra mászni”

Opciók	A	B	$Y$
1	0	0	1
2	0	1	1
3	1	0	0
4	1	1	1

12. Lehetőség – IMPLIKÁCIÓ TAGADÁSA

Jelölés: $\displaystyle A\nrightarrow B$ vagy $\displaystyle A \nsupseteq B$ vagy $A>B$

Leíró egyenlet: $\displaystyle Y=A \wedge \overline{B}$ vagy $\displaystyle Y=A \cdot \overline{B}$ vagy $\displaystyle Y=\overline{A} \nleftarrow \overline{B}$ vagy $\displaystyle Y=\overline {A} \downarrow {B}$

Az IMPLIKÁCIÓ TAGADÁSA a „nem igaz, hogy… A, akkor…B” szerű szerkezet. Az előző művelet tagadása, vagyis csak akkor lesz IGAZ, ha az IGAZ állításból (A=1) HAMIS (B=0) következmény születik. Ezt a logikai kapcsolatot KIVONÁS néven is ismert.

Opciók	A	B	$Y$
1	0	0	0
2	0	1	0
3	1	0	1
4	1	1	0

13. Lehetőség – FORDÍTOTT IMPLIKÁCIÓ

Opciók	A	B	$Y$
1	0	0	1
2	0	1	0
3	1	0	1
4	1	1	1

14. Lehetőség – TAGADOTT FORDÍTOTT IMPLIKÁCIÓ

Jelölés: $\displaystyle A \nleftarrow {B}$ vagy $\displaystyle A \not\subset {B}$ vagy $A<B$

Leíró egyenlet: $\displaystyle Y=\overline{A}\wedge B$ vagy $\displaystyle Y=\overline{A}\cdot B$ vagy $\displaystyle Y=\overline{A}\nrightarrow \overline{B}$ vagy $\displaystyle Y={A}\downarrow \overline{B}$

A TAGADOTT FORDÍTOTT IMPLIKÁCIÓ a „nem igaz, hogy ha nem B, akkor nem …A” szerkezet.
„Az nem igaz, hogy ha nem mászom falra, nem unalmas a matematika előadás” Kompetencia teszteken mondjuk ilyenkor jön a kérdés, hogy akkor ez a kérdés mikor IGAZ.

Opciók	A	B	$Y$
1	0	0	0
2	0	1	1
3	1	0	0
4	1	1	0

Végezetül jöjjön az antivalencia és az ekvivalencia. Nem, ezek nem harmadosztályú spanyol focicsapatok. Az ekvivalencia az azonosság mateksznobul, közönséges halandók nyelvén pedig két dolog egyenlősége. Az antivalencia pedig az ekvivalencia ellentéte. Sima ügy, nem? Mondom én, hogy nem nehéz a matematikai logika. Vizsgáljuk meg őket közelebbről…

15. Lehetőség – EKVIVALENCIA

Jelölés: $\displaystyle{A}\leftrightarrow {B}$ vagy $\displaystyle{A}\equiv {B}$

Leíró egyenlet: $\displaystyle Y={A} \nleftrightarrow \overline{B}$ vagy $\displaystyle Y=\overline{A} \nleftrightarrow {B}$ vagy $\displaystyle Y=\overline{A} \leftrightarrow \overline{B}$ vagy $\displaystyle Y=\overline{A \cdot B} + A \cdot B$

Az EKVIVALENCIA az „akkor és csak akkor” tipikus esete. Vagy mindkét teljesül egyszerre, vagy egyik sem.
„akkor és csak akkor mászom falra, ha unalmas a matematika előadás” vagy „akkor és csak akkor NEM mászom falra, ha NEM unalmas a matematika előadás”

Opciók	A	B	$Y$
1	0	0	1
2	0	1	0
3	1	0	0
4	1	1	1

16. Lehetőség – ANTIEKVIVALENCIA

Jelölés: $\displaystyle A\leftrightarrow B$ vagy $\displaystyle A \not\equiv B$ vagy $\displaystyle A\oplus_{}^{}B$

Leíró egyenlet: $\displaystyle Y={A} \leftrightarrow \overline{B}$ vagy $\displaystyle Y=\overline{A} \leftrightarrow {B}$ vagy $\displaystyle Y=\overline{A} \nleftrightarrow \overline{B}$ vagy $\displaystyle Y=\overline{A} \cdot \overline{B}+A \cdot B$

Az ANTIEKVIVALENCIA a „vagy-vagy” helyzet. Ilyen esetben CSAK az egyik feltételnek szabad teljesülnie.
„vagy felmászom a falra, vagy unalmas marad a matematika előadás” – gondolhatná a matektanár, hogy felrázza a hallgatóságot…

Opciók	A	B	$Y$
1	0	0	0
2	0	1	1
3	1	0	1
4	1	1	0

Feltételezem, mára ennyi volt. Viszont ezen túl kellett lenni, ez a táblázat az egész matematikai logika alapja. Ezek után az axiómák megértése már sokkal könnyebb lesz…

A Boole-algebra axiómái

Szerintem előbb elmagyarázom, hogy mi is az axióma szó jelentése. Ez egy olyan alapigazságot takar, amit az adott keretek között magától értetődőnek fogadunk el, ezért nem igényel sem bizonyítást, sem magyarázatot – például egyik macskám sem tud tengeralattjárót vezetni. Viszont én abban hiszek, hogy az ember valamit jobban megért, ha látja a bizonyítást. Laza 11 axiómát kell végigvennünk a matematikai logikában, de nyugi, nem nehéz egyik sem, már-már magától értetődik.

I. Axióma – asszociativitás

Ez az axióma kettő alakban is felírható:

1. számú alak: $\displaystyle A+ \left( B+C \right)=\left( A+B \right)+C$
2.számú alak: $\displaystyle A\cdot \left( B \cdot C \right)=\left( A\cdot B \right) \cdot C$

Az asszociativitás csoportosíthatóságot jelent, vagyis kifejezések átzárójelezhetőek, az eredményt nem fogja befolyásolni. A bizonyításhoz 2.számú alakot fogom alkalmazni. Jöhet is az igazságtáblázat, ezúttal 3 taggal. Ezek egyszerű szorzások, a lépéseket részletesen leírtam.

A kérdés: $\displaystyle A\cdot \left( B \cdot C \right) \stackrel{?}{=} \left( A\cdot B \right) \cdot C$

Opciók	$A$	$B$	$C$	$\displaystyle \left(b \cdot c \right)$	$\displaystyle \left(a \cdot b \right)$	$\displaystyle \left(b \cdot c \right) \cdot a$	$\displaystyle \left(a \cdot b \right) \cdot c$
1	$0$	$0$	$0$	$0 \cdot 0 = 0$	$0 \cdot 0 =0$	$0 \cdot 0 =0$	$0 \cdot 0 = 0$
2	$0$	$0$	$1$	$0 \cdot 1= 0$	$0 \cdot 0 =0$	$0 \cdot 0 =0$	$0 \cdot 1= 0$
3	$0$	$1$	$0$	$1\cdot 0= 0$	$0 \cdot 1 =0$	$0 \cdot 0 =0$	$0 \cdot 0 = 0$
4	$0$	$1$	$1$	$1\cdot 1= 1$	$0 \cdot 1 =0$	$0 \cdot 1 =0$	$0 \cdot 1= 0$
5	$1$	$0$	$0$	$0\cdot 0= 0$	$1 \cdot 0 =0$	$1 \cdot 0 =0$	$0 \cdot 0 = 0$
6	$1$	$0$	$1$	$0\cdot 1= 0$	$1 \cdot 0 =0$	$1 \cdot 0 =0$	$0 \cdot 1= 0$
7	$1$	$1$	$0$	$1\cdot 0= 0$	$1 \cdot 1 =1$	$1 \cdot 0 =0$	$1 \cdot 0 =0$
8	$1$	$1$	$1$	$1\cdot 1= 1$	$1 \cdot 1 =1$	$1 \cdot 1 =1$	$1 \cdot 1 =1$

Ha most megnézed a táblázat utolsó kettő oszlopát, akkor a kettő teljesen egyforma, vagyis bebizonyítottuk a $\displaystyle A\cdot \left( B \cdot C \right)=\left( A\cdot B \right) \cdot C \ \blacksquare$ alakot. A bizonyítás végén szereplő $\blacksquare$ szimbólumot Halmos Pál (1916-2006) amerikai-magyar matematikus vezette be. Minden levezetés végére én is oda fogom tenni. A $\displaystyle A+ \left( B+C \right)=\left( A+B \right)+C$ alak bizonyítása hasonló módon elvégezhető.

II. Axióma – kommutativitás

Magyarra lefordítva annyit tesz, hogy a kifejezésben szereplő egyes tényezők sorrendje felcserélhető, nem változtatja meg az eredményt. Ezt is két alakban írhatjuk fel:

1. számú alak: $\displaystyle A+B=B+A$
2. számú alak: $\displaystyle A \cdot B = B \cdot A$

Bizonyítsuk be az alábbi állítást:

$\displaystyle A + B \stackrel{?}{=} B + A$

Opciók	$A$	$B$	$A+B$	$B+A$
1	$0$	$0$	$1$	$1$
2	$0$	$1$	$1$	$1$
3	$1$	$0$	$1$	$1$
4	$1$	$1$	$1$	$1$

A táblázat utolsó két oszlopa egyenlő, vagyis: $\displaystyle A+B=B+A \blacksquare$

III. Axióma – disztributivitás

A szorzás az összeadásra nézve disztributív, vagyis a zárójelek felbonthatóak – a logikai szorzás tagonként, míg a logikai összeadás tényezőnként hajtandó végre. Ez az axióma is két alakban létezik:

1.számú alak: $\displaystyle A+\left( B\cdot C \right)=\left( A+B \right) \cdot \left( A+C \right)$
2. számú alak: $\displaystyle A+\left( B\cdot C \right)=\left( A \cdot B \right) + \left( A \cdot C \right)$

Bizonyítsuk be az 1.számú alakot: $\displaystyle A+\left( B\cdot C \right) \stackrel{?}{=}\left( A+B \right) \cdot \left( A+C \right)$

Jelöljük a $\displaystyle A+\left( B\cdot C \right)$ tagot $Y_1$ -el, míg a $\displaystyle \left( A+B \right) \cdot \left( A+C \right)$ tagot $Y_2$ -vel

Opciók	$A$	$B$	$C$	$\left( B \cdot C \right)$	$Y_1$	$\left( A + B \right)$	$\left( A + C \right)$	$Y_2$
1	$0$	$0$	$0$	$0 \cdot 0=0$	$0+0=0$	$0+0=0$	$0+0=0$	$0 \cdot 0 = 0$
2	$0$	$0$	$1$	$0 \cdot 1=0$	$0+0=0$	$0+0=0$	$0+1=1$	$0 \cdot 1 = 0$
3	$0$	$1$	$0$	$1 \cdot 0=0$	$0+0=0$	$0+1=1$	$0+0=0$	$1 \cdot 0 = 0$
4	$0$	$1$	$1$	$1 \cdot 1=1$	$0+1=1$	$0+1=1$	$0+1=1$	$1 \cdot 1 = 1$
5	$1$	$0$	$0$	$0 \cdot 0=0$	$1+0=1$	$1+0=1$	$1+0=1$	$1 \cdot 1 = 1$
6	$1$	$0$	$1$	$0 \cdot 1=0$	$1+0=1$	$1+0=1$	$1+1=1$	$1 \cdot 1 = 1$
7	$1$	$1$	$0$	$1 \cdot 0=0$	$1+0=1$	$1+1=1$	$1+0=1$	$1 \cdot 1 = 1$
8	$1$	$1$	$1$	$1 \cdot 1=1$	$1+1=1$	$1+1=1$	$1+1=1$	$1 \cdot 1 = 1$

Ha jól megnézzük, akkor a 6. oszlop és a 9. oszlop azonos, vagyis $\displaystyle A+\left( B\cdot C \right) = \left( A+B \right) \cdot \left( A+C \right) \blacksquare$

Megjegyzés: az $1+1=1$ nem elírás, hanem a Boolen-algebra – meg az informatika – sajátossága. Itt ne számként tekintsünk rá, hanem HAMIS(0), IGAZ (1) értékként.

IV.axióma – komplementer képzése

A komplementer szó kiegészítőt jelent – ez logikailag úgy fogható meg, hogy az IGAZ állítás nem létezhet HAMIS állítás nélkül. Ezt is két alakban lehet felírni:

1.alak: $A \cdot \overline{A}=0$
2.alak: $A + \overline{A}=1$

Bizonyítás:

Opciók	$A$	$\overline{A}$	$A \cdot \overline{A}$	$A + \overline{A}$
1	$0$	$1$	$0 \cdot 1 =0$	$0 +1 = 1$
2	$1$	$0$	$1 \cdot 0 =0$	$1+0 = 1$

A táblázat utolsó két oszlopa opciónként ellentétes eredményt mutat és ez volt a célunk $\blacksquare$

V.axióma – idempotencia

Nagyon leegyszerűsítve azt jelenti, hogy van két halmazom és mindkét halmaz ugyanazokból az elemekből áll. Ha két halmaz unióját vagy metszetét veszem – ezek kétváltozós kifejezések – akkor minden esetben ugyanazt az értéket kapom vissza.

1.alak: $A \cdot A=A$
2.alak: $A + A =A$

Legegyszerűbben ezt direkt behelyettesítéssel tudjuk bizonyítani:

Opciók	$A$	$A \cdot A$	$A +A$
1	0	$0 \cdot 0 = 0$	$0 +0 =0$
2	1	$1 \cdot 1 = 1$	$1 +1 =1$

A táblázat utolsó két oszlopa mindkét esetben egyenlő $A$ értékével és ezt akartuk bizonyítani $\blacksquare$

VI. axióma – identitás

Ezt az axiómát is kétféle módon tudjuk felírni:

1.alak: $A \cdot 1=A$
2.alak: $A + 0 =A$

egegyszerűbben ezt direkt behelyettesítéssel tudjuk bizonyítani:

Opciók	$A$	$A \cdot 1$	$A +0$
1	0	$0 \cdot 1 = 0$	$0 +0 =0$
2	1	$1 \cdot 1 = 1$	$1 +1 =1$

A táblázat utolsó két oszlopa mindkét esetben egyenlő $A$ értékével és ezt akartuk bizonyítani $\blacksquare$

VII. axióma – nullszabály

Ezt az axiómát is kétféle módon tudjuk felírni:

1.alak: $A \cdot 0=0$
2.alak: $A + 1 =1$

Egyszerűen, direkt behelyettesítéssel tudjuk bizonyítani:

Opciók	$A$	$A \cdot 0$	$A +1$
1	0	$0 \cdot 0 = 0$	$0 +1 =1$
2	1	$1 \cdot 0 = 0$	$1 +1 =1$

A táblázat utolsó két oszlopa mindkét esetben egyenlő 1.alak és 2.alak értékével és ezt akartuk bizonyítani $\blacksquare$

Megjegyzés: Ez az azonosság alkalmazható abban az esetben is, ha később egy ilyen $A \left(1+ B+C… \right)$ kifejezést kell egyszerűsíteni. Vegyük észre, hogy a 2.alak miatt a zárójelen belül lévő rész mindig 1 lesz, így a kifejezés $A \left(1\right)$ alakra egyszerűsödik.

VIII. axióma – $\displaystyle \overline{0}=1$ illetve $\displaystyle \overline{1}=0$ vagyis a $0$ és 1 egymás komplementerei

IX. axióma – elnyelés

Ez egy kicsit bonyolultabb, mint az eddigiek. Az elnyelés itt azt jelenti, hogy felesleges (redundáns) tagokat tudunk kivenni a kifejezésből, így egyszerűsödik a probléma, de a végeredmény nem változik. Ahogy eddig mindig, itt is két alakot tudunk felírni:

1.alak: $\displaystyle A+\left(A \cdot B \right)=A$
2.alak: $\displaystyle A\cdot \left(A + B \right)=A$

Jöhet az igazságtáblázat:

Opciók	$A$	$B$	$\displaystyle \left( A \cdot B \right)$	$\displaystyle \left( A + B \right)$	$\displaystyle A \cdot \left( A \cdot B \right)$	$\displaystyle A+\left( A \cdot B \right)$
1	$0$	$0$	$0$	$0$	$0$	$0$
2	$0$	$1$	$0$	$1$	$0$	$0$
3	$1$	$0$	$0$	$1$	$1$	$1$
4	$1$	$1$	$1$	$1$	$1$	$1$

Vegyük észre, hogy $A$ , $\displaystyle A+\left(A \cdot B \right)=A$ és $\displaystyle A\cdot \left(A + B \right)=A$ egyenlőek, vagyis a bizonyításunk helyes $\blacksquare$ .

Megjegyzés 1: a $\displaystyle B+\left(A +B \right)=B$ és a $\displaystyle B\cdot \left(A + B \right)=B$ is gyorsan bizonyítható egy igazságtáblázattal
Megjegyzés 2: a $\displaystyle A\cdot \left(AB + ABC+… \right)=A$ is ugyanígy levezethető, annyi a dolgunk, hogy kiemelünk $A$ -t, és az egyenlet ilyen alakú lesz: $\displaystyle A\cdot \left(1 + B+BC… \right)=A$ és ekkor beugrik nekünk a VI.axióma, vagyis a zárójeles tag értéke 1, vagyis: $\displaystyle A\cdot \left(1\right)=A$

Van még valami az elnyelési axióma kapcsán, amit meg kell mutatnom. A helyzet az, hogy $A$ és $B$ esetében összesen 32 variáció van a fenti 2 alak miatt:

$\displaystyle Y_1 \rightarrow A+\left( A \cdot B \right)=A$ és $\displaystyle Y_2 \rightarrow B+\left( A \cdot B \right)=B$ alakú kifejezések:

Opciók	$Y_1$	$Y_2$
1	$\displaystyle A + \left( A \cdot B \right)=A$	$\displaystyle B + \left( A \cdot B \right)=B$
2	$\displaystyle \overline{A} + \left( A \cdot B \right)=\overline{A}+B$	$\displaystyle \overline{B} + \left( A \cdot B \right)=\overline{B}+A$
3	$\displaystyle A + \left( \overline{A} \cdot B \right)=A+B$	$\displaystyle B + \left( \overline{B} \cdot A \right)=A+B$
4	$\displaystyle \overline{A} + \left( \overline{A} \cdot B \right)=\overline{A}$	$\displaystyle \overline{B} + \left( \overline{B} \cdot A \right)=\overline{B}$
5	$\displaystyle A + \left( A \cdot \overline{B} \right)=A$	$\displaystyle B + \left( B \cdot \overline{A} \right)=B$
6	$\displaystyle A + \left( \overline{A} \cdot \overline{B} \right)=A+\overline{B}$	$\displaystyle B + \left( \overline{A} \cdot \overline{B} \right)=B+\overline{A}$
7	$\displaystyle \overline{A} + \left( A \cdot \overline{B} \right)=\overline{A} + \overline{B}$	$\displaystyle \overline{B} + \left( B \cdot \overline{A} \right)=\overline{A} + \overline{B}$
8	$\displaystyle \overline{A} + \left( \overline{A} \cdot \overline{B} \right)=\overline{A}$	$\displaystyle \overline{A} + \left( \overline{A} \cdot \overline{B} \right)=\overline{B}$

$\displaystyle Y_1 \rightarrow A\left( A+B \right)=A$ és $\displaystyle Y_2 \rightarrow B\left( A+B \right)=B$ alakú kifejezések:

Opciók	$Y_1$	$Y_2$
1	$\displaystyle A \cdot \left( A + B \right)=A$	$\displaystyle B \cdot \left( A + B \right)=B$
2	$\displaystyle \overline{A} \cdot \left( A+ B \right)=\overline{A} \cdot B$	$\displaystyle \overline{B} \cdot \left( A+ B \right)=\overline{B} \cdot A$
3	$\displaystyle A \cdot \left( \overline{A} + B \right)=A \cdot B$	$\displaystyle B \cdot \left( \overline{B} + A \right)=B \cdot A$
4	$\displaystyle \overline{A} \cdot \left( \overline{A} + B \right)=\overline{A}$	$\displaystyle \overline{B} \cdot \left( \overline{B} + A \right)=\overline{B}$
5	$\displaystyle A \cdot \left( A \cdot \overline{B} \right)=A$	$\displaystyle B \cdot \left( B \cdot \overline{A} \right)=B$
6	$\displaystyle A \cdot \left( \overline{A} + \overline{B} \right)=A \cdot \overline{B}$	$\displaystyle B \cdot \left( \overline{A} + \overline{B} \right)=B \cdot \overline{A}$
7	$\displaystyle \overline{A} \cdot \left( A + \overline{B} \right)=\overline{A} + \overline{B}$	$\displaystyle \overline{B} \cdot \left( B + \overline{A} \right)=\overline{A} + \overline{B}$
8	$\displaystyle \overline{A} \cdot \left( \overline{A} \cdot \overline{B} \right)=\overline{A}$	$\displaystyle \overline{B} \cdot \left( \overline{A} \cdot \overline{B} \right)=\overline{B}$

X.axióma – kettős tagadás

Ez a kifejezés a magyar nyelvtanban is megvan, matematikailag így fest: $\neg \neg A = A$ . A bizonyítása nagyon egyszerű direkt behelyetesítéssel:

Opciók	$A$	$\overline{A}$	$\neg \neg {A}$
1	$0$	$1$	$0$
2	$1$	$0$	$1$

A táblázatból egyértelműen látható, hogy a kettős tagadás után visszakaptuk az eredeti $A$ állítást $\blacksquare$ .

XI. axióma – De Morgan azonosságok

Vegyük a már jól ismert két azonosságot:

1. azonosság: $\displaystyle \overline{A \cap B} \stackrel{?}{=} \overline{A} \cup \overline{B}$ majd írjuk át erre: $\displaystyle \overline{A \cdot B} \stackrel{?}{=} \overline{A} + \overline{B}$
2. azonosság: $\displaystyle \overline{A \cup B} \stackrel{?}{=} \overline{A} \cap \overline{B}$ és írjuk ét ezt is: $\displaystyle \overline{A + B} \stackrel{?}{=} \overline{A} \cdot \overline{B}$

Most már szinte mindent tudunk, kettő dolog hiányzik már csak. Ezek közül az egyik a műveleti sorrend ÉS a gyakorlás.

Műveleti sorrend a Boole-algebrában

A műveleti sorrend nem csak a Boole-algebrában kritikus jelentőségű, hanem az egész matematikában. Biztosan láttál már különféle posztokat az interneten. ahol „zseninek” kell lenni, hogy megold a zárójeles egyenletet. Hogy őszinte legyek, nem tudom, mióta van a zsenilaitás mércéje ilyen alacsony szinten. Tehát műveleti sorrend – nem csak matematikai logika:

1) zárójel
2) negáció
3) ÉS
4) VAGY

Az esetek zömében kapsz majd egy $Y$ kifejezést és ezt kell a lehető legegyszerűbb alakra hozni. Ebben a részben igazából megvan minden információ, amivel az ilyen matematikai logika feladatokat meg lehet oldani. Nem nagy ördöngősség, ha az alapok rendben vannak és van feladatmegoldási rutin. A következő részben adok szinte minden tpíuspéldához feladatokat.

Ha esetleg villamosmérnöki vonalon kötsz ki, ott az egész meg lesz bonyolítva még kapcsolási rajzzal is – legy egy rakás bemenet, kapcsoló aztán ezután kell felrajzolni a legegyszerűbb megoldást. Ennek az az értelme, hogy így a legfkevesebb áramköri elemet kell használni.

Feladatmegoldási stratégia

Írd ki magadnak az összes műveletet és axiómát egy lapra – ez hasznos lesz, amikor matematikai logika azni – ígyszerűbb a hibakeresés
Elnyelési szabály – legyél a mestere, egy csomó időt tudsz megspórolni, ami vizsgáln, ZH-n jól jön
Tisztán dolgozz, mindent egyértelműen jelölj!
Kerüld a szorzatnál az $x$ jelet – könnyen kaphatsz útközben egy plusz változót..
ABC sorrendben írd a tagokat egymás után
Bentről kifelé halajd – minden műveletet végezz el a zárójelen belül a műveleti sorrend szabályainak betartásával és csak ezután bontsd fel a zárójelet

Feladatok a matematikai logika részhez következő bejegyzésben

Matematikai logika