Упорядоченные множества и универсальная алгебра (вводный курс). Гуров С.И. - 65 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

Пусть дано уравнение
a(˜x) · X(˜x) = F ,
где a(˜x) и X(˜x) — формулы, реализующие соответственно известную и искомую булевы
функции (для простоты указывают именно формулы, а не порождённые ими классы). То-
гда решением данного уравнения будут любая функция, реализуемая формулами из глав-
ного идеала, порождённого формулой a(˜x) в соответствующей алгебре Линденбаума-
Тарского.
Например, пусть a(˜x) = x
1
x
2
, т.е. дано уравнение
x
1
x
2
X(x
1
, x
2
) = F . (∗)
Имеем x
1
x
2
= x
1
∨ x
2
, и главный идеал в алгебре Линденбаума-Тарского L
∗
2
, порождён-
ный классом формул [ x
1
∨ x
2
] составляют классы [ x
1
∨ x
2
], [ x
1
], [ x
2
], [ x
1
x
2
∨ x
1
x
2
],
[ x
1
x
2
], [ x
1
x
2
], [ x
1
x
2
] и F. На рис. 20 показана диаграмма Хассе данного идеала. Для
каждого класса указан вектор значений соответствующей функции при стандартном рас-
положении наборов переменных.
[ x
1
∨ x
2
]
(0, 1, 1, 1)
[ x
1
]
(0, 0, 1, 1)
[ x
1
x
2
∨ x
1
x
2
]
(0, 1, 0, 1)
[ x
2
]
(0, 1, 1, 0)
[ x
1
x
2
]
(0, 0, 0, 1)
[ x
1
x
2
]
(0, 0, 1, 0)
[ x
1
x
2
]
(0, 1, 0, 0)
F
(0, 0, 0, 0)
Рис. 20: Главный идеал в L
∗
2
, порожденный классом конъюнкции
Решением уравнения (∗) будет любая булева функция, реализующаяся формулами
из приведённых классов.
В бесконечных булевых алгебрах, как следует из теоремы 2.24, существуют и неглав-
ные (нетривиальные) ультрафильтры. Их также называют свободными, поскольку они не
фиксированы ни в какой точке исходного множества. Пересечение всех элементов такого
фильтра есть нулевой элемент.
При доказательстве указанной теоремы используется лемма Куратовского-Цорна, эк-
вивалентная, как мы знаем, аксиоме выбора. Заметим, что данная теорема является тео-
ремой чистого существования, и, поэтому, в каждом конкретном случае ультрафильтр
оказывается заданным неявно, как результат некоторого бесконечного итерационного
процесса. Без помощи аксиомы выбора никаких неглавных ультрафильтров построить
не удалось.
65
   Пусть дано уравнение
                                      a(x̃) · X(x̃) = F ,
где a(x̃) и X(x̃) — формулы, реализующие соответственно известную и искомую булевы
функции (для простоты указывают именно формулы, а не порождённые ими классы). То-
гда решением данного уравнения будут любая функция, реализуемая формулами из глав-
ного идеала, порождённого формулой a(x̃) в соответствующей алгебре Линденбаума-
Тарского.
   Например, пусть a(x̃) = x1 x2 , т.е. дано уравнение

                                     x1 x2 X(x1 , x2 ) = F .                                (∗)

Имеем x1 x2 = x1 ∨ x2 , и главный идеал в алгебре Линденбаума-Тарского L∗2 , порождён-
ный классом формул [ x1 ∨ x2 ] составляют классы [ x1 ∨ x2 ], [ x1 ], [ x2 ], [ x1 x2 ∨ x1 x2 ],
[ x1 x2 ], [ x1 x2 ], [ x1 x2 ] и F. На рис. 20 показана диаграмма Хассе данного идеала. Для
каждого класса указан вектор значений соответствующей функции при стандартном рас-
положении наборов переменных.


                                            [ x1 ∨ x2 ]
                                           (0, 1, 1, 1)
                                    A  A
                              AAAAA
                   [ x1 ]                 [ x1 x2 ∨ x1 x2 ]                [ x2 ]
               (0, 0, 1, 1)                 (0, 1, 0, 1)               (0, 1, 1, 0)
                                   A AA                          AAA
                                 A                             A
                              AAA                         AAA
                 [ x1 x2 ]                   [ x1 x2 ]                   [ x1 x2 ]
               (0, 0, 0, 1)                (0, 0, 1, 0)                (0, 1, 0, 0)
                                                                AAA
                                                              A
                                                          AAA
                                                F
                                           (0, 0, 0, 0)


            Рис. 20: Главный идеал в L∗2 , порожденный классом конъюнкции

   Решением уравнения (∗) будет любая булева функция, реализующаяся формулами
из приведённых классов.
   В бесконечных булевых алгебрах, как следует из теоремы 2.24, существуют и неглав-
ные (нетривиальные) ультрафильтры. Их также называют свободными, поскольку они не
фиксированы ни в какой точке исходного множества. Пересечение всех элементов такого
фильтра есть нулевой элемент.
   При доказательстве указанной теоремы используется лемма Куратовского-Цорна, эк-
вивалентная, как мы знаем, аксиоме выбора. Заметим, что данная теорема является тео-
ремой чистого существования, и, поэтому, в каждом конкретном случае ультрафильтр
оказывается заданным неявно, как результат некоторого бесконечного итерационного
процесса. Без помощи аксиомы выбора никаких неглавных ультрафильтров построить
не удалось.

                                                 65

Страницы