ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9336
Скачиваний: 24
61
8.
законы поглощения:
a
∨ a ∧b = а, a ∧ (а ∨ b) = а;
9.
законы Порецкого:
a
∨ a ∧b = а ∨ b, a ∧ (a ∨ b) = а ∧b;
10.
законы, определяющие действия с константами 0 или 1:
a
∨ = а,
a
∧ 0 = 0,
a
∨ 1 = 1,
a
∧ 1 = а,
a
∨ a = 1,
a
∧ a = 0.
Правило подстановки:
если в равносильных формулах
вместо всех вхождений некоторой переменной х подставить одну
и ту же формулу, то получатся равносильные формулы.
Правило замены:
если в формуле заменить некоторую под-
формулу на равносильную, то получится равносильная формула.
6.3
Нормальные
формулы
.
Совершенные
нор
-
мальные
формулы
Обозначим х
о
=
x
, х
1
= х,
⎩
⎨
⎧
=
δ
=
δ
=
δ
.
0
,
x
;
1
,
x
x
Любую конъюнкцию ранга n можно представить в виде:
Элементарной конъюнкцией
называется конъюнкция пе-
ременных, некоторые из которых могут быть взяты со знаком от-
рицания, причем переменная в конъюнкции не должна встречать-
ся более одного раза.
Или: элементарной конъюнкцией называется выражение ви-
да
n
2
1
n
2
1
x
...
x
,
x
δ
δ
δ
,
n
2
1
n
2
1
x
...
x
,
x
δ
δ
δ
.
То
есть
элементарная
конъюнкция
есть
логическое
произве
-
дение
переменных
,
взятых
в
некоторой
степени
δ
,
в
которой
ни
одна
переменная
не
употребляется
два
раза
.
Число
переменных
в
конъюнкции
или
дизъюнкции
назовем
ее
рангом.
Дизъюнкция
различных
элементарных
конъюнкций
называ
-
ется
дизъюнктивной нормальной формой (ДНФ).
Конъюнкция
различных
элементарных
дизъюнкций
называ
-
ется
конъюнктивной нормальной формой (КНФ).
Число
конъюнкций
в
ДНФ
называется
длиной
ДНФ
.
62
Если
мы
возьмем
любую
формулу
из
символов
a, b, c,…, x,
y, z,
∧
,
∨
, ¬,
→
, ~,
⊕
, (, ),
то
можно
ее
заменить
равносильной
ДНФ
.
a
→
b =
a
∨
b, a ~ b =
a
b
∨
a b, a
⊕
b = a b
∨
a
b.
Пример
(
а
∧
b )
→
(
с
∨
d) =
( )
b
a
∧
∨
с
∨
d =
a
∨
b
∨
c
∨
d;
ДНФ
весьма
просто
получается
из
таблицы
истинности
.
Достаточно
поставить
в
соответствие
каждому
значению
вектор
аргумента
,
на
котором
функция
принимает
значение
1,
элемен
-
тарную
конъюнкцию
,
называемую
полной
и
состоящую
из
всех
аргументов
.
Такая
ДНФ
,
членами
которой
являются
неповто
-
ряющиеся
полные
элементарные
конъюнкции
,
называется
со-
вершенной ДНФ (СДНФ),
а
ее
члены
констатуэнтами едини-
цы.
С
ДНФ
любой
булевой
функции
единственна
с
точностью
до
порядка
следования
членов
и
литералов
(
чего
нельзя
сказать
о
ДНФ
)
и
является
,
как
говорят
, канонической формой.
Пример
.
Пусть
задана
функция
(a
⊕
b)
→
(c ~ a).
Построим
таблицу
истинности
.
a b c a
⊕
b c ~ a (a
⊕
b)
→
(c ~ a)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
0 1 0
1 1 1
0
0
1
1
1
1
0
0
1
0
1
0
0
1
0
1
1
1
1
0
0
1
1
1
Построим
СДНФ
.
КНФ
так
же
удобна
для
представления
нулей
булевой
функ
-
ции
,
как
ДНФ
для
представления
единиц
.
СКНФ
для
предыдущего
примера
запишется
abc
c
ab
c
b
a
c
b
a
c
b
a
c
b
a
∨
∨
∨
∨
∨
)
c
b
a
)(
c
b
a
(
∨
∨
∨
∨
63
Каждая
из
составляющих
ее
полных
элементарных
дизъ
-
юнкций
является
конституэнтой нуля
и
определяет
значение
вектор
аргумента
,
на
котором
функция
обращается
в
нуль
.
6.4
Разложение
Шеннона
.
Декомпозиция
булевых
функций
Рассмотрим
разложение
булевой
функции
f(x
1
, x
2
,…, x
n
)
по
k
переменным
(x
1
,…, x
k
) –
разложение
Шеннона
.
Теорема 1.
Любая
функция
f(x
1
, x
2
,…, x
n
),
не
равная
тожде
-
ственно
нулю
,
представлена
в
виде
разложения
Шеннона
:
.
Заметим
,
что
,
1
x
,...,
x
,
x
k
2
1
k
2
1
=
δ
δ
δ
если
x
i
=
δ
i
,
для
∀
i
= k
,
1
.
Вы
-
берем
набор
δ
1
,
δ
2
,…,
δ
k
и
положим
,
что
x
i
=
δ
i
, i = 1,k.
Тогда
левая
часть
будет
равна
:
f(x
1
, x
2
,…, x
k
, x
k+1
, …, x
n
) = f(
δ
1
,…,
δ
k
, x
k+1
, …, x
n
),
а
правая
:
.
Здесь
k
1
k
1
x
,..,
x
δ
δ
разбиваются
на
единичные
и
нулевые
набо
-
ры
.
Согласно
закону
а
∨
0 =
а
,
получаем
,
что
левая
и
правая
части
формул
равны
при
любой
подстановке
переменных
х
1
,
х
2
,…,
х
k
.
Теорема 2.
Любая
булева
функция
может
быть
представле
-
на
формулой
,
являющейся
суперпозицией
∨
,
∧
, ¬.
Доказательство
.
1)
В
начале
докажем
для
f=1
или
f=0.
f(x
1
, x
2
,…, x
n
) = 1 = x
i
∨
x
i
;
f(x
1
, x
2
,…, x
n
) = 0 = x
i
∧
x
i
;
2)
Докажем
для
функции
,
не
равной
константе
,
f(x
1
, x
2
,…, x
n
)
разложим
по
n
переменным
.
Получим
.
)
x
,...,
,
,...,
,
(
x
&
V
)
x
,...,
x
,
x
,...,
x
,
x
(
f
n
1
k
k
2
1
i
k
1
i
)
,...,
,
(
n
1
k
n
2
1
i
k
2
1
+
δ
=
δ
δ
δ
∀
+
δ
δ
δ
δ
=
)
x
,...,
x
,
,...,
,
(
f
)
x
,...,
x
,
,...,
,
(
f
x
,...,
Vx
n
1
k
k
2
1
n
1
k
k
2
1
k
1
k
1
+
+
δ
δ
δ
δ
δ
=
δ
δ
δ
δ
δ
δ
δ
δ
δ
=
δ
δ
n
1
n
1
n
1
,...,
x
...
Vx
)
...
(
f
x
...
x
V
1
n
1
n
1
64
Это
совершенная
ДНФ
.
Из
этой
формулы
следует
способ
построения
СДНФ
.
Заметим
,
что
f
может
быть
разложена
(
в
булевой
алгебре
справедлив
принцип
двойственности
).
Согласно
закону
двойного
отрицания
(
)
(
)
.
x
...
x
x
)
,...,
,
(
f
x
...
x
x
)
,...,
(
f
x
,...,
x
V
)
x
,...,
x
,
x
,...,
x
,
x
(
f
)
x
,...,
x
,
x
(
f
n
2
1
n
1
n
2
1
n
1
n
1
n
1
n
2
1
,..,
n
2
1
n
2
1
,..,
n
1
n
1
,...,
n
1
k
k
2
1
n
2
1
δ
δ
δ
δ
δ
δ
δ
δ
δ
δ
δ
δ
δ
δ
+
∨
∨
∨
∧
=
δ
δ
δ
∨
∨
∨
∨
∧
=
=
δ
δ
=
=
(1)
Таким
образом
,
любая
булева
функция
f(x
1
, x
2
,…, x
n
),
не
равная
тождественно
единице
,
представлена
в
виде
выражения
1.
Покажем
связь
между
разложением
Шеннона
и
таблицами
Вейча
.
Представим
пространство
P
n
(X)
в
виде
декартова
произве
-
дения
пространств
P
k
(X
a
)
и
P
g
(X
b
), X
a
∪
X
b
= X, X
a
∩
X
b
=
∅
,
k + g = n:
P
n
(X) = P
k
(X
a
)
×
P
g
(X
b
).
Каждой
строке
таблицы
Вейча
взаимно
однозначно
сопоста
-
вим
точку
пространства
P
k
(X
a
),
столбцу
–
точку
пространства
P
g
(X
b
)
и
рассмотрим
разложение
Шеннона
булевой
функции
по
первым
k
переменным
.
Тогда
i-
строка
таблицы
Вейча
,
иден
-
тифицируемая
конъюнкцией
k
k
2
2
1
1
a
a
a
x
...
x
x
δ
δ
δ
∧
∧
∧
,
соответствует
остаточной
функции
.
Будем
называть
разложение
Шеннона
булевой
функции
f(X)
строчным
,
если
разложение
осуществляется
по
переменным
,
со
-
ответствующим
строкам
таблицы
Вейча
.
)
,...,
(
f
x
,...,
x
V
)
x
,...,
x
(
f
n
1
n
1
,...,
n
1
n
1
n
1
δ
δ
=
=
δ
δ
δ
δ
(
)
g
2
1
k
2
1
b
b
b
,
a
a
a
x
,...,
x
,
x
x
,...,
x
,
x
f
(
)
g
2
1
k
2
1
b
b
b
,
a
a
a
x
,...,
x
,
x
x
,...,
x
,
x
f
65
6.5
Представление
булевой
функции
картами
Карно
(
Вейча
)
Карта
Карно
–
это
диаграмма
,
состоящая
из
правильно
рас
-
положенных
квадратов
,
каждый
из
которых
соответствует
одной
из
2
n
полных
конъюнкций
соответствующих
функции
от
n
пере
-
менных
.
Значения
данной
функции
f
из
таблицы
истинностей
вносят
в
нужные
квадраты
.
Тогда
функция
f
равна
дизъюнкции
всех
полных
конъюнкций
,
для
которых
в
соответствующих
квад
-
ратах
стоит
единица
.
Рассмотрим
построение
карт
Карно
.
Пусть
задана
функция
от
двух
переменных
.
Тогда
карта
Карно
будет
выглядеть
x
1
00 01
x
2
10 11
Чтобы
наборы
не
мешали
внутри
клеток
,
их
можно
вынести
за
пределы
таблицы
x
1
0 1
0
x
2
1
В
карте
Карно
соседние
клетки
различаются
одной
компо
-
нентой
.
Для
кодировки
используется
код
Грея
.
Код
Грея
получа
-
ется
из
обыкновенного
весового
кода
сложением
по
mod 2.
Иско
-
мое
число
вычисляется
следующим
образом
.
Берем
весовой
код
в
качестве
первого
слагаемого
,
в
качестве
второго
слагаемого
бе
-
рем
тот
же
код
,
но
сдвинутый
на
один
разряд
вправо
.
Произво
-
дим
сложение
по
mod 2.
Тогда
карта
Карно
для
трех
переменных
будет
выглядеть
: