2Дискретка / Задачники / 2.Булева алгебра
.pdf3.БУЛЕВА АЛГЕБРА
1.Для заданной функции построить таблицу истинности, найти СДНФ и СКНФ, используя эквивалентные преобразования получить тупиковую ДНФ.
1)(z Å yx) Û yz Ú z / x, 2) z / x Þ (xy Ú z (x Å yz)) Û xz ,
2.Из заданного множества элементарных конъюнкций K выде- лить простые импликанты функции f .
1)K = {x, z, xy, yz}, f (x, y, z) = (0010 1111) ;
2)K = {xy, yz, x, xyz}, f (x, y, z) = (01111110) ;
3)K = {x, p, yz, xyz} , f (x, y, z) = (1010 1110 01011110).
3.Перечислить существенные переменные следующих функций:
1) |
f (x, y, z) = (x Þ (x Ú y)) Þ z ; |
2) |
f (x, y) = (x Ú y) Þ y ; 4) f (x, |
2) f (x, y, z) = (x Å y)(x ¯ y). y, z, p) = (x Ú y Ú y z Ú x y z ) p ;
4. Доказать, что если среди переменных функции f (x1,..., xn ),
имеются фиктивные, то функция принимает значение 1 на четном числе наборов. Верно ли обратное утверждение?
5.Эквивалентны ли формулы:
1)((x Ú y)Ú z) Þ ((x Ú y)(x Ú z)) и x : z ;
2)(x Þ y) Þ z и x Þ ( y Þ z);
3)((x Å y) Þ (x Ú y))((x Þ y) Þ (x Å y)) и x | y ?
6.Минимизировать заданную функцию методом Квайна:
1)x y z x y z x y z ,
2)x y z x y z x y z x y z x y z x y z ,
3)x y z x y z x y z x y z x y z ,
4)x y z x y z x y z x y z ,
5)x y z p x y z p x y z p x y z p x y z p ,
6)x y z p x y z p x y z p x y z p x y z p x y z p x y z p .
1
7. Минимизировать заданную функцию методом Блейка:
1) x y z x y z x y z , |
5) x y z x y p x z p y z p , |
||||||
2) x z x y y z z x , |
6) x y x z p y z p , |
|
|||||
3) x y x z y z , |
7) x y z x y p z p , |
|
|||||
4) x y z x y z x z , |
8) x y x z x y z p x y z p . |
||||||
8. Используя |
карты |
Карнафа |
минимизировать |
функцию |
|||
f (x, y, z), заданную набором своих значений: |
|
||||||
1) |
f |
= (0101 0010), |
4) |
f |
= (1100 0011), |
|
|
2) |
f |
= (1110 1101), |
5) |
f |
= (1111 1000), |
|
|
3) |
f |
= (0101 0111), |
6) |
f |
= (0111 1110). |
|
|
9. Используя |
карты |
Карнафа |
минимизировать |
функцию |
|||
f (x, y, z, p), заданную набором своих значений:
1) |
f |
= (1100 0101 0000 0001), |
5) |
f |
= (1111 1000 0100 1100), |
2) |
f |
= (1111 1000 0100 1100), |
6) |
f |
= (0000 0011 1111 1101), |
3) |
f |
= (0011 0011 0101 0011), |
7) |
f |
= (0001 1011 1101 1011), |
4) |
f |
= (0011 0011 0001 1111), |
8) |
f |
= (1101 0111 1110 1011). |
10.Построить все тупиковые ДНФ следующих функций
1)f (x, y, z) = (0111 1110),
2)f (x, y, z, p) = (1110 0110 0001 0101),
3)f (x, y, z, p) = (0110 1011 1101 1110),
2)f (x, y, z, p) = (1110 0110 0001 0101).
11.Выписать все сравнимые наборы для функции 2-х, 3-х и 4-х переменных.
12.Доказать следующие утверждения:
1)Если функция f (x1,..., xn ), n ³ 2 принимает значение 1 на не-
четном количестве наборов, то она нелинейна.
2) |
Если f ¹ const 0 и f P1 , то |
f ÏM . |
3) |
Если f ¹ const1 и f P0 , то |
f ÏM . |
4) |
Если в СДНФ знак везде заменить на знак Å , то получится |
|
формула, эквивалентная исходной.
2
13.Сколько 1 в наборе значений самодвойственной функции n переменных?
14.Для всех переключательных функций двух переменных опре- делить принадлежность их классам Поста.
15.Составить все возможные базисы из функций двух переменных.
16.Для функций из задания 8 определить принадлежность их классам Поста. Составить все возможные базисы из этих функций.
17.Проверить полноту заданной системы функций. Для функциональ-
но полной системы выделить все возможные базисы.
1)F = { f1, f2} , f1 = (0110 1001), f2 = (1000 1101) ;
2)F = { f1, f2 , f3 , f4},
f1 = (0110 1001), f2 = (1000 1101) , f3 = (0001 1100) , f4 = 0;
3) F = { f1, f2 , f3}, |
|
f1 = (0100 0100) , f2 |
= (1111 1100) , f3 = (1000 0000), |
4) F = { f1, f2 , f3 , f4}, f1 = xy , f2 = x : yz , f3 =1, f4 = 0; |
|
5) F = { f1, f2 , f3 , f4}, |
|
f1 = (1001 0110), |
f2 = (1100 0011), f3 =1, f4 = 0. |
18.По установленному сигналу каждый игрок замыкает или раз- мыкает выключатель, находящийся под его управлением. Если оба делают одно и то же, то выигрывает игрок A , в противном случае – игрок B . Построить такую схему, что бы при выигрыше A зажига- лась лампочка.
19.Муниципальный совет состоит из пяти членов, включая пред- седателя совета. Каждый член совета имеет для голосования кнопку «за» и кнопку «против». Постройте схему для определения приня- тия или непринятия решения путем высвечивания индикатора, если:
1)Решение принимается, если за него проголосует большинство.
2)Решение принимается, если за него проголосует большинст- во. Председатель совета голосует только в том случае, если голоса «за» и «против» разделились поровну.
3)Решение принимается, если за него проголосует большинст- во, исключая председателя, который имеет право вето.
3
Расчетно-графическая работа по теме «Булева алгебра»
Задание
Для заданной переключательной функции f (x, y, z, p):
1.Построить таблицу истинности;
2.Построить изображение на кубе;
3.Найти СДНФ и СКНФ;
4.Используя эквивалентные преобразования получить тупико- вую ДНФ;
5.Найти все минимальные формы методом Квайна и построить для них таблицу истинности;
6.Найти все минимальные формы методом Блейка, выбрав в качестве исходной любую ДНФ этой функции, отличную от СДНФ;
7.Найти минимальную форму методом карт Карнафа;
8.Определить принадлежность классам Поста;
9.Построить функционально полную систему функций так,
чтобы эта система была базисом и содержала f (x, y, z, p) .
Срок выполнения
К первому занятию, следующему после окончания темы «Булева алгебра».
Оформление
Пример решения типового задания с необходимыми пояснениями подробно рассмотрен в учебном пособии «Основы дискретной матема- тики». Оформление решений по соответствующему варианту приводить в полном соответствии с рассмотренными в учебном пособии задачами.
Форма защиты
Устно, в указанное преподавателем время. Студенты, выполнив- шие работу в установленный преподавателем срок и успешно напи- савшие контрольную работу по теме «Булева алгебра», от устной защиты освобождаются.
4