Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Алгебра Жегалкина




Множество булевых функций, заданный в базисе Жегалкина S4={,&,1} называется алгеброй Жегалкина. Основные свойства.

1. коммутативность

Н1Н2=Н2Н1, Н1&Н2=Н2&Н1;

2. ассоциативность

Н1 (Н2НЗ)=(Н1Н2)НЗ, Н1&(Н2&НЗ)=(Н1&Н2)&НЗ;

3. дистрибутивность

H1&(H2H3)=(H1&H2)(H1&H3);

4. свойства констант

Н&1=Н, Н&0=0, Н0=Н;

5. НН=0, Н&Н=Н.

Утверждение 1.4.1. Через операции алгебры Жегалкина можно выразить все другие булевы функции:

┐x=lx, xVy=xyxy, х~у=1ху,

ху=1хху, xy=lxyxy, х|у=1ху.

Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных Xi,X2,...,Xn называется выражение вида CoC1X1C2X2...CnXnC12X1X2...C12...nXlX2...Xn, где постоянные Cк могут принимать значения 0 ли 1. Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным (линей ная функция).

Например, f=xyzxyz и fl = l ху z-полиномы, причем второй является линейной функцией.

Теорема1.4.1. Каждая булева функция представляется в виде полинома Жегалкина единственным образом.

Задания для самостоятельной работы по теме 1.

1) Определите, какие из следующих предложений являются высказываниями, определите, истинные они или ложные:

1. Берлин - столица Турции.

2. Каждое целое число является числом действительным.

3. Принтер предназначен для вывода информации на бумагу.

4. Математическая логика - интересный предмет.

5. В котором часу открывается библиотека?

6. 5+х=3(х+1)2

7. Да здравствует мир!

8. Луна - искусственный спутник Марса.

9. Во всяком четырехугольнике противоположные стороны равны.

10. Сегодня хорошая погода.

11. Если х2-5х+6=0, то х=2, х=3.

12. Париж расположен на Сене и 2+3=5.

13. Число 2 четное и простое.

14. Здравствуйте, Василий Петрович.

15. Верно ли, что Пушкин родился в год Козы?

2) Записать символически следующие записи:

1. Идет дождь или кто-то не выключил воду.

2. В огороде бузина, а в Киеве дядька.

3. Если в огороде нет бузины, то в Киеве нет дядьки.

4. Я сегодня сдам лабораторную работу по "Компьютерной графике" или по"Программированию", а потом поеду на дачу.

5. Четырехугольник является квадратом тогда и только тогда, когда все его стороны и все углы равны.

6. 100 не делится ни на 3, ни на 7.

7. Петр встанет и уйдет, или Иван уйдет.

8. Петр встанет, и он или Иван уйдет.

9. Петр пойдет на дискотеку, а Иван не пойдет, или Петр не пойдет на дискотеку, а Иван приятно проведет время.

10. В степи не будет пыльных бурь тогда и только тогда, когда будут лесозащитные полосы, а если лесозащитных полос не будет, то пыльные бури уничтожат посевы и нанесут урон хозяйству.

11. Для того, чтобы натуральное число было нечетным, достаточно, чтобы оно было простым и больше двух.

12. Если "Спартак" или "Динамо" проиграют, и " Салют" выиграет, то "Арарат" потеряет первое место и, кроме того, "Заря" покинет высшую лигу.

13. Если параллелограмм не ромб, то его диагонали не перпендикулярны и не делят углы пополам.

14. Если Париж расположен на Темзе, то белые медведи обитают в Африке.

15. Я сделаю зарядку, и если будет хорошая погода, поеду за город.

 




Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 1445; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.