Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

53 p p q q ,  , П p p , . Следовательно p q q p Л   )( )( ) ( . Рассмотренный метод может быть использован для проверки того, является ли формула G логическим следствием формул F 1 ,…,F n . Для такой проверки необходимо: 1) представить формулу ... F G F F n 1 2     в виде КНФ, т.е. в виде конъюнкции элементарных дизъюнкций. 2) Если из множества дизъюнктов S { F , ,F ,G} 2 1   удалось вывести П, то G логическое следствие F 1 ,…,F n , в противном случае – нет. Пример 10.6. Доказать, что r является логическим следствием формул p q q r p , ,   . 1) Представляем формулы p q q r   , в виде КНФ: p q p q q r q r       , . , , } , { S p q q r p r    . 2) Резолютивный вывод: p r p q q r    , ; r p r p ,  ; П r r , Пример 10.7. Для задачи проверить вывод на логическое следствие. Если Сергей интересуется логикой, то он посещает лекции по дискретной математике и не пропускает семинарские занятия. Если Сергей посещает лекции, то он пропускает семинарские занятия. Следовательно, Сергей не интересуется логикой. Обозначим элементарные высказывания через пропозициональные переменные: