ВАРИАНТ 6

Задача 1. Даны множества чисел: , , и универсальное множество .

Найти множества чисел , . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( или )? пересекающимися, но не включающими одно в другое? непересекающимися ()?

Решение.

1)Найдем множество :

- элементы принадлежат множеству , но не принадлежат множеству .

- элементы принадлежат  обоим множествам и .

- элементы принадлежат хотя бы одному из множеств или

- элементы универсального множества, которые не принадлежат .

- элементы принадлежат хотя бы одному из множеств или .

2) Найдем множество

- элементы принадлежат  обоим множествам и .

элементы принадлежат  обоим множествам и .

- элементы универсального множества, которые не принадлежат .

- элементы принадлежат множеству , но не принадлежат множеству .

- элементы принадлежат хотя бы одному из множеств или .

3) Множество включает множество ( - подмножество , поскольку каждые его элемент входит в )

Ответ: , ,

Задача 2. Из группы в 15 человек должны быть выделены бригадир и 4 члена бригады. Сколькими способами это можно сделать?

Решить задачу, используя комбинаторику.

Решение.

Сначала выбираем бригадира. Это можно сделать 15 способами, поскольку всего 15 человек. Затем из оставшихся 14 выбираем 4 человека. Так как порядок, в котором они будут выбраны,  не имеет значения, то количество способов этого выбора равно количеству сочетаний из 14 по 4 . Далее применяем правило произведения и получаем .

НЕ нашли? Не то? Что вы ищете?

Ответ: 15015 способами.

Задача 3. Установить вид формулы алгебры логики:

.

Решение.

Для определения вида формулы составим таблицу истинности и выясним, является ли она тавтологией, отрицанием или выполнимой.

0

0

0

0

1

1

1

0

0

0

0

1

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0

0

1

1

0

0

0

1

0

1

1

0

0

0

1

1

1

1

1

1

0

1

0

0

0

0

0

1

1

1

0

1

0

1

1

1

1

1

1

1

1

1

0

1

1

1

Поскольку формула тождественно не равна ни 1, ни 0, то она является выполнимой.

Ответ: выполнимая.

Задача 4. С помощью таблицы истинности найти СДНФ и СКНФ булевой функции .

Решение.

Для того, что бы найти СДНФ и СКНФ, построим таблицу истинности данной функции :

0

0

0

1

1

1

0

1

1

0

1

1

1

0

1

1

1

1

1

1

1

0

0

0

1)Для нахождения СДНФ нужно из таблицы истинности выделить лишь те строки, результат которых равен 1. Для данной функции набор строк будет следующим:

0

0

0

1

1

1

0

1

1

0

1

1

1

0

1

1

1

1

Далее, для каждой строки выписываем конъюнкцию всех переменных по следующему алгоритму: если значение переменной в данной строке равно 1, то в конъюнкцию записываем саму переменную, а если равно 0, то - отрицание этой переменной. После этого все конъюнкции связываем в дизъюнкцию.

В результате, совершенная дизъюнктивно-нормальная форма (СДНФ) нашей функции равна: .

2)Для нахождения СКНФ нужно из таблицы истинности выделить лишь те строки, результат которых равен 0. Для данной функции набор строк будет следующим:

1

1

1

0

0

0

Далее, для каждой строки выписываем дизъюнкцию всех переменных по следующему алгоритму: если значение переменной в данной строке равно 0, то в дизъюнкцию записываем саму переменную, а если равно 1, то - отрицание этой переменной. После этого все дизъюнкции связываем в конъюнкцию.

В результате, совершенная конъюнктивно-нормальная форма (СКНФ) нашей функции равна: .

Ответ: ,

Задача 5. Дана матрица:

Построить ориентированный граф, для которого матрица B является матрицей инцидентности. Найти матрицу смежности.

Решение.

Построим ориентированный граф, воспользовавшись тем, что элементы матрицы заданы следующим условием:

, если вершина - является начало дуги ,

, если - является концом дуги ,

- в остальных случаях.

Тогда получаем

Матрица смежности определяется условием: это квадратная матрица, столбцам и строкам которой соответствуют вершины графа, элемент равен 1, если есть ребро графа, 0, если такого ребра (дуги) нет. Тогда

.

Ответ: .

Задача 6. Определить функцию , полученную из функций и по схеме примитивной рекурсии.

Решение.

Воспользуемся способом рекурсивного определения данной функции: ;

;

;

;

;

;

Можно предположить, что .

Докажем последнюю формулу методом математической индукции по переменной .

При , . Рассмотрим параметр на множестве натуральных чисел, начиная с 1.

При - выполняется. Допустим, что предположение верно при , то есть верна формула .

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

.

Таким образом, на основании метода математической индукции формула доказана для всех .

Ответ: .