Контрольная работа по "Дискретной математике"
Автор: War17202 • Октябрь 4, 2025 • Контрольная работа • 1,385 Слов (6 Страниц) • 51 Просмотры
Дискретная математика
Контрольная работа
1. Множества и основные операции над ними
1. Докажите тождества двумя способами:
а) используя определения равенства множеств и операций над множествами;
б) с помощью алгебры логики
(A\ B)\C = (A\C)\ (B \C)
РЕШЕНИЕ.
Построим диаграмму Венна. Она на рисунке 1.
[pic 1]
Рис. 1 — диаграмма Венна
И левая и правая части описывают область, залитую голубы. Поэтому соотношение верно.
Аналитически это следует из следующих формул теории множеств
,[pic 2]
.[pic 3]
Пусть а, в, с - логические функции принадлежности к множествам А,В, С соответственно. Тогда имеем формулы
[pic 4]
[pic 5]
Формула доказана с помощью диаграммы Венна, формул теории множеств и логики.
2. Отношения на множествах.
Для данного графика Р найти:
[pic 6]
(3,3),(3,2),(2,2),(1,2),(3,1)
РЕШЕНИЕ
Представим исходный график в виде графа на рисунке 2.
[pic 7]
Рис. 2 — график Р
График получим обращая стрелки. Он на рисунке 3.[pic 8]
[pic 9]
Рис. 3 — обратный график
Для того чтобы получить композицию отношений нарисуем на рсиунке 4 два рисунка 2 рядом.
[pic 10]
Рис. 4 — композиция графиков
Рисунок 4 показывает идемпотентность графика P. Он не меняется при композиции c собой.
Для того, чтобы вычислить нарисуем на рисунке 5 эти графы рядом.[pic 11]
[pic 12]
Рис. 5 — композиция прямого и обратного
Рисунок 5 показывает, что мы получаем тождественное отображение.
Рисунки 4 и 5 позволяют вычислить .[pic 13]
3. Функции алгебры логики. Многочлены Жегалкина
Для заданной булевой функции трех переменных
а) постройте таблицу истинности, найти двоичную форму булевой и привести функцию к СДНФ и CКНФ
б) Найдите двумя способами многочлен Жегалкина и ответить на вопрос,
является ли данная функция линейной
в) С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ.
[pic 14]
РЕШЕНИЕ.
Вычислим таблицу истинности с помощью формул в листинге 1
Листинг 1
Вычисление таблицы истинности
q=['x','y','z','C']
disp(q)
for i=1:1:2
if i==1
x=%f
else
x=%t
end
for j=1:1:2
if j==1
y=%f
else
y=%t
end
for k=1:1:2
if k==1
z=%f
else
z=%t
end
A=(~x | y)& (x | ~y)
B=~A | ~z
C=~B&y|B&~y
p=[x,y,z,C]
disp(p)
end
end
end
//disp(p)
Результат вычисление по формулам листинга 1 на рисунке 6.
4. Графы
[pic 15]
Рис. 6 — таблица истинности искомой функции
Выписываем из таблицы истинности строчки, где значения функции истинны и на их основе пишем СДНФ, она же ДНФ.
[pic 16]
Выписываем из таблицы истинности строчки, где значения функции ложны и на их основе пишем СКНФ, она же КНФ.
[pic 17]
Строим полином Жегалкина.
Начало
Задана совершенная ДНФ функции
[pic 18]
Шаг 1
. Заменяем каждый символ дизъюнкции на символ дизъюнкции с исключением.
[pic 19]
Шаг 2
Заменяем каждую переменную с инверсией равносильной формулой.
...