Перевірка правильності міркування шляхом побудови днф або кнф

Візьмемо міркування з попереднього прикладу.

За відомим твердженням (теорема 1) формула (E  C)  D є логічним наслідком формул A  B, (A  C)  D, B  E, якщо формула

F = (A  B)  ((A  C)  D)  (B  E)  ((E  C)  D) є суперечністю.

Для перевірки суперечності необхідно звести дану формулу до ДНФ, застосовуючи співвідношення 1-12 з розділу «Еквівалентні формули логіки висловлень».

Спочатку використаємо кілька разів співвідношення F₁ F₂ = F₁  F₂, щоб вилучити усі входження імплікації (). Маємо:

F = (A  B)  ( (A  C)  D)  (B  E)  ( (E  C)  D).

Зменшимо область дії зв’язки заперечення, де це потрібно, використовуючи співвідношення (F₁  F₂) = F₁  F₂ та (F₁  F₂) = F₁  F₂. Маємо:

F = (A  B)  (A  C  D)  (B  E)  (E  C  D) =

= (A  B)  (A  C  D)  (B  E)  E  C  D.

Далі застосуємо закон F₁  (F₂  F₃) = (F₁  F₂)  (F₁  F₃), де F₁= C  D, F₂=A, F₃=C  D:

F = (A  B)  (((C  D)  A)  ((C  D)  (C  D)))  (B  E)  E.

Приберемо зайві дужки:

F = (A  B)  ((C  D  A)  (C  D  (C  D)))  (B  E)  E.

Застосуємо закон F₁  (F₂  F₃) = (F₁  F₂)  (F₁  F₃), де F₁= C  D, F₂=С, F₃=D:

F = (A  B)  ((C  D  A)  (C  D  С)  (C  D  D))  (B  E)  E.

Спростимо отриману формулу, враховуючи, що F  F=0, а 0  F=0. Отже (C  D  С)= D  0=0, (C  D  D)=С  0=0 й (C  D  A)  0  0 = (C  D  A). Після спрощення та прибирання зайвих дужок маємо:

F = (A  B)  C  D  A  (B  E)  E.

Далі можна застосувати співвідношення F₁  (F₂  F₃) = (F₁  F₂)  (F₁  F₃), де F₁=A, F₂=А, F₃=В:

F = ((А  А)  (А  В))  C  D  (B  E)  E.

Оскільки F  F=0, то А  А=0 й 0  (А  В)= А  В. Отже, формула F приймає вигляд:

А  В  C  D  (B  E)  E.

За законом F₁  (F₂  F₃) = (F₁  F₂)  (F₁  F₃), де F₁=Е, F₂=B, F₃=Е отримаємо:

А  В  C  D  ((Е  B)  (Е  E)).

Оскільки (Е  E)=0, а значить, й (Е  B)  0=Е  B, то формула F буде мати вигляд:

А  В  C  D  Е  B.

Використовуючи властивість F  F=0, де F=B, маємо В  B=0, й тоді формула F приймає вигляд:

А  C  D  Е  0.

Знаючи, що F  0=0, маємо F = 0, тобто F є тотожно хибна формула.

Суперечність формули F доведено. Отже, можна сказати, що формула (E  C)  D є логічним наслідком формул A  B, (A  C)  D, B  E. Таким чином, задане міркування є логічно правильним.

Перевірка правильності міркування методом Девіса й Патнема

За допомогою даного методу перевіряється суперечність формули, поданої у вигляді множини диз’юнктів. Розглянемо міркування з першого прикладу. Щоб визначити, чи є воно логічно правильним, ми побудували за кожним реченням цього міркування формулу логіки висловлення й розглянули задачу: чи є формула, що являється перекладом висновку міркування, логічним наслідком формул, що являються посилками міркування.

За відомим твердженням (теоремою 1.1.1) формула (E  C)  D є логічним наслідком формул A  B, (A  C)  D, B  E, якщо формула

F = (A  B)  ((A  C)  D)  (B  E)  ((E  C)  D)

є суперечністю.

Щоб застосувати метод Девіса й Патнема для розв’язання цієї задачі, необхідно привести подану формулу до КНФ, а потім побудувати множину диз’юнктів.

Перетворимо формулу (AB) ((AC) D) (BE)  ((EC) D) у КНФ частинами:

1. (AB)AB;

2. ((AC) D) (AC) D ACD;

3. (BE)BE;

4.  ((EC) D)  ( (EC) D) (EC) D.

Отже, маємо множину диз’юнктів: S={AB, ACD, BE, E, C, D}, до якої вже можна застосувати метод Девіса й Патнема. Далі ми будемо розглядати диз’юнкти як множини літер.

Перше правило (правило тавтології) не застосовне (множина S не містить тавтологічних диз’юнктів), тому використовуємо друге правило. Спочатку виберемо у множині S однолітерний диз’юнкт (нехай це буде диз’юнкт {Е}), потім викреслюємо з множини S усі диз’юнкти, що містять літеру Е. У даному випадку такий диз’юнкт тільки один. Маємо множину S₁={AB, ACD, BE, C, D}. Множина S₁ не порожня, отже, тепер треба вилучити з диз’юнктів, що входять в S₁, усі входження літери E. Таке входження тільки одне. Після вилучення маємо множину S₂={AB, ACD, B, C, D}. Множина S₂ не містить порожнього диз’юнкту, отже, застосовуємо до неї метод Девіса й Патнема, оскільки S₂ суперечна тоді й тільки тоді, коли суперечна S. Правило тавтології не застосовне до S. За правилом 2 (з диз’юнктом {B}), вилучивши з S₂ диз’юнкт {B}, побудуємо множину S₃={AB, ACD, C, D}, яка не є порожньою. Маємо вилучити з диз’юнктів множини S₃ усі входження літери, контрарної до літери B, тобто літери В. Маємо множину S₄={A, ACD, C, D}. Ця множина не містить порожнього диз’юнкту, отже, до неї застосовуємо метод Девіса й Патнема. Шукаємо перше правило, що застосовне до S₄. Це правило однолітерних диз’юнктів. За цим правилом (з диз’юнктом {A}) маємо множину S₅={ACD, C, D}. Множина S₅ не порожня, тому вилучаємо з диз’юнктів цієї множини усі входження літери A. Маємо множину S₆={CD, C, D}. Оскільки S₆ не містить порожнього диз’юнкту, застосовуємо до неї метод Девіса й Патнема. За правилом 2 (з диз’юнктом {С}) маємо множину S₇={CD, D}. Оскільки S₇ не порожня, вилучаємо з диз’юнктів цієї множини усі входження літери C. Маємо множину S₈={D, D}. Оскільки S₈ не містить порожнього диз’юнкту, перевіряємо її суперечність. За правилом 2 (з диз’юнктом {D}) маємо множину S₉={D}. Оскільки ця множина не порожня, вилучаємо входження літери D з єдиного диз’юнкту {D}, що міститься у S₉. Маємо множину S₁₀={}, яка є суперечною, бо містить порожній диз’юнкт. Отже, й початкова множина диз’юнктів S суперечна.

Таким чином, формула (A  B)  ((A  C)  D)  (B  E)  ((E  C)  D) є суперечною, тому формула (E  C)  D є логічним наслідком формул A  B, (A  C)  D, B  E. Отже, задане міркування є логічно правильним.