Спирина, М.С. Дискретная математика

Т а б л и ц а 4.6 Таблица истинности X Y Y (4f-> Y ) X ((X -» Y ) X ) -> Y 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 Все точные знания, такие, как математические теоремы, фи­ зические, химические или биологические законы, а также собы­ тия повседневной жизни, ситуации, связанные с управлением различными системами, можно сформулировать в виде высказы­ ваний и перевести на язык алгебры логики. С помощью математи­ ческой логики устанавливается истинность или ложность слож­ ных высказываний на основе истинности или ложности простых. Если доказательство основано на применении таблиц истин­ ности, то говорят, что использован семантический способ доказа­ тельств, если в процессе доказательства использовались равно­ сильности алгебры логики, то способ называют синтактическим. Задача 21. Поможем синоптикам определить прогноз погоды. Известно, что если атмосферное давление понижается, то возмо­ жен дождь. В настоящее время атмосферное давление понижается. Возможен ли дождь? Решение. Формализуем условия задачи, введя обозначения. Пусть X — атмосферное давление понижается; Y — возможен дождь. Высказывание «Если давление понижается, то возможен дождь» имеет вид: Х-> Y. Тогда «Если давление понижается, то возможен дождь. Давление понижается» можно записать в виде конъюнкции (Х-+ Y) ■X. Сформулируем теорему: (( X - -> Y)X) -> Y - 1. Докажем истинность вывода, используя оба способа. Синтактический cnocofx ((ЛГ-> 0 -» Y - ((Д v У) • X) -» Y = = ( Y X ) - > Y = X Y v Y =X v Y v Y =X v 1 = 1. Семантический способ представлен в табл. 4.6. Из табл. 4.6 видно, что теорема истинна при любом наборе значений X и Y. Таким образом, доказана справедливость утверж­ дения «Возможен дождь». Получение тождественной единицы под­ тверждает справедливость доказываемой теоремы. 4.3.2. Необходимое и достаточное условия импликации Все логические операции имеют широкое применение в обыч­ ной речи. Но особенно важное значение в познании имеют опера­ ции импликации и эквиваленции. Рассмотрим пример. Высказы- 6 Дискретная математика 145