Курсовая работа: Минимальные формы булевых многочленов
4. А Ù В `= Æ
Любая конечная булева алгебра может содержать лишь 2 в степени n элементов, где n – натуральное число.
Пример 2. 1)Множество делителей 70 -ти D =<1,2,5,7,10,14,35,70>. Множество A =<2,5,7> -множество атомов решетки D .
10 = 2 Ú 5
14 = 2 Ú 7
35 =5 Ú 7
70 = (2 Ú 5) Ú 7
70
 |
10 
14 35
2 5 7
1
2) Множество А = {2,5,7}
Отношение вложенности.
{2,5,7}
 |
{2,5} {2,7} {5,7}
{2} {5} {7}
 |  |
Æ
Эта решетка изоморфна предыдущей.
Алгебра множеств и алгебра высказываний являются моделями абстрактной булевой алгебры. Все абстрактные булевы алгебры (которые состоят из одинакового числа элементов) изоморфны.
1.3Минимальные формы булевых многочленов
Определение. Понятие булева многочлена определяется рекурсивно. Пусть Х n = { x 1 ,…, xn } – множество из n символов (называемых неизвестными или переменными), которое не содержит символов 0 и 1 . Булевы многочлены над Х n суть объекты, которые могут быть получены последовательным применением следующих правил:
(I) х1 , х2 , …, х n , 0,1 – булевы многочлены;
(II) если p и q – булевы многочлены, то таковыми являются и
( p ) Ù ( q ), ( p ) Ú ( q ), ( p ) ¢ .
Обозначим множество всех булевых многочленов над Х n через Р n .
Пример. Вот несколько примеров булевых многочленов над {х1 , х2 }: 0,1, х1 , х2, х1 Ù х2 , х1 Ú х2 , х1 ¢ ,х1 ¢ Ù х2 .
Так как любой булев многочлен над x 1 ,…, xn модно рассматривать как булев многочлен над x 1 ,…, xn , xn +1 , мы имеем
Р1 Ì Р2 Ì … Ì Р n Ì Р n +1 Ì …