Задача 16

Все перестановки 7 чисел 1, 2, 3, 4, 5, 6, 7 упорядочены в лексикографическом порядке. Найти перестановку с номером N = 3089.

Решение

Число предшествующих перестановок равно

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

Алгоритм восстановления перестановки покажем, заполняя по шагам строки таблицы из трех столбцов.

Заполняем 1 строку.

В первый столбец запишем факториальное число, а во второй столбец элементы перестановки в порядке убывания. Первую цифру числа подчеркиваем. Она показывает, что число элементов перестановки меньше первого и расположенных в перестановке правее равно 4. Отсчитываем во втором столбце справа 4 элемента и выбираем элемент 5, который подчеркиваем и записываем в третий столбец

4132200

7654321

5

Заполняем теперь 2 строку. Первую строку повторяем без изменения.

В первый столбец записываем факториальное число, а во второй столбец последовательность элементов предыдущей строки этого столбца без элемента, записанного в третий столбец.

Выбираем (подчеркиваем) теперь вторую цифру факториального числа. Это цифра 1. Отсчитываем во втором столбце справа 1 элемент и выбираем предшествующий, это 2. Записываем его в 3 столбец

4132200	7654321	5
4132200	764321	2

По аналогии заполняем 3 строку

4132200	7654321	5
4132200	764321	2
4132200	76431	6

И так далее.

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

4132200	7654321	5
4132200	764321	2
4132200	76431	6
4132200	7431	4
4132200	731	7
4132200	31	1
4132200	3	3

Читая сверху вниз третий столбец, получаем искомую перестановку.

Ответ: 5264713.

Булевы функции

В следующих задачах будет использоваться функция

Напомним таблицу истинности функции , при этом кружок для простоты будем опускать

Задача 17

Построить таблицу истинности; ответ записать в виде набора значений, упорядоченного в соответствии с лексикографическим порядком наборов аргументов.

Решение

Для простоты знак сложения по модулю 2 будем писать как +.

Поэтому

.

Составляем таблицу истинности исходной функции, последовательно вычисляя значения скобок в записи функции

Ответ:

Задача 18

Построить СДНФ функции; ответ записать, упорядочив конъюнкции в лексикографическом порядке.

Решение

Выписываем сверху вниз конъюнкции для строк с . Если значение переменной в булевом наборе равно 0, пишем ее отрицание.

Задача 19

Упростить полученное выражение с помощью метода алгебраических преобразований и с помощью метода минимизирующих карт, ответ записать в виде минимальной ДНФ.

Решение

Метод алгебраических преобразований

Метод минимизирующих карт

Ответ:

Задача 20

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

Решение

1 способ

Вычисляем значения новых аргументов и подставляем в таблицу истинности исходной функции

Видим, что столбец функции совпадает со столбцом переменной .

2 способ

Ответ:

Задача 21

Построить многочлен Жегалкина исходной функции двумя способами, один из которых - метод неопределенных коэффициентов.

Решение

1 способ – с помощью алгебраических преобразований

Используем равносильности:

Записываем СДНФ и преобразуем ее, пользуясь тем, что любые две конъюнкции логически несовместны:

2 способ

Задача 22

Построить таблицу двойственной функции; ответ записать в виде упорядоченного набора значений.

Решение

Используем соотношение для вычисления значений двойственной функции.

Столбец значений двойственной функции получается переворотом и инвертированием столбца значений исходной функции:

Ответ: (0,1,0,0,0,0,1,1)

Задача 23

Построить СКНФ двойственной функции; ответ записать, упорядочив элементарные дизъюнкции в лексикографическом порядке.

Решение

Берем СДНФ исходной функции и заменяем в ней конъюнкции на дизъюнкции и наоборот:

Второй способ предполагает построение таблицы истинности и выписывание дизъюнкций для строк с . Если значение переменной в булевом наборе равно 1, пишем ее отрицание, в противном случае – саму переменную.