Нетрудно видеть, вычисление “в лоб” таблицы истиности для этого выражения потребовало бы таблицы из 24=16 строк. Используя прием незначащих состояний, удается сократить число рассматриваемых состояний до 5. Тавтология. Высказывания, которые истинны при любом состоянии своих переменных, играют особую роль и называются общезначимыми или тавтологиями. Определение 5.2. Тавтология - высказывание, значение которого - Т на любом состоянии переменных этого выражения. Противоречие - высказывание, значение которого - F, на любом состоянии переменных этого выражения. Для доказательства утверждения, что некоторое выражение - тавтология, у нас пока есть только таблицы истиности. Докажем, что pÚØp - тавтология. Ниже показана таблица истиности для pÚØp (Таблица 5.6.) Таблица 5.6. Таблица истиности для pÚØp
|
Главная