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

Таким образом, логические значения формул полностью о п ­ ределяются логическими значениями элементарных высказыва­ ний, из которых эти формулы состоят. Так, формула из примера 3 будет истинна, только если X — ложно, a Y — истинно. Во всех остальных случаях она —ложна. Две формулы алгебры логики А и В называются равносильны­ ми, если они принимают одинаковые логические значения при любом наборе значений элементарных высказываний, входящих в них. Обозначают равносильности (тождества) с помощью зн а ­ ка =. Формула А называется тождественно-истинной, или тавтоло­ гией, если она принимает значение «истинно» при всех значениях переменных, входящих в нее. Иными словами, тавтологией явл я ­ ется функция, где все переменные фиктивны и хотя бы при од ­ ном наборе значений аргументов ее значение равно 1. Так, тавто­ логиями будут: 1 ) a v а\ 2 ) а -» (Ь -> а)\ 3) a v (а -> (Ь -» а)). Первое утверждение a v а = 1 было доказано в подразд. 4.2. Докажем второе а - » (b -> а) - 1 (табл. 4.15). Т а б л и ц а 4.15 Таблица истинности а ь b -* а а -> (Ь -» а) 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 1 Третье a v (а - » (b -> а)) = 1 следует из второго и формулы a v l = = 1. Формула называется тождественно-ложной, если она прини ­ мает значение нуль при всех значениях переменной, входящих в нее. Так, тождественно-ложны формулы (а а) и (а а) • (а v v b -» а) (табл. 4.16). Т а б л и ц а 4.16 Таблица истинности а ь а а <-> а b —> о a v b—>а (о а) ■(a v b — » а) 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 155