Математическая логика и теория алгоритмов

1.9 Логические эквивалентности с кванторами

назад | оглавление | вперёд

 

Теорема. Разноименные кванторы не всегда коммутируют.
Доказательство. Пусть имеется двуместный предикат D ( x , y )= « x делится на y » на множестве натуральных чисел. Тогда очевидно, что и .
       Теорема доказана.

Теорема. Имеют место следующие логические следования и эквивалентности:
  1. Законы де Моргана
           

  2. Коммутация одноименных кванторов
           

  3. Законы дистрибутивности
           

  4. Законы ограничения действия
           

       Теорема доказана.

       Формула А находится в предваренной форме, если она имеет следуюший вид: , где



Теорема. Для любой формулы исчисления предикатов существует логически эквивалентная ей формула в предваренной форме.
Доказательство. Для того, чтобы привести формулу к предваренной форме, используют следующие шаги:        Теорема доказана.

Пример. Рассмотрим построение предваренной формы для формулы .
       .


назад | оглавление | вперёд