КАТЕГОРИИ: Архитектура-(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) |
A) элементтері болса 5 страница
Из особенностей логических переменных и аксиом вытекают некоторые закономерности, которые представляются как законы алгебры. Для булевой алгебры выявлены следующие соотношения, которые рассматриваются как законы. 1. Переместительный закон. 1.1. ; (2.1) 1.2. . (2.2) 2. Сочетательный закон. 2.1. ; (2.3) 2.2. . (2.4) 3. Распределительный закон. 3.1. ; (2.5) 3.2. . (2.6) Обе формы первого и второго закона и первая форма третьего закона (2.1, 2.2, 2.3, 2.4, 2.5) очевидны и особого доказательства не требуют. Остановимся лишь на (2.6). , что и требовалось доказать. В процессе доказательства использовались закон (2.5) и 4-ая и 7-ая аксиомы. 4. Закон поглощения. 4.1 . (2.7) Следствие: . (2.8) 4.2 . (2.9) Следствие: . (2.10) Доказательство (2.7): . Здесь содержится доказательство и для (2.9). 5. Закон склеивания. 5.1 ; (2.11) 5.2 . (2.12) Доказательство (2.11): . Доказательство (2.12): 6. Закон обобщённого склеивания. 6.1 ; (2.13) 6.2 . (2.14) Доказательство (2.13): Доказательство (2.14). Раскроем скобки сначала левой части равенства (2.14) а, затем, правой его части. ; . Результаты преобразований одинаковы, что подтверждает справедливость (2.14). 7. Закон без имени. 7.1 ; (2.15) 7.2 . (2.16)
Доказательство (2.15): . Доказательство (2.16). Развернём с помощью действия обратного склеиванию (см. 2.11). , тогда . 8. Закон де Моргана. 8.1. ; (2.17) 8.2. . (2.18) Доказательство (2.17) и (2.18) заключается в сравнивании табличных форм левых и правых частей этих равенств. Данный закон имеет обобщённую форму. 8.3. (2.19) Равенство (2.19) означает следующее. Отрицание функции равно самой функции с отрицанием переменных. Порядок выполнения операций сохраняется, а сами операции меняются с «И» на «ИЛИ» и с «ИЛИ» на «И».
Пример 2.1.1. . Чтобы сохранить при преобразовании порядок выполнения операций в правой части равенства использовались скобки. Функция называется двойственной по отношению к функции , если образуется из путем замены операций «И» на операцию «ИЛИ» и операций «ИЛИ» на операцию «И». Функцию будем называть оригиналом. Порядок выполнения операций в двойственной функции должен сохраняться таким, каким он был в оригинале.
Пример 2.2.1.
Для недопущения возможных ошибок при написании двойственной формы функций, рекомендуется в оригинале предварительно расставить скобки, дополнительно учитывающие ранги операций. Затем, в полученной двойственной форме, скобки, не изменяющие порядок выполнения операций, удаляются. Пример 2.2.2. . Расставляем дополнительные скобки, не меняющие формулу. . Делаем преобразование в двойственную форму. . Убираем ненужные скобки и получаем окончательный вид двойственной функции . Двойственные функции обладают следующими свойствами. 1. Если имеются две тождественно равные функции , то их двойственные формы также равны . 2. Если , то . Свойство подтверждается следующим образом. ; . 3. Если , то . Действительно, так как (согласно пятой аксиоме), то (согласно девятой аксиоме). 4. Если , то . Например, если , то . Эти свойства бывают очень полезны в тех случаях, когда преобразование логических выражений в двойственном виде делать удобнее, чем в оригинале. Примером двойственных функций можно считать все вторые формы законов булевой алгебры, если принять первые формы за оригиналы.
Форма логических функций представленных в базисе {И, ИЛИ, НЕ} называется нормальной. Пример 2.3.1. . Очень важным является более узкий класс функций со структурой, образованной элементарными составляющими двух типов: элементарных конъюнкций и элементарных дизъюнкций. Элементарной конъюнкцией k- того ранга или, иначе, минтермом k- того ранга называется логическое произведение k логических переменных, каждая из которых может быть представлена в прямом или инверсном виде.
Пример 2.3.2.
Замечание: конъюнкции не являются элементарными Элементарной дизъюнкцией называется логическая сумма любого числа логических переменных, каждая из которых может быть представлена в прямом или инверсном виде.
Пример 2.3.3.
Замечание: дизъюнкции не являются элементарными. Дизъюнкция любого числа элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).
Дата добавления: 2014-11-09; Просмотров: 397; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |