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

Множество булевых функций, заданный в базисе Жегалкина 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,X₂,...,X_n называется выражение вида C_oC₁X₁C₂X₂...C_nX_nC₁₂X₁X₂...C₁₂...nX_lX₂...X_n, где постоянные 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