Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Доказательство от противного




В основе МР лежит идея доказательства от противного.

Теорема. Если , где F противоречие, то Г |- S.

Доказательство (для теории £).

1. По теореме дедукции, если Г – множество формул, А и B Î Г и A|-£B, то Г|-А→В.

2. , следовательно .

3. Следствие из теоремы дедукции: А |- B, то |- A ® B.

4. Из 2 и 3 получаем . Т.к. F – противоречие, т. е. F=0, то

5. По теореме дедукции Г®S, следовательно, Г|-S.

 

Пустая формула не является истинной или ложной ни в какой интерпретации и, по определению, является противоречием. В качестве формулы F при доказательстве от противного по МР принято использовать пустую формулу ().

МР работает с особой стандартной формой формул, которая называется предложением или дизъюнктом.

Дизъюнкт - безкванторная ДНФ.






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных