Diszkrét matematika - 1. rész
Látjuk (lásd az 1.4. Táblázatot), ha értelmezzük j. amelyre j (x) = 0, j (y) = 1, akkor j (F1) = j (F2) = j (F3) = 1, de j (G) = 0. Következésképpen a G képlet nem logikus következménye az F1, F2, F3 képletnek.
A logikai következtetés fogalma szorosan kapcsolódik a kielégülés fogalmához.
Definíció. Az 1., F2, ..., F1 képletek készlete megvalósítható. ha létezik olyan j értelmezés, hogy j (F1) = j (F2) = ... = j (Fl) = 1.
Az 1., F2, ..., F1 képletek készletének érvényességét igazolni lehet, ha ezekhez a képletekhez közös igazságtáblát állítunk össze. Ha van legalább egy olyan vonal, amelyben F1 az F1, F2, ..., Fl képlet oszlopaiban áll, akkor ez a képletkészlet megvalósítható. Ha nincs ilyen vonal, akkor sok képlet nem kivitelezhető. Tehát az előző példa szerinti F2, F3, G> képletek készlete megvalósítható, mivel az első sorban az 1.4 táblázatban 1 oszlop van ezen képletek oszlopaiban.
A 4. témában a következő kijelentésre van szükségünk.
1.2. Tétel A G képlet az F1, F2, ..., Fk képletek logikus következménye, ha és csak akkor, ha a képletek
Bizonyítás. Hagyja, hogy a G képlet legyen az F1, ..., Fk képletek halmazának következménye. Tegyük fel, ellentmondással, hogy az L készlet kielégítõ. Ez azt jelenti, hogy van y értelmezése, hogy y (F1) = ... = y (Fk) = y (Ø G) = 1. De ha y (F1) = ... = y (Fk) = 1, akkor y (G) = 1, mivel G az F1, ..., Fk képletek logikai következménye. A kapott y (t G) = 1 és y (G) = 1 ellentmondás azt bizonyítja, hogy az 1., ..., Fk. Ø G> nem kivitelezhető.
Most hagyjuk, hogy az L képletek sorozata elérhetetlen legyen. Tekintsünk olyan j értelmezést, hogy j (F1) = ... = j (Fk) = 1. Mivel L nem kivitelezhető, akkor j (Ø G) = 0. Ha j (Ø G) = 0, akkor j (G) = 1. Ezért a j (G) = 1 egyenlőség az egyenletek j (F1) = ... = j (Fk) = 1 egyenletéből következik. Ez azt jelenti, hogy G logikus következménye az F1, ..., Fk képletnek.