Список задач повышенной сложности

Список задач разбит на 4 блока. Темы блоков указаны в соответствии с рабочей программой курса «Дискретной математики» (курс повышенного уровня). В квадратных скобках справа от номера задачи проставлены максимальные баллы, которые можно получить за ее выполнение.

Блок 1. Множества и бинарные отношения

1.[3] При голосовании в городскую думу в бюллетене в списке из трех кандидатов требовалось оставить не более одного. При подведении итогов оказалось, что кандидатов и вычеркнули 60% избирателей, кандидатов и - 80% избирателей, а кандидатов и - 70% избирателей. Какой процент избирателей проголосовал против всех кандидатов и какой кандидат набрал наибольшее число голосов?

2.[3] Сколько бинарных отношений можно определить на множестве из элементов?

3.[3] На множестве задано бинарное отношение . Какими свойствами это бинарное отношение обладает? Является ли оно отношением эквивалентности? порядка? В том случае, если - отношение эквивалентности, указать разбиение множества на классы эквивалентности.

4.[3] Рассмотрим на множестве действительныхчисел бинарные отношения , определенные условиями:

, , , .

Выяснить, какими свойствами обладают перечисленные бинарные отношения.

5.[3] Приведите пример рефлексивного, транзитивного, но не симметричного бинарного отношения на множестве из 4-х элементов.

6.[3] Приведите пример рефлексивного, симметричного, но не транзитивного бинарного отношения на множестве из 4-х элементов.

7.[3] Приведите пример транзитивного, симметричного, но не рефлексивного бинарного отношения на множестве из 4-х элементов.

8.[3] Пусть - конечное множество. Сопоставим каждому бинарному отношению на матрицу размера , называемую матрицей отношения, в которой на пересечении -й строки и -го столбца стоит 1. если и 0 в противном случае.

Что представляет собой матрица отношений в случае, если :

а) рефлексивно; б) симметрично; г) антисимметрично.

9.[4] Пусть - конечное множество. Определим на булеане бинарное отношение : (здесь , ). Является ли отношение отношением эквивалентности? Отношением частичного (линейного) порядка?

10.[4] Доказать, что если бинарное отношение одновременно симметрично и антисимметрично, то оно транзитивно.

11.[4] а) Сколько существует рефлексивных бинарных соотношений на множестве из элементов?

б) Сколько существует симметричных бинарных соотношений на множестве из элементов?

в) Сколько существует антисимметричных бинарных соотношений на множестве из элементов?

Блок 2. Элементы комбинаторики

1.[3] Сколько имеется четных четырехзначных чисел, в десятичной записи которых все числа различны?

2.[3] Сколько имеется четырехзначных чисел, в десятичной записи которых встречается цифра 5?

3.[3] Сколько различных каруселей можно сделать, расположив по окружности фигурки десяти зверей (карусели считаются одинаковыми, если фигурки идут друг за другом в одинаковом порядке)?

4.[3] а)Сколько разных шестибуквенных слов можно получить, переставляя буквы в слове «физика»?

б)Сколько разных восьмибуквенных слов можно получить, переставляя буквы в слове «черчение»?

5.[3] Сколькими способами можно разложить по восьми занумерованным коробкам три синих и пять красных шаров так, чтобы в каждой коробке оказалось ровно по одному шару?

6.[4] Докажите, что число упорядоченных разбиений -элементного множества на подмножеств, первое из которых содержит элемент, второе - элемента, …, -ое - элементов, равно .

7.[3] а) Сколько имеется пятизначных чисел, в десятичной записи которых цифры расположены в порядке убывания?

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

8.[3]. В студенческой группе учатся 9 девушек и 11 юношей. Сколькими способами можно сформировать команду из 7 человек для участия в спортивном состязании, если в нее должно войти не менее трех юношей?

9.[3] а) В классе учатся 18 человек. Сколькими способами можно составить график дежурств по классу на шесть дней так, чтобы каждый день дежурили по три человека, причем никто не дежурил дважды?

б) В классе учатся 18 человек. Сколькими способами можно разбить его учеников на 6 групп?

10.[3] а) Сколькими способами можно разложить 8 одинаковых шаров по трем занумерованным коробкам так, чтобы ни одна из коробок не осталась пустой?

б) Сколькими способами можно разложить 8 одинаковых шаров по трем занумерованным коробкам?

11.[4] а) Сколькими способами можно представить число в виде упорядоченной суммы положительных целых чисел?

б) Сколькими способами можно представить число в виде упорядоченной суммы неотрицательных целых чисел?

12.[6] Вывести формулу для числа сочетаний с повторениями из элементов по .

13.[4] Используя бином Ньютона, доказать тождества:

а) ;

б) ;

в) ( - четно);

г) ( - четно);

д) ( - нечетно);

е) ( - нечетно).

14.[6] Найти такое число , при котором число сочетаний из элементов по наибольшее, при условии, что:

а) - четное натуральное число; б) - нечетное натуральное число.

Блок 3. Булевы функции и способы их задания. Совершенные дизъюнктивные и конъюнктивные нормальные формы. Минимизация дизъюнктивных нормальных форм

Назовем весом булева вектора число его координат, равных 1.

1.[3] Сколько булевых векторов длины n имеет вес k?

Булевы вектора часто называют вершинами булева куба. Расстоянием (Хэмминга) между вершинами и куба называют число , равное числу координат, в которых они различаются, т.е. . Вершины (векторы) и называют соседними, если , и противоположными, если .

Например, расстояние между векторами и равно 2. Расстояние между векторами и равно 1 и, значит, они соседние. Расстояние между векторами и равно длине этих векторов, и, следовательно, они противоположные.

2.[6] Найти число неупорядоченных пар вершин булева куба , удаленных друг от друга на расстояние k ().

3.[4] Показать, что для любых противоположных наборов и выполняется равенство .

4.[6] Подсчитать число функций от переменных, у которых:

а) все переменные существенные;

б) одна переменная фиктивная, остальные существенные;

в) () переменных фиктивных, остальные - существенные.

5.[3] Пусть - подмножество булевых функций, причем , , , причем ни одна из функций не является тождественной константой, - алфавит переменных. Определить, является ли выражение формулой над множеством независимо от вида функций :

а) ; б) ;

в) ; г) ;

е) ; ж) .

6.[3] По функциям и , заданным векторами значений, построить векторы значений функции :

а) , , ;

б) , , .

7.[6]. Указать существенные и фиктивные переменные функции

().

8.[4] Выяснить, на скольких векторах булева куба обращается в ноль функция:

а) ; б) .

9.[4] Пусть задана вектором значений . Показать, что задается вектором .

10.[4] Показать, что если функция существенно зависит от переменной (), то двойственная ей функция также существенно зависит от переменной .

11.[4] Подсчитать число дизъюнктных слагаемых, образующих СДНФ функции .

12.[4] Пусть множества и не пересекаются и пусть СДНФ функций и имеют соответственно и дизъюнктных слагаемых. Найти число дизъюнктных слагаемых в СДНФ функций:

а) ; б) ;

в) .

13.[3] Найти число элементарных конъюнкций ранга r над множеством , обращающихся в единицу на наборе .

14.[4] Найти число всех элементарных конъюнкций над множеством , обращающихся в единицу на наборе .

15.[4] Подсчитать число функций от n переменных, для которых данная элементарная конъюнкция ранга r является импликантой.

16.[6] Пусть множества и не пересекаются, - простая импликанта функции , а - простая импликанта функции . Показать, что - простая импликанта функции .

17.[4] Назовем число элементарных конъюнкций, образующих ДНФ, ее длиной. Найти длину сокращенной ДНФ функции .

18.[6] Показать, что является существенной переменной тогда и только тогда, когда эта переменная явно входит в сокращенную ДНФ функции.

Блок 4. Классы Поста и замыкание. Полнота системы булевых функций

1.[3] Сколько функций содержит множество:

а) ; б) ; в)

г) ; д) ; е) ?

2.[3] Доказать, что ни один из классов Поста не содержится в другом.

3.[3] Пусть - произвольная булева функция, получена из путем отождествления всех переменных: . Определить , если: а) ; б) .

4.[3] Показать, что если , то либо немонотонная, либо несамодвойственная.

5.[4] Доказать, что функция, двойственная монотонной функции, монотонна.

6. [3] Доказать, что функция, двойственная линейной функции, линейна.

7.[4] Доказать, что пересечение замкнутых классов – замкнутый класс.

8.[6] Является ли объединение замкнутых классов замкнутым классом?

9.[4] Доказать, что совокупность функций, двойственных функциям из функционально замкнутого класса, образует функционально замкнутый класс.

10.[4] Назовем булеву функцию монотонно невозрастающей, если для любых наборов и значений переменных, таких что , выполняется неравенство . Привести пример булевой функции, заданной формулой над множеством монотонно невозрастающих функций, которая не является монотонно невозрастающей.

Замечание. Задача 10объясняет, почему в теории булевых функций не рассматривают монотонно невозрастающие функции. Дело в том, что интерес представляют свойства функций, которые «наследуются» при задании функций формулами, т.е. такие свойства, которые выделяют обладающие ими функции в замкнутый класс. Множество монотонно невозрастающих функций замкнутым не является.

11.[6] Дана произвольная несамодвойственная функция. Отождествить у нее некоторые переменные так, чтобы получилась несамодвойственная функция от возможно меньшего числа переменных.

12.[6] Дана произвольная немонотонная функция. Отождествить у нее некоторые переменные так, чтобы получилась немонотонная функция от возможно меньшего числа переменных.

13.[6] Доказать, что для монотонных функций справедливо разложение .

14.[6] Показать, что является существенной переменной тогда и только тогда, когда явно входит в полином Жегалкина функции.

15.[6] Найти число линейных функций от n переменных, существенно зависящих ровно от k переменных.

16.[4] Используя теорему о полноте двух систем, доказать, что

а) полная система; б) .

17.[4] Опираясь на доказательство леммы о функции, не сохраняющей 0, реализовать формулой над множеством либо 1, либо отрицание.

18.[4] Опираясь на доказательство леммы о функции, не сохраняющей 1, реализовать формулой над множеством либо 0, либо отрицание.

19.[4] Опираясь на доказательство леммы о несамодвойственной функции, реализовать формулой над множеством константы 0 и 1.

20.[4] Опираясь на доказательство леммы о немонотонной функции, реализовать формулой над множеством отрицание.

21.[4] Опираясь на доказательство леммы о нелинейной функции, реализовать формулой над множеством конъюнкцию.

22.[4] Доказать, что из любой полной системы можно выделить полную подсистему, содержащую не более пяти функций.

23.[4] Доказать, что всякий замкнутый класс функций, не совпадающий с , содержится, по крайней мере, в одном из классов Поста.

24.[6] Назовем систему булевых функций предполным классом, если эта система неполна и добавление к ней любой функции, ей не принадлежащей, приводит к образованию полной системы. Доказать, что:

а) классы Поста являются предполными;

б) других предполных классов, кроме классов Поста, нет.

25.[6] Доказать, что во всяком базисе содержится не более 4-х функций.