![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Если у двух логических функций совпадают таблицы истинности, то есть на всех наборах значений входных переменных они принимают одинаковое значение, то их называют равносильными или эквивалентными. Это обозначается знаком = (равно).
Для преобразования формул в равносильные важную роль играют следующие равенства, отражающие свойства логических операций, которые по аналогии с алгеброй вещественных чисел будем называть законами:
Переместительный закон (закон коммутативности):
a + b = b + a, a∙b = b ∙a. (4)
Сочетательный закон (закон ассоциативности):
(a + b) + c = a + (b + c), (5)
(a∙ b)∙ c = a∙ (b∙ c). (6)
Закон исключения констант (нуля и единицы):
a +0 = a, A∙1=A. (7)
Распределительный закон (закон дистрибутивности):
(a + b)∙ c = a∙ c + b∙c, (8)
(a + c)∙ (b + c) = a∙b + c, (9)
(a b)∙ c = a∙ c
b∙c. (10)
Закон противоречия:
(11)
Закон равносильности (идемпотентности):
. (12)
Закон двойного отрицания: (13)
Закон инверсии (формулы де Моргана):
(14)
(15)
Закон поглощения:
(16)
(17)
Закон склеивания (закон исключения):
(18)
(19)
Любой из этих законов может быть легко доказан с помощью таблиц истинности.
Докажем первый закон де Моргана (14) с использованием таблиц истинности. Построим таблицы истинности для левой и правой частей закона.
a | b | a+b | ![]() | ![]() | ![]() | ![]() |
Так как результирующие столбцы ( и
) совпали, то формулы, стоящие в левой и правой частях закона, равносильны.
Любой из законов алгебры высказываний может быть доказан путем логических рассуждений.
Докажем ещё один закон поглощения путем логических рассуждений. Для этого достаточно показать, что если правая часть истинна, то и левая часть истинна, и что если левая часть истинна, то и правая часть истинна.
Пусть истинна правая часть, т. е. A = 1, тогда в левой части дизъюнкция истинна по определению дизъюнкции. Пусть истинна левая часть. Тогда по определению дизъюнкции истинна или формула A, или формула
, или обе эти формулы одновременно. Если A ложна, тогда
ложна. Следовательно, A может быть только истинной.
Еще одним способом вывода новых формул являются тождественные преобразования. Например, тот же закон поглощения можно вывести при помощи законов исключения единицы и дистрибутивности:
Для операций импликации, эквивалентности и строгой дизъюнкции также может быть сформулирован ряд важных свойств. В частности, каждая из этих операций может быть выражена через конъюнкцию, дизъюнкцию и отрицание. Убедитесь в этом, доказав самостоятельно следующие соотношения:
Дата публикования: 2014-11-28; Прочитано: 516 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!