Решение практических заданий по дискретной математике (стр. 2 из 4)
Так как функция полностью определена и соответствие сюръективно, то имеем отображение N1 на N2 .
Так как для любых двух различных элементов из N1 их образы из N2 также различны, то отображение является инъективным.
Так как отображение является одновременно сюръективным и инъективным, то имеем биективное отображение (взаимно однозначное отображение).
Задание 3
Частично упорядоченное множество М задано множеством упорядоченных пар
.Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной.
Решение:
Построим диаграмму:
Построим таблицу:
| Парыэлементов | Н.Г. | В.Г. | Н.Н.Г. | Н.В.Г. |
| 1,2 | 1 | 2,5 | 1 | 2 |
| 1,3 | 1 | 3,4,5 | 1 | 3 |
| 1,4 | 1 | 4,5 | 1 | 4 |
| 1,5 | 1 | 5 | 1 | 5 |
| 1,6 | 1 | 6,2,5 | 1 | 6 |
| 2,3 | 1 | 5 | 1 | 5 |
| 2,4 | 1 | 5 | 1 | 5 |
| 2,5 | 2,6,1 | 5 | 2 | 5 |
| 2,6 | 6,1 | 2,5 | 6 | 2 |
| 3,4 | 3,1 | 4,5 | 3 | 4 |
| 3,5 | 3,1 | 5 | 3 | 5 |
| 3,6 | 1 | 5 | 1 | 5 |
| 4,5 | 4,3,1 | 5 | 4 | 5 |
| 4,6 | 1 | 5 | 1 | 5 |
| 5,6 | 6,1 | 5 | 6 | 5 |
Так как любая пара элементов имеет единственную наибольшую нижнюю грань и единственную наименьшую верхнюю грань, то заданное частично упорядоченное множество М является решеткой.
Решетка М является дедекиндовой, когда выполняется равенство:
для таких
, что 
.Решетка М не является дедекиндовой, т.к. указанное равенство не вы-полняется, например, для элементов 2, 3, 4:
Одним из условий дистрибутивности решетки является ее дедекиндо-вость. Так как решетка М не является дедекиндовой, то она не является дистрибутивной решеткой.
Задание 4
Является ли полной система булевых функций
? Если система функций полная ,то выписать все возможные базисы.Решение:
Рассмотрим функцию
.1. Принадлежность функции к классу
: 
.Следовательно,
.2. Принадлежность функции к классу
: 
.Следовательно,
.3. Принадлежность функции к классу
.Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:
.Найдем коэффициенты
.Фиксируем набор 000:
,
, 
Следовательно,
.Фиксируем набор 100:
, 
, 
Следовательно,
.Фиксируем набор 010:
, 
, 
.Следовательно,
.Фиксируем набор 001:
, 
, 
, 
.Следовательно, функция (по нашему предположению) может быть представлена полиномом вида:
.Если функция линейная, то на всех остальных наборах ее значение должно равняться 1. Но на наборе 111
. Значит, функция не является линейной, т.е. 
.4. Принадлежность функции к классу
.Функция самодвойственная, если на любой паре противоположных наборов (наборов, сумма десятичных эквивалентов которых равна
, где п – количество переменных функции) функция принимает противоположные значения.Вычисляем
. Вычисляем значения функции на оставшихся наборах: 
Строим таблицу:
| (000)0 | (001)1 | (010)2 | (011)3 | (100)4 | (101)5 | (110)6 | (111)7 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
На наборах 1 и 6, 2 и 5, 3 и 4 функция принимает одинаковые значения. Следовательно,
.5. Принадлежность функции к классу
.Из таблицы видно: 000 < 111 , но
. Следовательно, 
.Рассмотрим функцию
.1. Принадлежность функции к классу
: 
.Следовательно,
.2. Принадлежность функции к классу
: 
.Следовательно,
.3. Принадлежность функции к классу
.Предполагаем, что
.Фиксируем набор 000:
, 
.Фиксируем набор 100:
, 
.Фиксируем набор 010:
, 
.Фиксируем набор 001:
, 
.Окончательно получаем
.Это равенство не соблюдается на наборе 011:
, 
.Следовательно,
.4. Принадлежность функции к классу
.Вычислим значения функции на оставшихся наборах: