нетрудно заметить, что последний столбец в этой таблице совпадает со столбцом для p. Поэтому, можно сказать, что с этой точки зрения выражение (pÚq)Ù(pÚØq) эквивалентно p, и везде, где мы встретим это выражение, мы можем его заменить на p. Как мы уже отмечали, одной из наших забот является упрощение сложных высказываний. Поэтому, для упрощения выражений, мы определим, что означает для двух выражений быть эквивалентными и заменим более сложное на менее сложное. Определение 5.3. Два высказывания называются эквивалентными, если они на одних и тех же состояниях своих переменных принимают одни и те же значения. Другими словами, если эти высказывания имеют одинаковые таблицы истиности, то они эквивалентны. Таким образом, один способ установить эквивалентность двух высказываний - вычислить их таблицы истиности и сравнить. Мы, однако, воспользуемся другим способом. Теорема 5.1. Два высказывания p и q - эквивалентны (обозначается pºq) тогда и только тогда, когда pÛq - общезначимо. Доказательство: Пусть pºq. Значит таблицы истиности для p и q совпадают. Следовательно, на тех состояниях, где p=Т, q=Т также, а где p=F, то и q=F. Отсюда следует, что pÛq всегда Т (поскольку мы имеем либо ТÛТ, либо FÛF), т.е. pÛq - общезначимо или тавтология. Пусть pÛq -общезначимо. Тогда если p=Т, то q должно быть Т, а если p=F, то и q должно быть F. Таким образом, на одних и тех же состояниях эти выражения принимают одинаковые значения. Следовательно, таблицы истиности для p и q совпадают. Последнее означает по определению , что pºq. (Доказательство закончено.) Эта теорема показывает, что установить эквивалентность можно, доказав общезначимость специального высказывания. Свойства эквивалентности. Основные, часто используемые свойства эквивалентности приведены в таблице 5.8. Таблица 5.8. Свойства эквивалентности
|
Главная