Logikai függvények

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

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}ⁿ 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 2²ⁿ, hiszen az n változó 2ⁿ darab lehetséges értékének mindegyikéhez két értéket rendelhetünk.

Egyváltozós logikai függvények

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

Identitás, változatlanul hagyás q id(q) 0 0 1 1

Negáció, ellentét q nem(q) 0 1 1 0

Konstans 1 q 1 0 1 1 1

Konstans 0 q 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 (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 0 vagy az azonosan hamis leképezés, mely mindenhez a 0-t rendeli.

Ezek közül külön figyelmet érdemel a tagadás, más néven nem vagy NOT operáció, melyet a gyakorlati életben is használnak.

Általában felülvonással jelöljük: ${\overline {q}}$.

Az előbbiből kiindulva:

${\overline {\overline {q}}}=q$ (a dupla tagadás megegyezik az identitással),

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

${\overline {0}}=1$.

Kétváltozós logikai függvények

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,&{\text{ha }}x=1{\text{ és }}y=1,\\x+y,&{\text{ha }}x\neq 1{\text{ vagy }}y\neq 1\end{cases}}$, ahol a második összeadás a számok összeadása (kivéve 1 + 1 esetén, ami itt 1 lesz).

Logikai szorzás, és $\cdot$ 0 1 0 0 0 1 0 1

Logikai összeadás, vagy $+$ 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}}$ és

${\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.

Kapcsolódó szócikkek

• Boole-algebra (informatika)