Elemei a matematikai logika, algebra logikai függvények
Mint már említettük, a értéke Boole képletű teljesen függ a szereplő értékeket ebben a képletben megnyilatkozások. Ezért, Boole-formulával függvénye alkotó elemi javaslatokat.
Például, a (X y) ®z függvénye három változó F (x, y. z). A jellemzője ez a funkció az a tény, hogy az érvelése, hogy két értéket: nulla vagy egy, és így a funkció is vesz két értéket: nulla vagy egy.
Funkció Boole változók N (vagy Boole-függvény) függvénye változók n, ahol minden változó veszi a két érték: 0 és 1, és ahol a funkció csak akkor kerülhet egy a két érték: 0 vagy 1.
Nyilvánvaló, azonosak, és azonosan igaz hamis képlete Boole-függvények állandók, és a két egyenértékű képletek kifejezni ugyanazt a funkciót.
Nézzük, mi van a funkciók száma n változók. Nyilvánvaló, hogy minden Boole-függvény (általános képletnél algebra logika) megadható egy igazság táblázatot, amely tartalmazza 2n sort. Ezért, az egyes funkciók n változó veszi 2n értékek álló nullák és egyesek. Tehát a n-változós függvény teljesen meghatározott területén értékei nullák hosszúságú 2n. A csomagok száma álló nullák, egyenlő hosszúságú 2n. Ennélfogva, a számos különböző logikai függvények n változók egyenlő algebra.
Különösen a különböző funkciók egy változó négy, és a különböző funkciók két tizenhat változó. Például, az összes funkciót a matematikai logika az egyik lehet táblázat foglalja össze változó. 8.
A lehetséges logikai függvények egy változó
Ebből a táblázatból következik, hogy a két funkció egyetlen változó állandó lesz: F 1 (x) ° 1, F 4 (x) ° 0, F 2 (X) º X és.
Bármilyen tetszőleges Boole-függvény lehet képviselt formájában Boole képletek.
Tegyük fel például, F (x 1, x 2 xn) - egy tetszőleges függvény a Boole-változók n. Tekintsük a képlet
ÚF (1,1. 0) x 1x 2. Ú (1)
ÚF (1,1. 1,0,1) x 1x 2. xn Ú. Ú
amelyek összetétele a következő: minden távon a logikai összeg egy együtt, amelyben az első kifejezés az az érték, a függvény F bizonyos meghatározott változók x 1, x 2 xn. míg a fennmaradó tagjai együtt olyan változók vagy azok negáltjai. Így a jel alatt negáció azok, és csak azokat a változókat, hogy az első ciklus összefüggésben van értéke 0. Tehát, az (1) tartalmaz egy logikai összefüggésben az összes lehetséges szempontjából a megadott formában.
Nyilvánvaló, hogy az (1) képletű teljesen meghatározza a F (x 1, x 2 xn). Más szóval, függvény értékei F, és a képlet (1) azonos minden készlet változó értékek x 1, x 2 xn.
Például, ha 1 x értéket veszi fel 0 és a további változók vállalja a értéke 1, az F funkció van beállítva, hogy az F (0,1,1. 1). Ebben a logikai kifejezést F (0,1. 1) x 2. xn. tartalmazza az (1), szintén megkapja a értéke F (0,1. 1), mint x 2. Xn º1, és F (x 1, x 2 xn) 1ºF (x 1, x 2 xn). Minden más logikai szempontból az (1) van egy értéke 0. Sőt, azok tagadása a változó jelek másképpen oszlanak, mint a fenti kifejezést, de ha a változás a változók ugyanazokat az értékeket összefüggésben adja meg a 0 jel sem tagadja a jel, a jel 1 alatti tagadás jele . Ebben az esetben, az egyik tagja az összefüggésben értéke 0, és ezért az összes a összefüggésben az értéke 0, és F (x 1, x 2 xn) 0º0. Ebben az összefüggésben alapján egyenértékűségét x Ú 0 ° X értéke az (1) képletű jelentése F (0,1. 1).
Nyilvánvaló, hogy a fent említett (1) nagymértékben egyszerűsíthető, ha azt, hogy dobja el ezeket a logikai kifejezéseket, amelyben az első tag összefüggésben azaz F (x 1, x 2 x n) értéke 0 (és ezért minden összefüggésben értéke 0). Ha az első kifejezés a logikai kötőszavak tagnak van egy értéke 1 (azaz, F (x 1, x 2 xn) = 1), akkor, alkalmazásával equipollence 1x ° x. Ez a tag a kötőszó nem tud írni.
Így, az eredmény az (1), amely csak elemi propozíciós változók, és a következő tulajdonságokkal rendelkezik.
1. Minden egyes logikai kifejezés képletű tartalmazza az összes változók szerepelnek a F (x 1, x 2 xn).
2. Minden logikai szempontból formula más.
3. Egyik logikai képlet magában foglalja a kifejezés nem változó és annak tagadása.
4. Egyik kifejezés logikai képlet nem tartalmaz ugyanolyan változó kétszer.
Ezek a tulajdonságok nevezik tulajdonságok tökéletessége, vagy röviden tulajdonságokkal (C). Így az ingatlan a tökéletesség - egy sor tulajdonságai Boole-függvények, amelyben azt a legegyszerűbb formában.
A fenti tárgyalásból látható, hogy egyes funkciók nem azonosan megfelelnek az hamis csak általános képletű jelzett típusú.
Ha a függvény F (x 1, x 2 xn) kap egy igazság táblázatot, akkor a megfelelő képlet a matematikai logika érhető el egyszerűen. Sőt, az egyes változókat, amelyek az F (x 1, x 2 x n) = 1, írunk együtt elemi propozicionális változók figyelembe a kötőszó tag xk. ha az érték az xk egy meghatározott értékrend a változók egy 1. és egy tagadása xk. ha az érték az xk van 0. diszjunkcióját összes kötőszavak rögzített a megkövetelt képlet.
Tegyük fel például, a F (x 1, x 2, x 3), amely az alábbi igazság táblázat (táblázat. 9).
Az igazság táblázat függvény F (x 1, x 2, x 3)
Készletei értékek változók (1,1,0 részt) és (0,1,0), ahol a függvény értéke 1, írunk a összefüggésben, és a kívánt képlet amelynek a tulajdonságait a (c) a formája
Tekintsük az úgynevezett dualitás törvényének használják átalakítása logikai egyenletek.
Tegyük fel, a képlet Egy tartalmaz csak műveletek összefüggésben, diszjunkció, és tagadás. Fogjuk hívni együttállása működését a kettős működés diszjunkciót, és a szétválás működését a kettős működését összefüggésben.
Formula A és A * nevezzük kettős, ha a képletet A * nyerik képlet helyett, hogy minden műveletet a kettős.
Például, az alábbi képlet: A = (x Úy) Z általános képletű kettős akarat képletű A * ° (X y)Úz.
Azt állítjuk, bizonyítás nélkül a következő tétel tekintetében kettős formula.
Tétel 1. Ha a A és B képletek egyenértékűek, akkor azok megegyeznek, és kettős képletű, azaz A * ºV *.
Tétel 2 Ha a képlet A (X 1, X 2, ..., xn) egy kettős képletű A * (x 1, x 2, ..., xn), majd a következő egyenértékűség
Így, ennek eredményeként a tagadása képlet kapott kettős formula, amelyben a változók a negáltjai.