Yee matematikai logika
Meghatározása 1. Funkciók logikinperemennyh algebra minden n-változós függvény, amelyek figyelembe két érv az értékek 1 és 0, és a függvény maga veszi két érték egyikét: 0 vagy 1.
Minden képlet matematikai logika függvénye a matematikai logika. Azonosan igaz, egyforma hamis formula, amely egy állandó funkció.
Belátható, hogy minden funkció képviselheti egy Boole logikai képlet, és ez a nézet a következő:
(*)
Formula (*) lehet alakítani egy olyan képlet, amely csak elemi propozíciós változók, és a következő tulajdonságokkal tökéletessége (vagy tulajdonságok (C)):
1) minden egyes kifejezés a logikai képlet magában foglalja az összes változók szerepelnek a funkció;
2) az összes logikai kifejezések képlete eltér;
3) nem logikai képlet kifejezés nem tartalmaz ugyanolyan változó és a negáltja;
4) egyike sem a logikai képletű kifejezés nem tartalmaz ugyanolyan változó kétszer.
Az igazság táblázat meghatározó funkció könnyű megszerezni a megfelelő általános képletű, amelynek tulajdonságai Boole (C). Sőt, az egyes változókat, amelyek a függvény értéke 1, írd együttállása elemi propozicionális változók, figyelembe tagjaként az összefüggésben
Meghatározása 2.Elementarnoy konyunktsieyn változók nevezzük összefüggésben változók vagy azok negáltjai.
3. meghatározása diszjunktív normál forma (DNF) általános képletű A jelentése megegyezik ez az úgynevezett általános képletű képviselő diszjunkcióját összefüggésben elemi.
Meghatározása 4.Sovershennoy Diszjunktív normál forma (PDNF) általános képletű A nevezzük a tulajdonságait DNP A. (C).
PDNF lehet előállítani két módon: a) segítségével az igazság táblázat (lásd fent). b) útján egyenértékű transzformációk.
Jellemzően termelnek PDNF a formulyA ekvivalens transzformációk.
1. Annak érdekében, hogy bármely képletű DNF.
2. A DNF A egyenértékű átalakulások PDNF szerezni következetesen elérése teljesítmény PDNF négy tulajdonságok:
1) Legyen B távú DNF, amely nem tartalmaz
2) Ha A DNP Meet két kifejezés nem azonosak
3) Ha a B kifejezés egy változóban DNF
4) Amikor a kifejezés a B DNF összefüggésben A tartalmaz
Meghatározása 5.Elementarnoy dizyunktsieyn változók nevezik diszjunkcióját változók vagy azok negáltjai.
Meghatározása 6.Konyunktsiya normál forma (CNF) általános képletű A egyenértékű azzal képletű képviselő együttállása elemi diszjunkcióban.
Meghatározása 7.Sovershennoy konjunktív normál forma a képletű (SKNF A), az úgynevezett CNF A. kielégítő négy tulajdonságok:
1) az összes elemi diszjunkció szerepel a CNF A. tartalmazza az összes változót;
2) az összes elemi diszjunkciót szerepelnek a CNF A. különböző;
3) minden egyes elemi diszjunkció, A. részében CNF tartalmaz egy időrés változó;
4) egyik elemi diszjunkciót, tagja a CNF A. nem tartalmaz egy változó és a negáltja.
SKNF lehet előállítani két módja van: a) útján igazság táblázatot (a dualitás törvényének, megkapjuk a segítségével igazság táblák
Jellemzően termelnek SKNF általános képletű, vagy ekvivalens transzformációk.
1. Annak érdekében, hogy bármely képletű CNF.
2. Egy CNF egyenértékű transzformációk kapjunk SKNF A. következetesen elérése teljesítményt tulajdonságait négy SKNF.
1) Ha egy elemi diszjunkciót V. tagja CNF nem tartalmazza a variábilis A.
2) Ha egyes elemi diszjunkció változó
3) Ha a CNF Egy tartalmaz két azonos elemi diszjunkciót, majd az egyik lehet dobni, mint
4) Ha az elemi diszjunkció egy pár
1. példa Find általános képlettel meghatározott függvény F (x, y, z), és amelyet az igazság táblázat:
Határozat. Származtatása szabály a következő képlet segítségével algebra logikai igazság táblázat függvény F (x, y, z), kapjuk:
.
Egyszerűbb a képlet, ezt kapjuk:
Ezért a kívánt meghatározó képlet függvény F (x, y, z), lehet tekinteni
2. példa A következő képlettel oka PDNF korábban hozza annak ekvipotenciális DNP transzformációk :.
Képlet 3. példa A 2. példa PDNF által talált elkészítése igazság táblázat.
Határozat. Alkotunk egy igazság táblázat a képlet.
4. példa A képlet a 2. példa, hogy megtalálják SKNF egyenértékű átalakulások korábban, hogy azt a CNF.
Határozat. 2. példa: A továbbiakban
.
5. példa Formula 2. példa találni SKNF, meghatározva a negáltja előtti DNP, majd a következő képlet segítségével kettősség.
Minden Boole-formulával vannak osztva három osztályba: 1) azonosan igaz; 2) azonosan hamis; 3) megvalósítható.
A képlet az úgynevezett megvalósítható. ha 1 legalább egy értékrend a tag változók és nem ugyanaz, mint az igazság.
Teoreme.Dlya a logikai formula azonosan igaz (hamis), akkor és csak akkor, ha minden elemi diszjunkció (együtt) részében CNF (DNF A) tartalmaz egy változót és a tagadás.
6. példa Will képletű azonosan igaz azonosan hamis vagy megvalósítható?
Határozat. Itt egy példa, hogy minden normális formában:
Előállítása DNP nem azonos a hamis, hiszen minden egyes elemi együtt tartalmaz egy változó és a negáltja. Következésképpen, az eredeti képlet igaz azonosan vagy megvalósítható. Transzformálására adott CNF képlet.
Ez a munka nem ugyanaz igaz, mint az összege elemi
1.34. Az igazság táblázat kap a meghatározó képlet a függvény
1.35. enged
1.36. Hívjuk a funkció a többség
a) Készíts egy táblázatot, amely meghatározza a funkciója a többség és kifejezni ezt a funkciót tekintve alapvető műveleteket.
b) Egyszerűbb a kifejezést
1.37. Boole-függvény
.
Minden Boole-függvény két változó kap kettős Boole-függvény.
1.38. Boole-függvény
a) megőrzi 0, ha;
b) megőrizve az 1 ha.
Között a Boole-függvények egy vagy két változó, hogy megtalálja az összes funkciót, hogy megőrizze az 1. és az összes funkciót, hogy megőrizze 0.
1.39. A következő képletek és megtalálni PDNF SKNF minden kétféleképpen (ekvivalencia transzformációk és használata az igazság táblázat):
1.40. Keresse PDNF azonosan igaz az összes képlet, amely tartalmaz: 1) egy variábilis, 2) két változó, 3) három változó.
1.41. Keresse SKNF azonosan igaz az összes képlet, amely tartalmaz: 1) egy variábilis, 2) két változó, 3) három változó.
1.42. Bizonyítsuk egyenértékűség képletek
1.43. Keresse meg a legegyszerűbb formája a képlet, a következő teljesen normális formában:
1.44. A kritérium azonos igazság és hamisság képletű identitás, meghatározza, hogy az adott képlet azonosan igaz, hamis vagy azonosan megvalósítható: