Similar presentations:
Проблема разрешимости
1.
2. Классы логических формул
• тождественно истинные (тавтологии);• тождественно ложные (противоречия);
• выполнимые (нейтральные).
3. Тавтология
Формула A называется тождественноистинной (или тавтологией), если она
принимает значение 1 при всех значениях
входящих в нее переменных.
4. Противоречие
Формула A называется тождественноложной (или противоречием), если она
принимает значение 0 при всех значениях
входящих в нее переменных.
5. Выполнимая
Формула A называется выполнимой (илинейтральной), если она принимает значение
“истина” хотя бы на одном наборе значений
входящих в нее переменных и не является
тавтологией.
6. Проблема разрешимости
В связи с этим возникает задача полученияответа на вопрос: к какому классу относится
данная формула?
7. Способы решения
• с помощью таблиц истинности;• с помощью равносильных преобразований;
• приведение формулы к нормальной форме.