![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Мы уже заметили, что конъюнкция совпадает с обычным арифметическим умножением, попробуем ввести сложение: 0+0=0; 0+1-1; 1+0=1; 1+1=? Если принять 1+1=1, то получим дизъюнкцию. Если принять 1+1=0, то получим исключающее или. Принимаем второе соотношение: х+у=хÅу. Такое сложение совпадает с известным в теории чисел сложением по модулю 2. Заметим, что всегда хÅх=0.
Всякая композиция сложений, умножений и констант называется арифметическим многочленом.
Многочленом Жегалкина называют многочлен вида , где суммирование ведется по некоторому множеству различных наборов (i1, i2,…,ik), в котором ни один индекс не повторяется.
Теорема. Всякая булева функция может быть представлена в виде многочлена Жегалкина и притом единственным образом.
Выразим три основные логические операции через сложение и умножение, превратив их в многочлены Жегалкина.
Конъюнкция хÙу=ху уже готовый многочлен Жегалкина. Отрицание =хÅ1. Дизъюнкция
=(xÅ1)(yÅ1)+1= xy Å x Å y Å1Å1= xy Å x Å y.
Дата публикования: 2015-10-09; Прочитано: 352 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!