Читайте также:
|
Две формулы Ф и 
называются равносильными или эквивалентными (обозначаются 
или 
), если они задают одну и ту же булеву функцию, т.е. при любых значениях пропозициональных букв, входящих в них, Ф и принимают одинаковые значения.
Отношение равносильности на множестве формул является отношением эквивалентности. Действительно, легко заметить, что каждая формула равносильна себе (рефлективность); если , то 
(симметричность); если 
и 
, то 
(транзитивность).
Теорема об эквивалентной замене. Если 
- формулы и 
является подформулой формулы Ф, причем и формула 
- есть результат замены какого-либо вхождения в Ф подформулы на 
, то 
.
В заключение этого пункта введем еще три часто употребляемые понятия. Формула Ф называется противоречивой (или невыполнимой), если она принимает только значение ложь, выполнимой в противном случае, опровержимой, если она не является тавтологией.
Формула 
является противоречивой, а 
- опровержимой и выполнимой.
Акцентируя внимание студентов, что проверка того, является ли данная формула тавтологией, является одновременно и проверкой на опровержимость. Эту проверку можно производить и методом построения контрпримера, только на первом шаге нужно присваивать формуле значение И: этот же процесс проверяет формулу на выполнимость.
Дата добавления: 2015-11-14; просмотров: 75 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Построение контрпримера | | | Некоторые логические законы |