Множества + Булевы функции +отношения =6 задач

Дискретная математика
Контрольная работа
(6 задач)
Номер варианта определяется последней цифрой студбилета (зачетной книжки). Если номер билета оканчивается на 0, то это десятый вариант. Задания нумеруются следующим образом. Например, задание 3.4. означает, что это третье задание четвертого варианта.

Задание №1.

Доказать равенство множеств:
а) исходя из определения равенства множеств;
б) Преобразуя левую (или правую) часть равенства в правую часть (соответственно, в левую);
в) используя характеристические функции и представляя множества с помощью булевых векторов.

1.3. (A \ B) (B \ A) (A B) = A B

Задание №2.

на множестве А(в каждом варианте А – конкретное множество) задано бинарное отношение . Какими из свойств (рефлективность, симметричность, транзитивность и т.д.) оно обладает?

2.3. а) А – множество действительных чисел и для любых x, y Аимеем .
б) А – множество квадратных матриц одного порядка и для любых X, Y А имеем (здесь - это определить матрицы X).

Задание №3.
На множестве с помощью булевой матрицы задать бинарное отношение , которое одновременно обладает следующими свойствами.

3.3. рефлексивно, антисимметрично и транзитивно.

Задание №4.

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

а)
x y z 

0 0 0 1 0 0 1 0 1 1 0 1 1
0 0 1 0 1 1 0 0 1 1 0 1 1
0 1 0 1 1 0 0 1 1 0 0 1 1
0 1 1 1 0 1 1 1 1 1 1 1 0
1 0 0 0 1 1 1 1 0 0 1 0 1
1 0 1 1 1 1 1 0 1 1 1 1 0
1 1 0 1 0 1 1 1 0 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 0 1
   4.1. 4.2. 4.3. 4.4. 4.5. 4.6. 4.7. 4.8. 4.9. 4.10.













Здесь в столбцах указаны номера вариантов.

б)
x y z   

0 0 0 0 1 1 0 0 0 1 1 0 1 0
0 0 0 1 1 0 1 0 1 1 0 1 0 0
0 0 1 0 0 1 1 1 0 1 0 0 1 0
0 0 1 1 0 1 1 1 1 0 1 0 0 1
0 1 0 0 1 0 0 1 1 1 1 1 0 0
0 1 0 1 1 1 1 0 1 0 0 1 1 1
0 1 1 0 1 1 0 1 0 1 1 1 0 1
0 1 1 1 0 1 1 0 1 1 0 1 1 1
1 0 0 0 1 0 1 1 0 1 1 0 1 1
1 0 0 1 0 0 1 0 1 0 1 1 0 0
1 0 1 0 1 0 0 0 1 1 1 0 1 1
1 0 1 1 1 1 0 1 0 0 1 1 1 1
1 1 0 0 1 1 1 1 1 1 0 1 1 0
1 1 0 1 0 1 1 1 1 1 1 1 0 1
1 1 1 0 1 0 1 1 1 0 0 1 1 1
1 1 1 1 1 1 0 1 0 1 1 0 1 1
    4.1. 4.2. 4.3. 4.4. 4.5. 4.6. 4.7. 4.8. 4.9. 4.10.

Задание №5.

Булева функция задана таблично. Показать, что система из этой функции функционально полна, и выразить через функцию дизъюнкцию или конъюнкцию (на выбор).


x y z 

0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 0 0 1 0 1 0 1 0
0 1 0 0 1 1 0 0 1 1 1 1 1
0 1 1 1 0 1 1 0 0 1 1 1 1
1 0 0 0 1 0 1 1 1 0 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0 0
1 1 0 1 0 1 1 1 1 0 0 0 1
1 1 1 0 0 0 0 0 0 0 0 0 0
   5.1. 5.2. 5.3. 5.4. 5.5. 5.6. 5.7. 5.8. 5.9. 5.10.

Задание №6.

Можно ли с помощью указанных операций записать любую формулу алгебры высказываний?

6.3. Сложение по модулю 2 и эквивалентности ~.