Задачи и упражнения. 1. Определите количество всех функций алгебры логики от одной переменной; от двух, трех, четырех, пяти переменных

1. Определите количество всех функций алгебры логики от одной переменной; от двух, трех, четырех, пяти переменных.

2. Изобразите графически следующие функции:
а) f(x,y) = (1,1,0,0);
б) f(x,y) = (1,0,1,0);
в) f(x,y,z) = (0,1,0,1,1,1,0,0).

3. Укажите название следующих функций:
а) f(x,y) = (0,1,1,0); б) f(x,y) = (1,0,0,1);
в) f(x,y) = (1,0,0,0); г) f(x,y) = (1,1,1,0)

4. Удалите несущественную переменную и назовите полученную элементарную функцию:
а) f(x,y,z) = (0,1,0,1,0,1,0,1);
б) f(x,y,z) = (1,1,0,0,1,1,0,0);
в) f(x,y,z) = (0,1,0,1,1,1,1,1);
г) f(x,y,z) = (0,0,0,1,0,0,0,1);
д) f(x,y,z) = (1,1,1,1,0,1,0,1);
е) f(x,y,z) = (0,0,1,1,1,1,0,0).

5. Путем ввода несущественной переменной z получите эквивалентную функцию f(x,y,z) для следующих ФАЛ:
а) f(x,y) = (0,0,1,0);
б) f(x,y) = (1,0,1,1);
в) f(x,y) = (0,1,0,0).
Затем переименуйте переменные x и y в y и z соответственно и выполните ввод несущественной переменной х для тех же функций. Выполните также переименование у в z и введите несущественную переменную у.

6. Постройте полную и сокращенную таблицы истинности для следующих формул:
а) ;
б) ;
в) ;
г) .

7. Определите с помощью таблиц истинности, являются ли следующие логические формулы тавтологией, противоречием или ни тем, и ни другим.

а) ;
б) ;
в) ;
г) ;
д) ;
е) ;
ж) ;
з) ;
и) ;
к) ;
л) ;
м) .

8. Докажите, что если (x & y) – тавтология, то тавтологиями являются x и y, и что если x – тавтология, то и – тоже тавтологии.

9. Определите с помощью таблиц истинности, какая элементарная функция реализуется следующей формулой:
а) ;
б) ;
в) ;
г)

10. Докажите с помощью таблиц истинности, что следующие пары формул эквивалентны:

а) и ;
б) и ;
в) и ;
г) и ;
д) и ;
е) и ;
ж) и ;
з) и ;

11. Исключите возможно большее число скобок в формулах:
а) ;
б) ;
в) ;
г) .

12. Восстановите скобки в формулах в соответствии с приоритетом логических операций:
а) ;
б) ;
в) .

13. Используя свойства элементарных функций, упростите формулы:
а) ;
б) ;
в) ;
г) ;
д) .
е) ;
ж) ;
з) ;
и)

14. Докажите или опровергните тождественную истинность следующих формул путем эквивалентных преобразований:
а) ;
б) ((x ≡ y) ˙·(x | y)) ≡ x & y;
в) (x → y) ≡ ;
г) (x → z) ≡ ((x Ú (y & z)) →((x Ú y) & z))

15. Проверьте с помощью эквивалентных преобразований, будут ли эквивалентны следующие формулы:
а) x → (y ↓ z) и (x → y) ↓ (x → z);
б) x → (y ≡ z) и (x → y) ≡ (x → z);
в) ;
г) .

16. Электрическая цепь, содержащая только двухпозиционные переключатели, изображена с помощью диаграммы на рис. 9, где возле каждого переключателя пишется буква, истинностное значение которой соответствует прохождению тока через этот переключатель. Условие прохождения тока через контур можно выразить логической формулой . Две цепи назовем эквивалентными, если через одну из них ток идет тогда и только тогда, когда он идет через другую; из двух цепей та считается более простой, которая содержит меньшее число переключателей.
а) Нарисуйте электрическую цепь, представленную формулой , затем упростите формулу и нарисуйте соответствующую упрощенную цепь;
б) для цепи, изображенной на рис. 10, постройте эквивалентную, более простую цепь, и запишите соответствую

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

17. Найдите функцию, двойственную заданной:
а) f(x,y,z) = (1,1,1,1,0,0,1,1);
б) f(x,y,z) = (1,0,0,0,1,0,0,0);
в) f(x,y,z) = (0,1,0,1,1,0,1,0);
г) f(x,y,z) = (1,1,1,0,1,0,0,0).

18. Используя принцип двойственности, запишите формулы, двойственные заданным, затем расставьте в полученных формулах скобки, указывающие порядок выполнения действий, и упростите полученные формулы путем эквивалентных преобразований:
а) ;
б) ;
в) ;
г) .

19. Пусть U – формула, содержащая только связки (ù, &, Ú), а U^* – двойственная ей формула. Докажите:
а) U – тавтология тогда и только тогда, когда – тавтология;
б) если – тавтология, то тоже тавтология;
в) формула логически эквивалентна формуле ;
г) если U ≡ W – тавтология, то тавтологией является и U^* ≡ W^*.

20. С помощью принципа двойственности выведите новые тождества:
а) ;
б) ;
в) ;
г) ;
д) ;
е) ;
ж) ;
з) .

21. Используя свойство из задачи 19(в), запишите формулу, эквивалентную заданной:
а) ;
б) ;
в) ;
г) ;
д) ;
е) .

22. С каждой из приведенных ниже формул выполните следующие действия:
– упростите исходную формулу;
– запишите двойственную и упростите её;
– запишите эквивалентную формулу и упростите её:
а) ;
б) ;
в) .

23. Для заданной функции запишите СДНФ и СКНФ.
а) f (x, y, z) = (1, 0, 0, 0, 0, 0, 1, 1)
б) f (x, y, z) = (0, 1, 1, 0, 0, 1, 1, 0);
в) f (x, y, z) = (1, 1, 0, 1, 1, 0, 0, 0);
г) f (x, y, z) = (0, 1, 0, 1, 0, 0, 1, 1).

24. Пусть каждый из трех членов комитета голосует «за», нажимая на кнопку. Постройте по возможности более простую электрическую цепь, через которую ток проходил бы тогда и только тогда, когда не менее двух членов комитета голосуют «за». Указание: составьте таблицу истинности для соответствующей функции, запишите её в виде СДНФ, упростите полученную формулу и изобразите эквивалентную последней формуле электрическую цепь с двухпозиционными переключателями.

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

26. Механизм приводится в движение тремя рычагами и действует лишь тогда, когда ровно два из них находятся в одинаковом состоянии. Запишите зависимость состояния механизма от состояний рычагов в виде логической формулы и упростите её.

27. «Сложение n – разрядных двоичных чисел».
Даны два n – разрядных двоичных числа x = (x_n x_{n -1}... x ₁) и y = (y_n y_{n -1}... y ₁), где x_i, y_i равны 0 или 1 и i =1, 2,..., n. Складывая числа «столбиком», каждый разряд z_i суммы z = (z_{n +1} z_n z_{n ‑1}... z ₁) можно вычислить по формуле z_i = x_i + y_i + p_{i -1}, где p_i (i = 1, 2,..., n +1) обозначает результат переноса из i ‑го разряда в (i +1)‑ый разряд. При этом p ₀ =0 и x_{n +1} = y_{n +1} =0.
а) Выразите значения разрядов суммы z_i, i = 1, 2,..., n +1 через значения разрядов слагаемых x_i, y_i и переносы p_{i -1} в виде формулы со связками (ù,&,Ú);
б) Выразите переносы p_i, i = 1, 2,..., n через разряды слагаемых x_i, y_i и переносы p_{i -1} в виде формулы со связками (ù, &, Ú).
Указание: составьте таблицы истинности для функций z_i, p_i и затем запишите для каждой из них СДНФ или СКНФ.

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

а) ;
б) ;
в) ;
г) ;
д) ;
е) .

29. Докажите, что формула является тавтологией тогда и только тогда, когда соответствующая ей СДНФ состоит из 2 ⁿ дизъюнктивных членов, где n – число переменных символов.

30. Докажите, что формула является противоречием тогда и только тогда, когда соответствующая ей СКНФ состоит из 2 ⁿ конъюнктивных членов.

31. Запишите все булевы функции от двух переменных на языке формул, содержащих только связки из следующих систем: (ù, &), (ù, Ú), (ù, ®), (|) – штрих Шеффера и (¯) – стрелка Пирса.

32. Определите принадлежность функций к основным замкнутым классам:
а) f (x, y) = ;
б) f (x, y, z) = (x ® y) Ú;
в) f (x, y, z) = x Ú (z ® y);
г) f (x, y, z) = (x Ú y) ® y & z;
д) f (x, y, z) = (x ®) & z Ú (º z);
е) f (x, y, z) = (x ¯) ® (y Ú).

33. Используя доказательство леммы о несамодвойственной функции, подберите для каждой функции из задачи 32 такую замену переменных, с помощью которой можно получить константу 0 или 1.

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

35. Используя доказательство леммы о нелинейной функции, подберите для каждой функции из задачи 32 такую замену переменных, с помощью которой можно получить функцию &.

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

а) ;
б) ;
в) ;
г) ;
д) ;
е) ;
ж) ;
з) F = {}

37. Для функции f (x, y, z), заданной своими нулевыми наборами, постройте все МДНФ методом неопределенных коэффициентов:
а) f (0,1,1)= f (1,0,0)= f (1,1,1)=0;
б) f (0,0,0)= f (0,1,1)= f (1,1,1)=0;
в) f (0,0,1)= f (0,1,0)= f (1,0,1)=0;
г) f (0,0,0)= f (0,0,1)= f (1,1,0)=0.

38. Для функции f (x, y, z), заданной своими единичными наборами, постройте все ТДНФ методом «наискорейшего спуска»:
а) f (0,0,0)= f (0,1,1)= f (1,0,0)= f (1,1,1)=1;
б) f (0,1,0)= f (1,0,0)= f (1,1,0)= f (1,1,1)=1;
в) f (0,0,0)= f (1,0,0)= f (1,0,1)= f (1,1,0)=1;
г) f (0,0,0)= f (0,0,1)= f (0,1,0)= f (1,0,0)=1.

39. Постройте СокрДНФ путем аналитических преобразований «склеивания» и «поглощения» для f (x, y, z), заданной своими нулевыми наборами:
а) f (0,1,0)= f (1,0,0)= f (1,1,0)=0;
б) f (1,0,1)= f (1,1,0)= f (1,1,1)=0;
в) f (1,0,0)= f (1,1,0)= f (1,1,1)=0;
г) f (0,0,0)= f (1,0,0)=0.

40. Для функции f (x, y, z), заданной своими нулевыми наборами,
– нарисуйте геометрическое представление;
– выпишите все интервалы 3-го, 2-го и 1-го ранга;
– выпишите все покрытия для f (x, y, z) ранга 6 и изобразите их графически;
– составьте покрытие, соответствующее СокрДНФ и изобразите его графически;
– выпишите все неприводимые покрытия:
а) f (0,0,0)= f (1,0,0)= f (1,1,0)=0;
б) f (1,0,0)= f (1,0,1)= f (1,1,0)=0;
в) f (0,0,0)= f (0,1,0)= f (1,1,0)=0;
г) f (0,0,1)= f (1,0,0)= f (1,1,0)=0.

41. Для функции f (x, y, z), заданной своими единичными наборами, постройте ДНФ Куайна:
а) f (0,1,0)= f (1,0,0)= f (1,0,1)= f (1,1,0)=1;
б) f (0,1,1)= f (1,0,0)= f (1,0,1)= f (1,1,1)=1;
в) f (0,0,0)= f (0,1,0)= f (1,1,0)= f (1,1,1)=1;
г) f (0,0,0)= f (0,0,1)= f (0,1,1)= f (1,0,0)=1.

42. Для функции четырех переменных f (x, y, z, v), заданной своими нулевыми наборами, постройте карту Карно и, пользуясь полученной картой, запишите СокрДНФ и составьте все возможные МДНФ:
а) f (0,1,0,0)= f (0,1,1,0)= f (0,1,1,1)= f (1,0,0,1)= f (1,1,0,1)= f (1,1,1,1)=0;
б) f (0,0,0,1)= f (0,1,0,1)= f (0,1,1,0)= f (1,0,1,0)= f (1,0,1,1)= f (1,1,0,1)=0;
в) f (0,0,0,1)= f (0,0,1,1)= f (0,1,1,1)= f (1,0,0,0)= f (1,0,0,1)= f (1,0,1,0)=0;
г) f (0,0,1,1)= f (0,1,0,0)= f (0,1,0,1)= f (1,0,0,0)= f (1,0,1,1)= f (1,1,1,1)=0.

Список литературы

1. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики». М., МАИ, 1992.

2. Я.М. Ерусалимский «Дискретная математика». М., Вузовская книга, 2001.

3. С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики», Москва, ИНФРА-М, 2002.

4. О.П. Кузнецов, Г.М. Адельсон-Вельский «Дискретная математика для инженера». М., «Энергия», 1980.

5. Ф.А. Новиков «Дискретная математика для программистов». СПб: Питер, 2001.

6. Яблонский С.В. Введение в дискретную математику. Москва, Мир, 1989.

7. Мендельсон Э. Введение в математическую логику. Москва, Наука, 1976.

8. И.А. Лавров, Л.Л. Максимова. «Задачи по теории множеств, математической логике и теории алгоритмов». М., Физматлит, 2002.

9. Компьютеры. Справочное руководство в трех томах. Т.1. Москва, Мир, 1986.

10. Математическая энциклопедия в пяти томах под редакцией И.М. Виноградова. Москва, Советская энциклопедия, 1985.

Наталья Дмитриевна Бовда

Дискретная математика

Курс лекций

Часть II

Учебное пособие

Редактор Е. М. Марносова

Темплан 2006г., позиция №5

Лицензия ИД № 04790 от 18.05.2001

Подписано в печать Формат 60х84 1/16

Бумага газетная. Печать офсетная. Усл. печ. л. – 5,34

Уч.-изд.л. 5,5 Тираж 100 экз. Заказ

Волгоградский государственный технический университет

400131, Волгоград, просп. им. В.И.Ленина, 28

РПК «Политехник» Волгоградского государственного

технического университета

400131, Волгоград, ул. Советская, 35

Дата добавления: 2014-01-07