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

• а = а — снятие двойного отрицания; • a - ^ b - a ' w b —_снятие импликации; • a ~ b = a b v a - _b — снятие эквиваленции; • а V b = ab v ab — снятие строгой дизъюнкции. Все эти формулы получаются простой проверкой по таблице истинности с учетом истинности каждой операции, правильного раскрытия скобок и выполнения операций по приоритету. Чита­ телю предлагается проверить самому эти тождества. Знание законов математической логики помогает не только упрощать высказывания, но и правильно, логически рассуждать. Так, некоторые формулы помогают понять законы правильного мышления (см. далее в подразд. 4.4). С помощью введенных логических операций над высказывани­ ями можно строить различные сложные высказывания. Использо­ вание скобок дает возможность установить порядок выполнения операций. Рассмотрим несколько примеров на установление истинности сложного высказывания. 1. ( X v Y ) - * Y -+Х. Истинность сложного высказывания можно установить с п о ­ мощью таблицы истинности (табл. 4.12). Введем порядок действий, определяющий последовательность столбцов в таблице истинности для высказывания (X v У) -» - ^ Y ^ ± X : _ _ = ____ _ =------- 1) X; 2) X v У; 3) У; 4) У -» X; 5) У -> X; 6) (X v У) ->У -> Любые простые и сложные высказывания, полученные из эл е ­ ментарных высказываний с помощью конечного числа введенных логических операций, называются формулами алгебры логики. Для упрощения формул, содержащих скобки и различные л о ­ гические операции, будем учитывать ряд правил. Так, при опус­ кании скобок: • самой первой выполняется конъюнкция между элементарны­ ми высказываниями и их отрицаниями; • дизъюнкция выполняется раньше импликации и эквиваленции; • знак отрицания над формулой дает возможность опустить скоб ­ ки, в которых эта формула заключена. Т а б л и ц а 4.12 Таблица истинности для двух переменных X Y X X v Y 7 F -» X 7 -» X ( X V У) -> 7 -У X 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 153