Teljességi tétel - studopediya
A célja ennek a szakasznak, hogy foglalkozzon az egyik fő kérdés az, hogy a matematikai logika - a kérdés a szükséges és elégséges feltételeit teljességének rendszer logikai funkciókat. A válasz erre a kérdésre adott, a következő tétel, a bizonyítás, amely kerül sor az eljárás A. Kuznyecov és
SK Jablonski.
3. Tétel (a teljesség) A Boole-függvények D-rendszer teljes volt, szükséges és elégséges, hogy ez nem teljes mértékben tartalmazza, bármely öt zárt osztályok T0. T1. S, M, L.
Proof .Neobhodimost. Legyen - egy komplett rendszer, amely teljes egészében tartalmazza az egyik osztály T0. T1. S, M, L. Az általánosság elvesztése nélkül, azt feltételezzük, hogy. Aztán. Következésképpen ,. ami lehetetlen.
Megfelelősége. Hagyja, logikai funkciók Rendszer D nem szerepel bármelyik osztályban T0. T1. S, M, L, majd a D biztos ott vannak a következő funkciók :. nem őrzi 0; . 1 nem őrzi; Nem önduális funkció; nemlineáris függvény; nem monoton függvénye. Figyelembe véve a koncepció egy dummy változó, akkor feltételezhetjük, hogy ezek a funkciók függenek ugyanazokat a változókat.
Először össze egy funkció a rendszer D állandók 0 és 1.
Tekintsük a funkciót. Ez a funkció a szuperpozíció a funkciók és. Mert nem tartoznak az osztály T0. . Most, ha g (1) = 1, akkor - az állandó 1. Behelyettesítve a konstans 1 függvény. kapunk egy konstans 0.
Most. A következő egyenletből g (0) = 1 és g (1) = 0, arra a következtetésre jutunk, hogy a. Vegye nesamodvoystvennuyu funkciót. Nyilvánvaló, hogy ebben az esetben van egy sor változó. hogy =.
Tekintsük a funkció és a konstrukció segítségével működésének szuperpozíció funkciót. Aztán kapunk:
Így, h (0) = h (1). Ez azt jelenti, hogy h (x) egy konstans 0 vagy 1. Mivel megszerkesztettük a funkciót. majd a szuperpozíció ezt a funkciót az egyik állandók ad egy másik állandó. Következésképpen, a konstansok 0 és 1, általunk épített.
Ekkor, felhasználva az előző tétel, fel tudjuk használni a szuperpozíció funkciók és állandók 0.1 build függvény. és így az összes funkciót. Korábban már kimutatták, hogy a Boole-függvény felírható szuperpoziciójával már beépített funkciókat. Ezért, a teljes bizonyítási marad megépíteni a funkciót. Ehhez vesszük a funkció és a kivitelezést ez a funkció egy polinom Zhegalkin. Mivel ez a funkció nem lineáris, akkor ott van a polinom kifejezés, amely legalább két tényező. Az általánosság elvesztése nélkül feltételezhetjük, hogy ezek a tényezők, és. Akkor tudjuk írni Zhegalkin polinomiális függvény az alábbi formában:
Egyedisége miatt polinom függvény nem azonosan nulla. Mi választjuk ki a változók értékei. hogy. Tekintettel erre, érkezünk a funkció
ahol a konstans 0 vagy 1. Construct függvényében az alábbiak szerint:
Tehát, a teljességi tétel teljesen bizonyított.
Olyan alkalmazásoknál, ahol szükség annak megállapítására, hogy a rendszer logikai funkciók teljes, teszünk egy asztal nevű asztalok nagyböjt. Ezek a táblázatok a következők.
Ez könnyen ellenőrizhető, hogy ez a funkció nem tartozik T0. vagy T1. Ettől. és a értéke a függvény egy beállított (0,0,0) nagyobb, mint a beállított (1,1,1), akkor a függvény nem monoton. Nyilvánvaló, hogy az összes változó ez a funkció elengedhetetlen. Mivel ez a funkció nem mérkőzésen. egyikkel sem. ez nem lineáris. Amint a 6. példában, ki lehet mutatni, hogy a funkció önduális. Következésképpen D4 rendszer nem teljes.
Azt mondjuk, hogy a rendszer a Boole-függvények nem csökkenthető. ha nem lehet kizárni semmilyen funkciót, így a fennmaradó kizárását követően a rendszer tele volt megint.
Egyértelmű, hogy minden teljes rendszert Boole-függvények lehet csökkenteni a legalacsonyabb feltételeket. Amint következik teljességi tétel, minden irreducibilis komplett rendszer tartalmaz legfeljebb 5 funkciókat. A következő tétel azt mutatja, hogy a valóságban a szám mindig csökken 4.
Tétel 4Maksimalnoe lehetséges funkciók száma a teljes rendszer kiküszöbölhetetlen Boole-függvények 4.
Valóban, az igazolást a teljességi tétel, láttuk, hogy ki minden teljes rendszer logikai funkciókat lehet megkülönböztetni teljes alrendszer, amely legfeljebb öt funkciót. Sőt, a funkciót. Ez nem őrzi 0 vagy 1 nem tárolja, vagy ha ez önduális. Ezért amellett, hogy ezt a funkciót, a rendszer elegendő elhagyni csak három funkciója van: a nem-lineáris, nem monoton, vagy funkciók nem helytálló az 1. vagy nesamodvoystvennuyu funkciót.
A következő példa azt mutatja, hogy az állandó 4 nem lehet leereszteni.
7. példa Tekintsük a rendszer funkcióit.
Szerkesztési nagyböjt asztal ebben a rendszerben:
A táblázat azt mutatja, hogy a rendszer teljes, és nem csökkenthető, a
Kérdések az önuralmat
1. Melyik rendszer logikai függvények az úgynevezett teljes?
2. Mi a neve, hogy bezárja a készlet Boole-függvények?
3. Mi az osztály Boole-függvények úgynevezett zárt?
4. Határozza meg a legfontosabb öt zárt osztályok.
5. Határozza meg a tétel a teljesség igényével.
6. Fogalmazza algoritmus nagyböjt.
7. Melyik rendszer logikai függvényeket is kiküszöbölhetetlen?
8. Mi a lehető legnagyobb számú funkciók teljes rendszert kiküszöbölhetetlen Boole-függvények?