КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Законы алгебры логики
В логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие: · законы идемпотентности: o x Ù x = x o x Ú x = x · x Ù 1 = x · x Ú 1 = 1 · x Ù 0 = 0 · x Ú 0 = x · x Ù Ø x = 0 – закон противоречия · x Ú Ø x = 1 – закон исключения третьего · Ø Ø x = x – закон снятия двойного отрицания · законы поглощения o x Ù (y Ú x) = x o x Ú (y Ù x) = x Доказательство этих и последующих законов элементарно осуществляется с помощью построения таблиц истинности или простейших логических рассуждений. Следующая группа законов представляет взаимосвязь между логическими операциями: · (x º y) = (x ® y) Ù (y ® x) · x ® y = Ø x Ú y · законы Де Моргана o Ø (y Ú x) = Ø y Ù Ø x o Ø (y Ù x) = Ø y Ú Ø x Замечательным следствием приведенных выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции: конъюнкцию или отрицание или дизъюнкцию или отрицание. Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:
На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок: · Ø x = x | x · x Ù y = (x | y) | (x | y) Также следует отметить, что x | y = Ø (x Ù y).
К основным законам алгебры логики также относятся следующие: · коммутативные законы o х Ù y = y Ù х o х Ú y = y Ú х · дистрибутивные законы o х Ù (y Ú z) = (х Ù y) Ú (х Ù z) o х Ú (y Ù z) = (х Ú y) Ù (х Ú z) · ассоциативные законы o х Ù (y Ù z) = (х Ù y) Ù z o х Ú (y Ú z) = (х Ú y) Ú z Еще одним важным законом алгебры логики является закон двойственности. Пусть формула A содержит только операции конъюнкции, дизъюнкции и отрицания. Для операции конъюнкции двойственной считается дизъюнкция, а для дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из A путем замены в ней каждой операции на двойственную. Например, для формулы (х Ú y) Ù z двойственной формулой будет (х Ù y) Ú z. Для двойственных формул справедлива следующая теорема: если формулы A и B равносильны, то равносильны и двойственные им формулы, то есть A* = B*. Данную теорему оставим без доказательства. С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул. Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула α проще формулы b, если α содержит меньше букв и логических операций. Например, для формулы (Ø (x Ú y) ® x Ú y) Ù y можно записать следующую цепочку преобразований, приводящих ее к более простому виду: (ØØ (x Ú y) Ú x Ú y) Ù y = (x Ú y Ú x Ú y) Ù y = (x Ú y) Ù y = y.
Дата добавления: 2015-04-24; Просмотров: 378; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |