КР 1 ОДМиТА 2012
.docxМинистерство образования Республики Беларусь
Учреждение образования
«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»
Институт информационных технологий
Специальность: Информационные системы и технологии в экономике. КОНТРОЛЬНАЯ РАБОТА
По курсу «Основы дискретной математики и теории алгоритмов»
Вариант 5
Студент-заочник 1 курса
Группы
№ зачётки:
ФИО:
Адрес:
Тел. моб:
Дата выполнения: 11.12.12
Минск, 2012
Задание 1.
Используя диаграммы Эйлера-Венна, решить задачу:
На кафедре иностранных языков работают 18 преподавателей, из них 12 преподают английский язык, 11 – немецкий, 9-французский; 5 преподавателей преподают английский и немецкий языки, 4 - английский и французский, 3 –немецкий и французский. Сколько преподавателей преподают все три языка? Только два языка?
Решение:
Для решения задачи используются следующие обозначения:
А – множество преподавателей английского языка;
В – множество преподавателей немецкого языка;
С – множество преподавателей французского языка;
U – множество преподавателей.
Диаграмма Эйлера-Венна с учетом введенных обозначений примет следующий вид:
Мощности множеств А, В, С и U равны:
m(A) = m(A B С)+m(A С)+m(A B C)+m(A B C)=12;
m(B) = m(A B C)+m(A B С)+ m(A B C)+ m(A B C)=11;
m(C) = m(A С)+ m(A С)+m(A B С)+ m(A B C)=9;
m(U) = m(A B С)+m(A B С)+m(A С)+ m(A B C)+
+ m(A B С)+ m(A B С)+ m(A B С)=18
Мощности множеств преподавателей двух языков:
m(A B)=m(A B C)+m(A B C)=5;
m(A C)=m(A C)+ m(A B C)=4;
m(B C)=(A C)+ m(A B C)=3
С учетом предыдущих формул можно записать:
m(U) = m(A B С)+m(A B С)+m(A С)+
m(A B C)+ m(A B С)+ m(A B С)+ m(A B C)=
=m(A)- m(A B С)- m(A B C)- m(A B C)+
m(B)- m(A B С) - m(A B C)+ m(A B C)+
m(C)- m(A B С) - m(A B С) - m(A B C)+
+ m(A B C)+ m(A B С) + m(A B С) + m(A B C)=
=m(A)+m(B)+m(C)-m(A B C)- m(A B С)- m(A B С)-
-2* m(A B C)= m(A)+m(B)+m(C)-[m(A B) - m(A B C)]-[ m(A C - m(A B C)]-[m(B С) - m(A B C)]- 2* m(A B C)=
= m(A)+m(B)+m(C)-m(A B)-m(A C) – m(B C)+ m(A B C)=
=12+11+9-5-4-3+m(A C)=20+m(A B С).
Следовательно:
m(U)=20+m(A B С)=28m(A B С)= -2
Ответ: Задача не имеет решения.
Задание 2
Упростить выражение: A A \B\B
Решение:
A A \B\B
(U )=U
Ответ:
Задание 3
С помощью ДНФ и КНФ установить выполнимость формулы:
(AB)()
Решение:
Разложение формулы:
Ответ: Поскольку полученная формула не удовлетворяет условию теорем 3 и 4, то можно сделать вывод о ее выполнимости.
Задание 4
С помощью совершенных нормальных форм установить, равносильны ли
формулы α и β:
= A();
= A.
Решение:
Построение СДНФ:
Ответ: Поскольку СДНФ не равны, то формулы α и β не равносильны.
Задание 5
Проверить правильность рассуждения тремя способами:
Если функция непрерывна на данном интервале и внутри его не обращается в ноль, то функция имеет одинаковые знаки на концах данного интервала. Функция имеет одинаковые знаки на концах интервала, но обращается в ноль внутри его. Следовательно, функция разрывна.
Решение:
Посылки и заключения в рассуждении состоят из следующих элементарных высказываний:
А – «Функция непрерывна на данном интервале»;
В – «Функция не обращается в ноль внутри данного интервала»;
С – «Функция имеет одинаковые знаки на концах интервала».
Посылки и заключения:
− A ∧ B → C (посылка Р1);
− C ∧ B (посылка Р2);
− A (заключение Q).
Рассуждение верно, если импликация (A∧ B →C)∧(C ∧ B)→ A тождественно истинна. Для проверки правильности рассуждения строится таблица истины:
Рассуждение не верно, т.к. полученное значение не является тождественно истинным.
Проверим правильность рассуждения, методом от противного. Для этого заключения Q полагается ложным, т.е. Q = A = 0 , а посылка Р2 истинной, т.е. P2= C= 1. Тогда A =1, C =1, B =1⇒ B = 0. В этом случае посылка Р1 равна
P1= A ∧ B → С = 1 ∧ 0 →1=0→1=1. Поскольку ни одна из посылок не приняла значение ложно, то можно сделать вывод, что рассуждение не верно.
Преобразование к равносильной формуле:
Ответ: Поскольку полученная формула не является тождественно истинной, то рассуждение не верно.
Задание 6
По заданной функции проводимости построить наиболее простую схему:
f(0,1,0)=f(1,1,0)=f(1,1,1)=0
Решение:
Формула алгебры высказываний, имеющую заданную логическую функцию – СДНФ:
Упрощения выражения:
Ответ:
Задание 7
Упростить схему:
Решение:
Соответствующая схеме формула:
Упрощение выражения:
Ответ:
Задание 8
Для заданного графа построить:
1. Матрицу смежности;
2. Матрицу инциденций;
3. Матрицу достижимостей;
4. Найти число внутренней устойчивости, полагая граф неориентированным;
5. Найти число внешней устойчивости, полагая граф неориентированным.
Решение:
Обозначение графа:
Для заданного графа G=(X, Г(X)) множество вершин:
X={X1, X2, X3, X4, X5, X6,}; Г(X1)={X2,X3,X6}; Г(X2)={X3}; Г{X3}={X4,X6}; Г(X4)={X5}; Г(X5)={X6}; Г(X6)=.
Матрица смежности:
Матрица инциденций:
Поскольку граф не имеет петель, то каждый столбец матрицы В содержит единственный элемент, равный 1 (начало дуги) и единственный элемент равный -1 (конец дуги):
Матрица достижимостей:
Число внутренней устойчивости:
Внутренне устойчивые множества для заданного графа:
S1={X1, X4};S2={X1, X5}; S3={X2, X4}; S4={X2, X5}; S5={X2, X6};
S6={X3, X5}; S7={X4, X6}; S8={X2, X4, X6}.
Из них максимальными являются: S1, S2, S4, S6, S8.
Следовательно, число внутренней устойчивости равно:
Число внешней устойчивости :
Внешне устойчивые множества для заданного графа
R1={X1, X4, X6};R2={X1, X3, X5}; R3={X1,X2,X4};
R4={X1,X4,X5}; R5={X1,X4}.
Из них минимальными являются: R2, R5. Следовательно, число внешней устойчивости графа равно:
Задание 9
Для графов G1 и G2 найти G1 G2; G1 G2; G1 G2.
Решение:
Обозначение графов:
Для заданного графа G1 = (X1,ГI(X)) множество вершин:
XI= {X1,X2,X3};ГI(X1)={X2}; ГI(X2)={X3}; ГI(X3)={X1}.
Для заданного графа G2=(XII, ГII(X)) множество вершин:
XII= {X1,X2,X3}; ГII (X1)={X2}; ГII (X2)={X3}; ГII (X3)={X3}.
Объединение графов G1 G2:
Пересечение графов G1 G2:
Декартово пересечение графов G1 G2: