Подготовка к контрольной работе № 2

Контрольная работа № 2 состоит из 2-х частей: часть 1 включает 6 заданий, часть 2 – два задания. Правильное решение каждого задания части 1 оценивается 1 баллом. Правильное решение каждого задания части 2 оценивается ориентировочно 2 баллами. Максимальное количество баллов, которое можно получить за контрольную работу № 2, составляет 10 баллов. Начисленные баллы учитываются в рамках накопительной балльной системы.

КР № 2 рассчитана на 1 час 20 минут. Структура контрольной работы показана в табл. 4. Примерные варианты КР №2 приведены в таблице 5.

	Таблица 5
	Примерный вариант 1 (КР 2)
	Часть 1
	Составить таблицу истинности функции, заданной формулой .
	Применяя равносильные преобразования, доказать тождественную истинность формулы .
	Представить в виде СДНФ и СКНФ функцию
	Представить в виде полинома Жегалкина функцию
	Определить, каким из классов Поста принадлежит функция .
	Используя критерий полноты, выяснить, полна ли система функций .
	Часть 2
	Пусть множества и не пересекаются, - простая импликанта функции , а - простая импликанта функции . Показать, что - простая импликанта функции
	Доказать, что для монотонных функций справедливо разложение .
	Примерный вариант 2 (КР № 2)
	Часть 1
	Составить таблицу истинности функции, заданной формулой .
	Применяя равносильные преобразования, доказать тождественную истинность формулы .
	Представить в виде СДНФ и СКНФ функцию .
	Представить в виде полинома Жегалкина функцию .
	Определить, каким из классов Поста принадлежит функция .
	Используя критерий полноты, выяснить, полна ли система функций .
	Часть 2
	Показать, что если функция существенно зависит от переменной (), то двойственная к ней функция также существенно зависит от переменной .
	Является ли объединение замкнутых классов замкнутым классом? Ответ обосновать.

Задания 2-й части контрольной работы №2 формулируются на основе и с использованием банка задач, приведенного в учебном пособии Олейник Т.А. «Основы дискретной математики: теория и практика. М.:МИЭТ, 2010»: Л.1. § 2.1 - § 2.5, задачи повышенной сложности 2.1 – 2.43.

Для подготовки к выполнению части 2 контрольной работы № 2 рекомендуется прорешать задачи из этого списка.