Ugrás a tartalomhoz

A matematikai logika alkalmazásszemléletű tárgyalása

Pásztorné Varga Katalin, Várterész Magda, Sági Gábor

Panem Kft.

Az ítéletlogika strukturális tulajdonságairól

Az ítéletlogika strukturális tulajdonságairól

Hálók és Boole-algebrák

A matematikai struktúrák közül a hálók és Boole-algebrák igen fontos szerepet játszanak a logikai kutatásokban. Ebben a részben az ítéletlogikával kapcsolatban foglalkozunk velük.

4.5.1. DEFINÍCIÓ. Egy U;=;, matematikai struktúrát hálónak nevezünk, ha és binér műveletek U-n és eleget tesznek az ún. hálóaxiómáknak, azaz tetszőleges x,y,zU-ra

( 1 )

x y = y x

( 2 )

x y = y x

(kommutativitás)

( 3 )

( x y ) z = x ( y z )

( 4 )

( x y ) z = x ( y z )

(asszociativitás)

( 5 )

x ( x y ) = x

( 6 )

x ( x y ) = x

(abszorptivitás)

Vegyük észre, hogy (1) és (2), (3) és (4), illetve (5) és (6) kölcsönösen átírhatók egymásba a és a műveletek felcserélésével. Emiatt mondjuk, hogy a két hálóművelet egymás duálisa. Ha a háló nyelvén leírt kifejezésben rendre felcseréljük a hálóműveleteket egymással, az új kifejezést az eredeti kifejezés duálisának nevezzük. Ez azt jelenti, hogy például az (1) és a (2) hálóaxiómák, a (3) és a (4) hálóaxiómák és az (5) és a (6) hálóaxiómák egymás duálisai. Tehát a hálóaxiómákat duálisukra cserélve visszakapjuk az eredeti axiómarendszert. Ezért fennáll a hálóelméleti dualitás elve, miszerint a hálóelmélet minden igaz formulájának duálisa (a hálóműveletek felcserélésével kapott formula) is igaz formula. Ennek az az oka, hogy a hálóelmélet egy igaz formulája mindig következménye a hálóaxiómáknak.

Az (5) és a (6) axiómák következménye például, hogy mindkét hálóművelet idempotens. Az idempotencia tulajdonságot így nem soroltuk a hálóaxiómák közé.

4.5.2. LEMMA. Egy U;=;, hálóban a és a műveletek idempotensek, azaz tetszőleges xU-ra

x x = x és x x = x .

BIZONYÍTÁS. idempotenciája a következőképpen igazolható. Ha (6)-ban y helyébe xx-et helyettesítünk, az x(x(xx))=x kifejezést kapjuk. De (5) szerint x(xx)=x. Írjunk be az x-et az x(xx) helyett az előző kifejezésbe, és megkapjuk, hogy xx=x. A másik műveletre az idempotenciát a dualitás miatt nem kell bizonyítani.

4.5.3. DEFINÍCIÓ. Legyen U; gyönge részbenrendezett halmaz és X az U nemüres részhalmaza. Az aU elemet az Xalsó korlátjának nevezzük, ha minden xX-re ax. X-nek egy a alsó korlátja Xlegnagyobb alsó korlátja (infimuma), ha X tetszőleges a alsó korlátjára aa. a jelölése inf X. Továbbá a bU elemet az Xfelső korlátjának nevezzük, ha minden xX-re xb. X-nek egy b felső korlátja Xlegkisebb felső korlátja (szuprémuma), ha X tetszőleges b felső korlátjára bb. b jelölése sup X.

Általában U nem minden részhalmazának van legnagyobb alsó vagy legkisebb felső korlátja, de ha van, akkor egyértelmű.

4.5.4. DEFINÍCIÓ. Egy U; gyönge részbenrendezett halmazt (relációrendszert) hálónak nevezünk, ha U bármely kételemű részhalmazának van legnagyobb alsó és legkisebb felső korlátja. Ha U bármely nemüres részhalmazának van legnagyobb alsó és legkisebb felső korlátja, akkor a háló teljes háló.

Minden háló – mint részbenrendezett halmaz – ábrázolható hálódiagrammal. A hálódiagram a hálókat jól jellemzi, de a hálódiagram részhálót megadó részletei is fontos információkat tartalmaznak.

4.5.5. DEFINÍCIÓ. Az U; háló hálódiagramjában (Hasse-diagramjában) U elemei csúcsok és az ul csúcsból az uk csúcsba akkor vezet él, ha a rendezés szerint ul és uk szomszédos elemek, azaz ha uluk fennáll, de nincs olyan uj, hogy uluj és ujuk fennállna. Ekkor azt is mondjuk, hogy uklefediul-t.

Az előzőekben a hálóra kétféle definíciót adtunk, most megmutatjuk, hogy a két definíció ekvivalens. Egy – relációrendszerként megadott – rH háló relációja alapján az univerzumon két binér műveletet definiálva előállítunk egy mrH matematikai struktúrát. Egy – matematikai struktúraként definiált – mH háló két binér művelete bármelyikének felhasználásával pedig az univerzumon egy-egy binér relációt definiálunk és így előállítunk egy rmH relációrendszert.

  1. Definiáljuk először az rH-val jelölt U; háló rendezési relációja alapján a következő két binér műveletet:

x y inf   { x , y } és x y sup   { x , y } .

Könnyen belátható, hogy az így definiált műveletek eleget tesznek a háló−axiómáknak, vagyis hálóműveletek.

( 1 ) inf   { x , y } = inf   { y , x } ( 2 ) sup   { x , y } = sup   { y , x } ( 3 ) inf   { inf   { x , y } , z } = inf   { x , inf   { y , z } } ( 4 ) sup   { sup   { x , y } , z } = sup   { x , sup   { y , z } } ( 5 ) inf   { x , sup   { x , y } } = x ( 6 ) sup   { x , inf   { x , y } } = x

A kapott – matematikai struktúraként előálló – hálót jelöljük mrH-val.

  1. Most megmutatjuk, hogy egy mH-val jelölt U;=;, háló egyes hálóműveleteivel a következő módon definiált R és R binér relációk gyönge rendezési relációk, és hogy tetszőleges x,yU elempárnak van az egyes relációk szerinti legnagyobb alsó és legkisebb felső korlátja. A relációk definíciója legyen a következő: tetszőleges x,yU-ra

    1. x R y pontosan akkor álljon fenn, ha xy=x,

    2. x R y pedig pontosan akkor teljesüljön, ha xy=x.

R a , R a művelet kommutativitása miatt antiszimmetrikus, idempotenciája miatt reflexív és asszociativitása miatt tranzitív. R és R tehát gyönge rendezési relációk U-n, ún. duális rendezési relációk. Most belátjuk, hogy tetszőleges x,yU esetén az {x,y} halmaz legnagyobb alsó korlátja az R szerint xy. A (3) axióma és az idempotencia miatt

( x y ) y = x ( y y ) = x y ,

azaz (xy)Ry. (1), (3) és az idempotencia miatt

( x y ) x = ( y x ) x = y ( x x ) = y x = x y ,

azaz (xy)Rx. Ennek megfelelően xy az {x,y} halmaz alsó korlátja. Ha z is alsó korlát, vagyis zx=z és zy=z, akkor

z ( x y ) = ( z x ) y = z y = z ,

tehát zR(xy). Ez azt jelenti, hogy xy valóban a legnagyobb alsó korlátja az {x,y} halmaznak, vagyis xy éppen az R szerinti inf {x,y}.

Hasonlóan bizonyítható, hogy az {x,y} halmaz legkisebb felső korlátja az R szerint xy, vagyis xy éppen az R szerinti sup {x,y}. Tehát U bármely kételemű részhalmazának van legnagyobb alsó és legkisebb felső korlátja, vagyis az U;R az 4.5.4. definíció szerint háló. A dualitás miatt nem kell bizonyítani, hogy U;R szintén háló.

A relációrendszerként kapott hálót jelöljük rmH-val.

  1. Tekintsünk egy mH hálót. Belátjuk, hogy mH=mrmH. A két hálóművelet alapján definiált két reláció egymás duálisa, ezért ha valamely x,yU esetén xRy, akkor yRx. Legyen az rmH háló U;=,R;,. Fentebb beláttuk, hogy tetszőleges x,yU elempár R szerinti legnagyobb alsó korlátja éppen xy és legkisebb felső korlátja éppen xy. Vegyük most az mrmH hálót. Ebben a hálóban a hálóműveletek az R szerinti inf {x,y} és sup {x,y} lesznek, amelyek – mint láttuk – rendre az eredeti és műveletek.

  2. Tekintsünk egy rH hálót. Belátjuk, hogy rH=rmrH. Az mrH háló a következő lesz: U;;inf {x,y},sup {x,y}. Vizsgáljuk most az rmrH hálót. Az az R binér reláció, amelyet az inf {x,y} alapján a ,,ha x=inf {x,y}, akkor xRy” definícióval adunk meg, éppen az eredeti reláció.

4.5.6. DEFINÍCIÓ. Az U;=;, háló disztributív háló, ha a két hálóművelet egymásra nézve kölcsönösen disztributív, azaz minden x,y,zU-ra

( 7 )   x ( y z ) = ( x y ) ( x z ) ( 8 )   x ( y z ) = ( x y ) ( x z )

A következő példán illusztráljuk, hogy nem minden háló disztributív. Tekintsük az alábbi ábrán látható Hasse-diagramokat.

Figure 4.12. Hasse-diagramok

Hasse-diagramok

Ezek valóban hálók, de nem disztributív hálók. Mindkét diagram szerinti rendezésre ugyanis sup {b,inf {c,d}}=b, viszont a 4.12(a) diagram szerint

inf   { sup   { b , c } , sup   { b , d } } = d

és a 4.12(b) diagram szerint pedig

inf   { sup   { b , c } , sup   { b , d } } = e ,

tehát a disztributivitási axiómák nem állnak fenn. Ebből világos, hogy egy disztributív hálónak nem lehet sem a 4.12(a) ábrán, sem a 4.12(b) ábrán lévő Hasse-diagrammal ábrázolható részhálója. Birkhoff 1934-ben igazolta, hogy ennek megfordítása is igaz, vagyis egy háló akkor és csak akkor disztributív, ha részhálóinak egyike sem ábrázolható sem a 4.12(a) ábrán, sem a 4.12(b) ábrán látható Hasse-diagrammal [9].

Ha az R rendezés szerint U-nak van legkisebb eleme, azaz olyan aU, hogy minden xU-ra aRx, és van legnagyobb eleme, azaz olyan bU, hogy minden xU-ra xRb, akkor a háló korlátos. A korlátos háló legkisebb elemét jelölje min, a legnagyobb elemét pedig max (A korlátos háló legkisebb elemét szokták nullelemnek, a legnagyobb elemét pedig egységelemnek is nevezni.)

4.5.7. DEFINÍCIÓ. Az U;=;, korlátos háló valamely a elemének komplementuma egy olyan xU elem, amelyre

a x = min   és a x = max   .

Abból, hogy egy háló korlátos, nem következik, hogy minden elemének lenne komplementuma, és az sem, hogy ha egy elemének van komplementuma, akkor legfeljebb egy komplementuma lenne. Azt az a elemet, amelynek van legalább egy komplementuma, a háló komplementumos elemének, ha pedig a-nak pontosan egy komplementuma van, akkor a háló egyértelműen komplementumos elemének nevezzük. Ha a háló minden eleme komplementumos (egyértelműen komplementumos), akkor azt mondjuk, hogy a háló komplementumos (egyértelműen komplementumos).

Figure 4.13. Komplementumos háló Hasse-diagramja

Komplementumos háló Hasse-diagramja

4.5.8. PÉLDA. A 4.13. ábrán látható hálóban az a elem egyértelműen komplementumos, egyetlen komplementuma e. Az e elem viszont nem egyértelműen komplementumos, mert komplementuma a is és c is.

Birkhoff disztributivitási kritériumának következménye, hogy egy korlátos disztributív háló minden elemének legfeljebb egy komplementuma van [64]. Ha tehát egy U;=;, korlátos disztributív háló komplementumos, akkor egyértelműen komplementumos. Ebben az esetben van olyan k:UU függvény, amely a háló minden eleméhez annak komplementumát rendeli. Az így kapott U;=;k,, matematikai struktúrában teljesülnek az ún. komplementum axiómák, azaz tetszőleges xU-ra

( 9 )   x k ( x ) = min   ( 10 )   x k ( x ) = max   .

4.5.9. DEFINÍCIÓ. Boole-algebrának nevezzük a disztributív, egyértelműen komplementumos hálókat.

Az (1)(10) axiómákból következnek – tehát minden Boole-algebrában érvényesek – a De Morgan-azonosságok.

4.5.10. LEMMA. Egy U;=;k,, Boole-algebrában minden x,yU-ra

k ( x y ) = k ( x ) k ( y ) é s k ( x y ) = k ( x ) k ( y ) .

BIZONYÍTÁS. Bizonyítsuk be az első azonosságot. Ha k(x)k(y) valóban komplementuma xy-nak, akkor (9) és (10) bal oldalán behelyettesítve a két kifejezést, a min, illetve a max elemet kellene kapjuk. (9) bal oldalán behelyettesítés után az

( x y ) ( k ( x ) k ( y ) )

kifejezés áll, ami (7) miatt

( ( x y ) k ( x ) ) ( ( x y ) k ( y ) ) .

Alkalmazva (1)-et és (3)-at, ebből az

( ( x k ( x ) ) y ) ( x ( y k ( y ) )

kifejezést nyerjük. (9) miatt ez (min y)(xmin ), ami (8)-at alkalmazva a

( ( min   y ) x ) ( ( min   y ) min   )

kifejezést adja. De (2) és (6) miatt ez épp

( ( min   y ) x ) min   .

Megint alkalmazzuk (1)-et és (7)-et, így nyerjük, hogy

( ( min   y ) min   ) ( x min   ) ,

majd pedig megint (1)-et és (5)-öt alkalmazva kapjuk, hogy min (xmin ). Végül még egyszer (6) alkalmazásával megkapjuk az eredményt: min. Hasonlóan járhatunk el a (10) axiómába való helyettesítés után.

A másik De Morgan-azonosság ennek duálisa, tehát a dualitás elve miatt fennáll.

A továbbiakban megmutatjuk, hogy egy hatványhalmaz a relációval és az {i,h} halmaz a ¬,, műveletekkel Boole-algebrát alkot.

A hatványhalmazok mint Boole-algebrák

Legyen H tetszőleges halmaz, jelölje a ,,részhalmaz” gyönge rendezési relációt, és legyen U=P(H). Egyszerű belátni, hogy az U; gyönge részbenrendezett halmaz háló. Ha {x,y} legfeljebb kételemű részhalmaza U-nak, akkor a

{ h H | h x és h y } U

halmaz épp ennek legnagyobb alsó korlátja, és a

{ h H | h x vagy h y } U

halmaz pedig épp a legkisebb felső korlátja.

Állítsuk most elő a két hálóműveletet: xyinf {x,y} és xysup {x,y}. Ezek a műveletek a hálóaxiómáknak nyilván eleget tesznek: minden x,y,zU esetén

( 1 ) x y = y x ( 2 ) x y = y x ( 3 ) ( x y ) z = x ( y z ) ( 4 ) ( x y ) z = x ( y z ) ( 5 ) x ( x y ) = x ( 6 ) x ( x y ) = x

Könnyű továbbá belátni, hogy a két művelet egymásra nézve kölcsönösen disztributív, tehát minden x,y,zU-ra

( 7 ) x ( y z ) = ( x y ) ( x z ) ( 8 ) x ( y z ) = ( x y ) ( x z ) .

Az U;=;; struktúra tehát disztributív háló. U-nak van legkisebb eleme, az üres halmaz, van legnagyobb eleme, a H halmaz. Definiáljunk U-n egy unér műveletet: x¯{hH|hx}. Ekkor minden xU esetén

( 9 ) x x ¯ = ( 10 ) x x ¯ = H

tehát x¯ az x komplementuma. Ezzel beláttuk, hogy az U;=; ¯;; matematikai struktúra Boole-algebra.

Az igazságértékek Boole-algebrája

Legyen U az igazságértékek {i,h} halmaza, legyenek és U-n értelmezett binér logikai műveletek, a konjunkció és a diszjunkció. Vizsgáljuk most az U;=;, struktúrát. A művelettáblák felhasználásával – hosszadalmasan ugyan, de egyszerűen – be lehet látni, hogy a és a logikai műveletek teljesítik a hálóaxiómákat, azaz tetszőleges X,Y,ZU-ra igaz, hogy

( 1 ) X Y = Y X ( 2 ) X Y = Y X ( 3 ) ( X Y ) Z = X ( Y Z ) ( 4 ) ( X Y ) Z = X ( Y Z ) ( 5 ) X ( X Y ) = X ( 6 ) X ( X Y ) = X

Például az (5) és a (6) belátásához megmutatjuk, hogy tetszőleges YU mellett a bal és a jobb oldal ugyanaz az igazságérték. Ha X épp i, akkor i(iY)=i és i(iY)=i. Ha pedig Xh, akkor h(hY)=h és h(hY)=h.

A két művelet egymásra nézve kölcsönösen disztributív is, azaz tetszőleges X,Y,ZU-ra igaz, hogy:

( 7 ) X ( Y Z ) = ( X Y ) ( X Z ) ( 8 ) X ( Y Z ) = ( X Y ) ( X Z )

A bizonyítást itt is a és a művelettáblái felhasználásával végezhetjük el. A (7) fennáll, mivel a bal oldal akkor i, ha X épp i és Y,Z közül legalább az egyik i, valamint a jobb oldal is akkor i, ha X épppen i és Y,Z közül legalább az egyik i. A (8) is fennáll, mivel a bal oldal akkor h, ha X épp h és Y,Z közül legalább az egyik h, valamint a jobb oldal akkor h, ha Xh és Y,Z közül legalább az egyik h. Az U;=;, struktúra tehát disztributív háló.

Definiáljunk rendezést a konjunkció segítségével az U halmazon. hi, mert ih=h. E rendezés szerint U legkisebb eleme h és legnagyobb eleme i. A komplementumképző művelet a negáció, hiszen minden xU-ra

( 9 ) X ¬ X = h ( 10 ) X ¬ X = i

Tehát az U;=;¬,, struktúra Boole-algebra.

4.5.11. MEGJEGYZÉS. A diszjunkcióval definiált rendezés (vagyis a duális rendezés) szerint ih, mert ih=i. Ekkor a legkisebb elem az i és a legnagyobb elem a h.

Az ítéletlogika műveleteinek tulajdonságairól

Mint azt már láttuk, egy n-változós formula igazságtáblája egy olyan n+1 oszlopot és 2n sort tartalmazó táblázat, amelynek a fejlécében az n ítéletváltozó (prímformula) adott sorrendben, valamint a formula szerepel. A sorokban az ítéletváltozók alatt az {i,h} halmaz elemeiből álló összes lehetséges igazságérték n-es mindegyike pontosan egyszer fordul elő mint az ítéletváltozók interpretációi, továbbá a formula alatt a formulának az illető sorban lévő interpretációbeli helyettesítési értéke szerepel. Mivel egy halmaz önmagával való n-szeres Descartes-szorzata a halmaz elemeiből kialakítható összes lehetséges rendezett n-esek halmaza, az n-változós formula igazságtáblájának soraiban lévő igazságérték n-esek halmaza az {i,h}n halmaz.

Egy n-változós formula igazságtáblája tehát egy {i,h}n{i,h} logikai műveletet ad meg, amit a formula által leírt logikai műveletnek neveztünk. Egy n-változós formula tehát az általa leírt n-változós logikai művelettel azonosítható. Mivel egy n-változós formula egy olyan összetett állításséma, amelyben n egyszerű állítást helyettesítő ítéletváltozó fordul elő, az összetett állítássémákat osztályozhatjuk úgy, hogy közülük azokat, amelyek ugyanazt a logikai műveletet írják le, egy osztályba soroljuk. Ennek megfelelően a különböző – n-változós formulákat tartalmazó – osztályok száma nem nagyobb, mint ahány különböző n-változós logikai művelet van, vagyis mint 22n.

Tekintsük az ítéletlogika összes (jólformált) formuláinak a halmazát. Megállapítottuk, hogy egy összetett állítás alapján felírt formula egy logikai művelettel azonosítható. Ezért mondhatnánk azt is, hogy a logikai műveletek vizsgálatához foglalkozzunk az ítéletlogika (jólformált) formuláinak a halmazával. Ebben az esetben fel kell tenni azt a kérdést, hogy vajon tetszőleges {i,h}n{i,h} logikai művelethez hozzá tudunk-e rendelni legalább egy olyan formulát, ami azt a műveletet leírja. Más szóval a probléma az, hogy az általunk kiválasztott ¬, , és logikai összekötőjelekkel és ítéletváltozókkal elő lehet-e minden n-változós logikai művelethez a műveletet leíró formulát állítani.

4.5.12. DEFINÍCIÓ. A logikai műveletek egy halmazát funkcionálisan teljesnek nevezzük, ha e műveleteknek megfelelő logikai összekötőjeleknek és ítéletváltozóknak a felhasználásával tetszőleges {i,h}n{i,h} logikai művelethez meg lehet konstruálni egy a műveletet leíró formulát.

A következőkben belátjuk, hogy bármely n-változós logikai művelet leírható csak a ¬, a és a logikai összekötőjeleket tartalmazó formulával. Ez azt jelenti, hogy a {¬,,} művelethalmaz funkcionálisan teljes. Ennek felhasználásával azt is igazolni fogjuk, hogy a {¬,}, {¬,} és {¬,} művelethalmazok is funkcionálisan teljesek. Végül bizonyítjuk, hogy a {,,i} művelethalmaz is funkcionálisan teljes, vagyis tetszőleges n-változós logikai művelet leírható e három művelet felhasználásával, azaz ún. Zsegalkin-alakban. Ez az alak főleg a kriptográfiában használatos a kulcsok vizsgálatánál [19], de nagy jelentősége van a Boole-függvények elméletében a függvényanalízis során [66] is.

4.5.13. DEFINÍCIÓ.

  1. Egy prímformulát (ítéletváltozót) vagy annak a negáltját közös néven literálnak nevezünk. A prímformulát a literál alapjának hívjuk. Egy literált esetenként egységkonjunkciónak vagy éppen egységdiszjunkciónak (egységklóznak) is fogunk nevezni.

  2. Elemi konjunkció az egységkonjunkciót és a különböző alapú literálok konjunkciója, elemi diszjunkció vagy klóz pedig az egységdiszjunkció és a különböző alapú literálok diszjunkciója. Egy elemi konjunkció, illetve egy elemi diszjunkció teljes egy n-változós logikai műveletre nézve, ha mind az n ítéletváltozó alapja valamely literáljának.

  3. Diszjunktív normálformának – röviden DNF-nek – nevezzük az elemi konjunkciók diszjunkcióját, konjunktív normálformának – röviden KNF-nek – pedig az elemi diszjunkciók (klózok) konjunkcióját. Kitüntetett a diszjunktív normálforma (KDNF), ha teljes elemi konjunkciók diszjunkciója, illetve kitüntetett a konjunktív normálforma (KKNF), ha teljes elemi diszjunkciók konjunkciója.

Logikai műveletet leíró KDNF és KKNF előállítása

A továbbiakban megadunk két algoritmust, amellyel tetszőleges b:{i,h}n{i,h} logikai művelethez meg lehet konstruálni egy a műveletet leíró – speciális alakú – formulát. A konstrukció eredménye kitüntetett diszjunktív, illetve konjunktív normálforma lesz. Adjuk meg először is a b művelet művelettábláját. Az első n oszlopba a művelettábla fejlécében írjuk be az X1,X2,,Xn ítéletváltozókat.

A b-t leíró kitüntetett diszjunktív normálforma előállítása:

  1. Válasszuk ki a művelettábla azon sorait, ahol az igazságérték n-eshez bi igazságértéket rendel. Legyenek ezek a sorok az s1,s2,,sr. Minden ilyen sorhoz rendeljünk hozzá egy X1X2Xn teljes elemi konjunkciót úgy, hogy az Xj literál Xj vagy ¬Xj legyen aszerint, hogy ebben a sorban Xj oszlopában az i vagy a h igazságérték szerepel. Az így nyert teljes elemi konjunkciók legyenek rendre ks1,ks2,,ksr.

  2. A ks1,ks2,,ksr teljes elemi konjunkciókból készítsünk egy diszjunkciós láncformulát. Az így kapott ks1ks2ksr formula kitüntetett diszjunktív normálforma.

Igazoljuk, hogy a ks1ks2ksr formula valóban a b logikai műveletet írja le. Először is vegyük észre, hogy a ksj teljes elemi konjunkcióhoz az sj sorban lévő interpretációbeli Boole-értékelés i igazságértéket, a többi interpretációbeli Boole-értékelés pedig h igazságértéket rendel. Tehát az s1,s2,,sr sorokbeli interpretációkban – mivel van olyan diszjunkciós tag, amely i igazságértékű – a KDNF helyettesítési értéke i. A többi sorban viszont a KDNF-ben szereplő minden teljes elemi konjunkció igazságértéke h, tehát a KDNF helyettesítési értéke h.

4.5.14. PÉLDA. Legyen a b:{i,h}3{i,h} logikai művelet művelettáblája:

X

Y

Z

b

a teljes elemi konjunkciók

i

i

i

h

i

i

h

i

X Y ¬ Z

i

h

i

h

i

h

h

i

X ¬ Y ¬ Z

h

i

i

i

¬ X Y Z

h

i

h

h

h

h

i

i

¬ X ¬ Y Z

h

h

h

i

¬ X ¬ Y ¬ Z

A b logikai műveletet leíró kitüntetett diszjunktív normálforma:

( X Y ¬ Z ) ( X ¬ Y ¬ Z ) ( ¬ X Y Z ) ( ¬ X ¬ Y Z ) ( ¬ X ¬ Y ¬ Z )

A b logikai műveletet leíró kitüntetett konjunktív normálforma előállítása:

  1. Válasszuk ki a művelettábla azon sorait, ahol az igazságérték n-eshez bh igazságértéket rendel. Legyenek ezek a sorok az s1,s2,,sr. Minden ilyen sorhoz rendeljünk hozzá egy X1X2Xn teljes elemi diszjunkciót úgy, hogy az Xj literál Xj vagy ¬Xj legyen aszerint, hogy ebben a sorban Xj oszlopában a h vagy az i igazságérték szerepel. Az így nyert teljes elemi diszjunkciók legyenek rendre ds1,ds2,,dsr.

  2. A ds1,ds2,,dsr teljes elemi diszjunkciókból készítsünk egy konjunkciós láncformulát. Az így kapott ds1ds2dsr formula kitüntetett konjunktív normálforma.

Igazoljuk, hogy a ds1ds2dsr formula valóban a b logikai műveletet írja le. Először is vegyük észre, hogy a dsj teljes elemi diszjunkcióhoz az sj sorban lévő interpretációbeli Boole-értékelés h igazságértéket, a többi interpretációbeli Boole-értékelés pedig i igazságértéket rendel. Tehát az s1,s2,,sr sorokbeli interpretációkban – mivel van olyan konjunkciós tag, amely h igazságértékű – a KKNF helyettesítési értéke h. A többi sorban viszont a KKNF-ben szereplő minden teljes elemi diszjunkció igazságértéke i, tehát a KKNF helyettesítési értéke i.

4.5.15. PÉLDA. Legyen a b:{i,h}3{i,h} logikai művelet művelettáblája:

X

Y

Z

b

a teljes elemi diszjunkciók

i

i

i

h

¬ X ¬ Y ¬ Z

i

i

h

i

i

h

i

h

¬ X Y ¬ Z

i

h

h

i

h

i

i

i

h

i

h

h

X Y ¬ Z

h

h

i

i

h

h

h

i

A b-t leíró kitüntetett konjunktív normálforma:

( ¬ X ¬ Y ¬ Z ) ( ¬ X Y ¬ Z ) ( X Y ¬ Z )

Az ítéletlogika mint Boole-algebra

Beláttuk, hogy a {¬,,} funkcionálisan teljes művelethalmaz. Ebből következik, hogy az n-változós ítéletlogikai formulák – ugyanazt a logikai műveletet leíró – osztályainak halmaza és az összes n-változós logikai műveletek halmaza kölcsönösen egyértelműen megfeleltethető egymásnak. Ezért az ítéletlogika alkalmas az összes logikai művelet tanulmányozására is.

Jellemezzük igazhalmazukkal a logikai műveleteket. Egy {i,h}n{i,h} művelet igazhalmaza az {i,h}n részhalmaza, tehát az összes {i,h}n{i,h} logikai művelet igazhalmazainak halmaza a P({i,h}n) hatványhalmaz. Mint korábban láttuk, egy halmaz hatványhalmaza Boole-algebra a  ¯, és műveletekkel. Így mondhatjuk azt, hogy az ítéletlogika algebrai modelljei a Boole-algebrák.

Vizsgáljuk most az összes n-változós formula Ω halmazát. Megmutatjuk, hogy az Ω;0;¬,, struktúra Boole-algebra. Legyenek A és Bn-változós ítéletlogikai formulák. AB pontosan azokban az interpretációkban igaz, ahol mindkét formula igaz, tehát AB igazhalmaza az A és B formulák igazhalmazainak metszete. AB pontosan azokban az interpretációkban igaz, ahol legalább az egyik formula igaz, tehát AB igazhalmaza az A és B formulák igazhalmazainak uniója. ¬A pontosan azokban az interpretációkban igaz, ahol A hamis, tehát ¬A igazhalmaza az A igazhalmazának komplementuma az {i,h}n halmazra nézve. Ezért a formulákon értelmezett ¬, és ,,műveletek” rendre megfeleltethetők a T({i,h}n);=; ¯;;-beli  ¯, és műveleteknek. Így Ω;0;¬,, is Boole-algebra.

4.5.16. MEGJEGYZÉS. Definiáljunk rendezést a konjunkció segítségével az Ω halmazon. Ha AB0A, akkor legyen AB. Az AB0A viszont pontosan azt jelenti, hogy A igazhalmaza része B igazhalmazának. Tehát a legkisebb elem a kielégíthetetlen formula és a legnagyobb elem a tautológia.

A Boole-algebra általános tárgyalásánál már láttuk, hogy az (1)(10) axiómákból következik néhány fontos azonosság, például a De Morgan-szabályok. Az ítéletlogika esetében ezek bizonyítása jó gyakorlat a szemantika és a formális átalakítások megtanulásához.

4.5.17. PÉLDA. Bizonyítsuk be a ¬(XY)0¬X¬Y De Morgan-szabályt. Ha ¬X¬Y valóban negáltja XY-nak, akkor a (9) axióma bal oldalán behelyettesítve a két formulát, a (XY)(¬X¬Y) formulát kapjuk, aminek a jobb oldal szerint kielégíthetetlennek kellene lennie. A disztributivitás miatt a bal oldalon a (XY¬X)(XY¬Y) formulát kapjuk. De

X Y ¬ X 0 Y X ¬ X 0 Y 0

és

X Y ¬ Y 0 X 0 ,

tehát a bal oldal kielégíthetetlen. (10) bal oldalán az (XY)(¬X¬Y) formulát kapjuk, amelyről be kell látni, hogy tautológia. Alkalmazva a disztributivitást, az eredmény a (¬X¬YX)(¬X¬YY) formula, ami tautológia, mivel

¬ X ¬ Y X 0 ¬ Y ¬ X X 0 ¬ Y 0

és

¬ X ¬ Y Y 0 ¬ X 0 .

Beláttuk tehát, hogy az {¬,,} művelethalmaz funkcionálisan teljes. Ezután annak igazolására, hogy egy művelethalmaz funkcionálisan teljes, csak azt kell megmutatni, hogy a fenti három művelet kifejezhető a vizsgált művelethalmaz elemeinek felhasználásával. Ehhez elegendő megmutatni, hogy a ¬X, XY, XY formulák által leírt műveletek közül a művelethalmazban nem szereplők leírhatók olyan formulával is, melyben csak a vizsgált művelethalmaz műveleteinek megfelelő logikai összekötőjeleket használtunk.

  1. { ¬ , } felhasználásával elő lehet állítani a hiányzó XY formulát alkalmazva a De Morgan-szabályt: XY0¬(¬X¬Y)

  2. { ¬ , } felhasználásával elő lehet állítani a hiányzó XY formulát, ha alkalmazzuk most is a De Morgan-szabályt: XY0¬(¬X¬Y)

  3. { ¬ , } felhasználásával állítsuk elő az XY és az XY formulákat: XY0¬(X¬Y) és XY0¬XY

  4. { , , i } felhasználásával állítsuk elő a ¬X és az XY formulákat: ¬X0Xi és XY0((Xi)(Yi))i

  5. { | } felhasználásával állítsuk elő a ¬X, az XY és az XY formulákat: ¬X0X|X,XY0(X|Y)|(X|Y) és XY0(X|X)|(Y|Y)

Normálformák egyszerűsítése

Az 1950-es években az elektronikai alkalmazások miatt előtérbe került a normálformák egyszerűsítésével kapcsolatos probléma. Az első komoly munkát [51] több mint 20 évig tartó kutatási és alkalmazási periódus követte. Mi itt csak azt az eredeti algoritmust ismertetjük, amely kitüntetett diszjunktív normálformák átalakítására alkalmas. A diszjunktív normálformák egyszerűsítési algoritmusainak kutatása az 1950–1970-es évekre tehető. Ez volt az a kezdeti időszak, amikor az elektronikus berendezések tervezése funkcionálisan teljes művelethalmazokat ({¬,,},{NAND¬},{NOR¬}) realizáló funkcionális elemek segítségével történt. A későbbiekben a tervezést az időközben kifejlesztett programozható logikai mátrixokra (PLA), valamint memóriaelemek felhasználására alapozták. Két összefoglaló mű a témában: [6,11].

Egy ítéletlogikai formula logikai összetettségén a formulában szereplő logikai összekötőjelek számát értettük. Ugyanazt az logikai műveletet leíró két formula közül azt tekintjük egyszerűbbnek, amelyiknek a logikai összetettsége kisebb. Legyen X egy ítéletváltozó, k egy az X-et nem tartalmazó elemi konjunkció, d egy az X-et nem tartalmazó elemi diszjunkció. Ekkor az

( 1 ) ( X k ) ( ¬ X k ) 0 k és ( 2 ) ( X d ) ( ¬ X d ) 0 d

egyszerűsítési szabályok alkalmazásával konjunktív, illetve diszjunktív normálformákat írhatunk át egyszerűbb konjunktív, illetve diszjunktív normálformába.

Az (1) szabályt bizonyítjuk: a disztributivitás miatt

( X k ) ( ¬ X k ) 0 ( X ¬ X ) k ,

de X¬X0 és k0k. A (2) szabály ennek duálisa, tehát a dualitás elve miatt fennáll.

Az (1) egyszerűsítési szabályt alkalmazzuk a kitüntetett diszjunktív normálformák egyszerűsítésére. Az egyszerűsítési szabály alkalmazásával a (Xk), (¬Xk) elemi konjunkciópárt a k elemi konjunkcióval helyettesítjük, és így a formulában szereplő elemi konjunkciók száma is, és az egyes elemi konjunkciókban szereplő literálok száma is csökken. Az egyszerűsítések során a KDNF-ből egy DNF áll elő. A duális egyszerűsítési szabály hasonló módon alkalmas a kitüntetett konjunktív normálformák egyszerűsítésére.

A klasszikus Quine–McCluskey-féle algoritmus kitüntetett diszjunktív normálforma egyszerűsítésére:

  1. Soroljuk fel a KDNF-ben szereplő összes teljes elemi konjunkciót az L0 listában, j:=0.

  2. Megvizsgáljuk az Lj-ben szereplő összes lehetséges elemi konjunkciópárt, hogy alkalmazható-e rájuk az (1) egyszerűsítési szabály. Ha igen, akkor a két kiválasztott konjunkciót ✓-val megjelöljük, és az eredmény konjunkciót beírjuk egy Lj+1 listába. Azok az elemi konjunkciók, amelyek az Lj vizsgálata végén nem lesznek megjelölve, nem voltak egyszerűsíthetők, tehát belekerülnek az egyszerűsített diszjunktív normálformába.

  3. Ha az Lj+1 konjunkciólista nem üres, akkor j:=j+1. Hajtsuk végre újból a 2. lépést.

  4. Az algoritmus során kapott, de meg nem jelölt elemi konjunkciókból készítsünk egy diszjunkciós láncformulát. Így az eredeti KDNF-fel logikailag ekvivalens, egyszerűsített DNF-et kapunk.

4.5.18. PÉLDA. A 4.5.14. példabeli KDNF egyszerűsítése.

Az L0 konjunkciólista:

  1. X Y ¬ Z

  2. X ¬ Y ¬ Z

  3. ¬ X Y Z

  4. ¬ X ¬ Y Z

  5. ¬ X ¬ Y ¬ Z

Minden elemi konjunkciót egyszerűsítettünk. Az egyszerűsítés eredményeképp nyert elemi konjunkciók L1 listája:

1.

(az L0-beli 1–2.-ből)

X ¬ Z

bekerül a DNF-be

2.

(az L0-beli 2–5.-ből)

¬ Y ¬ Z

bekerül a DNF-be

3.

(az L0-beli 3–4.-ből)

¬ X Z

bekerül a DNF-be

4.

(az L0-beli 4–5.-ből)

¬ X ¬ Y

bekerül a DNF-be

Az L2 konjunkciólista üres. Az eredmény:

( X ¬ Z ) ( ¬ Y ¬ Z ) ( ¬ X Z ) ( ¬ X ¬ Y )

Egy A diszjunktív normálforma bármelyik kj elemi konjunkciójára igaz, hogy 0kjA. Ezt más szóval úgy fejezzük ki, hogy kjimplikánsaA-nak, ami azt jelenti, hogy kj igazhalmaza részhalmaza az A igazhalmazának.

A Quine–McCluskey-féle eljárással kapott DNF-et redukált DNF-nek, a benne lévő elemi konjunkciókat pedig prímimplikánsoknak nevezzük, mivel az elemi konjunkciókból nem hagyható el literál úgy, hogy a formula még mindig leírja az eredeti logikai műveletet. Az eredmény DNF elemi konjunkcióiban lévő literálok száma minimális.

Lehetséges azonban, hogy a redukált DNF-ből egyes elemi konjunkciókat elhagyva a formula továbbra is az eredeti logikai műveletet írja le. Ehhez azt kell biztosítani, hogy a megmaradó prímimplikánsok igazhalmazainak uniója megegyezzen a McCluskey-algoritmussal kapott DNF igazhalmazával. Azt a redukált DNF-et, amelyből már nem hagyható el elemi konjunkció, minimális DNF-nek nevezzük. A minimális DNF megkereséséhez megadunk egy ,,lefedési” táblázatot a formula igazhalmazának elemei és a formula prímimplikánsai között. A táblázat felső szegélyében a formula igazhalmazának elemeit, az oldalszegélyben a prímimplikánsokat soroljuk fel. Egy prímimplikáns sorában az ő igazhalmazának elemei alá × jelet írunk. Azt mondjuk, hogy a prímimplikáns ,,lefedi” ezeket az elemeket. Ha van a prímimplikáns által ,,lefedett” elemek között olyan, amelyet csak ez a prímimplikáns fed le, akkor az illető prímimplikánst lényeges prímimplikánsnak nevezzük és a lefedési táblában *-gal jelöljük. Most megadjuk a 4.5.18. példa lefedési táblázatát és lényeges prímimplikánsait.

i i h

i h h

h i i

h h i

h h h

X ¬ Z

×

×

¬ Y ¬ Z

×

×

¬ X Z

×

×

¬ X ¬ Y

×

×

A formula igazhalmazának elemei közül megtartjuk azokat, amelyeket a lényeges prímimplikánsok nem fednek le. Ezekkel, valamint azokkal a nemlényeges prímimplikánsokkal, amelyek a maradék igazhalmazelemek közül lefednek legalább egyet, új lefedési táblázatot szerkesztünk. Az új táblázat alapján – valamilyen heurisztika szerint – kiválasztjuk azokat a prímimplikánsokat, amelyek szükségesek a maradék elemek lefedéséhez.

h h h

¬ Y ¬ Z

×

¬ X ¬ Y

×

A lényeges prímimplikánsok és az új lefedési táblázat alapján kiválasztott prímimplikánsok diszjunkciója minimális DNF. Ez esetünkben vagy az

( X ¬ Z ) ( ¬ X Z ) ( ¬ Y ¬ Z ) ,

vagy az

( X ¬ Z ) ( ¬ X Z ) ( ¬ X ¬ Y )

formula.

Most alkalmazzuk a McCluskey-féle eljárást arra az esetre, amikor a logikai művelet a tábla minden sorában i igazságértéket rendel az interpretációhoz, tehát minden sorhoz rendeltünk teljes elemi konjunkciót. A logikai műveletet leíró KDNF-ben ezért az összes lehetséges teljes elemi konjunkció szerepel.

Vegyük észre, hogy ha kiválasztunk egy teljes elemi konjunkciót és abban egy ítéletváltozót, akkor biztosan van a teljes elemi konjunkciók között olyan, aminek a segítségével a kiválasztott változó kiegyszerűsíthető. Az interpretációkat a táblázat soraiba úgy írjuk be, hogy az első oszlopba a táblázat első felében (első 2n1 sor) i igazságértékek, a második felében h igazságértékek kerüljenek. Ugyanezt a beírási módot kövessük a két kitöltendő 2n1 sort tartalmazó résztáblára, és így tovább. Ennek az a jelentősége, hogy nem kell minden konjunkciópárra ellenőrizni az egyszerűsíthetőséget, hanem ezt csak az első 2n1 konjunkcióhoz vizsgáljuk. A k-adik konjunkcióhoz kiválasztjuk a (2n1+k)-adik sorban lévő konjunkciót, amellyel az első változót kiegyszerűsítjük. Így megkapjuk a maradék n1 változóval felírható összes lehetséges teljes elemi konjunkciót. Az eljárás ugyanígy folytatódik a soronkövetkező változóra, míg az n1-edik lépés után a megmaradt két elemi konjunkció az Xn és a ¬Xn. Tehát az egyszerűsítések után az Xn¬Xn DNF-hez jutottunk, ami viszont tautológia. Így az n-edik lépés után már nem marad literál az elemi konjunkcióban. Azt mondjuk, hogy az eredmény az üres elemi konjunkció, jelölése: .

Vizsgáljuk most azt az n-változós műveletet, amelyik minden sorban h igazságértéket rendel az interpretációhoz. Ennek felírva a KKNF-jét, minden sorhoz rendeltünk teljes elemi diszjunkciót. A leképezést leíró KKNF-ben ezért az összes lehetséges teljes elemi diszjunkció szerepel. A KDNF egyszerűsítésénél elmondottakat követjük itt is, és az ítéletváltozókat sorra kiegyszerűsítjük. Az n1-edik lépés után a megmaradt két elemi diszjunkció az Xn és a ¬Xn. Az így kapott Xn¬Xn KNF kielégíthetetlen formula. Az n-edik lépés után most sem marad literál az elemi diszjunkcióban. Azt mondjuk, hogy az eredmény az üres elemi diszjunkció vagy üres klóz, jelölése: .

4.5.19. PÉLDA. Tautológia egyszerűsítése:

X

Y

Z

b

teljes elemi konjunkció

i

i

i

i

X Y Z

i

i

h

i

X Y ¬ Z

i

h

i

i

X ¬ Y Z

i

h

h

i

X ¬ Y ¬ Z

h

i

i

i

¬ X Y Z

h

i

h

i

¬ X Y ¬ Z

h

h

i

i

¬ X ¬ Y Z

h

h

h

i

¬ X ¬ Y ¬ Z

Az X változó kiegyszerűsítése után:

elemi konjunkció

Y Z

Y ¬ Z

¬ Y Z

¬ Y ¬ Z

Az Y változó kiegyszerűsítése után:

elemi konjunkció

Z

¬ Z

A kapott DNF: Z¬Z. A Z-vel való ,,egyszerűsítés” után pedig: .

A McCluskey-féle klasszikus eljáráson kívül sok más egyszerűsítési módszert ismerünk, most ezeket nem tárgyaljuk, hisz csak a problémát akartuk felvetni.

A Boole-függvények funkcionális teljességéről általában

Az előző részben konstruktív módon mutattuk meg, hogy az {,,¬} logikai művelethalmaz funkcionálisan teljes. Ennek ismeretében – ugyanilyen eszközökkel – megmutattuk néhány további logikai művelethalmaz funkcionális teljességét. Ez azt biztosítja, hogy tetszőleges logikai művelet leírható valamilyen speciális alakú formulával. Ebben a fejezetben – a Boole-függvények elméletének tárgyalásánál – ez a lehetőség segítségünkre lehet. A Boole-függvények – logikai műveletek mint leképezések – tulajdonságainak vizsgálata során 1921-ben Post [30] olyan kritériumrendszert talált, amely pontosan akkor teljesül Boole-függvények egy halmazára, ha az funkcionálisan teljes.

Legyen B={i,h}. A Bn halmazt szokás n-dimenziós Boole-térnek vagy Boole-kockának, egy f:BnB leképezést pedig n-változós Boole-függvénynek is nevezni.

4.5.20. DEFINÍCIÓ. Legyen a_=(a1,a2,,an) és b_=(b1,b2,,bn) az n-dimenziós Boole-tér két tetszőleges eleme. Azt mondjuk, hogy a_megelőzib_-t, és ezt a_b_-vel jelöljük, ha a1b1, a2b2, …, anbn.

4.5.21. DEFINÍCIÓ. Legyenek f:BnB és gi:BkB, (i=1,2,…,n) Boole-függvények. Az

f ( g 1 , g 2 , , g n ) ( X 1 , X 2 , , X k ) f ( g 1 ( X 1 , X 2 , , X k ) , g 2 ( X 1 , X 2 , , X k ) , , g n ( X 1 , X 2 , , X k ) )

k-változós Boole-függvényt az f (külső) és a g1,,gn (belső) Boole-függvények szuperpozíciójának nevezzük.

4.5.22. DEFINÍCIÓ. A pni(X1,X2,,Xn)=Xi(1in)n-változós Boole-függvényt i-edik projekciónak nevezzük.

Jelölje O2 az {f:BnB|1n} függvényhalmazt.

4.5.23. DEFINÍCIÓ. Legyen HO2, azaz H Boole-függvények egy halmaza. H-t Boole-függvények egy zárt osztályának vagy klónnak nevezzük, ha H tartalmazza az összes projekciót (az összes logikai változót) és zárt a szuperpozícióra, vagyis ha tetszőleges fHn-változós és g1,g2,,gnHk-változós Boole-függvények esetén az f(g1,g2,,gn)H.

4.5.24. DEFINÍCIÓ. Boole-függvények egy H zárt osztályát maximális zárt osztálynak vagy maximális klónnak nevezzük, ha fH esetén H{f} elemeinek szuperpozícióival O2 minden eleme előáll.

Post megmutatta, hogy az O2 függvényhalmaz maximális klónjainak száma öt, nevezetesen

  1. C 2 { f O 2 | f ( i , i , , i ) = i } . Ezek az i konstanst őrző Boole-függvények.

  2. C 3 { f O 2 | f ( h , h , , h ) = h } . Ezek a hkonstanst őrző Boole-függvények.

  3. L 1 { f O 2 | f Zsegalkin polinomja lineáris } . Ezek a lineáris Boole-függvények. f Zsegalkin-polinomja lineáris, ha f(X1,X2,,Xn) előáll c0c1X1c2X2cnXn alakban, ahol cjB (j=0,1,,n). (A legyen nagyobb prioritású, mint .)

  4. D 3 { f O 2 | f = f d } . Ezek az önduális Boole-függvények. Definíció szerint egy f Boole-függvény duálisa az az fd Boole-függvény, amelyre fd(X1,X2,,Xn)=¬f(¬X1,¬X2,,¬Xn).

  5. A 1 { f O 2 | bármely a _ , b _ B n re , ha a _ b _ , akkor f ( a _ ) f ( b _ ) } . Ezek a monoton (rendezéstartó) Boole-függvények.

Nyilvánvaló, hogy mind az öt osztály tartalmazza az összes projekciót. Megmutatjuk, hogy a fenti függvényosztályok zártak a szuperpozícióra.

  1. Legyenek fn-változós, g1,g2,,gnk-változós i konstanst őrző Boole-függvények. Ekkor az f(g1,g2,,gn)(X1,X2,,Xk) szuperpozíció minden változójába i-t helyettesítve azt kapjuk, hogy

f ( g 1 ( i , i , , i ) , g 2 ( i , i , , i ) , , g n ( i , i , , i ) ) = f ( i , i , , i ) = i .

Tehát szuperpozícióval csak i-t őrző Boole-függvények állnak elő.

  1. Legyenek most f,g1,g2,,gnh konstanst őrző Boole-függvények. A zártságot ugyanúgy igazoljuk, mint az i konstanst őrző Boole-függvények esetén.

  2. Legyenek

f ( X 1 , X 2 , , X n ) = c 0 c 1 X 1 c 2 X 2 c n X n , g 1 ( X 1 , X 2 , , X k ) = c 0 1 c 1 1 X 1 c 2 1 X 2 c k 1 X k , g n ( X 1 , X 2 , , X k ) = c 0 n c 1 n X 1 c 2 n X 2 c k n X k

lineáris Boole-függvények. Az f(g1,g2,,gn)(X1,X2,,Xk) szuperpozíció alakja:

c 0 c 1 ( c 0 1 c 1 1 X 1 c k 1 X k ) c n ( c 0 n c 1 n X 1 c k n X k )

is lineáris. Mivel cjB, egy cj(c0jc1jX1ckjXk) kifejezés cj=h esetén a h konstans, cj=i esetén a (c0jc1jX1ckjXk) kifejezés. Továbbá a művelet kommutatív és asszociatív, így az előbb nyert kifejezés

( c 0 c 0 1 c 0 n ) ( c 1 1 X 1 c 1 n X 1 ) ( c k 1 X k c k n X k )

alakba átírható. XX=h és hX=X felhasználásával, C0(c0c01c0n) éppen i, ha benne az i konstansok száma páratlan és h különben. A (cs1XscsnXs) kifejezés pedig CsXs alakban is írható, ahol Cs=i, ha csw együtthatók között az i konstansok száma páratlan, Cs=h különben. Így a kifejezés alakja C0C1X1CkXk, ami lineáris Zsegalkin-polinom.

  1. Legyenek fn-változós, g1,g2,,gnk-változós önduális Boole-függvények. Belátjuk, hogy az f(g1,g2,,gn)(X1,X2,,Xk) szuperpozíció szintén önduális.

¬ f ( g 1 , g 2 , , g n ) ( ¬ X 1 , ¬ X 2 , , ¬ X k ) = = ¬ f ( g 1 ( ¬ X 1 , ¬ X 2 , , ¬ X k ) , g 2 ( ¬ X 1 , ¬ X 2 , , ¬ X k ) , , g n ( ¬ X 1 , ¬ X 2 , , ¬ X k ) ) = = ¬ f ( ¬ ( ¬ g 1 ( ¬ X 1 , ¬ X 2 , , ¬ X k ) ) , ¬ ( ¬ g 2 ( ¬ X 1 , ¬ X 2 , , ¬ X k ) ) , , ¬ ( ¬ g n ( ¬ X 1 , ¬ X 2 , , ¬ X k ) ) )

Ez a gi függvények öndualitása miatt

¬ f ( ¬ ( g 1 ( X 1 , X 2 , , X k ) ) , ¬ ( g 2 ( X 1 , X 2 , , X k ) ) , , ¬ ( g n ( X 1 , X 2 , , X k ) ) ) ,

ami f öndualitása miatt

f ( g 1 ( X 1 , X 2 , , X k ) , g 2 ( X 1 , X 2 , , X k ) , , g n ( X 1 , X 2 , , X k ) ) .

  1. Legyenek fn-változós, g1,g2,,gnk-változós monoton Boole-függvények és a_b_. Az f(g1(X1,X2,,Xk),,gn(X1,X2,,Xk)) szuperpozíciós kifejezésbe helyettesítsük be először a_-t, majd b_-t. Fennáll, hogy

( g 1 ( a _ ) , g 2 ( a _ ) , , g n ( a _ ) ) ( g 1 ( b _ ) , g 2 ( b _ ) , , g n ( b _ ) ) .

Mivel az f monoton,

f ( g 1 ( a _ ) , g 2 ( a _ ) , , g n ( a _ ) ) f ( g 1 ( b _ ) , g 2 ( b _ ) , , g n ( b _ ) ) .

A zárt függvényosztályok maximalitását – terjedelmi okok miatt – nem bizonyítjuk.

4.5.25. TÉTEL. (POST TÉTELE.)

Boole-függvényeknek egy F={f1,f2,,fn} halmaza akkor és csak akkor funkcionálisan teljes, ha az

F C 2 , F C 3 , F L 1 , F D 3 , F A 1

halmazok egyike sem üres.

BIZONYÍTÁS.

  • A feltétel szükséges, ugyanis ha a felsorolt különbséghalmazok közül legalább egy F\H (H Boole-függvények valamelyik maximális zárt osztálya) üres lenne, akkor FH lenne és ezért szuperpozícióval csak H-beli Boole-függvényeket lehetne előállítani.

  • A feltétel elégségességét konstrukciós technikával igazoljuk. Előállítjuk Boole-függvények funkcionálisan teljes halmazának, a {¬,} halmaznak az elemeit az F elemeinek szuperpozíciójaként. Tekintsünk egy olyan F0={f1,f2,f3,f4,f5} függvényhalmazt, ahol f1A1 (nem monoton), f2C3. (nem h konstanst őrző), f3C2 (nem i konstanst őrző), f4D3 (nem önduális), f5L1 (nem lineáris). Az F-nek ilyen F0 részhalmaza biztosan van a feltételek miatt. A bizonyítás során ezt a függvényhalmazt használjuk.

  1. Az f2,f3,f4 függvények szuperpozícióival előállítjuk az i és a h konstansokat. Az f2 nem h konstanst őrző, f3 nem i konstanst őrző, ezért az argumentumokba ugyanazt a változót beírva a következő függvényeket kapjuk.

    f 2 ( X , X ,..., X ) = { vagy  ¬ X vagy konstans  i f 3 ( X , X ,..., X ) = { vagy  ¬ X vagy konstans  h

Tehát a következő négy függvénypár valamelyike áll elő:

f 2

f 3

1.

i

h

i , h előáll az fj(X,X,,X)-szel (j=2,3)

2.

i

¬ X

f 2 = i ,f3(i,i,,i)=h

3.

¬ X

h

f 2 ( h , h , , h ) = i ,f3=h

4.

¬ X

¬ X

az f4-re szükség van, hogy i,h valamelyikét előállítsuk

f 4 nem önduális, tehát van olyan (m1,m2,,mn) értékkombináció, hogy

f 4 ( m 1 , m 2 , , m n ) = f 4 ( ¬ m 1 , ¬ m 2 , , ¬ m n ) .

Vezessük be a következő jelölést:

X m { X , ha m = i ¬ X , ha m = h

Az {Xm1,Xm2,,Xmn}-ből X=i esetén az (m1,m2,,mn) értékkombinációt, az X=h esetén viszont a (¬m1,¬m2,,¬mn) értékkombinációt kapjuk. Ez azt jelenti, hogy f4(Xm1,Xm2,,Xmn) konstans függvény, tehát az i vagy a h konstans előállt. A ¬X biztosítja a másik konstans előállítását.

  1. A konstansokból és az f1 (nemmonoton) függvény segítségével a negáció előállítható. Mivel f1 nem monoton, van olyan a_b_ értékkombináció, hogy f1(a_)f1(b_). Írjunk f1 azon argumentumaiba X-et, ahol ajbjés aj-t oda, ahol aj=bj. Az így kapott függvény a negáció, mert X=h esetén f1(a_)-t és X=i esetén f1(b_)-t kapjuk. f1(a_)f1(b_) miatt f1 értéke X=i-ra h kell, hogy legyen.

  2. A konjunkció előállításához szükséges az f5 nemlineáris függvény. f5(X1,,Xn)-nek van legalább két olyan Xi,Xj változója, amelyeknek a konjunkciója szerepel a {,,i} műveletekkel felírt Zsegalkin-formában, vagyis

f 5 ( X 1 , , X n ) = g 1 X i X j g 2 X i g 3 X j g 4 ,

ahol g1,g2,g3,g4 csak az Xi,Xj-től különböző Xk változóktól függő függvények. Helyettesítsünk be gs változóiba (s=1,2,3,4) olyan a_ értékkombinációt, amelyre g1(a_)=i. Ilyen helyettesítés biztosan van, mert különben nem lenne a Zsegalkin-formában XiXj-t tartalmazó tag. Vezessük be a gj(a_)-ra (j=2,3,4) a Cj jelölést. Az f5(X1,,Xn) előző kifejezéséből ezzel a helyettesítéssel kapott kétváltozós h(Xi,Xj) függvény Zsegalkin-formája:

X i X j C 2 X i C 3 X j C 4 .

A C2,C3,C4-ről feltételezhetjük, hogy értékeiket egymástól függetlenül veszik fel. Végezzük el h(Xi,Xj)-ben az (Xi,XjXi¬C3,Xj¬C2) helyettesítést. Megmutatjuk, hogy ez a helyettesítés C2,C3,C4 tetszőleges értékei mellett lehetőséget nyújt a konjunkció előállítására. Vizsgáljuk a kapott h(Xi¬C3,Xj¬C2) függvényt a C2,C3,C4 különböző értékkombinációira. Két csoportra oszthatjuk a C2,C3,C4 értékkombinációkat aszerint, hogy C2C3C4h vagy i. Nézzük végig a 4.14. táblázat segítségével a C2C3C4=h eseteket, itt azonnal megkapjuk a műveletet:

Table 4.14. A h(Xi¬C3,Xj¬C2) függvény komponensei behelyettesítve

C 2

C 3

C 4

X i ¬ C 3 X j ¬ C 2

C 2 X i ¬ C 3

C 3 X j ¬ C 2

C 4

(a)

h

h

h

X i X j

h

h

h

(b)

h

i

h

¬ X i X j

h

X j

h

(c)

i

h

h

X i ¬ X j

X i

h

h

(d)

i

i

i

¬ X i ¬ X j

¬ X i

¬ X j

i


  1. X i X j h h h = X i X j

  2. ¬ X i X j h X j h = ¬ X i X j X j = X i X j

  3. X i ¬ X j X i h h = X i ¬ X j X i = X i X j

  4. ¬ X i ¬ X j ¬ X i ¬ X j i = X i X j

A C2C3C4=i esetben a h(Xi¬C3,Xj¬C2) függvény az

X i X j i

polinomot adja mind a négy esetben, ami a konjunkció negáltja. Ezekben az esetekben tehát a h(Xi¬C3,Xj¬C2)i függvény állítja elő a műveletet.

Ezzel Post tételét bebizonyítottuk.

4.5.26. PÉLDA. Tekintsük a {|} – vagyis a Sheffer-vonás – egyelemű függvényhalmazt. A Sheffer-vonás művelettáblája alapján megállapíthatjuk, hogy a művelet

  • nem i és nem h konstanst őrző,

  • nem monoton (i|i=h, h|h=i miatt),

  • nem önduális (i|h=h|i miatt) és

  • nem lineáris (X|Y=XYi miatt).

Post tétele alapján Boole-függvények tetszőleges halmazáról – a példához hasonlóan – eldönthető, hogy funkcionálisan teljes-e.

Feladatok

4.5.1. FELADAT. A következő formulát írjuk át DNF-be, majd onnan KNF-be.

( X Y Z ) ( ¬ Z ¬ Y ¬ X )

Milyen következtetés vonható le a kapott formula alakjából?

4.5.2. FELADAT. Hozzuk KNF és DNF formára a következő formulákat:

  1. ¬ ( X Y ¬ X ) ¬ ( X Y ¬ Y )

  2. ( Z X ) ( ¬ ( Y Z ) X )

  3. ( ( X Y ) ( Z ¬ X ) ) ( ¬ Y ¬ Z )

  4. ( ( ( ( X Y ) ¬ X ) ¬ Y ) ¬ Z ) Z

  5. ( X ( Y Z ) ) ( ( X ¬ Z ) ( X ¬ Y ) )

4.5.3. FELADAT. Adott a b:{i,h}n{i,h} logikai művelet az alábbi művelettáblával:

X

Y

Z

b

i

i

i

h

i

i

h

h

i

h

i

i

i

h

h

h

h

i

i

i

h

i

h

h

h

h

i

i

h

h

i

i

Adjuk meg a b-t leíró KKNF-et, majd egyszerűsítsük.

4.5.3.FELADAT. Vezessük be az alábbi háromváltozós logikai műveleteket.

  1. b 1 ( X , Y , Z ) akkor és csak akkor i, ha pontosan egy argumentuma i.

  2. b 2 ( X , Y , Z ) akkor és csak akkor i, ha pontosan két argumentuma i.

Írjuk fel a bevezetett műveletek igazságtábláit, majd fejezzük ki őket a ¬,, összekötőjeleket tartalmazó formulákkal. Egyszerűsíthetők-e a felírt formulák a Quine–McCluskey-féle algoritmussal?

4.5.5. FELADAT. Mely maximális zárt függvényosztályoknak elemei az XY, XY, XY, XYZ függvények?

4.5.6. FELADAT. Van-e lineáris Zsegalkin-polinomja az X¬Y¬XY formulával leírt Boole-függvénynek?

4.5.7. FELADAT. Igazságtáblával adott rögzített n-re egy {i,h}n{i,h} Boole-függvény. Hogyan lehet ellenőrizni, hogy ez a függvény önduális-e?

4.5.8. FELADAT. Hány különböző n-változós önduális Boole-függvény létezik?

4.5.9. FELADAT. Mi a jellegzetessége egy önduális függvényt leíró KDNF alakú formulának?

4.5.10. FELADAT. Igazoljuk, hogy

  1. X i ¬ X j X i = X i X j

  2. ¬ X i X j X j = X i X j

  3. ¬ X i ¬ X j ¬ X i ¬ X j i = X i X j