Головна |
Нехай формули 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. | Незалежна система функцій і базис функціонально замкнутого класу. | Мінімізація ДНФ. Метод мінімізують карт. | Аксіоматичні теорії. Визначення та властивості обчислення висловлювань. | Повнота і несуперечність обчислення висловлювань. Незалежність аксіом. | Общезначімость виведених в численні предикатів формул. |