Головна

Равносильность формул логіки предикатів. Правила переходу до рівносильним формулам в логіці предикатів, що збігаються з аналогічними правилами в логіці висловлювань.

  1.  B. ЕПР-кореляції в синаптичних переходах в мозку як можлива основа породження свідомості
  2.  I. Загальнодержавні норми і правила з ОП
  3.  I. Правила і норми з техніки безпеки.
  4.  I. Рішення логічних задач засобами алгебри логіки
  5.  III. Формулюємо своїми словами виділену інформацію, робимо пропозиції коротше.
  6.  III.2.10. Ознаки незавершеності демографічного переходу в Росії
  7.  III.2.3. Типи проходження демографічного переходу

Нехай формули F і G мають один і той же безліч вільних змінних (зокрема, пусте).

Формули F і G рівносильні в даній інтерпретації, якщо на будь-якому наборі вільних змінних вони приймають однакові значення (тобто якщо формули виражають в даній інтерпретації один і той же предикат).

Формули F і G рівносильні на множині M, якщо вони рівносильні у всіх інтерпретаціях, заданих на множині M.

Формули F і G рівносильні (в логіці предикатів), якщо вони рівносильні у всіх множинах (тоді будемо писати F  G).

Зазначимо кілька правил переходу від одних формул до інших, їм рівносильним (у всіх інтерпретаціях). Для формул ЛП зберігаються всі равносильности і правила рівносильних перетворень логіки висловлювань. Крім того, існують такі правила:

1. Перенесення квантора через заперечення. Нехай A - формула ЛП, що містить вільну змінну x. Тоді справедливі равносильности

(  x) A (x) (  x)  A (x);

(  x) A (x) (  x)  A (x).

Оскільки кванторів всього два, то можна вважати їх протилежними один одному. Тоді це правило можна формулювати і так: при перенесенні квантора через заперечення він змінюється на протилежний.

2. Винесення квантора за дужки. Нехай формула A (x) містить вільну змінну x, формула B не містить змінної x і немає змінних, вільних в одній з них і пов'язаних в інший. тоді

(  x) (A (x) & B) (  x) A (x) & B;

(  x) (A (x) & B) (  x) A (x) & B;

(  x) (A (x)  B) (  x) A (x)  B;

(  x) (A (x)  B) (  x) A (x)  B.

3. Перестановка однойменних кванторів:

(  x) (  y) A (x, y) (  y) (  x) A (x, y);

(  x) (  y) A (x, y) (  y) (  x) A (x, y).

4. Перейменування пов'язаних змінних. Замінюючи пов'язану змінну формули A іншої змінної, яка не входить в цю формулу, в Квантором і всюди в області дії квантора, отримуємо формулу, рівносильну A. Це правило застосовується при складанні формул ЛП з формул A і B, якщо є змінні, вільні в одній з них і пов'язані в інший. Таку пов'язану змінну замінюємо іншої змінної, яка не входить в ці формули.

16. Теорема про існування наведеної форми для кожної формули логіки предикатів.

теорема: Для будь-якої формули існує рівносильна їй наведена формула, причому безлічі вільних і пов'язаних змінних цих формул збігаються. Така наведена формула називається наведеної формою даної формули.

17. Теорема про існування нормальної форми для кожної наведеної формули логіки предикатів.

теорема: Для будь-якої наведеної формули існує рівносильна їй нормальна формула тієї ж довжини. Така формула називається нормальною формою даної наведеної формули.




 Формули логіки висловлювань та їх еквівалентність. Правило рівносильних перетворень. |  Двоїстість. Закон подвійності. |  Нормальні форми формул. Теорема про єдиності СДНФ і СКНФ. |  Повні системи булевих функцій. Суперпозиції. Теорема про повноту системи функцій, виражених за допомогою суперпозиції через функції іншої повної системи. |  Функціонально решітка поста. Замкнені класи T0, T1. |  Незалежна система функцій і базис функціонально замкнутого класу. |  Мінімізація ДНФ. Метод мінімізують карт. |  Аксіоматичні теорії. Визначення та властивості обчислення висловлювань. |  Повнота і несуперечність обчислення висловлювань. Незалежність аксіом. |  Общезначімость виведених в численні предикатів формул. |

© 2016-2022  um.co.ua - учбові матеріали та реферати