Контрольная работа по "Дискретной математике"

Дискретная математика. 8 задач. ...

Условие.
1) Равносильны ли формулы F и G?
2) Является ли формула G логическим следствием формул F1,...,Fk? Привести высказывания, соответствующие формулам.
3) Привести к СДНФ.
4) Является ли полным класс K булевых функций?
5) Привести формулу к ПНФ и СНФ.
6) Нарисовать диаграмму автомата. Найти язык, допускаемый автоматом.
7) Найти приведенный автомат (таблицу переходов), эквивалентный данному.
8) Изобразить диаграмму переходов недетерминированного автомата, допускающего язык L. Найти эквивалентный приведенный детерминированный автомат.

Условие.
1) Равносильны ли формулы F и G?
2) Является ли формула G логическим следствием формул F1,...,Fk? Привести высказывания, соответствующие формулам.
3) Привести к СДНФ.
4) Является ли полным класс K булевых функций?
5) Привести формулу к ПНФ и СНФ.
6) Нарисовать диаграмму автомата. Найти язык, допускаемый автоматом.
7) Найти приведенный автомат (таблицу переходов), эквивалентный данному.
8) Изобразить диаграмму переходов недетерминированного автомата, допускающего язык L. Найти эквивалентный приведенный детерминированный автомат.

Привести к СДНФ.
Решение:
Составим таблицу истинности.
X
Y
Z
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
По составленной таблице истинности выбираем строки, в которых F=1 и выписываем элементы конъюнкции.
Для получения СДНФ необходимо соединить полученные конъюнкции знаком дизъюнкции.
СДНФ=
Задание 4.
Является ли полным класс K булевых функций?
Решение:
Используем критерий полноты (теорему Поста). Проверим, содержится ли K как подмножество в каком-нибудь из основных замкнутых классов. Результаты проверки соберем в таблицу
T0
T1
S
M
+
-
-
+
+
-
-
-
Для проверки, принадлежит ли функция классу T0 , найдем значение функции от нулевых аргументов.
Функция : , т.е. функция сохраняет 0.
Функция : , т.е. функция сохраняет 0.
Для проверки, принадлежит ли функция классу T1 , найдем значение функции от единичных аргументов.
Функция : , т.е. функция не сохраняет 1.
Когда найдена хотя бы одна функция, не принадлежащая классу, остальные функции можно не проверять.
Для проверки, принадлежит ли функция классу S , проверим равенство .
Для функции : .
Составим таблицу значений для левой и правой частей равенства.
x
y
1
1
1
1
1
1
1
1
Значения не совпадают, следовательно, равенство не выполняется, то есть функция не принадлежит классу S.
Для проверки, принадлежит ли функция классу M, нарисуем диаграмму частично упорядоченного множества векторов из 0 и 1.
Для функции это будут векторы из двух координат:
По рисунку видим, что нет значений 0 выше чем 1. Следовательно, функция принадлежит классу M.
Для проверки, принадлежит ли функция классу M, нарисуем диаграмму частично упорядоченного множества векторов из 0 и 1.
По рисунку находим два вектора (1,1,0)>(1,0,0), в которых значении 0 выше чем 1. Следовательно, функция не принадлежит классу M.
Так как, не во всех столбцах есть -, класс не является полным.
Задание 5.
Привести формулу к ПНФ и СНФ.
.
Решение:
Применяем алгоритм приведения к ПНФ, используя законы логики предикатов.
Применяем алгоритм приведения к СНФ, используя правило отбрасывания кванторов существования.
Задание 6.
Нарисовать диаграмму автомата. Найти язык, допускаемый автоматом.
a
b
1
2
4
2
3
4
1
3
4
2
4
4
4
Решение:
Построим диаграмму:
По рисунку ищем все возможные пути из начального состояния 1 в заключительное состояние 2.
Ответ: .
Задание 7.
Найти приведенный автомат (таблицу переходов), эквивалентный данному.
a
b
1
8
9
2