endast erinevate täielike EKD 3 Valemi F TKNK nim valemiga F samaväärset valemit, mis kujutab endast erinevate täielike EDK. Kui valem F ei ole samaselt väär, siis tal leidub TDNK. Kui valem F ei ole samaselt tõene, siis tal leidub TKNK (Teoreem 5+Järeldus 1) 4 Täielikule disjunktiivsele normaalkujule viimise algoritmi sammud 1) Elimineerida valemist implikatsioonid ja ekvivalentsid. 2) Viia eitused vahetult lausemuutujate ette, jätta ära kahekordsed eitused. 3) Viia konjunktsioonid disjunktsioonidest sügavamale. 4) Jätta ära samaselt väärad ja korduvad liikmed ning liikmetest korduvad literaalid. 5) Lisada liikmetele puuduvad lausemuutujad ning viia uuesti konjunktsioonid disjunktsioonidest sügavamale. 6) Järjestada igas liikmes literaalid ja jätta ära korduvad liikmed
o TDNK-le viimine: Koostame valemi põhjal tõeväärtustabeli Vaatame vaid neid ridu, mil valem on tõene Koostame konjuktsioonid ridadele vastavatest elementide tõeväärtustest (nt kui X=t, Y=t ja Z=v, siis saame X&Y&¬Z) Ühendame saadud konjuktsioonid ühiseks disjunktsiooniks o TDNK-le viimise algoritm: Elimineerida implikatsioonid ja ekvivalentsid Viia eitused vahetult lausemuutujate ette (st konjunktsioonide ja disjunktsioonide sisse) Korrutada disjunktsioonid läbi (distributiivsuse seaduse abil) Kaotada samaselt väärad konjunktsioonid ja sama liikme mitmekordsed esinemised konjunktsioonides Lisada konjunktsioonidele puuduvad muutujad Korrastada valem (järjestada muutujad konjunktsioonides ja
Tõestus. Et valem ¬F ei ole samaselt väär, siis leidub tal täielik disjunktiivne normaalkuju. Leiame mõlemast poolest eituse, seejärel viime paremal eituse sissepoole De Morgani seaduste abil. Nii saame Paremal poolel võis lausemuutujate ette tekkida kahekordseid eitusi. Jättes need ära, ongi tulemuseks valemi F täielik konjunktiivne normaalkuju TDNK’le teisendamise algoritm, etappidel kasutatavad samaväärsused o Elimineerime implikatsioonid ja ekvivalentsid 8 F → G ≡ ¬F ∨ G, F ↔ G ≡ F & G ∨ ¬F & ¬G o Viime eitused vahetult lausemuutujate ette, kasutades De Morgani seadusi ¬(F & G) ≡ ¬F ∨ ¬G, ¬(F ∨ G) ≡ ¬F & ¬G Kui kuskile tekib kahekordne eitus, siis jätame selle ära. o Viime konjunktsioonid disjunktsioonidest sügavamale, kasutades distributiivsuse seadusi F & (G ∨ H ) ≡ F & G ∨ F & H (F ∨ G) & H ≡ F & H ∨ G & H
b) X Y Z (X Z) (Y Z) 5) a) X X X b) X X X 6) a) X t X b) X v v c) X t t d) X v X 7) a) ¬(X Y ) ¬X ¬Y b) ¬(X Y ) ¬X ¬Y 8) a) X Y ¬Y ¬X b) X Y ¬X Y c) X Y ¬(X ¬Y ) 9) a) X Y ¬(X ¬Y ) b) X Y ¬X Y 10) a) X Y (X Y ) (Y X) b) X Y X Y ¬X ¬Y Täielikule disjunktiivsele normaalkujule teisendamine. 1. Asenda implikatsioonid ja ekvivalentsid samaväärsete valemitega 8b), 10b) 2. Vii eitused vahetult muutujate ette 7a), 7b), 1) 3. Vii konjunktsioonid disjunktsioonidest sügavamale 4a) 4. Eemalda samaselt väärad ja võrdsed lihtkonjunktsioonid X ¬X v, 6d), 5b) 5. Tee lihtkonjunktsioonid täielikeks K K t K (X ¬X) K X K ¬X 4. LOENG Hulga mõiste ja osahulk
annaabi.ee 
