![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Многочлен Жигалкина является суммой константы 0 или 1 и различных одночленов (элементарных конъюнкций переменных без инверсий), в которые все переменные входят не более одного раза (могут не входить). Причём все одночлены в многочлене Жигалкина различны.
Подсчитаем число различных многочленов Жигалкина. Количество различных одночленов из n переменных равно числу всех подмножеств множества мощности n (мощности множества – степени), т.е. равно два в степени n. Пустое подмножество здесь – это константа 1. Например, при n = 2 имеет четыре одночлена: x y, x, y и 1.
Число полиномов (многочленов) Жигалкина равно числу булевых функций (от n переменных), т.е. между полиномами и функциями можно установить взаимно однозначное соответствие, что доказывает единственность полинома Жигалкина для каждой булевой функции. Все полиномы Жигалкина от двух переменных x и y и функции f0, …, f15, которым они соответствуют:
x | x+1 | y | y+1 | x+y | x+y+1 | ||
f0=0 | f15=1 | f3=x | f12= ![]() | f5=y | f10= ![]() | f6=x+y | f9=x~y |
xy | xy+1 | xy+x | xy+y | xy+x+1 | xy+y+1 | xy+x+y | xy+x+y+1 |
f1=x&y | f14=x ![]() | f2= ![]() ![]() | f4= ![]() ![]() | f13= x ![]() | f11= y ![]() | f7=x ![]() | f8=x ![]() |
27. Правила перехода к равносильным формулам в логике предикатов: перестановка одноименных кванторов и переименование связанных переменных.
3. Перестановка одноименных кванторов:
( x) (
y) A(x, y)
(
y) (
x) A(x, y);
( x) (
y) A(x, y)
(
y) (
x) A(x, y).
4. Переименование связанных переменных. Заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора, получаем формулу, равносильную A. Это правило применяется при составлении формул ЛП из формул A и B, если есть переменные, свободные в одной из них и связанные в другой. Такую связанную переменную заменяем другой переменной, не входящей в эти формулы. Это утверждение доказывается индукцией по длине формулы.
Дата публикования: 2014-11-29; Прочитано: 533 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!