Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Многочлен Жигалкина. Количество многочленов Жигалкина для n переменных. Единственность многочлена Жигалкина для каждой булевой функции



Многочлен Жигалкина является суммой константы 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= x f5=y f10= y 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= (x y) f4= (y x) f13= x y f11= y x f7=x y f8=x y

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; Прочитано: 534 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...