Komplett rendszerek logikai funkciók - studopediya
Definíció. Logikai rendszer funkciói (f1. F2. Fn) nevezzük teljes. ha van olyan logikai függvény leírható szuperpoziciójával a funkciók a rendszer.
A rendszer logikai függvények befejeződött, szükséges és elégséges, hogy tartalmazza:
- legalább egy funkció, nem rendelkeznek állandó nulla;
- legalább egy funkció, nem rendelkeznek állandó on;
- legalább egy funkcióját, hogy nem lineáris;
- legalább egy funkcióját, hogy nem monoton;
- legalább egy függvény, ami nem önduális.
Ez a kritérium a teljesség a rendszer.
A rendszer funkciói 1. f2. fn>, ami a teljes, ez az úgynevezett alapul.
Minimum alapján hívják alapot, amely a tápanyag legalább az egyik feladatot fi. alapját képező teszi a rendszer funkciói 1. f2. fn> hiányos.
Figyelembe vesszük funkciók függvényében n érveket. A számos különböző funkciói megegyeznek.
Triviális teljes rendszer részei az összes funkció.
egy inverziós funkciók, diszjunkciót és együtt alkotnak egy teljes rendszert. Ez következik az alaptétel, amely kimondja, hogy minden Boole-függvény felírható egy diszjunkció mintermov (vagy együtt makstermov).
bázis nem minimális, mivel következtében csökkentett lehet annak kiürítése / \ vagy \ /. Ebből következik, De Morgan:
Bázisok és minimálisak.
a) - funkcionálisan teljes rendszer (ez következik Tétel Zhegalkin);
b) a következményei a funkció és a konstans 1 :;
c) függvény és következményeit inverzió. .
Példa. Bizonyítsuk be, hogy Schaeffer funkció alkot teljes rendszert
Bizonyítás. kifejezzük ¯ és / \ függvény Schaeffer:
Mivel - a teljes rendszer, az állítás bizonyított.
Példa. Mi kifejezetten a funkció használatával csak akkor működhet Schaeffer:
.
Példa. Bizonyítsuk be, hogy egy ↓ B alkot funkcionálisan teljes rendszer
Mivel inverzió diszjunkciót expresszálódik csupán az a funkciója „Pierce Arrow”, és - funkcionálisan teljes rendszer, A ↓ B funkcionálisan teljes rendszer.
Példa. Fejezzük ki a funkciót, csak a funkció „Pierce Arrow”:
A választás funkcionálisan teljes táblázat a rendszer.
Inversion - nem menti a 0 és 1 nem monoton, \ / - nem önduális, nem lineáris.
Mindkettő önálló kettős funkciója van. rendszer
Meg lehet mutatni, hogy az a teljes rendszer funkcióit, akkor válassza ki a teljes alrendszer, amely nem több, mint négy funkció. enged
Ha fk (11 ... 1) = 1, ez nem magától kettős funkcióval fk (00 ... 0) ≠ 0.
Ha fk (11 ... 1) = 0, akkor az ugyanazt a funkciót nem menti a 1 konstans és monoton.
Hozzátéve, hogy fk hiányzó három funkció, megkapjuk a rendszer, amely legfeljebb négy funkció.
Példa. Hozzon létre egy minimális alapot, amely magában foglalja a funkció
Bázisok 8, f11> 11, f14> nem minimális, mivel f8 és f11 A magukat funkcionálisan teljes.
Példa. 0 kifejezni a funkciót a rendszerben, f11>:
Mert konverziót használja a rendszert, mint egy nagy: