Курсовая работа: Минимальные формы булевых многочленов

3. a + (b * c) = (a + b) * (a + c)

4. a* (b + c) = (a * b) + (a * c)

5. a + 0 = a , a * 1 = a . (Тождественность)

6. a + a ` = 1, a * a ` = 0. (Дополнительность)

Эта система аксиом является полной и независимой.

Пример 1: Пусть множество В – это множество В= {1,0} на котором заданы две бинарные операции:

+	1	0	*	1	0
1	1	1	1	1	0
0	1	0	0	0	0

И унарная операция: 0` = 1, 1 ` = 0.

Пример 2: Множество делителей числа 70: <1,2,5 , 7,10,14,35,70>

1. a + b = НОД (a, b)

2. a * b = НОК (a, b)

3. a` = 70/a

Определение: Пусть С - непустое подмножество множества В. Говорят, что С - подалгебра алгебры В , если она сама является алгеброй с теми же операциями.

Подмножество С - есть подалгебра алгебры В Û С замкнуто относительно трех операций.

Пример 3: Если С=<1,2,35,70> замкнуто относительно операций «+ », «* », «` », тогда С является подалгеброй алгебры В .

Определение: Две булевы алгебры В и В` изоморфны : В ~ В` , если существует взаимно-однозначная функция f : B ® B ` , такая, что:

1. f (a + b) = f (a) + f (b)

2. f (a * b) = f (a) * f (b)

3. f (a`) = (f (a))`

Для булевой алгебры справедливы принципы дуальности.

Основные теоремы абстрактной булевой алгебры.

1. Идемпотентный закон: a + a = a, a * a = a.

2. Граничный закон: a + 1 = 1, a + 0 = a .

3. Абсорбционный закон: a + (a * b) = a, a * (a + b) = a.

4. Ассоциативный закон: a + (b + c) = (a + b) + c, a * (b * c) = (a * b) * c.

5. Единственность дополнения: если $ x : a + x = 1 , a * x = 0, то x = a `.

6. Инволютивный закон: ((a`))` = a Þ 0` = 1 , 1` = 0.

7. Закон де Моргана: (a + b)`=a` * b`, (a * b)` = a` + b`.

Булева алгебра как решетка.

Поскольку для булевой алгебры справедливы ассоциативный, коммутативный и абсорбционный законы, то согласно определению булева алгебра есть решетка. В этой решетке