Поняття логiчн. насл. Теор. про еквiвалентнiсть рiзних означень логiчного наслiдку. modus ponens, modus tollens, правило силогiзму, метод резол.

Поняття логiчн. насл. Теор. про еквiвалентнiсть рiзних означень логiчного наслiдку. modus ponens, modus tollens, правило силогiзму, метод резол.

F називається логiчним наслiдком ф-л H1, H2, H3,..., Hn, якщо для довiльної iнтерп. I простих висл., що входять в цю формулу з рiвностей

I(H1) = I(H2) = ... = I(Hn)=1 випливає, що I(F)=1.

Запис: H1, H2,..., Hn |= F

modus ponens: A, A→B|= B

modus tallens: A→B, B |= A

силогiзму: A→B, B→C|= A→C

резолюцiй: X→F, X → G |= F∨G

Теорема. Наступнi твердження є рiвносильними

1. H1, H2,..., Hn |= F;

2. Формула (H1 ∧ H2 ∧ ... ∧ Hk) → F є тавтологiєю;

3. Формула H1 ∧ H2 ∧ ... Hk ∧ F є тотожно хибною;

4. Формула H1 ∨ H2 ...Hn ∨ F є тотожно-iстиною.

Доведення. Для доведення теореми покажемо, що справедливим є такий

ланцюг iмплiкацiй 1. → 2. → 3. → 4. → 1.

1. → 2. Припустимо, що Поняття логiчн. насл. Теор. про еквiвалентнiсть рiзних означень логiчного наслiдку. modus ponens, modus tollens, правило силогiзму, метод резол. формула F є логiчним наслiдком формул H1, H2,..., Hn.

Покажемо, що формула (H1 ∧ H2 ∧ ... ∧ Hk) → F є тавтологiєю. Припустимо, що це не так. Це означає, що iснує така iнтерпр. I простих висловлювань, якi входять в цю формулу, що I((H1 ∧ H2 ∧ ... ∧ Hk) →

F)=0. Звiдки, використовуючи властивiсть iмплiкацiї i кон’юнкцiї, отримаємо I(H1) = I(H2) = ... = I(Hn)=1 i I(F)=0, що неможливо, оскiльки формула F є логiчним наслiдком формул H1, H2,..., Hn. Отримали суперечнiсть, а отже формула є тавтологiєю.

2. → 3. H1 ∧ H2 ∧ ... Hk ∧ F може набувати значення істина для деякої iнтерпретацiї I тодi i тiльки тодi, коли I(H Поняття логiчн. насл. Теор. про еквiвалентнiсть рiзних означень логiчного наслiдку. modus ponens, modus tollens, правило силогiзму, метод резол.1) = I(H2) = ... = I(Hn)=1 i I(F)=1, тобто I(F)=0. А це неможливо, оскiльки формула

(H1∧H2∧...∧Hk) → F є тавтологiєю. Отже формула H1∧H2∧... Hk∧F є тотожно хибною.

3. → 4. Якщо формула H1 ∧ H2 ∧ ... Hk ∧ F є тотожно хибною, то для будь-якої iнтерпретацiї I, якщо I(H1) = I(H2) = ... = I(Hn)=1, то I(F)=0. Припустимо, що для деякої iнтерпретацiї I формула (H1 ∨ H2 ∨ ... ∨ Hn ∨ F) набуває значення 0. Це можливо тодi i тiльки тодi, коли I(H1) = I(H2) = ... = I(Hn) = I(F)=0, звiдки I(H1) =I(H2) = ... = I(Hn)=1 i I(F)=0, але оскiльки виконується твердження3., то для цiєї iнтерпретацiї Поняття логiчн. насл. Теор. про еквiвалентнiсть рiзних означень логiчного наслiдку. modus ponens, modus tollens, правило силогiзму, метод резол. I з того, що I(H1) = I(H2) = ... = I(Hn)=1 повинно випливати I(F)=0. Отримали суперечнiсть. Отже формула H1 ∨ H2 ...Hn ∨ F тотожно iстинна.

4. → 1. Те, що формула H1 ∨ H2 ∨ ... ∨ Hn ∨ F є тотожно істиною означає, що для довiльної iнтерпретацiї I з умови I(H1) = I(H2) = ... = I(Hn)=0 випливає I(F)=1. Тобто, для довiльної iнтерпретацiї I

якщо I(H1) = I(H2) = ... = I(Hn)=1, то I(F)=1. А це, за визначенням логiчного наслiдку, означає, що формула F є логiчним наслiдком ф-лH1, H2,..., Hn.

3. Еквiвалентнi формули, приклади. Теорема про еквiвалентнiсть рiзних означень еквiвалентних формул. Основнi властивостi логiчних операцiй, зокрема закони дистрибутивностi Поняття логiчн. насл. Теор. про еквiвалентнiсть рiзних означень логiчного наслiдку. modus ponens, modus tollens, правило силогiзму, метод резол. та де Моргано. Принцип двоїстостi в численнi висловлювань.

X i Y називаються еквiвалентними, якщо для будь-якої iнтерпретацiї I має мiсце I(X ) = I(Y).

Теорема Наступнi твердження є рiвносильними.

A). X ~ Y;

Б). таблицi iстинностi формул X , Y збiгаються;

В). формула X↔Y є тавтологiєю.

(X ∧X ) ~X~ (X ∨X ); (X ∧Y) ~ (Y∧X )

дистрибутивнiсть:

((X ∧Y) ∨ Z) ~ ((X∨Z) ∧ (Y∨Z));

((X ∨Y) ∧ Z) ~ ((X∧Z) ∨ (Y∧Z));

закони де Моргана:

(X ∧Y) ~ (X ∨ Y); (X ∨Y) ~ (X ∧ Y).

Принцип двоїстостi числення висловлювань.

Якщо двi еквiвалентнi формули (F G) мiстять лише зв’язки , ∨, ∧, то Поняття логiчн. насл. Теор. про еквiвалентнiсть рiзних означень логiчного наслiдку. modus ponens, modus tollens, правило силогiзму, метод резол. замiною зв’язок ∨ на ∧ i ∧ на ∨ в обох формулах отримаємо еквiвал. F ~G.

4. Поняття про ДНФ та КНФ. Теорема про еквiвалентнiсть довiльної формули числення


documentarktzaf.html
documentarkugkn.html
documentarkunuv.html
documentarkuvfd.html
documentarkvcpl.html
Документ Поняття логiчн. насл. Теор. про еквiвалентнiсть рiзних означень логiчного наслiдку. modus ponens, modus tollens, правило силогiзму, метод резол.