ДЗ 1, 2: Дискретная математика вариант 5

Домашнее задание №1

Задача №1
Для заданного теоретико-множественного тождества:
а) проиллюстрировать тождество диаграммой Эйлера-Венна;
б) проверить тождество методом эквивалентных преобразований или методом характеристических функций Задача №2
Для заданных на множестве А = {1,2,3,4,5} бинарных отношений ρ и τ:
1. записать матрицы и построить графики
2. найти композицию ρ^оτ
3. исследовать свойства отношений ρ, τ и ρ^оτ (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность).
ρ = {(x, y) : x(6-y) ≤ 8}
τ = {(x, y) : |x-y| > 2}
Задача №3
Пусть Н – подгруппа, порожденная элементом b в мультипликативной группе вычетов по модулю р, а gH – класс смежности группы z по подгруппе Н с представителем g.

1. вычислить подгруппу Н и смежный класс gH
2. каждый элемент класса gH представить в виде двоичного числа длины 7
3. на множестве полученных векторов построить диаграмму Хассе для отношения порядка

Выписать любые три максимальные цепи и антицепи и указать их не диаграмме Хассе
р = 97, b = 8, g = 6
Задача №4
Проверив аксиомы, установить, является ли заданная алгебра с двумя бинарными операциями полукольцом или кольцом. При этом:
а) для полукольца (не являющегося кольцом), проверить, является ли полукольцо коммутативным, идемпотентным, замкнутым;
б) для кольца проверить, будет ли оно булевым, есть ли в нем делители нуля, является ли кольцо полем.
Множество упорядоченных пар (х, у), где х,у {0,1,2}, с операциями сложения и умножения упорядоченных пар, определенных по следующим правилам:
(a,b)+(c,d)=(a+b,c+d); (a,b)^.(c,d)=(ab,cd),
причем операции сложения и умножения элементов выполняются в поле Z₃ вычетов по модулю 3.

Домашнее задание №2

Задача №1
Для булевой функции f , заданной в таблице 1:
а) найти сокращенную ДНФ
б) найти ядро функции
в) получить все тупиковые ДНФ и указать, какие из них являются минимальными
г) на картах Карно указать ядро и покрытия, соответствующие мин. ДНФ.
Задача №3
Автомат задан набором ({a,b},{q₁,q₂,q₃,q₄,q₅},Qs,Qf), где {а,b} - алфавит, Q_s -множество начальных состояний (входов), Q_f - множество конечных состояний (выходов), и списком дуг с метками, определяющим допустимые переходы. Запись (i,j,a,b) означает, что дуга (i,j), идущая из состояния q_i в состояние q_j, имеет две метки - а и b.

1. Построить граф автомата и найти язык L, допускаемый автоматом.
2. Детерминизировать автомат.
3. Построить графы автоматов, представляющих языки L₀, L L₀, L°L₀, L*
4. Из построенных графов удалить λ -переходы.

Входы Q_s={1,5}
Выход Q_f={4}
дуги: (1,5,а), (2,1,а), (2,4,b), (3,2,a), (4,3,a), (5,2,b), (5,4,b)
L₀={aⁿ(ba)^ma | n,m>0}