Дискретка (Жаркова)

Практическое занятие № 4 КР № 1 на 40 минут

Практическое занятие № 4 по лекциям 3-4 Тема: «Булевы функции и способы их задания»

Обсуждаемые понятия, утверждения, алгоритмы

Булев вектор. Функции алгебры логики (булевы функции). Задание булевых функций таблицей истинности и вектором значений. Элементарные булевы функции одной и двух переменных. Формулы над множеством функций, задание функций формулами. Фиктивные и существенные переменные, равные функции, алгоритм удаления и введения фиктивных переменных.

Теоретические сведения

Теоретические сведения и примеры решения типовых задач базового уровня приведены в Л1. § 2.1. Краткое изложение теории есть в Л2. Глава 2. § 2.1, п. 1, 2, стр. 24-27.

Учебная литература, используемая на занятии

1.Олейник Т.А. Основы дискретной математики: теория и практика. – М.: МИЭТ, 2010

2.Клюшин А.В., Кожухов И.Б., Олейник Т.А. Сборник задач по дискретной математике. – М.: МИЭТ,

2008.

Практика под руководством педагога

№Обязательные задачи

1.Булевы векторы и булевы функции Л2. 2.1 (а,б), 2.4 (а,б), 2.5(а), 2.6(а)

2.1. а) Перечислить вершины булева куба B4 , соседние с вершиной

0,1, 0, 0 .

б) Определить число вершин булева куба Bn , соседних с данной вершиной.

2.4. Найти номер булева вектора:

а) (1, 0, 0,1,1) ; б) (1,1, 0, 0,1, 0) ;

2.5.а) Перечислить векторы значений булевых функций двух переменных, принимающих на противоположных наборах значений переменных одинаковые значения?

2.6.а) Перечислить векторы значений булевых функций двух переменных, принимающих на наборах веса 1 значение 0.

11

2.4.а) 19; б) 50; в) 31; г) 77.

2.5.а) (0000) , (0110) , (1001) , (1111) ; б) 22n 1 .

2.6.а) (0000) , (0001) , (1000) , (1001) ;

б) 22n Cnk . Указание к б). Вес k имеют Cnk булевых векторов от n переменных. Следовательно, Cnk определенных координат функции равны 1, а остальные 2n Cnk координаты могут принимать любые значения (0 или 1).

2.10. а) (1111) ; б) (0100 0111) ; в) (11111101) ; г) (1110 1110 1110 0001) .

2.8. а) x1 - существенная, x2 - фиктивная; б) x1 - фиктивная; x2 , x3 - существенные;

в) x3 - фиктивная; x1 , x2 - существенные; г) x1 , x3 - фиктивные; x2 , x4 - существенные.

2.9.а) (1110 1010) ; б) (10) ; в) (1001) ; г) (01) .

12

Домашняя работа № 4

Булевы функции и способы их задания. Задание булевой функции таблицей истинности и вектором значений. Задание булевых функций формулами.

Обязательные задачи

2.10. Задать вектором значений функцию, реализуемую формулой:

2.15. Применяя таблицы истинности, доказать равносильность формул:

2.16. Применяя таблицы истинности, доказать равносильность формул:

2.17. Применяя таблицы истинности, доказать равносильность формул:

а) x y y x x y ; б) x y y x .

2.8. Указать существенные и фиктивные переменные функции:

2.9. Задать вектором значений функцию, равную данной и существенно зависящую от всех своих аргументов:

Банк дополнительных задач и задач на дом

Л.2. 2.1(в*), 2.2.(в*)2.11*, 2.12 (а*)

2.1 в*) Определить число неупорядоченных пар соседних вершин булева куба Bn . 2.2. в) Найти число неупорядоченных пар вершин булева куба Bn , удаленных друг от друга на расстояние k ( 0 k n ).

2.5.б) Найти число булевых функций от n переменных, принимающих на противоположных наборах значений переменных одинаковые значения.

2.6.б) Найти число булевых функций от n переменных, принимающих на

2.11. в), г) является; а), б), д), е) не является.

2.12. а) (10011111) ; б) (0010 0000 0010 0010) .

14