Лекции.Орг
 

Категории:


Универсальный восьмиосный полувагона: Передний упор отлит в одно целое с ударной розеткой. Концевая балка 2 сварная, коробчатого сечения. Она состоит из...


Архитектурное бюро: Доминантами формообразования служат здесь в равной мере как контекст...


Деформации и разрушения дорожных одежд и покрытий: Деформации и разрушения могут быть только покрытий и всей до­рожной одежды в целом. К первым относит...

Випереджені нормальні форми



У логіці висловлювань були введені дві нормальні форми: кон’юнктивна і диз’юнктивна. В аксіоматичній системі логік вводиться третя нормальна форма, яку називають випередженою нормальною формою.

Означення 4.2.1.Формула Ф у логіці предикатів знаходиться у випередженій нормальній формі (ВНФ) тоді і тільки тоді, коли вона може бути зображена у вигляді ( )… ( ) (А), де ( ) є або ( х), або ( х) і всі різні для різних і = 1, …, п, а А – формула, що не містить квантора. Приставку ( ) називають префіксом, а Аматрицею формули Ф. Якщо формула А залежить від вільної змінної х, то це записується як А (х), якщо ні, то – А.

Теорема 4.2.1.Для будь-яких формул F, G, H теорії числення першого порядку справедливі такі еквівалентності:

а) х F(x) х ( F (x));

б) х F(x) х ( F(x));

в) х F(x) G х (F(x) G);

х F(x) G х (F(x) G);

г) х F(x) G х (F(x) G);

х F(x) G х (F(x) G);

д) х F(x) х Н (х) х (F(x) Н (х));

е) х F(x) х Н (х) х (F(x) Н (х));

є) х F(x) х Н (х) х у (F(x) Н (у));

ж) х F(x) х Н (х) х у (F(x) Н (у)).

Доведення . Виконаємо доведення еквівалентності.

а) х F(x) х ( F(x)). Нехай r – довільна інтер-претація на деякій області R. Якщо ( х F(x)) істинна в інтерпретації r, то х F(x) хибна в r. Це означає, що існує такий елемент k(x) R, для якого F ( k (x) ) хибна, або те саме, що F (k (x) ) істинна в r. Отже, х ( F(x)) істинна в r.

Якщо ( х F(x)) хибна в r, то х F(x) істинна в r. Це означає, що F(x) виконується на всіх послідовностях із R або що F(x) не виконується на жодній такій послідовності з R. Отже, х ( F(x)) хибна в r. Таким чином,

( х F(x)) х ( F(x)).

Доведення еквівалентності б) аналогічне доведенню еквівалентності а).

Доведемо еквівалентність в) х F(x) G

Û х (F(x) G). Нехай маємо хF(x) G ( хF(x))→ →G х ( F(x)) → G.

Отже,

1) х ( F(x)) → G – гіпотеза;

2) F(x) → х ( F(x)) – правило 7;

3) F(x) → G – транзитивність із 1) і 2) ;

4) x ( F(x) → G) x (F(x) G) – загальнозначність із 3).

І навпаки:

1) x (F(x) G) x ( F(x) → G) – гіпотеза ;

2) F(x) → G – правило 6 із 1;

3) ( F(x) → G) → ( G → F(x)) ‒ тавтологія ;

4) G → F(x) – МР із 2) і 3) ;

5) x ( G → F(x)) – узагальнення із 4 ;

6) х ( G → F(x)) → ( G → х F(x)) – схема аксіом АП5 ;

7) G → x F(x) – МР із 5 і 6 ;

8) ( G → xF(x)) → ( x F(x) → G) – тавтологія ;

9) x F(x) → G x F(x) G – МР із 7) і 8).

Доведемо спочатку першу еквівалентність г).

1) х F(x) G х ( F(x)) → G – гіпотеза ;

2) ( F(x)) → G – правило 6 ;

3) ( F(x)) → G) → х ( F(x) → G) – правило 7 ;

4) х ( F(x) G) х (F(x) G) – МР із 2) і 3).

І навпаки:

1) х ( F(x) → G) – гіпотеза;

2) х ( F(x) → G) → ( F(x) → G) – правило 7 ;

3) F(x) → G – МР із 1) і 2) ;

4) x ( F(x)) → F(x) – правило 6 ;

5) x ( F(x)) → G x ( F(x)) G х (F(x)) G – транзитивність із 3) і 4).

Доведення інших еквівалентностей із в) і г) тепер легко випливає із законів де Моргана.

x F(x) G ( x F(x) G)

Û (( х F(x)) G ( х ( F(x) G)

Û ( х (F(x) G) x (F(x)) G).

x F(x) G ( x F(x) G)

Û( х ( F(x)) G) ( х ( F(x) G) Û ( х (F(x) G) x (F(x) G).

Аналогічно доводяться й інші еквівалентності із г).

Доведення решти еквівалентностей пропонуються як вправи.

Теорема доведена.

Із теореми 4.2.1 випливає такий метод побудови ВНФ. Для зведення формули Ф до випередженої нормальної форми використовують такі дії:

а) вилучення логічних зв’язок “ →” і “ ” :

А В = (А → В) (В → А) ; А → В = А В ;

б) вилучення і перенесення знака “ ” всередину формул:

( x F(x)) = х ( F(x)); ( х F(x)) =

= x ( F(x)); F = F;

в) перенесення кванторів:

Q x Р(х) G = Q x (F(x) G);

Q x Р(х) G = Q x (F(x) G);

х F(x) х Н (х) = х (F(x) Н (х));

х F(x) х Н (х) = х (F(x) Н (х));

Q1 х F(x) х Н (х) = х у (F(x) Н (у));

Q1 х F(x) х Н (х) = х у (F(x) Н (у)).

Виходячи із методу побудови ВНФ, алгоритм отримання випередженої нормальної форми матиме такі кроки.

1. Вилучити логічні зв’язки еквіваленції “ ” та імплікації “ →” за допомогою правил а).

2. Перенести знак операції заперечення “ ” всередину формул, користуючись правилами: (F G) =

F G; (F G) = F G, і правилами б).

3. Виконати перейменування пов’язаних змінних, якщо є така необхідність.

4. Винести квантори на початок формули, використовуючи правила в).

Обґрунтуванням цього алгоритму є твердження, що безпосередньо випливає з теореми 4.2.1.

Теорема 4.2.2. Алгоритм випередженої нормальної форми перетворює будь-яку формулу А теорії числення предикатів першого порядку АП в таку формулу В, яка знаходиться у ВНФ, що ├ А В у ПL.

Приклад 4.2.1. Звести формулу х F(x) → х Н (х) до ВНФ.

Розв’язання. Користуючись кроками 1, 2, 4 алгоритму, отримаємо

х F(x) → х Н (х) = ( х F(x)) х Н (х) =

= х ( F(x)) х Н (х) = х ( F(x) Н (х)).

Приклад 4.2.2.Отримати ВНФ для формули

х у z (Р (х, у) Р(у, z)) → z R(x, y, z).

Розв’язання. Користуючись кроками 1, 2, 3, 4 алгоритму, отримаємо

х у z (Р (х, у) Р (у, z)) → z R(x, y, z) =

=( z y ( z (Р(х, у) Р(у, z)) z R(х, у, z) =

= x y z ( Р(х, у) Р(у, z)) u R(х, у, и) =

= x y z u ( Р(х, у) Р(у, z) R(х, у, и)).

Оскільки матриця А формули Ф не містить кванторів, то її можна подати у кон’юнктивній нормальній формі (КНФ). Формула Р знаходиться у кон’юнктивній нормальній формі, якщо вона має вигляд Р = ,

де = , і кожне ‒ це атомарна формула або її заперечення.





Дата добавления: 2016-12-31; просмотров: 258 | Нарушение авторских прав


Рекомендуемый контект:


Похожая информация:

  1. A) формирование общегосударственного фонда трудовых ресурсов
  2. I. ЗАВДАННЯ ЦІЄЇ ФОРМИ СКЛАДАЮТЬСЯ ЗІ ВСТУПНОГО ЗАПИТАННЯ ТА ЧОТИРЬОХ ВАРІАНТІВ ВІДПОВІДЕЙ, СЕРЕД ЯКИХ ПОТРІБНО ВИБРАТИ ОДИН ПРАВИЛЬНИЙ.
  3. I. ЗАВДАННЯ ЦІЄЇ ФОРМИ СКЛАДАЮТЬСЯ ЗІ ВСТУПНОГО ЗАПИТАННЯ ТА ЧОТИРЬОХ ВАРІАНТІВ ВІДПОВІДЕЙ, СЕРЕД ЯКИХ ПОТРІБНО ВИБРАТИ ОДИН ПРАВИЛЬНИЙ.
  4. II.Система государственного регулирования цен на лекарственные препараты. Формирование ценовой политики в аптеке.
  5. III. ОРГАНИЗАЦИОННО-УПРАВЛЕНЧЕСКИЕ ОСНОВЫ ФОРМИРОВАНИЯ СЕТИ ПРОФИЛЬНЫХ КЛАССОВ В РЕГИОНЕ
  6. III. Порядок формирования Совета
  7. III. Формирование новых понятий и способов действия.
  8. IV.2.1. Формирование побудительных тенденций.
  9. V. Устная речь. (20 мин) Направлено на формирование компетенции ОК-5.
  10. А. Первоначальное расселение и формирование ветвей славянства
  11. А. Пожизненный, стойкий, типоспецифический B. Не формируется
  12. Аварийно-спасательные и аварийно-восстановительные формирования ОАО РЖД постоянной готовности.


Поиск на сайте:


© 2015-2019 lektsii.org - Контакты - Последнее добавление

Ген: 0.017 с.