Файл: 1. Булевы функции и способы их задания.pdf

3. Заполняем строку стоящую ниже: находим сумму по модулю 2 всех пар соседних элементов вышестоящей строки.
В каждой следующей строке элементов будет на 1 меньше чем впредыдущей, в последней строке будет 1 элемент
4. Крайние левые значения полученных строк будут коэффициентами многочлена Жегалкина (конъюнкция будет состоять из тех переменных, которые в наборе стоящим в данной строке в первом столбце принимают значение 1)
Пример 4. Найти многочлен Жегалкина для функции ̃ ( ) из
примера 1 используяметод треугольника.
1. Заполним первый столбец таблицы истинности и расположим вектор значений функции в первой строке
1 1 0 0 1 0 1 1 2. Заполним вторую строку: берем два соседних элемента это 1 и 1, находим их сумму по модулю 2, так как , то получившийся 0 записываем во вторую строку, между элементами которые складывали
1 1 0 0 1 0 1 1 0 берем следующие два соседних элемента первой строки это 1 и 0, находим их сумму по модулю 2, так как , то получившийся 1 записываем во вторую строку, между элементами которые складывали
1 1 0 0 1 0 1 1 0 1

3. Аналогично поступаем с каждой парой соседних элементов первой строки, записываем получившиеся суммы во вторую строку
1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 4. Потому же принципу заполняем оставшиеся строки
1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1
5. Первый (наклонный столбик) получившегося треугольника – это коэффициенты многочлена Жегалкина. Подчеркиваем 1 стоящие в наклонном столбике и наборы переменных в соответствующей строке.
1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1
Для подчеркнутых наборов построим конъюнкции по правилу: в конъюнкцию входят переменные равные 1 на рассматриваемом наборе.
Выпишем конъюнкции для нашего примера.

1 1 0 0 1 0 1 1 1- свободный член
0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1
Составляем многочлен Жегалкина. Коэффициент, находящийся в строке надо поставить перед конъюнкцией, выписанной в этой строке и соединить между собой получившиеся произведения знаком . Если некоторый коэффициент равен нулю, то такая конъюнкция не будет входить в многочлен Жегалкина (
), поэтому на 0 в наклоном столбике можно не обращать внимания. Если коэффициент равен 1, то соответствующую конъюнкцию мы записываем в многочлен
Жегалкина, однако сам коэффициент перед конъюнкцией не пишут
(
). Многочлен Жегалкина в нашем примере:
Пример 5. (задание типового расчета)
Для функции заданной формулой
(( ) ( ̅ )) (( ̅| ) ( ̅ ̅))
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ найдите таблицу истинности, вектор значений, носитель функции и его дополнение, СДНФ, СКНФ и многочлен Жегалкина.
1. Построим таблицу истинности. Разобьем функцию на элементарные, согласно правилам порядка выполнения действий в формулах.
– значение функции записано в первом столбике таблицы истинности
̅ – второй столбик
– третий столбик
– четвертый столбик
| – пятый столбик
̅ – шестой столбик
̅ – седьмой столбик

– восьмой столбик
– девятый столбик
̅ – десятый столбик
– одиннадцатый столбик x y z
1 2
3 4
5 6
7 8
9 10 11 0
0 0
0 1
0 0
1 1
1 1
0 1
1 0
0 1
0 1
1 0
0 1
0 1
0 1
1 0
1 0
1 1
0 0
1 0
1 1
0 1
1 0
1 1
1 1
1 1
0 0
0 0
1 0
0 1
0 0
1 0
1 1
1 1
1 1
0 1
1 1
0 1
1 0
0 0
1 1
0 1
0 1
1 1
1 0
0 0
1 0
1 0
1 1
0 1
1 1
1 1
0 0
0 0
1 0
0 0
0 1
1 2. Вектор значений ̃ ( ) (последний столбик таблицы истинности).
3.Носитель функции
{( ) ( ) ( ) ( ) ( ) ( ) ( )}
̅̅̅ = {(011)} - дополнение носителя.
4.
̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ , .
5.
̅ ̅
,
6. Найдем многочлен Жегалкина
1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1 1 0