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

Дискретная  математика

1. Задание множеств

 

1.3.Задать перечислением элементов множество:

{y | x=y+z,    x,z  ÎX, X= {1,2}} 

Решение:

Обозначим A={y | x=y+z,    x,z  ÎX, X= {1,2}}

x=y+z, отсюда y=x-z

Составим таблицу:

 

Таким образом, получаем:

A={-1, 0, 1} 
 

2.3.Найти булеан множества и записать все его компоненты с помощью характеристической функции:

X = Æ; 

Решение:

Булеаном множества  X является множество всех подмножеств множества X, в данном случае подмножеством пустого множества может быть только само пустое множество.

Таким образом: B(X) = {Æ} = Æ = X;

Составим таблицу  компонентов булеана и характеристических функций подмножеств множества Х

 

Таким образом, значение характеристической функции  равно 1 
 

(Это  задание решать  не нужно, оно  нужно для задания  №7!) 5.Обследование 100 студентов дало следующие результаты о количестве студентов, изучающих различные иностранные языки: испанский - 28, немецкий - 30, французский - 42, испанский и немецкий - 8, испанский и французский - 10,  немецкий и  французский - 5, все три языка - 3. 

7.В отчете об обследовании 100 студентов, изучающих иностранные языки (См. задание 5), указывалось, что количество студентов, изучающих различные языки таково: все три языка 5, немецкий и испанский 10, французский и испанский 8, немецкий и французский 20, испанский 30, немецкий 23, французский 50. Инспектор, представивший этот отчет, был уволен. Почему?

Решение:

Введем  обозначения: С – множество всех опрошенных студентов; И – множество студентов, изучающих испанский язык; Н – множество студентов, изучающих немецкий язык; Ф – множество студентов, изучающих французский язык.

По условию  задачи:

=5

=10

=8

=20

=30

=50

=23

Тогда ( )/( )=10-5=5; 

( )/( )=8-5=3;

( )/( )=20-5=15;

Получаем  следующие диаграммы:

Отсюда  находим, что:

только  испанский язык изучают 30-5-5-3 = 17 студентов;

только  французский язык изучают 50-3-5-15 = 27 студентов;

только  немецкий язык изучают 23-5-5-15 = -2 студентов;

Очевидно, что отрицательного значения быть не может и в отчете инспектора есть ошибки, поэтому он был уволен. 

9.4.Пусть I = { a,b,c,d,e,f }, X = { a,b,c }, Y = {a,c,e,f }, Z = { d,e }. Определить множество, заданное формулой, перечислением элементов и с помощью характеристической функции:   (X ÈY) Ç(X ÈZ));

14.7.Какие из следующих утверждений справедливы:  ÆÍ{Æ};

2. Операции  над множествами

2.1.Даны множества А, В, С  и СÍВ. Доказать, что А Ç С Í А Ç В; 

4.3.Доказать справедливость тождеств: A\ (B\C) = (A\B) È (A Ç C);

5.2.Доказать, справедливость тождеств:

9.Решить систему уравнений

где А, В, С - данные множества, В Í А Í С. 

11.6.Доказать, что:  А ´ B = (A ´ D) Ç(C ´ B) Û A Í C и B Í D;

3. Отношения и функции

1.15.Пусть [a,b],[c,d] Í R. Найти геометрическую интерпретацию множеств: {-1,0,1} x [a,b]; 
 

2.3.Определить всеми возможными способами бинарное отношение на множестве А ={1,2,3,4,5}   и указать его свойства, если  xry Û  х делит у; 

8.Определить все возможные бинарные отношения на множестве {a,b} и найти среди них все отношения эквивалентности, а также все отношения являющиеся одновременно симметричными и транзитивными,  но не рефлексивными. 

9.3.Пусть А и В - конечные множества с мощностью  m и n соответственно.

Сколько существует взаимно однозначных соответствий  между А и В ? 

11.1.Пусть f  и g - функции. При каких условиях f ^-1 является функцией ; 

16.8.Найти область определения, область значений, график отношения r, обратное отношение

r^-1, дополнение отношения`r, композиции r  · r, r · r^-1, r^-1 · r  для отношения: хrу  Û х,у Î (0,10],  y ³lg x; 

17.1.Доказать, что для любых отношений r₁ и r₂ справедливы соотношения:

4. Специальные бинарные отношения

 

5.Доказать, что если отношения r₁ и r₂ антисимметричны, то антисимметричны и отношения:  r₁Çr₂  и r₁^-1, а объединение r₁Èr₂ антисимметричных отношений на А антисимметрично тогда и только тогда, когда  r₁Çr₂^-1 Í I_А. 

11.1. Пусть £ и < на множестве N= {1,2,3,...} определены обычным образом. Доказать, что < · < ¹<;

5. Элементы  комбинаторики

 

4. Сколькими способами можно указать на шахматной доске два квадрата без ограничения цвета  квадратов? 

8.3.Найти число векторов , координаты которых удовлетворяют условиям:

11.3.Доказать следующие свойства биномиальных коэффициентов:

6. Функции алгебры логики

 

1.3. Построить таблицу истинности для формулы и, используя правила равносильных преобразований формул, привести ее  к ДНФ и к КНФ, построить полином Жегалкина. Проверить правильность выполненных преобразований с использованием диаграмм Вейча. Найти существенные переменные функции, заданной  формулой (x®y)¯(y«z); 

2.2.Определить СДНФ, СКНФ, СПНФ для функции, заданной векторно:a _f =(0001 0101 0110 1001); 

3.5.Реализовать формулы системы D формулами над множеством связок  S.

D= {Ú,®,Å},   S = {|}; 

7.3.Доказать справедливость тождеств:   

10.2.Найти длину СДНФ функции :  = (x₁Úx₂Ú ... Úx_n) (`x<sub>1</sub>Ú`x₂Ú ... Ú`x_n);

7. Минимизация булевых функций

1.3.Найти геометрическую интерпретацию следующих функций. Указать все грани единичного трехмерного куба, все максимальные интервалы, соответствующие данной функции. Определить МДНФ данной функции. (x | (xy)) ® z; 

3.3.Найти МДНФ для функции, заданной вектором: a_f=(**10 0**1 0**0 *111); 

4.3.Найти МДНФ для частично определенной булевой функции методом таблиц различий и методом симметричных таблиц. Сравнить результаты.

 N₁ =(*0101**)È(*10011*) È(1***000);        N₀=(0*0*01*)È(0*1**1) È(000**11); 

5.  Записать формулу, полученную в п.4.3, в виде суперпозиции над {|}.