КАТЕГОРИИ: Архитектура-(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) |
Аксиомы, основные теоремы и тождества алгебры логики
В алгебре логики рассматриваются переменные, которые могут принимать только два значения: 0 и 1. В дальнейшем переменные будем обозначать латинскими буквами х, у, z,.... В алгебре логики определено отношение эквивалентности (=) и три операции: дизъюнкция (операция ИЛИ), обозначаемая знаком V (+); конъюнкция (операция И), обозначаемая точкой, которую можно опускать (например, х·у=ху); отрицание (инверсия, операция НЕ), обозначаемое чертой над переменными или элементами 0 и 1 (например, , ). Отношение эквивалентности удовлетворяет следующим свойствам: х = х—рефлексивность; если х=у, то у=х - симметричность; если х = у и у = z, то x = z — транзитивность. Из отношения эквивалентности следует принцип подстановки: если х=у, то в любой формуле, содержащей х, вместо х можно подставить у, и будет получена эквивалентная формула. Алгебра логики определяется следующей системой аксиом:
Аксиома (1.30) утверждает, что в алгебре логики рассматриваются только двоичные переменные, аксиомы (1.31) — (1.33) определяют операции дизъюнкции и конъюнкции, а аксиома (1.34)—операцию отрицания. Если в аксиомах (1.31) —(1.34), заданных парами, произвести взаимную замену операций дизъюнкции и конъюнкции, и также элементов 0 и 1, то из одной аксиомы пары получится другая. Это свойство называется принципом двойственности. С помощью аксиом алгебры логики можно доказать целый ряд теорем и тождеств. Одним из эффективных методов доказательства теорем является метод перебора всех значений переменных. Если теорема истинна, то с учетом (1.31)—(1.34) при подстановке любых значений переменных в обе части выражения, формулирующего утверждение теоремы, должно получиться тождество. Метод перебора не слишком трудоемок, так как переменные могут иметь только два значения: 0 и 1. Так, методом перебора легко убедиться в справедливости следующих теорем: идемпотентные законы
коммутативные законы
ассоциативные законы
дистрибутивные законы
законы отрицания
законы двойственности (теоремы де Моргана)
закон двойного отрицания
законы поглощения
операции склеивания
операции обобщенного склеивания
Теоремы (1.35) —(1.42) и (1.44) —(1.47) записаны парами, причем каждая из теорем пары является двойственной другой, так как из одной теоремы пары можно получить другую на основании принципа двойственности, т. е. путем взаимной замены операций дизъюнкции и конъюнкции, а также элементов 0 и 1, если они имеются. Теорема (1.43) самодвойственна, так как она не изменяется по принципу двойственности (отсутствуют элементы 0 и 1 и операции дизъюнкции и конъюнкции). Если в логическое выражение входят операции дизъюнкции и конъюнкции, то следует соблюдать порядок выполнения операций: сначала выполняется операция конъюнкции, а затем операция дизъюнкции. В сложных логических выражениях для задания порядка выполнения операций используются скобки. Некоторые теоремы и тождества алгебры логики имеют особое значение, так как позволяют упрощать логические выражения. Например, в соотношениях (1.35), (1.39)—(1.41), (1.44) —(1.47) правая часть проще левой. Поэтому, произведя в логических выражениях соответствующие преобразования, можно добиться существенного их упрощения. Особенно часто для преобразования логических выражений, с целью их упрощения, используются тождества (1.44) — (1.47). Операция сумма по модулю два (исключающее ИЛИ, логическая неравнозначность) обозначается символом Å и определяется соотношением
Используя аксиомы алгебры логики, легко убедиться, что:
Из соотношений следует, что значение х Å у совпадает со значением младшего разряда суммы двух двоичных чисел, где х и у — значения младших разрядов этих чисел. Соответственно этому значение i -ro разряда суммы двух двоичных чисел будет определяться значением xi Å yi Å zi; где xi и yi — значения i -x разрядов двоичных чисел, a z i —перенос в i -й разряд из предыдущего (i— 1)-го разряда. Операция сумма по модулю два коммутативна, ассоциативна и дистрибутивна относительно операции конъюнкции, т. е.
Для операции сумма по модулю двасправедливы также следующие тождества:
Дата добавления: 2014-11-18; Просмотров: 2933; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |