Kezdőlap


Cím:	A matematikai logika logikusabb, mint gondolnánk II.
Füzet:	2022/március, 159 - 164. oldal	PDF \| MathML
Témakör(ök):	Számítástechnika, informatika, Szakmai cikkek, Számítástudomány

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Ha alaposan megfigyeljük a cikk első részében kapott ábrát, egy további nyereséget is elkönyvelhetünk: ahogy az algebrában, úgy a logikában is vannak azonosságok. Ezek egyike-másika közismert, ahogy az algebrában is vannak nevezetes azonosságok, például ${(a + b)}^{2} = a^{2} + 2 a b + b^{2}$ . A logikában ilyen a $\neg (A^B) = \neg A \lor \neg B$ , vagy $(A \to B)^(B \to A) = A \Leftrightarrow B$ .
Ez utóbbi kapcsán felmerül, hogy miként lehet összetettebb logikai kifejezéseket egyszerűbb alakra hozni. Nos, ez egyáltalán nem bonyolult. A könnyebb megértés kedvéért foglaljuk táblázatba az öt alapművelet eredményének szabályát. Elég csak az egyik állapotot megjegyezni, a többi esetben mindig a tagadása lesz az eredmény: az és művelet igaz, ha mind a két részállítás igaz, a vagy művelet hamis, ha mind a két részállítás hamis, a kizáró vagy művelet igaz, ha a két részállítás logikai értéke különböző, az azonosság művelet igaz, ha a két részállítás logikai értéke azonos, végül a következtetés művelet hamis, ha az, amiről következtetünk igaz, de az, amire következtetünk hamis. Összefoglalva:

Végezetül a tagadások okozta cseréket is rendszerezzük:

\begin{matrix} amit tagadunk & mozgatás \\ A & oszlopcsere (OCS) \\ B & sorcsere (SCS) \\ AésB & átlós csere (ÁCS) \\ a művelet & betűcsere (BCS) \end{matrix}

Az összetett állításoktól a számítógépig

A formalizálás banálisan egyszerű, a szomszédos ábra a modell.

A bal felső részbe a bal oldalon lévő kifejezés

(A^B)

, a jobb felső részbe pedig a jobb oldali

(B \to A)

logikai sakktáblában található értékei kerüljenek, ezeket a középső mező négy szegmensének bal és jobb felső részébe másoljuk át, középre pedig a két oldal közötti művelet jelét

(\otimes)

illesszük be.
Ezek után szegmensenként külön-külön értékeljük ki a műveleti szabályokban foglaltak alapján:

i \otimes i

(= h)

h \otimes h

(= h)

h \otimes i

(= i)

és

h \otimes i

(= i)

.
Az eredményt rögzítsük az eddig üres cellákba, majd a logikai sakktáblában keressük ki, hogy ez melyik művelet értéktáblázata

(\neg B)

Másik magyarázó példaként álljon itt az

(A \to B)^(B \to A) = A \Leftrightarrow B

nevezetes logikai azonosság igazolása.

Nézzük meg egy olyan kifejezés kiértékelését, ahol az előbbieket kicsit módosítva jutunk el a megoldáshoz.
Egyszerűsítsük le a

\begin{matrix} \neg (B \to \neg A)^(\neg B \to \neg A) \end{matrix}

kifejezést. Elsőre talán ijesztőnek tűnhet, de a tagadásokat könnyen megoldhatjuk cserékkel.

Egyszer érdemes belegondolni, hogy ez mit is jelent. A cikk előző részében az

A

állítás az volt, hogy Kedd van, a

B

állítás pedig az, hogy Esik az eső. Ezeket felhasználva ez a kifejezés így szól: Nem igaz az, hogy, ha esik az eső, akkor nem kedd van, és ha nem esik az eső, akkor nem kedd van. Leegyszerűsítve: Kedd van és esik az eső.

A vállalkozó kedvűeknek ajánlok néhány feladatot:

(A^B) \lor (A \otimes B)

(A \lor B)^(B \to A)

\neg (B \to A) \otimes A

(A \Leftrightarrow B) \Leftrightarrow \neg A

(A \lor \neg B) \to \neg (\neg A \lor B)

\neg [A \to (A \otimes B)]

[\neg B \otimes (A^B)]^[B \to \neg (A^B)]

Ideje rátérnünk arra, hogy ez az egész miként kapcsolódik a számítógépekhez.
A számítógépek elektromos árammal működnek. És nem csak energiaforrásként használják az elektromos energiát, az információt is elektromosan továbbítják. Feldolgozáskor a leggyorsabb eldöntési technika a nyerő, márpedig az elektromos technológiában a folyik vagy nem folyik áram eldöntése lényegesen gyorsabb és még egyszerűbb is, mint az áram nagyságát megmérni. Ez két állapot megkülönböztetését jelenti, tehát a kétállapotú rendszerek használata gyorsabb és egyszerűbb is.
Ilyen rendszert kettőt is ismerünk, a matematikai logika igaz/hamis rendszere és a kettes számrendszer, ahol két különböző számjegy, a

0

és az

1

létezik. Már az elektronika hajnalán képesek voltak olyan áramköröket készíteni, amelyek modellezik a logikai műveleteket, ezeket logikai kapuknak nevezik. A teljesség igénye nélkül említsünk meg néhányat. A tagadás megfelelője az egy bemenettel és egy kimenettel rendelkező NOT kapu, a kimenetén folyik áram, ha a bemenetén nem, és a kimeneten nem folyik áram, ha a bemeneten igen. A két bemenettel és egy kimenettel rendelkező AND, OR, XOR kapu pedig az és, a vagy és a kizáró vagy művelet szabálya szerint működik.
A számítógép neve a számításra és nem a matematikai logikára utal, hiszen akkor talán ítélőgépnek hívnánk. De az állítások kiértékelése a mindennapokban sokkal kisebb szerephez jut, mint a számítások elvégzése. Abba azonban ritkán gondolunk bele, hogy a kettes számrendszerben mennyire egyszerű a műveletek elvégzése, ezért ehhez mondanék néhány adalékot.
A kettes számrendszerben az összeadás és a szorzás szabálya is elég egyszerű egy számjegy esetén, akár egy sorban el is mondható:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

és

1 + 1 = 0

, valamint

0 \cdot 0 = 0

0 \cdot 1 = 0

1 \cdot 0 = 0

és

1 \cdot 1 = 1

.
Az algebra szabályai függetlenek a számrendszertől: a számrendszer alapszámának

k

-adik hatványával szorzás

k

darab

0

számjegynek a szám végére írását jelenti, így például kettes számrendszerben az

101_{2} (= 5_{10})

kétszerese, négyszerese, nyolcszorosa:

1010_{2}

10100_{2}

és

101000_{2}

.
A kettes számrendszerben a szorzás könnyen kiváltható összeadással. Az egyik tényező kettes számrendszerbeli alakja pont azt mutatja meg a különböző helyiértékeken álló

1

számjegyeivel, hogy a másik tényezőnek melyek azok kettőhatványszorosai, amelyeket össze kell adnunk. Nézzük meg a

9 \cdot 11_{10}

szorzást.

\begin{matrix} 1001 \cdot 1011_{2}. Ebben az1011_{2}szám egyszeresét és nyolcszorosát kell összeadni, hiszen9 = 1 + 8_{10}. \\ Csak három nullát kell a végére biggyeszteni, hogy meglegyen a nyolcszoros, és azt az eredetivel összeadni.101000_{2} + 1011_{2}. \end{matrix}

Ez valóban nagy könnyebbség, csak ki kell dolgozni azokat az áramköröket, amelyek kettes számrendszerben elvégzik az összeadást. Vagy mégsem?
Nem bizony.
Elég csak szemrevételezni az alábbi ábrát, és feltűnik, hogy az imént említett AND és XOR logikai kapuk lehetővé teszik az összeadást. Tehát nem kell ezeket kidolgozni, hiszen ezek a logikai kapuk már megvannak.

Ha elég sok, elég apró és elég gyors logikai kaput tudunk összedolgozni, akkor a

9 \cdot 11_{10}

szorzásnál lényegesen összetettebb műveleteket is el tudunk végezni.
És a mikroprocesszor icipici logikai kapuk millióit hordozza, és többszáz milliárd műveletre képes másodpercenként, ezért tudnak ezek a gépek többféle, az ember számára bonyolult vagy unalmas munkát kiváltani.
Ezért is érdemes legalább egy főhajtással tisztelegni George Boole (1815. november 2. ‐1864. december 8.) angol matematikus előtt, aki lerakta a matematikai logika alapjait.

Az arckép forrása:
https://www.sciencephoto.com/media/223560/view/english-mathematician-george-boole.