ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.02.2024
Просмотров: 6
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Построение полинома Жегалкина методом треугольника:
| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| 1 | Z | Y | YZ | X | XZ | XY | XYZ |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 1 | 0 | 0 | | |
| 1 | 0 | 1 | 1 | 0 | | | |
| 1 | 1 | 0 | 1 | | | | |
| 0 | 1 | 1 | | | | | |
| 1 | 0 | | | | | | |
| 1 | | | | | | | |
1. Строится треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
2. Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
3. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
4. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы.
5. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Построение полинома Жегалкина методом неопределённых коэффициентов:
Запишем данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами:
f(X,Y,Z) = a000 ⊕ a001Z ⊕ a010Y ⊕ a100X ⊕ a011YZ ⊕ a101XZ ⊕ a110XY ⊕ a111XYZ
f(0,0,0) = a000 = 0 ⇒ a000 = 0
f(0,0,1) = a000 ⊕ a001 = 0 ⊕ a001 = 0 ⇒ a001 = 0
f(0,1,0) = a000 ⊕ a010 = 0 ⊕ a010 = 1 ⇒ a010 = 1
f(1,0,0) = a000 ⊕ a100 = 0 ⊕ a100 = 1 ⇒ a100 = 1
f(0,1,1) = a000 ⊕ a001 ⊕ a010 ⊕ a011 = 0 ⊕ 0 ⊕ 1 ⊕ a011 = 1 ⇒ a011 = 0
f(1,0,1) = a000 ⊕ a001 ⊕ a100 ⊕ a101 = 0 ⊕ 0 ⊕ 1 ⊕ a101 = 0 ⇒ a101 = 1
f(1,1,0) = a000 ⊕ a010 ⊕ a100 ⊕ a110 = 0 ⊕ 1 ⊕ 1 ⊕ a110 = 1 ⇒ a110 = 1
f(1,1,1) = a000 ⊕ a001 ⊕ a010 ⊕ a100 ⊕ a011 ⊕ a101 ⊕ a110 ⊕ a111 = 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ a111 = 1 ⇒ a111 = 1
Окончательно получаем: Y ⊕ X ⊕ XZ ⊕ XY ⊕ XYZ
Введённая функция: X→Z∨Y
Вектор функция: 11110111
Таблица истинности:
| X | Y | Z | X→Z | X→Z∨Y |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Совершенная дизъюнктивная нормальная форма (СДНФ)
¬X¬Y¬Z ∨ ¬X¬YZ ∨ ¬XY¬Z ∨ ¬XYZ ∨ X¬YZ ∨ XY¬Z ∨ XYZ
Совершенная конъюнктивная нормальная форма (СKНФ)
¬X∨Y∨Z
Полином Жегалкина
1⊕X⊕XZ⊕XY⊕XYZ
Решение
Построение совершенной дизъюнктивной нормальной формы:
Найдём наборы, на которых функция принимает истинное значение: { 0, 0, 0 } { 0, 0, 1 } { 0, 1, 0 } { 0, 1, 1 } { 1, 0, 1 } { 1, 1, 0 } { 1, 1, 1 }
В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:
K1: { 0, 0, 0 } — ¬X¬Y¬Z
K2: { 0, 0, 1 } — ¬X¬YZ
K3: { 0, 1, 0 } — ¬XY¬Z
K4: { 0, 1, 1 } — ¬XYZ
K5: { 1, 0, 1 } — X¬YZ
K6: { 1, 1, 0 } — XY¬Z
K7: { 1, 1, 1 } — XYZ
Объединим конъюнкции с помощью операции ИЛИ и получим совершенную дизъюнктивную нормальную форму:
K1 ∨ K2 ∨ K3 ∨ K4 ∨ K5 ∨ K6 ∨ K7 = ¬X¬Y¬Z ∨ ¬X¬YZ ∨ ¬XY¬Z ∨ ¬XYZ ∨ X¬YZ ∨ XY¬Z ∨ XYZ
Построение совершенной конъюнктивной нормальной формы:
Найдём наборы, на которых функция принимает ложное значение: { 1, 0, 0 }
В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:
D1: { 1, 0, 0 } — ¬X∨Y∨Z
Объединим дизъюнкции с помощью операции И и получим совершенную конъюнктивную нормальную форму:
D1 = (¬X∨Y∨Z)
Построение полинома Жегалкина методом Паскаля:
| X | Y | Z | (X→Z)∨Y | | | | | | | |
| 0 | 0 | 0 | 1 | → | 1 | → | 1 | → | 1 | 1 |
| 0 | 0 | 1 | 1 | ⊕ 1 | 0 | → | 0 | → | 0 | |
| 0 | 1 | 0 | 1 | → | 1 | ⊕ 1 | 0 | → | 0 | |
| 0 | 1 | 1 | 1 | ⊕ 1 | 0 | ⊕ 0 | 0 | → | 0 | |
| 1 | 0 | 0 | 0 | → | 0 | → | 0 | ⊕ 1 | 1 | X |
| 1 | 0 | 1 | 1 | ⊕ 0 | 1 | → | 1 | ⊕ 0 | 1 | XZ |
| 1 | 1 | 0 | 1 | → | 1 | ⊕ 0 | 1 | ⊕ 0 | 1 | XY |
| 1 | 1 | 1 | 1 | ⊕ 1 | 0 | ⊕ 1 | 1 | ⊕ 0 | 1 | XYZ |
Построение полинома Жегалкина методом треугольника:
| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| 1 | Z | Y | YZ | X | XZ | XY | XYZ |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | 0 | 0 | | |
| 1 | 1 | 0 | 1 | 0 | | | |
| 0 | 1 | 1 | 1 | | | | |
| 1 | 0 | 0 | | | | | |
| 1 | 0 | | | | | | |
| 1 | | | | | | | |
1. Строится треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
2. Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
3. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
4. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы.
5. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Построение полинома Жегалкина методом неопределённых коэффициентов:
Запишем данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами:
f(X,Y,Z) = a000 ⊕ a001Z ⊕ a010Y ⊕ a100X ⊕ a011YZ ⊕ a101XZ ⊕ a110XY ⊕ a111XYZ
f(0,0,0) = a000 = 1 ⇒ a000 = 1
f(0,0,1) = a000 ⊕ a001 = 1 ⊕ a001 = 1 ⇒ a001 = 0
f(0,1,0) = a000 ⊕ a010 = 1 ⊕ a010 = 1 ⇒ a010 = 0
f(1,0,0) = a000 ⊕ a100 = 1 ⊕ a100 = 0 ⇒ a100 = 1
f(0,1,1) = a000 ⊕ a001 ⊕ a010 ⊕ a011 = 1 ⊕ 0 ⊕ 0 ⊕ a011 = 1 ⇒ a011 = 0
f(1,0,1) = a000 ⊕ a001 ⊕ a100 ⊕ a101 = 1 ⊕ 0 ⊕ 1 ⊕ a101 = 1 ⇒ a101 = 1
f(1,1,0) = a000 ⊕ a010 ⊕ a100 ⊕ a110 = 1 ⊕ 0 ⊕ 1 ⊕ a110 = 1 ⇒ a110 = 1
f(1,1,1) = a000 ⊕ a001 ⊕ a010 ⊕ a100 ⊕ a011 ⊕ a101 ⊕ a110 ⊕ a111 = 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ a111 = 1 ⇒ a111 = 1
Окончательно получаем: 1 ⊕ X ⊕ XZ ⊕ XY ⊕ XYZ
