Поняття лог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. Припустимо, що формула 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(H1) = 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(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 висловлювань.

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вал. F ~G.

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

Дата добавления: 2015-09-04