- •Методические материалы к изучению курса «Дискретная математика»
- •Часть IV. Булевы функции
- •Содержание
- •§1. Высказывания и операции над ними.
- •§2. Формулы алгебры логики. Таблицы истинности.
- •§3. Логическое следование и равносильность формул. Связь с булевыми алгебрами.
- •§4. Нормальные формы. Двойственность.
- •4.1. Дизъюнктивная нормальная форма. Совершенная дизъюнктивная нормальная форма.
- •4.2. Конъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма.
- •§5. Булевы функции и основные их классы. Полином Жегалкина.
- •5.1. Понятие булевой функции и способы её задания.
- •5.3. Полином Жегалкина.
- •5.4. Функциональная полнота.
- •§6. Минимизация булевых функций.
- •6.2. Сокращённая днф. Метод Квайна.
- •§7. Применение к релейно-контактным схемам.
- •Варианты индивидуальных заданий Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Вариант 8
- •Вариант 9
- •Вариант 10
- •Вариант 11
- •Вариант 12
- •Вариант 13
- •Вариант 14
- •Вариант 15
- •Вариант 16
- •Вариант 17
- •Вариант 18
- •Вариант 19
- •Вариант 20
- •Вариант 21
- •Вариант 22
- •Вариант 23
- •Вариант 24
- •Вариант 25
- •Вариант 26
- •Вариант 27
- •Вариант 28
- •Вариант 29
- •Вариант 30
- •Образец выполнения индивидуального задания
- •Литература
Вариант 30
1. Составить таблицу истинности формул (x)(y|x), ((x)). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.
2. Проверить двумя способами, будут ли эквивалентны следующие формулы x(yz) и (xy)(xz):
а) составлением таблиц истинности;
б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
3. С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Построить полином Жегалкина.
4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 0)=f(0, 0, 1)=f(1, 0, 1)=f(1, 1, 1)=1. К каким классам Поста принадлежит эта функция?
5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х1, х2, х3, х4), заданной вектором своих значений (1001 1011 1100 0101).
6. Является ли полной система функций ={xy, y}? Образует ли она базис?
7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: (A\B)\C=A\(BC).
Приложение 2
Образец выполнения индивидуального задания
Задание 1. Составить таблицу истинности формул x((yx)), x|(). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.
Решение. Таблица истинности формулы строится следующим образом. Заголовки таблицы представляют собой всевозможные подформулы формулы, образованные её логическими операциями в порядке их выполнения. Заголовки строк это всевозможные наборы строк значений пропозициональных переменных. На пересечении строки и столбца стоит значение соответствующей подформулы на соответствующем наборе переменных. Всего можно составить 2п всевозможных наборов из 0 и 1, значит, и строк у таблицы будет столько же. Следовательно, если формула содержит 2 переменные, то строк у таблицы будет 4, если содержит 3 переменные, то 8. Наборы формируем следующим образом. Упорядочим переменные, входящие в формулы: (x, y) (для первой формулы), (x, y, z) (для второй формулы). Каждый упорядоченный набор представляет собой некоторую последовательность из нулей и единиц. Поэтому его можно рассматривать как некоторое число, записанное в двоичной системе. Располагая наборы в порядке возрастания соответствующих чисел, мы получим упорядочение наборов значений в лексикографическом порядке.
Для первой формулы всевозможными подформулами в порядке их выполнения являются: ,yx, (yx), x((yx)). Поэтому таблица истинности формулы следующая:
-
x
y
yx
(yx)
x((yx))
0
0
1
1
1
1
0
1
0
0
1
1
1
0
1
0
0
1
1
1
0
1
1
0
Для второй формулы всевозможными подформулами в порядке их выполнения являются: ,,xy, ,,, x|(). Поэтому таблица истинности формулы следующая:
-
x
y
z
xy
x|()
0
0
0
1
1
0
1
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
0
1
1
0
1
1
0
1
1
0
0
1
0
1
0
1
1
0
0
1
1
0
0
0
1
1
1
1
0
1
0
0
1
1
0
Для составления СДНФ выберем те наборы значений переменных, при которых формула принимает значение 1: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 1, 0). Составим соответствующие им конъюнкты: , z, , z, x, xy. Составляя из них ДНФ, получим СДНФ формулы: zzxxy. Ей соответствует следующая переключательная схема:
Для упрощения схемы необходимо упростить формулу, а именно, найдём её минимальную форму.
Применим к СДНФ сначала операцию неполного склеивания
zzxxy~
zxzzxxy
(применили склеивания
z~z,~,
x~x,zz~zzz,
z~z,x~x,
xxy~xxxy)
zx
zzxxy
(применили склеивания
~,z~z,
~,x~x)
а затем элементарного поглощения:
.
(здесь операции поглощения следующие:
~,z~,~,~и т.д.).
В результате приходим к сокращённой ДНФ формулы: . Очевидно, она является также минимальной. Её схема следующая
Она и будет упрощённым вариантом предыдущей схемы.
Задание 2. Проверить двумя способами, будут ли эквивалентны следующие формулы x(yz) и (xy)|(xz).
а) составлением таблиц истинности;
б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
Решение. а) Две формулы эквивалентны тогда и только тогда, когда их таблицы истинностей совпадают. Построим сокращённые таблицы обеих формул в одной таблице. В сокращённой таблице заголовки столбцов содержат пропозициональные переменные и самую формулу, а значения подформул указываются прямо под логическими операциями в формуле.
-
x
y
z
x
(yz)
(xy)
|
(xz)
0
0
0
1
1
0
1
0
0
0
1
1
1
0
1
1
0
1
0
0
0
1
1
0
0
1
1
1
1
1
0
1
1
0
0
0
1
1
0
1
1
0
1
0
1
1
1
0
1
1
0
1
0
0
1
1
1
1
1
0
1
0
1
0
Значения формул (они выделены жирным шрифтом) не совпадают на некоторых наборах значений переменных (например, на наборе (0, 1, 0)), то есть таблицы истинности у формул различны. Следовательно, формулы неэквивалентны.
б) Приведём обе формулы к СДНФ. Для первой формулы имеем
x(yz)
x&(z)&x(x&y&)(&x)(z&x)
(x&y&)(x&&z)(x&&)(x&y&z)(x&&z)
(x&y&)(x&&z)(x&&)(x&y&z).
(1) По определению операцию заменили на отрицание операции.
(2) От операции перешли к операциями &.
(3) От операции перешли к операции.
(4), (5) Применили законы де Моргана и снятия двойного отрицания.
(6) Применили законы де Моргана, снятия двойного отрицания и дистрибутивность & относительно . Получили ДНФ формулы.
(7) 2-ю и 3-ю конъюнкцию разбили на две, применив эквиваленции x&~(x&&z)(x&&) иx&z~(x&y&z)(x&&z).
(8) Убрали лишнюю конъюнкцию x&&z. Получили СДНФ формулы.
Для второй формулы имеем
(xy)|(xz)
(xy)(xz)((xy)&(yx))((xz)&(zx))
((y)&(x))((z)&(x))
(&)(&x)(y&)(y&x)(&)(&x)(z&)(z&x)
(&)(y&x)(&)(z&x)
(&&z)(&&)(x&y&z)(x&y&)
(&y&)(&&)(x&y&z)(x&&)
(&&z)(&&)(x&y&z)(x&y&)(&y&)(x&&).
(1) По определению операцию | заменили на отрицание операции &.
(2) По определению операцию заменили на отрицание операции.
(3) Применили законы де Моргана и снятия двойного отрицания.
(4) От операции перешли к операциями &.
(5) От операции перешли к операции.
(6) Применили дистрибутивность (ab)&(cd)~(a&c)(a&d)(b&c)&(b&d).
(7) Воспользовались законами противоречия и А0~А. Получили ДНФ формулы.
(8), (9) Привели к условиям совершенства и получили СДНФ формулы (как и для предыдущей формулы.
Две формулы эквивалентны тогда и только тогда, когда их СДНФ (СКНФ) совпадают. Так как для наших формул их СДНФ различны, формулы неэквивалентны.
Задание 3. С помощью эквивалентных преобразований приведите формулу (x|)(z) к ДНФ, КНФ, СДНФ, СКНФ. Построить полином Жегалкина.
Решение. 1) Приведём формулу к ДНФ и СДНФ:
(x|)(z)()(z)(x&)
(x&)(x&)
(x&)(x&)
(x&)((x&)
Получили ДНФ формулы. Теперь преобразуем ДНФ по алгоритму получения всех условий совершенства:
(x&&z)(x&&)(&y&z)(& &z)
(x&&z)(& &z)(x&&)
(x&&z)(x&&)(&y&z)(&&z)(x&&).
(1) Одновременно заменили | на отрицание операции &, и на отрицание.
(2) Одновременно применили закон двойного отрицания и заменили наи его отрицание.
(3) Операцию заменили на.
(4) Применили закон де Моргана.
(5) Заменили на.
(6), (7) Одновременно применили законы де Моргана и снятия двойного отрицания.
(8) Воспользовались дистрибутивностью & относительно .
(9) 1-й, 2-й и 3-й конъюнкты преобразовали, добавив недостающие переменные и их отрицания заменив каждый из них на два (шаг 1-й алгоритма приведения к СДНФ).
(10) 5-й и 6-й конъюнкты опустили, так как они уже участвуют в полученной ДНФ (шаг 2-го алгоритма).
2) Приведём формулу к КНФ и СКНФ. При этом до преобразования (7) наши преобразования, применённые при решении задачи на получение ДНФ и СДНФ, повторяются:
(x|)(z)~(x&)(
(x&))
(x&()))(x&((у)&)))
(x&))(xz)&&&
(xz)&&
Получили КНФ формулы. Теперь преобразуем КНФ по алгоритму получения всех условий совершенства:
(xyz)&(xz)&(x)&&
(xyz)&(xz)&(xz)&(x)&&&
(xyz)&(xz)&(x)&&
(8) Воспользовались ассоциативностью и коммутативностью .
(9) 1-й и 2-й конъюнкты объединили в один с помощью дистрибутивности & относительно .
(10) К подформуле применили закон дистрибутивности.
(11) Воспользовались тем, что у~1.
(12) Применили сложную дизъюнкцию относительно .
(13) Применили законы исключённого третьего и идемпотентности.
(14) В 1-й и 2-й дизъюнкты добавили недостающие литеры и разбили их по два дизъюнкта каждую (1-я операция приведения к СКНФ).
(15) Операцию, аналогичную (14) проделали с 3-м и 4-м дизъюнктами.
(16) Опустили лишние дизъюнкты.
3) Найдём полином Жегалкина. Для представления булевой функции в виде полинома Жегалкина достаточно в её СДНФ выразить операции &, , через операции булева кольца по формулам А&В=АВ, АВ=АВАВ (причём, если А и В являются конституентами единицы, а в СКНФ все члены являются ими, то имеем АВ=АВ), =1А, АА=0, раскрыть скобки, пользуясь дистрибутивностью операции относительно и привести подобные члены. Имеем
(x&&z)(x&&)(&y&z)(&&z)(x&&)
xzxyzzx
x(1y)zx(1y)(1z)(1x)yz(1x)(1y)zx(1z)
x(1y)zx(1y)(1z)(1x)yz(1x)(1y)zx(1z)
xzxyzxxyxzxyzyzxyzzxzyzxxz
xzxz.
Таким образом, xzxz полином Жегалкина формулы.
Ответ: ДНФ((x|)(z))~(x&),
СДНФ((x|)(z))=(x&&z)(x&&)(&y&z)
(&&z)(x&&),
полином Жегалкина формулы xzxz.
Задание 4. Найти все сокращённые и минимальные ДНФ булевой функции f(0, 1, 1)=f(1, 0, 0)=f(1, 0, 1)=0. К каким классам Поста принадлежит эта функция?
Решение. Нам даны наборы значений переменных, на которых функция принимает значение 0. На остальных наборах она принимает значение 1. Это следующие наборы: (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 1, 0), (1, 1, 1). Им соответствуют конъюнкции , z, , x, xyz. Поэтому СДНФ функции имеет вид
zxxyz.
Применим к СДНФ сначала операцию неполного склеивания
xyzxxyz
(применили склеивания
z~z,у~у,
уxу~ууxу,xуxyz~xyxуxyz)
а затем элементарного поглощения:
xy.
(здесь операции поглощения следующие:z~,
у~и т.д.).
В результате приходим к сокращённой ДНФ формулы: xy.
Для нахождения минимальной ДНФ из сокращённой ДНФ является использование таблицы Квайна. Заголовками столбцов ТК являются конституенты единицы СДНФ, а заголовками строк простые импликанты из сокращённой ДНФ. Таблица заполняется знаками «+» на пересечениях тех строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. В тупиковую ДНФ выбирается минимальное число тех простых импликант, знаки «+» при которых охватывают все столбцы ТК.
ТК для функции примера 6.2 имеет вид
-
z
y
xy
xyz
+
+
+
+
y
+
+
xy
+
+
Минимальное число простых импликант, знаки «+» при которых охватывают все столбцы, образуют импликанты первой, второй и четвёртой строк, то есть ,иxу, а также первой, третьей и четвёртой строк, то есть ,yиxу, Поэтому xу и yxу являются МДНФ функции.
Проверим, к каким классам Поста принадлежит функция. Так как f(0, 0, 0)=10 и f(1, 1, 1)=1, то f Р0 и f Р1.
Функция самодвойственна, если на всех противоположных наборах значений переменных она принимает противоположные значения. Но на двух противоположных наборах значений (0, 0, 0) и (1, 1, 1) она принимает одинаковое значение 1. Значит, функция не является самодвойственной, то есть fS.
Для проверки на монотонность можно построить помеченный куб, в вершинах которого проставляются значения функции. Построив всевозможные маршруты от вершины (000) до вершины (111), убеждаемся, что на каждом из этих маршрутов при переходе от произвольной вершины (1, 2, 3) к смежной вершине (1, 2, 3) будет выполнено условие f(1, 2, 3)f(1, 2, 3). Если для какого-либо маршрута это условие нарушено, то функция монотонной не является.
Рассмотрим процедуру проверки на монотонность для нашей функцииf(x, y, z). Построим помеченный куб, в вершинах которого проставлены значения функции f(x, y, z). Как видим, существует маршрут от вершины (000) к вершине (111), для которого при переходе от одной вершины к другой значение функции меняется от 1 к 0. Например, это маршрут ((000, 100), (100, 1100), (110, 111)). По этому маршруту имеем, что f(1, 0, 0)<f(0, 0, 0). Следовательно, функция монотонной не является: fМ.
Проверим функцию на линейность. Предположим, что функция линейна: f(х, у, z)=c0c1xc2ус3z, где
c0=f(0, 0, 0)=1,
c1=c0f(1, 0, 0)=10=1,
c2=c0f(0, 1, 0)=11=0,
c2=c0f(0, 0, 1)=11=0,
то есть f(х, у, z)=1х. Составим таблицы истинности f(х, у, z) и 1х:
-
x
y
z
f(х, у, z)
1х
0
0
0
1
1
0
0
1
1
1
0
1
0
1
1
0
1
1
0
1
1
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
0
Таблицы истинности f(х, у, z) и 1х не совпадают. Следовательно, f(х, у, z) не является линейной, то есть f(х, у, z)L.
Ответ: xy сокращённая ДНФ, xу и yxу все минимальные ДНФ функции,
f Р0, f Р1, fS, fМ, fL.
Задание 5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х1, х2, х3, х4), заданной вектором своих значений (0001 0111 1101 1001).
Решение. Применим метод Квайна-Мак-Класки. Алгоритм метода следующий:
1. Представим каждую конституенту булевой функции в виде двоичного набора длины 4.
2. Сгруппируем наборы так, чтобы в каждую группу попали те и только те наборы, которые имеют одинаковое число единиц, располагая их в порядке возрастания числа единиц.
3. Сравнивая наборы из соседних групп, выделяем пары, отличающиеся только в одной позиции (тем самым выделяем конституенты, отличающиеся только одной литерой).
4. В обоих выделенных наборах пар заменяем отличающиеся символы (0 и 1) на «-» (тем самым из двух различных наборов получаем один и тот же набор из 0, 1 и «-», что соответствует тому, что два одинаковых элементарных произведения склеили по отличающейся литере, при этом знак «-» соответствует тому, что соответствующая литера в полученном элементарном произведении будет отсутствовать).
Если в результате склеивания получается уже имеющийся набор, то результат склеивания (то есть полученный набор) опускается (это соответствует тому, что согласно закона идемпотентности одинаковые элементарные произведения сливаются в одну). Если в результате склеивания получаются наборы, отличающиеся только в одной позиции, причём в соответствующей позиции одного стоит знак «-» (у других 0 или 1), то остальные опускаются (что соответствует элементарному поглощению)
5. После всевозможных склеиваний на очередном этапе, переходим к пункту 2.
Процесс продолжается до тех пор, пока склеивать будет нечего. Простыми импликантами являются те элементарные произведения, которые не участвовали в процессе склейки на очередном шаге.
Располагать группы и результаты всех шагов будем в таблице. Кроме того, наборы, участвующие при склейке на очередном шаге, будем помечать знаком «*». Тогда после конечного шага все наборы, не участвовавшие при склейке на очередном шаге, останутся непомеченными.
Таблица выглядит следующим образом
-
I шаг
II шаг
1000*
100-
1-00
0011*
0101*
0110*
1001*
1100*
0-11*
-011*
01-1
011-
10-1
--11
0111*
1011*
-111*
1-11*
1111*
На первом шаге склеили: 1) 1000 с 1001 получили 100-; 2) 0011 с 0111 получили 0-11; 3) 0101 с 0111 получили 01-1; 4) 0110 с 0111 получили 011-; 5) 0011 с 1011 получили -011; 5) 1001 с 1011 получили 10-1. На втором шаге склеили: 1) -011 с -111 получили -11; 2) 0-11 с 1-11 получили -11. Больше склеивать нечего. Непомеченными остались 100-, 1-00, 01-1, 011-, 10-1, --11. Им соответствуют простые импликанты ,,,,,. Это означает, что сокращённой ДНФ функции является.
Для построения тупиковых и минимальных ДНФ построим таблицу Квайна:
|
1000 |
0011 |
0101 |
0110 |
1001 |
1100 |
0111 |
1011 |
1111 |
--11 |
|
+ |
|
|
|
|
+ |
+ |
+ |
100- |
+ |
|
|
|
+ |
|
|
|
|
1-00 |
+ |
|
|
|
|
+ |
|
|
|
01-1 |
|
|
+ |
|
|
|
+ |
|
|
011- |
|
|
|
+ |
|
|
+ |
|
|
10-1 |
|
|
|
|
+ |
|
|
+ |
|
Тупиковой ДНФ является конъюнкция наименьшего числа тех простых импликант, которые покрывают в совокупности все конституенты единицы функции. Таковыми будут и. В обеих тупиковых ДНФ одинаковое число вхождений переменных. Поэтому обе являются минимальными.
Ответ. Сокращённая ДНФf~
,
Тупиковые и минимальные ДНФ
и .
Задание 6. Является ли полной система функций ={x, y}? Образует ли она базис?
Решение. Система булевых функций является полной тогда и только тогда, когда для каждого из классов Поста система содержит функцию, не лежащую в данном классе. Поэтому, для того, чтобы доказать, что система функций является полной достаточно проверить, что для любого класса Поста в данной системе функций существует функция, не принадлежащая данному классу. Если это условие не выполнено, то система функций не является полной.
Введём обозначения: f(х, у)=x, g(х, у)=y. Составим таблицу истинности обеих функций:
-
x
y
x
y
0
0
1
1
0
1
0
1
1
0
0
0
1
1
1
1
Из таблицы видно, что f(1, 1)=g(1, 1)=1, то есть fP1, g P1. Таким образом, существует класс, такой, что все функции данной системы лежат в этом классе. Это означает, что система функций полной не является.
Так как система не является полной, то она базис образовывать не может.
Ответ: Система функций полной не является и базис не образует.
Задание 7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: А\(В\С)=(А\В)(АС).
Решение. Переведём сначала правую и левую части на язык алгебры логики. При этом А, В и С соответствуют a, b и c соответственно: А\(В\С)a&, (А\В)(АС)(a&)(a&c)
Имеем
a&~a&(c)~(a&)(a&c),
то есть a&~(a&)(a&c). Это означает, что А\(В\С)=(А\В)(АС).
Ответ. Соотношение истинно.