Вариант 30

1. Составить таблицу истинности формул (x)(y|x), ((x)). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

2. Проверить двумя способами, будут ли эквивалентны следующие формулы x(yz) и (xy)(xz):

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

3. С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Построить полином Жегалкина.

4. Найти все сокращённые и минимальные ДНФ переключательной функции f(0, 0, 0)=f(0, 0, 1)=f(1, 0, 1)=f(1, 1, 1)=1. К каким классам Поста принадлежит эта функция?

5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (1001 1011 1100 0101).

6. Является ли полной система функций ={xy, y}? Образует ли она базис?

7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: (A\B)\C=A\(BC).

Приложение 2

Образец выполнения индивидуального задания

Задание 1. Составить таблицу истинности формул x((yx)), x|(). Для СДНФ второй формулы составить переключательную схему и её упрощённый вариант.

Решение. Таблица истинности формулы строится следующим образом. Заголовки таблицы представляют собой всевозможные подформулы формулы, образованные её логическими операциями в порядке их выполнения. Заголовки строк  это всевозможные наборы строк значений пропозициональных переменных. На пересечении строки и столбца стоит значение соответствующей подформулы на соответствующем наборе переменных. Всего можно составить 2^п всевозможных наборов из 0 и 1, значит, и строк у таблицы будет столько же. Следовательно, если формула содержит 2 переменные, то строк у таблицы будет 4, если содержит 3 переменные, то 8. Наборы формируем следующим образом. Упорядочим переменные, входящие в формулы: (x, y) (для первой формулы), (x, y, z) (для второй формулы). Каждый упорядоченный набор представляет собой некоторую последовательность из нулей и единиц. Поэтому его можно рассматривать как некоторое число, записанное в двоичной системе. Располагая наборы в порядке возрастания соответствующих чисел, мы получим упорядочение наборов значений в лексикографическом порядке.

Для первой формулы всевозможными подформулами в порядке их выполнения являются: ,yx, (yx), x((yx)). Поэтому таблица истинности формулы  следующая:

x	y		yx	(yx)	x((yx))
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. Составляя из них ДНФ, получим СДНФ формулы: zzxxy. Ей соответствует следующая переключательная схема:

Для упрощения схемы необходимо упростить формулу, а именно, найдём её минимальную форму.

Применим к СДНФ сначала операцию неполного склеивания

zzxxy~

zxzzxxy

(применили склеивания

z~z,~,

x~x,zz~zzz,

z~z,x~x,

xxy~xxxy)

zx

zzxxy

(применили склеивания

~,z~z,

~,x~x)

а затем  элементарного поглощения:

.

(здесь операции поглощения следующие:

~,z~,~,~и т.д.).

В результате приходим к сокращённой ДНФ формулы: . Очевидно, она является также минимальной. Её схема  следующая

Она и будет упрощённым вариантом предыдущей схемы.

Задание 2. Проверить двумя способами, будут ли эквивалентны следующие формулы x(yz) и (xy)|(xz).

а) составлением таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

Решение. а) Две формулы эквивалентны тогда и только тогда, когда их таблицы истинностей совпадают. Построим сокращённые таблицы обеих формул в одной таблице. В сокращённой таблице заголовки столбцов содержат пропозициональные переменные и самую формулу, а значения подформул указываются прямо под логическими операциями в формуле.

x	y	z	x		(yz)	(xy)	|	(xz)
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(yz)



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. Получили СДНФ формулы.

Для второй формулы имеем

(xy)|(xz)

(xy)(xz)((xy)&(yx))((xz)&(zx))

((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) Применили дистрибутивность (ab)&(cd)~(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&))(xz)&&&

(xz)&&

Получили КНФ формулы. Теперь преобразуем КНФ по алгоритму получения всех условий совершенства:

(xyz)&(xz)&(x)&&

(xyz)&(xz)&(xz)&(x)&&&

(xyz)&(xz)&(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&&)

xzxyzzx

x(1y)zx(1y)(1z)(1x)yz(1x)(1y)zx(1z)

x(1y)zx(1y)(1z)(1x)yz(1x)(1y)zx(1z)

xzxyzxxyxzxyzyzxyzzxzyzxxz

xzxz.

Таким образом, xzxz  полином Жегалкина формулы.

Ответ: ДНФ((x|)(z))~(x&),

СДНФ((x|)(z))=(x&&z)(x&&)(&y&z)

(&&z)(x&&),

полином Жегалкина формулы  xzxz.

Задание 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. Поэтому СДНФ функции имеет вид

zxxyz.

Применим к СДНФ сначала операцию неполного склеивания

xyzxxyz

(применили склеивания

z~z,у~у,

уxу~ууxу,xуxyz~xyxуxyz)

а затем  элементарного поглощения:

xy.

(здесь операции поглощения следующие:z~,

у~и т.д.).

В результате приходим к сокращённой ДНФ формулы: xy.

Для нахождения минимальной ДНФ из сокращённой ДНФ является использование таблицы Квайна. Заголовками столбцов ТК являются конституенты единицы СДНФ, а заголовками строк  простые импликанты из сокращённой ДНФ. Таблица заполняется знаками «+» на пересечениях тех строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. В тупиковую ДНФ выбирается минимальное число тех простых импликант, знаки «+» при которых охватывают все столбцы ТК.

ТК для функции примера 6.2 имеет вид

		z	y	xy	xyz
	+	+
	+		+
y			+	+
xy				+	+

Минимальное число простых импликант, знаки «+» при которых охватывают все столбцы, образуют импликанты первой, второй и четвёртой строк, то есть ,иxу, а также первой, третьей и четвёртой строк, то есть ,yиxу, Поэтому xу и yxу являются МДНФ функции.

Проверим, к каким классам Поста принадлежит функция. Так как f(0, 0, 0)=10 и f(1, 1, 1)=1, то f Р₀ и f Р₁.

Функция самодвойственна, если на всех противоположных наборах значений переменных она принимает противоположные значения. Но на двух противоположных наборах значений (0, 0, 0) и (1, 1, 1) она принимает одинаковое значение 1. Значит, функция не является самодвойственной, то есть fS.

Для проверки на монотонность можно построить помеченный куб, в вершинах которого проставляются значения функции. Построив всевозможные маршруты от вершины (000) до вершины (111), убеждаемся, что на каждом из этих маршрутов при переходе от произвольной вершины (₁, ₂, ₃) к смежной вершине (₁, ₂, ₃) будет выполнено условие f(₁, ₂, ₃)f(₁, ₂, ₃). Если для какого-либо маршрута это условие нарушено, то функция монотонной не является.

Рассмотрим процедуру проверки на монотонность для нашей функции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)=c₀c₁xc₂ус₃z, где

c₀=f(0, 0, 0)=1,

c₁=c₀f(1, 0, 0)=10=1,

c₂=c₀f(0, 1, 0)=11=0,

c₂=c₀f(0, 0, 1)=11=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у и yxу  все минимальные ДНФ функции,

f Р₀, f Р₁, fS, fМ, fL.

Задание 5. Найти сокращённую, все тупиковые и минимальные ДНФ булевой функции f(х₁, х₂, х₃, х₄), заданной вектором своих значений (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, то есть fP₁, g P₁. Таким образом, существует класс, такой, что все функции данной системы лежат в этом классе. Это означает, что система функций полной не является.

Так как система не является полной, то она базис образовывать не может.

Ответ: Система функций полной не является и базис не образует.

Задание 7. С помощью алгебры логики проверить истинность соотношения для любых множеств А, В, С: А\(В\С)=(А\В)(АС).

Решение. Переведём сначала правую и левую части на язык алгебры логики. При этом А, В и С соответствуют a, b и c соответственно: А\(В\С)a&, (А\В)(АС)(a&)(a&c)

Имеем

a&~a&(c)~(a&)(a&c),

то есть a&~(a&)(a&c). Это означает, что А\(В\С)=(А\В)(АС).

Ответ. Соотношение истинно.