Переключательные функции и нормальные формы

Задача 1. Запишите формулы для следующих суперпозиций:

1) ,

2) ,

3) ,

4) .

Составьте таблицы истинности и найдите наиболее простую булеву формулу.

Задача 2. Проверьте, будут ли равносильными следующие формулы.

1) и ,

2) и ,

3) и ,

4) и .

Задача 3. Упростите формулы, используя равносильные преобразования.

1) ,

2) ,

3) ,

4) .

Задача 4. Запишите булевы формулы для функций , , , , .

Задача 5. Запишите СДНФ и СКНФ для функций

, ,

, .

КОНТАКТНЫЕ СХЕМЫ. МИНИМИЗАЦИЯ

Задача 1. Упростите контактные схемы, используя равносильные преобразования.

1) 2)

 

3) 4)

 

 

Задача 2. Постройте СДНФ по карте Карно и упростите ее до ДНФ.

Задача 3. Минимизируйте ДНФ и КНФ по карте Карно.

1) 2)

3) 4)

Задача 4. Минимизируйте ДНФ и КНФ для неполностью определенных переключательных функций.

1) 2)

Задача 5. Запишите число и, добавив недостающие слева нули, получите векторное задание функции .

1). Постройте для этой функции а) таблицу, б) множество , в) карту Карно.

2). Найдите СДНФ, СКНФ, минимальные ДНФ и КНФ.

3). Постройте наиболее простую контактную схему, реализующую эту функцию.

Дополнительные задачи

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

2. Пусть каждый из членов комитета голосует «за» нажатием на кнопку. Постройте по возможности наиболее простую электрическую цепь, через которую ток проходил бы тогда и только тогда, когда не менее двух членов комитета голосуют «за».

12. ТИПЫ БУЛЕВЫХ ФУНКЦИЙ. ПОЛИНОМЫ ЖЕГАЛКИНА

Задача 1. Представьте следующие функции полиномами Жегалкина. Проверьте принадлежность их к классам , и

1) , 2) , 3) , 4) , 5) , 6) , 7) , 8) , 9) , 10) , 11) , 12) , 13) , 14) , 15) , 16) , 17) , 18) , 19) , 20) .

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

Задача 3. Определите, являются ли монотонными следующие функции

1) , 2) , 3) , 4) , 5) , 6) , 7) , 8) , 9) , 10) , 11) , 12) , 13) , 14) , 15) , 16) , 17) .

Задача 4. Найдите двойственные для следующих функций. Какие из них являются самодвойственными?

1) , 2) , 3) , 4) , 5) , 6) , 7) .

Задача 5. Докажите, что функция образует функционально полную систему.

Задача 6. Проверьте полноту системы функций. В случае полноты определите, является ли система базисом. Укажите базис.

1) , 2) , 3) , 4) .

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Баврин И.И. Дискретная математика. М.: Высш. шк., 2007. 200 с.

2. Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: МГТУ, 2004. 744 с.

3. Зарецкая М.А. Дискретная математика для программистов. Магнитогорск: МГТУ, 2009. 172 с.

4. Зарецкая М.А., Файнштейн А.С. Метод математической индукции и комбинаторика. Методическая разработка для студентов специальности 230105. Магнитогорск: МГТУ, 2008.

5. Краснов М.Л., Киселев А.И., Макаренко Г.И. и др. Вся высшая математика, т. 7. — М.: Эдиториал УРСС, 2004. 208 с.

6. Кузнецов О.П. Дискретная математика для инженера. СПб.: Лань, 2004. 370 с.

7. Шевелев Ю.П. Дискретная математика. СПб.: Лань, 2008. 592 с.