Класифікація формул логіки предикатів. ЛЗЗ формули

Серед формул логіки предикатів особливе місце займають тотожно істинні формули. Формула логіки предикатів називається тотожно істинною або логічно загальнозначущою (скорочено ЛЗЗ), якщо вона істинна в будь - якій інтерпретації. Те, що формула α є ЛЗЗ, позначають ╞α (аналогічно позначалися тавтології). Зазначимо, що всі тавтології логіки висловлень є логічно загальнозначущими формулами (кожна формула логіки висловлень є формулою логіки предикатів).

Очевидно, будь - яка формула логіки предикатів, яка одержується з тавтології шляхом застосування підстановки формул якщо до формули логіки висловлень , яка є тавтологією, застосувати підстановку , де – будь - які формули логіки предикатів, одержимо ЛЗЗ формулу логіки предикатів.

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

Крім формул, які є окремими випадками тавтологій, є ЛЗЗ формули, які властиві самій логіці предикатів.

Наведемо деякі з них.

Як уже зазначалося, ЛЗЗ формули є законами логіки.

Зокрема, наведені формули носять назви таких законів:

1, 2 – закони де Моргана для кванторів;

3, 4 – дистрибутивні закони відносно ᴧ і відносно ∨ відповідно;

5 – правосторонній дистрибутивний закон відносно ∨;

6 – лівосторонній дистрибутивний закон відносно;

7 – лівосторонній дистрибутивний закон відносно;

8 – закон пронесення квантора через кон’юнкцію.

Зазначимо, що наведені ЛЗЗ формули 1– 8 можна узагальнити, замінивши атомарні предикати і відповідно довільними формулами і , у яких x –вільна предметна змінна, а Q –будь - якою формулою , яка не містить змінної х.

Для логічно загальнозначущих формул має місце таке твердження: якщо формули α і α→β – логічно загальнозначущі, то формула β також логічно загальнозначуща.

З поняттям логічної загальнозначущості тісно пов’язані питання виконуваності, суперечності формули.

Формула логіки предикатів називається:

1) виконуваною, якщо вона виконувана хоча б в одній інтерпретації;

2) суперечністю (тотожно хибною, невиконуваною), якщо вона хибна в будь - якій інтерпретації;

3) спростовною, якщо вона спростовна хоча б в одній інтерпретації.

Очевидно, має місце наступне твердження:

Формула α – логічно загальнозначуща (суперечна) тоді і тільки тоді, коли ┐α– суперечна (загальнозначуща).