Алгебра Буля

Алгеброй Буля называется множество элементов произвольной природы , в котором определены две бинарные операции, назовем их, условно, сложение и умножение и обозначим и , и одна унарная операция, обозначим ее .

Введенные операции должны удовлетворять следующим аксиомам:

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

;

2) ассоциативность:

;

3) взаимная дистрибутивность:

,

;

4) идемпотентность:

;

5) инволюция:

;

6) правила де Моргана:

,

.

Кроме введенных операций в алгебре Буля должны существовать два особых элемента, назовем их условно и , подчиняющиеся требованиям:

,

,

.

Алгебру Буля составляет множество , где 0 и 1 являются логическими переменными (булевыми переменными), с введенными бинарными операциями дизъюнкция и конъюнкция и унарной операцией черта, выделенными элементами являются 0 и 1: .

Алгебру Буля составляет множество подмножеств произвольного множества с введенными операциями объединение, пересечение и дополнение: и .Выделенными элементами являются пустое множество и само множество :

,

= ,

.

Название «булева алгебра» связано с именем английского математика Джорджа Буля, хотя полное формальное представление булевой алгебры было дано лишь в 1904 году Хантингтоном.

Задачи

1. Построив таблицу истинности, проверить равенства:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) ;

11) .

2. Построить таблицы истинности соответствующих функций, выяснить эквивалентны ли формулы и :

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) .

3. Проверить эквивалентность формул и с помощью эквивалентных преобразований:

1) , ;

2) , ;

3) , ;

4) ,

;

5) , ;

6) , ;

7) , ;

8) , ;

9) ,

;

10) , ;

4. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выяснить, является ли функция g двойственной к функции f:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , ;

11) , ;

12) , .

5. Используя принцип двойственности, построить формулу, реализующую функцию, двойственную к функции f, и проверить, будет ли полученная формула эквивалентна формуле V:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) , ;

9) , ;

10) , .

6. Указать все фиктивные переменные у функции f:

1)

2)

3)

4)

5)

6)

7. Показать, что x ₁ – фиктивная переменная у функции f (реализовав для этой цели функцию f формулой, не содержащей явно переменную x ₁):

1) ;

2) ;

3) ;

4) 5) 6) 7)

8) 9) 10)

8. Представить в СДНФ следующие функции:

1)

2)

3) ;

4)

5)

6)

7)

8)

9)

10) .

9. Представить в СКНФ следующие функции:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

10. С помощью эквивалентных преобразований построить ДНФ функции :

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11. Используя эквивалентные преобразования, построить КНФ функции :

1)

2) ;

3)

4)

5)

6)

7)

12. Применяя преобразования вида и построить из заданной ДНФ функции ее совершенную ДНФ:

1)

2)

3)

4)

5)

6)

7)

8)

13. С помощью преобразований вида и построить из данной КНФ функции ее совершенную КНФ:

1)

2)

3)

4)

5)

6)

7)

8)

14. Используя дистрибутивный закон и эквивалентности , и перейти от заданной КНФ функции к ДНФ:

1)

2)

3)

4)

5)

6)

7)

15. Используя дистрибутивный закон и эквивалентности и перейти от заданной ДНФ функции к ее КНФ:

1)

2)

3)

4)

5)

6)

7)

8)

16. Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций:

1)	6)
2)	7)
3)	8) .
4)	9)
5)	10) .

17. Методом треугольника Паскаля построить полином Жегалкина для следующих функций:

1) 2)

3) 4)

5) 6)

7) 8)

9) 10)

18. Представив функцию формулой над множеством связок {&, }, преобразовать полученную формулу в полином Жегалкина функции (используя эквивалентности ):

1)

2)

3)

4)

5)

6)

7)

8)

9)

10) .

19. Выяснить, является ли функция самодвойственной:

1)

2)

3)

4)

5)

6)

7)

8) ;

9) ;

10) ;

11) ;

12) ;

13) ;

14)

15) .

20. Выяснить, является ли самодвойственной функция , заданная векторно:

1)

2)

3)

4)

5)

6)

7)

8) ;

9)

10)

11)

12)

13)

14)

15) .

21. Представив функцию f полиномом, выяснить, является ли она линейной:

1)

2)

3)

4)

5) ;

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

22. Выяснить, является ли линейной функция , заданная

векторно:

1)

2)

3)

4)

5)

6)

7)

8) ;

9)

10)

11)

12)

13)

14)

15) .

23. Выяснить, принадлежит ли функция f множеству :

1) ;

2)

3)

4)

5) ;

6)

7)

8)

9)

10)

24. Подсчитать число функций, зависящих от переменных и принадлежащих множеству :

1) ; 3) ; 5) ;

2) ; 4) ; 6) ;

7) ; 27) ;

8) ; 28) ;

9) ; 29) ;

10) ; 30) ;

11) ; 31) ;

12) ; 32) ;

13) ; 33) ;

14) ; 34) ;

15) ; 35) ;

16) ; 36) ;

17) ; 37) ;

18) ; 38) ;

19) ; 39) ;

20) ; 40) ;

21) ; 41) ;

22) ; 42) ;

23) ; 43) ;

24) ; 44) ;

25) ; 45) .

26) ;

25. Доказать, что:

1) ;

2) .

26. По вектору значений выяснить, является ли функция f монотонной:

1)

2)

3)

4)

5)

6)

7)

8)

27. Проверить, является ли функция f монотонной:

1)

2)

3)

4)

5)

6)

7)

8)

28. Выяснить, полна ли система функций:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

29. Выяснить, полна ли система А функций, заданных векторами своих значений:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

30. Выяснить, полна ли система А:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

31. Проверить, является ли система функций А базисом в Р ₂:

1)

2)

3)

4)

5)

6)

7)

8)

32. Из полной в Р ₂ системы А выделить всевозможные базисы:

1)

2)

3)

4)

5)

6)

7)

8)

33. Выяснить, можно ли расширить до базиса в множество :

1) ; 5) ;

2) ; 6) ;

3) ; 7) ;

4) ; 8) .

34. Выяснить, полна ли система функций :

1) ;

2) ;

3) ;

4) .