Logikai függvények

A Wikipédiából, a szabad enciklopédiából

A logikai függvények olyan matematikai leképezések, melyek a 0 és 1 számokból álló véges sorozatokhoz rendelik a 0 vagy 1 számot. Alkalmazásait tekintve kiemelkedőnek tekinthető a logika igaz-hamis értékeléseinek modellezése (ítéletlogika) és a digitális számítógépek elemi szintű működésének leírása.

A digitális számítógépek munkamódszerének és felépítésének megértéséhez szükség van a logikai függvény fogalmára.

Fogalmak, tételek[szerkesztés | forrásszöveg szerkesztése]

Egy logikai függvény tehát olyan n változós függvény, melynek változói a {0,1} halmazból vehetnek fel értéket, a függvényérték pedig szintén a {0,1} halmazból valók. Itt az 1 értékre gyakran mint az igaz, a 0 értékre mint a hamis hivatkoznak (főleg logikai alkalmazásaiban). Formálisan, a {0,1}n Descartes-szorzat segítségével egy f függvény logikai, ha:

f:\{0,1\}^n\rightarrow\{0,1\}

Az n változós logikai függvények száma 22n, hiszen az n változó 2n darab lehetséges értékének mindegyikéhez két értéket rendelhetünk.

Egyváltozós logikai függvények[szerkesztés | forrásszöveg szerkesztése]

Az egyváltozós logikai függvények a következők:

id
0 0
1 1
nem
0 1
1 0
1
0 1
1 1
0
0 0
1 0

Tehát az identitás leképezés, mely minden értékhez saját magát rendeli, a tagadás (nem), mely minden értékhez az ellenkezőjét rendeli (értsd: a 0-hoz az 1-et, az 1-hez a 0-t), az 1 vagy az azonosan igaz leképezés, mely mindenhez az 1-et rendeli és a a 0 vagy az azonosan hamis leképezés, mely mindenhez az 0-t rendeli.

Ezek közül külön figyelmet érdemel a tagadás, nem vagy NOT operáció, melyet általában felülvonással jelölünk. Az x logikai érték (tehát 0 vagy 1) tagadása:

\overline{x}

Értelemszerűen tehát:

\overline{\overline{x}}=x,
\overline{1}=0,
\overline{0}=1

Kétváltozós logikai függvények[szerkesztés | forrásszöveg szerkesztése]

A 16 kétváltozós logikai függvény közül csak a nemtriviálisakat említjük. Minthogy ezek {0,1} × {0,1} \rightarrow {0,1} típusú függvények, ezért ezek kétváltozós műveleteknek is tekinthetők.

  • Logikai szorzás (más néven és vagy AND művelet)
x\cdot y:=x\cdot y\,, ahol a második szorzás a számok szorzása.
  • Logikai összeadás (más néven vagy illetve OR művelet)
x+y \ =  
 \ \begin{cases} \ 1, & \mbox{ha }x=1, y=1, \\ x+y, & \mbox{ha } x\ne 1 \mbox{ vagy } y\ne 1\end{cases} , ahol a második összeadás a számok összeadása.
\cdot 0 1
0 0 0
1 0 1
+ 0 1
0 0 1
1 1 1

Ezen két művelet közötti triviális kapcsolatot írja le az alábbi két, úgy nevezett de Morgan-azonosság:

\overline{x\cdot y}=\overline{x}+\overline{y},
\overline{x+ y}=\overline{x}\cdot\overline{y}

Azért elegendő ez a két művelet, mert minden logikai függvény előállítható pusztán kétváltozós műveletekkel:

Tétel – Akárhányváltozós logikai függvény felírható a tagadás és a logikai összeadás (vagy a tagadás és a logikai szorzás) segítségével.

Lásd még[szerkesztés | forrásszöveg szerkesztése]