Funkcionálisan komplett rendszerek funkcióit
A propozicionális logika tartják Boole-függvények, azaz függvénynek, amelyek csak két érték: igaz vagy hamis. Boole-függvények lehet osztani műveleti osztályok (funkciócsoport), tekintetében egy adott tulajdonság. Az osztály Boole-függvények úgynevezett zárt, ha a kombináció a funkciók ez az osztály tartalmazza azt is. Kombinációjával Boole-függvények értünk függvényében álló Boole-függvények többi csatlakoztatott karakter logikai műveleteket.
Számos zárt osztályok funkciók:
1) Az osztály műveleteit, amelyek megőrzik nulla :.
2) Az osztály műveleteit, hogy megőrizzék az egység :.
3) Az osztály S önduális funkciók tartalmaznak funkciók átellenes készletek részesülő ellentétes értékeket.
4) L osztály lineáris függvények tartalmazhat funkciók által képviselt egy polinom Zhegalkin első fokú.
5) M osztályú monoton függvények: bináris vektorok. hol. . bevezette a következő részleges sorrendben. Úgy gondoljuk, hogy. if. M osztályú meghatározása a következő:
Check kiegészítők Boole-függvények zárt osztályok végzik igazság táblázat. Tulajdonjogának igazolásához egy logikai függvény az L osztály végzi létrehozunk egy polinom Zhegalkin.
Boole-függvény azt mondják, hogy monoton. ha minden n-dimenziós bináris vektorok a, hogy. Ebből következik, hogy
A tétel a monoton függvények: minden Boole-függvény az aláírás a matematikai logika, amely nem tartalmaz negáltjai, monoton funkciója. bármely monoton Boole-függvények más mint 0, és 1, ott egyenértékű azzal Boole-függvény nélkül a negatívokat.
1. példa Annak meghatározására, hogy egy monoton függvény.
- nem tartalmaz negáltjai ez monoton.
A funkció az úgynevezett kettős funkciója működjön. Ez a funkció a önduális. if.
Ezek önduális funkció
Ellenőrizze a önduális műveletek végezhetők az igazság táblázat, amely az utolsó oszlop: az első 0 vagy 1 helyébe 1 vagy 0, holtversenyben utolsó helyre, ha az utolsó helyen 1 vagy 0 ellenőrzéseket vannak - mint a második sorban, és az utolsó előtti, és így tovább, egészen a közepén. Ha kap két azonos értékeket legalább két szimmetrikus a középső sor utolsó oszlopában az igazság tábla, hogy a funkció nem önduális.
2. példa Annak meghatározása, hogy funktsiyasamodvoystvennoy.
Készítünk egy kettős funkciója az eredeti:
Ha a kettős funkciójú, az eredeti az eredeti, az eredeti funkciója a önduális.
A rendszer logikai függvényeket is funkcionálisan teljes. ha Boole-függvény leírható szuperpoziciójával (komplex funkció) a rendszer funkcióit.
Tétel bejegyzést a funkcionális teljességére. A rendszer funkciói teljes, szükséges és elégséges, hogy ez nem teljesen foglalt a következők bármelyikével zárt osztályok T0. T1. L, M és S.
A teszt a funkcionális teljesség rendszerének Boole-függvények épített az úgynevezett asztal nagyböjt, amely megjegyzi tartoznak jellemzői zárt osztályok. Ha van legalább egy hátránya, a rendszer teljes minden oszlopában a nagyböjt, különben - nem.
Példa 1. Ellenőrizze teljesség funkcionális rendszer logikai funkciókat.
A tulajdonjog igazolásához a zárt osztály műveleteit. Készítünk egy igazság táblázat a függvény:
rendszer funkciói Á alkot egy teljes rendszert, mivel az egyes Post osztályok a rendszer jellemzői, amelyek nem tartoznak ebbe az osztályba. rendszer funkciói Á az alapja, hiszen tele van, és amikor törli az egyik feladatot a rendszer hiányossá válik.
Példa 4.Opredelit hogy a teljes készlet funkciók F =, és ha ez egy alapon.
x Ù Oy
x Ù Oy
x Ù Oy:
4) Mivel f (0,0) = f (1,1), ezért, az f (x Ù Oy) monoton;
5) zhegalkin polinom: x + xy.
4) Mivel f (0,0) 5) zhegalkin polinom: x + y + xy. A rendszer funkciók hiányos. Példa 5.Opredelit hogy a teljes készlet funkciók: Azt, hogy az igazság táblázat mind az öt funkció (f2 és f4 asztal lehet alakítani külön). Predikátumok és kvantifikátorok Legyen A - egy sor tárgyak egy tetszőleges jellegű (tárgykörben állítmány), n-ed rendű predikátum - tetszőleges térképen 1. példa állítmány A (x) = «x ≤ 2" egy sor, az X = R - Single. A predikátum B (x y.) = «Xy> 0" beállítani X = - két helyen. Ha X =, akkor n -place predikátum egy n -place Boole-függvény. Nullary predikátum megnyilatkozás. Mivel a beállított értékek bármelyike állítmány rejlik a készlet, a predikátumok képes az összes logikai műveletek, valamint az összes ismert tulajdonságai logikai műveletek predikátumok -ról. Tekintsük ezeket a tulajdonságokat (egyszeri predikátumok írt kényelem a tulajdonságok): 6. kivételével harmadik törvénye: P (x) P (x) = 1. 8. törvények De Morgan: 9. tulajdonságai műveletek logikai állandók: Hogy predikátum működését egy speciális fajtája, amely az úgynevezett kvantifikátorok. Tegyük fel, hogy adott n -place állítmány az X, ami azt jelenti, hogy egy sor megfelelő állapot A. és hagyja, hogy a - az egyik változó. Aztán rekord azt jelenti, hogy az összes változó értékei ingatlan egy teljesül. Symbol nevű univerzális kvantor (általánosság). A predikátum (N- 1) a férőhelyes. Attól függ, hogy a változókat. Adott egy egyváltozós predikátum P (x), akkor az állítás xP (x) egy állítmány nullary, vagyis valódi vagy hamis állítás. N- ed rendű reláció X és változó bejegyzés azt jelenti, hogy van egy értéket egy változó. A kotoroysvoystvo A teljesül. Symbol hívják az egzisztenciális kvantor. A predikátum (N- 1) férőhelyes függ a változók. egyszeri állítmány P (x) jóváhagyása xP (x) egy állítmány nullary, vagyis valódi vagy hamis állítás. Példa 2. készlet adott X = R predikátum A (x) = «x ≤2». Mondván x (x ≤ 2) - hamis, x (x ≤ 2) - igaz. Recording xA (xA) nem jelenti azt, hogy a általános képletű A jelentése x változó. A x változó egy változó a kvantor. és A - kvantor körét. Vannak egyenértékű: Állítmány valódi kilétét (hamis identitás). ha minden lehetséges változók értékét tart értéke 1 (0). Ajánlat - Single állítmány halmazán megadott N. - „van egy x. amelyekre a helyes „- igaz állítás; - „x igaz minden” - egy hamis állítás. Ajánlat - kétágyas állítmány meghatározni A. A predikátum nevezzük megvalósítható. ha valamilyen változók értékét ez igaz. Példa 4.Nayti megnyilatkozás értéket. Triple állítmány halmazán megadott N. Határozat: Let = 1. Az egyenértékűség akkor és csak akkor, ha valamilyen oknál. és az állítmány igaz képest azonos y. vagyis az eredeti állítás igaz. Legyen A - általános képletű - egy változó, amely szerepel a képletben A (egy vagy több alkalommal). Csatlakozás a képletű nevezzük kötött. ha van ilyen - a változó a kvantor vagy kvantor akcióban. Ha a bejegyzés egy nem csatlakozik, akkor azt mondják, hogy szabad legyen. A képlet előfordulása mindkét változó rendelkezésre képlet előfordulása az x változó csatlakoztatva van, és előfordulása a változó szabadon. Minden egyes predikátum igazság domain a beállított Y = X X A (x) = 1>, ahol az alapul veszi az 1 értéket. A készlet az igazság állítmány A predikativ A (x) = «x ≤ 2" az X halmazon = valódi oltalmi körét beállítása Y = x R, x ≤ 2>. A régió kereszteződés és a szakszervezeti igazság állítmány reláció igaz: A következő mondat azt jelenti: - „igaz az összes m: m elosztjuk n» vagy «bármilyen pozitív nem nulla szám osztva n» - egyetlen állítmány függ n. végrehajtható predikátuma területe annak igazság - n = 1>, hiszen minden számot elosztjuk 1; - „van m, az alábbi állítások: m van osztva n” vagy „van egy pozitív nem nulla szám, amely osztható a más természetes, nem nulla szám” - egyetlen predikátum függ n. azonosan igaz állítmány, a terület az igazság - A; - „igaz minden n: m van osztva n” vagy „pozitív nem nulla szám osztva bármilyen pozitív nem nulla szám” - egyetlen predikátum függ m. azonosan hamis állítmány, a terület saját igazság üres halmaz; - „Van n. akinek a valódi: m van osztva n „vagy” pozitív nem nulla szám osztva a pozitív nem nulla szám „- egyetlen predikátum függ m. azonosan igaz állítmány, a terület az igazság - A. 1.Vydelit predikátumok minden állítmány az igazság kiderítése, a terület és a régióban, ha X = R. Két predikátumok ábrázolni az igazság tartomány grafikusan. 2) az x = 0 az x - 2 = 0; 5) jegyű szám x prím.
Kapcsolódó cikkek