Проблема разрешимости

1.

2. Классы логических формул

• тождественно истинные (тавтологии);
• тождественно ложные (противоречия);
• выполнимые (нейтральные).

3. Тавтология

Формула A называется тождественно
истинной (или тавтологией), если она
принимает значение 1 при всех значениях
входящих в нее переменных.

4. Противоречие

Формула A называется тождественно
ложной (или противоречием), если она
принимает значение 0 при всех значениях
входящих в нее переменных.

5. Выполнимая

Формула A называется выполнимой (или
нейтральной), если она принимает значение
“истина” хотя бы на одном наборе значений
входящих в нее переменных и не является
тавтологией.

6. Проблема разрешимости

В связи с этим возникает задача получения
ответа на вопрос: к какому классу относится
данная формула?

7. Способы решения

• с помощью таблиц истинности;
• с помощью равносильных преобразований;
• приведение формулы к нормальной форме.