Тексты лекций / Текст лекции 4
.pdf
Тема 4 «Представление булевых функций формулами специального вида» Олейник Т.А., 2020
и, наконец, = ,соответствующаявектору(1,1). Итак,каноническийполиномЖегалкина от двух переменных имеет вид .
Рассуждая аналогично, выпишем в общем виде канонический полином Жегалкина от трех переменных:
.
Имея перед глазами общие виды канонических полиномов, не составит труда перепи-
сать в каноническом виде любой конкретный полином. Например, |
|
1 = 1 0 1 1 ; |
|
= |
|
= 0 0 0 1 1 1 0 |
1 . |
Чтобы задать функцию полиномом Жегалкина, применяют метод равносильных пре-
образований и метод неопределенных коэффициентов. С первым из них мы уже позна-
комились, доказывая возможность представления произвольной булевой функции полиномом Жегалкина.
Рассмотрим метод неопределенных коэффициентов. Пусть функция зависит от
переменных. Запишем в общем виде канонический полином Жегалкина от переменных и для каждого набора ( , ,..., ) значений переменных составим уравнение
( , ,..., ) = ( , ,..., ).
В результате получим систему из 2 уравнений, которая однозначно определяет коэффициенты полинома.
Пример 9. Используя метод неопределенных коэффициентов, построить полином Жегалкина функции:
а) ( , ) = | ; б) ( , , ) = (10110111).
◄ а) Выпишем таблицу истинности функции (табл. 2.26). |
|
|
|
|
|||||||||||
Канонический полином Жегалкина от двух переменных имеет вид: |
|
|
|
||||||||||||
|
|
|
|
( , |
) = |
|
|
. |
|
|
|
|
|||
Таблица 2.26 |
|
Поэтому должны выполняться равенства: |
|
|
|
|
|||||||||
|
(0,0) = 1 |
= (0,0) = |
0 |
0 |
0 0;(0,1) = 1 = |
||||||||||
|
|
|
|
||||||||||||
|
|
|
(0,1) = |
1 |
0 |
0 1;(1,0) = 1 |
= (1,0) = |
|
|||||||
0 |
0 |
1 |
|
||||||||||||
|
0 |
1 1 0;(1,1) = 0 = (1,1) = |
|
1 |
|
||||||||||
0 |
1 |
1 |
|
||||||||||||
|
|
|
|
1 |
1 1. |
|
|
|
|
||||||
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|||||
|
Откуда последовательно находим |
= 1, |
= 0, |
= 0, = 1. |
|||||||||||
1 |
1 |
0 |
|
||||||||||||
|
Таким образом, = 1 . |
|
|
|
|
|
|
||||||||
|
Таблица 2.27 |
б) Выпишем таблицу истинности функции (табл. 2.27). |
|
||||||||||||
|
ЗапишемвобщемвидеканоническийполиномЖегалкинаоттрех |
||||||||||||||
|
|
|
|
||||||||||||
переменных: |
|
|
|
|
|
|
|
|
|
||||||
0 |
0 |
0 |
1 |
|
( , |
, |
) = |
|
|
|
|
|
|||
0 |
0 |
1 |
0 |
|
|
|
|||||||||
|
|
|
|
|
|
. |
|
Нам нужно |
|||||||
0 |
1 |
0 |
1 |
подобрать такие коэффициенты ,чтобы на каждомнаборезначений |
|||||||||||
0 |
1 |
1 |
1 |
переменных выполнялось равенство |
|
|
|
|
|
||||||
1 |
0 |
0 |
0 |
|
( |
, |
, ) = ( , , ). |
|
|
|
|||||
1 |
0 |
1 |
1 |
Имеем: |
|
|
|
|
|
|
|
|
|
||
1 |
1 |
0 |
1 |
(0,0,0) = 1 = (0,0,0) = |
|
0 |
0 |
0 0 |
|
||||||
1 |
1 |
1 |
1 |
|
0 0 0 0 0 0 0 0 = 1; |
||||||||||
11
Тема 4 «Представление булевых функций формулами специального вида» Олейник Т.А., 2020
(0,0,1) = 0 = (0,0,1) = 1 1 |
|
0 |
0 1 |
0 0 1 0 0 0 0 1 = 1; |
|||
(0,1,0) = 1 = (0,1,0) = 1 1 0 |
1 |
1 0 |
|
0 0 0 0 1 0 1 0 = 0; |
|||
(0,1,1) = 1 = (0,1,1) = 1 1 1 |
0 |
1 |
1 1 |
0 0 1 0 1 0 1 1 = 1; (1,0,0) = 0 = (1,0,0) = 1 1 0 0 0 1 0 0
1 1 0 1 0 1 0 0 = 1; (1,0,1) = 1 = (1,0,1) = 1 1 1 0 0 1 0 1
1 1 1 1 1 0 1 0 1 = 0; (1,1,0) = 1 = (1,1,0) = 1 1 0 0 1 1 1 0 1 1
0 1 0 1 1 1 1 0 = 1; (1,1,1) = 1 = (1,1,1) = 1 1 1 0 1 1 1 1 1 1
|
0 1 1 1 1 1 1 1 1 = 0. |
|||||
Теперь, когда коэффициенты найдены, запишем полином Жегалкина: |
|
|
||||
( , , |
) = 1 1 0 |
1 |
|
|
|
|
|
1 |
0 |
|
1 |
|
0 . |
Упростив запись, получим
( , , ) = 1 . ►
Упражнение 2.26. Используя метод неопределенных коэффициентов, построить полином Жегалкина функции:
а) ( , ) = (1011); б) ( , , ) = (11100101).
Ответы и указания к упражнениям
2.25. |
CДHΦ |
|
̄= ̄ |
|
̄= |
|
|
|
|
= ̄ |
|
|
|
|
|||||
|
|
|
|
= ( 1) |
( |
1) = |
. |
||
2.26. а) 1 |
; |
б) 1 |
|
|
|
. |
|
|
|
12