![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Множество всех булевых функций P2 является замкнутым классом (Почему?). Общее их число всех булевых функций n переменных равно его мощности . Из множества этих функций выделяют некоторые классы (подмножества).
1. Булева функция f сохраняет константу 0, если
f(0, 0, …, 0) = 0
Множество всех булевых функций, сохраняющих константу 0, образует класс .
Теорема. Число всех булевых функций, сохраняющих константу 0, равно .
Доказательство. Булева функция, принадлежащая классу K0, на наборе <0, 0, …, 0> принимает значение равное 0, но таких наборов 2n – 1, следовательно общее число таких функций .
2. Булева функция f сохраняет константу 1, если
f(1, 1, …, 1) = 1
Множество всех булевых функций, сохраняющих константу 1, образует класс .
Теорема. Число всех булевых функций, сохраняющих константу 1, равно .
Доказательство. Булева функция, принадлежащая классу K1, на наборе <1, 1, …, 1> принимает значение равное 1, но таких наборов 2n – 1, следовательно общее число таких функций .
3. Булева функция называется двойственной функцией к функции f и обозначается f*.
ZB. По определению , т.е. функция
является двойственной к функции
.
Рассмотреть, что происходит с таблицей истинности.
Замечание. Замена кортежей соответствует переворачиванию таблицы.
Булева функция называется самодвойственной, если она совпадает с двойственной себе функцией f = f*.
ZB. Класс самодвойственных булевых функций: 1. ; 2.
.
Множество всех самодвойственных булевых функций, образует класс .
Теорема. Число всех самодвойственных булевых функций равно .
Доказательство. Любую булева самодвойственную функция, принадлежащая классу S, можно определить на половине наборов, т.е. 2n-1, следовательно, общее число таких функций .
4. Булева функция f называется линейной функцией, если она может быть записана в следующем виде , где
.
Множество всех линейных булевых функций, образует класс .
Теорема. Число всех линейных булевых функций равно .
Доказательство. Имеется всего 2n+1 различных наборов значений коэффициентов ck. следовательно, общее число таких функций .
5. Набор значений переменных не меньше набора
, если
для всех j = 1, 2, …, n. В этом случае пишут
, в противном случае наборы называются несравнимыми.
Булева функция f называется монотонной функцией, если для любых двух наборов, таких, что имеет место неравенство
.
Множество всех монотонных булевых функций, образует класс .
Число всех монотонных булевых функций оценивается асимптотически:
, где А – некоторая константа.
Теорема (Пост-Яблонского).
Для того чтобы множество N булевых функций было полной системой, необходимо и достаточно найти для каждого из пяти замкнутых классов Поста K0, K1, S, M, L функцию из N, которая ему не принадлежит.
ZB. Рассмотрим множество из одной функции Шеффера . Это - полная система. Согласно теореме Поста эта единственная функция должна не принадлежать ни одному из классов Поста.
1. ;
вывод
2. вывод
3. вывод
4. вывод
5. вывод
Дата публикования: 2014-11-04; Прочитано: 3706 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!