Решение. Решение задачи осуществим с помощью диа­граммы Эйлера-Венна (рис. 5) icon

Решение. Решение задачи осуществим с помощью диа­граммы Эйлера-Венна (рис. 5)


2 чел. помогло.
Смотрите также:
2. Решение задач с помощью кругов Эйлера...
Решение задач одно из важных применений Excel...
Решение : Сделаем замену...
Решение задач с помощью дробных рациональных уравнений. (8 класс)...
Решение от 26. 03. 2009г. №74, решение от 21. 04. 2010г., решение от 24. 11. 2010г. №287...
Решение задачи распознавания туберкулезных бацилл на изображениях...
Решение vi/37
Приказ № от 2010 г...
Решение, принимаемое апелляционной инстанцией...
Решение задачи...
Самостоятельная работа    2 часа в неделю Всего часов ...
Решение прямой задачи кинематики манипулятора на базе...



Загрузка...
скачать
Примеры решений заданий по дискретной математике


1. Упростить выражение:



Решение. Выразив операцию разности двух множеств через их пересечение и дополнение, получим:



далее используем закон 19 отрицания отрицания:



затем на основании дистрибутивного закона 5 получим:



применив закон 11 А А= U и закон 14 U В = В, получим:



на основании закона 7 де Моргана получим окончательно:



Очевидно, что полученное выражение упростить нельзя.


2. В группе занимается 40 человек, из них 20 человек из­учают французский язык, 20 человек - английский язык, 14 человек немецкий язык; английский и французский языки -9 человек; немецкий и английский языки - 7 человек; немец­кий и французский - 5 человек, все три языка - 2 человека. Сколько человек не изучают ни одного языка.

Решение. Решение задачи осуществим с помощью диа­граммы Эйлера-Венна (рис. 1.5).



Рис. 1.5.

Введем обозначения: А - множество человек, из­учающих английский язык;

В - множество человек, изучающих французский язык; С - множество человек, изучающих немецкий язык. Тогда, мощности А, В и С равны:

m(А) = 20, m(В) = 20, m(С) = 14.

Из условия задачи известно, что все три языка изучают 2 человека. Следовательно, n(AВС) = 2.

Определим число человек, изучающих только два языка:

m(ВС) = m(B С) - m(АBС) = 5-2 = 3,

m(А С) = m(АС) - m(АBC) = 7-2 = 5,

m(АВ) = m(АВ) - m(АBC) = 9-2 = 7.

Таким образом, только французский и немецкий языки изучают 3 человека, только английский и немецкий языки - 5 человек, только английский и французский языки - 7 человек.

Число человек, изучающих только по одному языку:

m(A )=m(A)-m(AB)-m(AC)=20-9-5=6,

m(B)=m(B)-m(AB)-m(BC)=20-9-3=8,

m(C)=m(C)-m(AC)-m(BC)=14-7-3=4.

откуда получаем, что 6 человек изучают только английский язык, 8 человек - только французский язык, 4 человека -только немецкий язык.

Тогда, число студентов, не изучающих ни одного языка:

m( ) = m(U) - m(А) - m(В\А) - m(C\A\B) = m(U) - m(A)-(BC) - m(С) = 40-20-11-4 = 5 .


3. Построить истинностную таблицу сложного высказывания, заданного формулой:

S = (A→C) B

Очевидно, истинностная таблица будет содержать 23 = 8 строк. Скобки применяются, если нарушается естественный порядок операций: отрицание, конъюнкция, импликация, двойственная импликация. Скобки (А→С) указывают на то, что сначала нужно выполнить импликацию, а затем найти

(А→С) В. Скобки в выражении можно опустить. Заключительной операцией в построении истинностной таблицы для S будет дизъюнкция двух высказываний: (А→С) В и .

Построим таблицу:

A

C

B

A→C

(A→C)B



A↔



S

1

1

1

1

1

0

0

1

1

1

1

0

1

0

1

1

0

0

1

0

1

0

0

0

0

1

1

1

0

0

0

0

1

1

0

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

0

1

1

1

0

1

0

1

0

0

0

1

0

1

0

1

1


^ 4. Доказать равенство множеств, преобразуя множества к одинаковому виду с помощью основных законов алгебры множеств.

А)



Применим дистрибутивный закон



По закону исключения третьего



По закону идемпотентности пересечение множества с общим множеством дает это же множество



Б)

















В)























Г)







Применим ассоциативный закон





^ 5. Построить таблицы истинности для формул:



А

В







0

0

1

1

0

0

1

1

1

0

1

0

0

0

1

1

1

0

0

1


^ 6. Получить ДНФ для формул:

=

в) =

7. Получить СДНФ для формул:





^ 8. Получить СДНФ, а затем перейти к СКНФ

.



.

СКНФ -



.

^ 9. Построить (синтезировать) автомат по содержательному описанию.

1.10. Автомат выдает сигнал 1, если на вход поступит слово МАМА, сигнал 2, если поступит слово МАМАЛЫГА, и 0 во всех остальных случаях. Слова отделяются друг от друга пробелами.






Q0

Q1

Q2

мама

0

0

0

лыга

0

0

0

« «

0

1

2

Х

0

0

0

«х«/0






Q0

Q1

Q2

мама

Q1

Q0

Q0

лыга

Q0

Q2

Q0

« «

Q0

Q0

Q0

Х

Q0

Q0

Q0

10. Бросают три игральные кости (с шесть гранями каждая). Сколькими способами они могут упасть так, что либо все оказавшиеся вверху грани одинаковы, либо все попарно различны?


6 вариантов, когда все одинаковы и 6*5*4=120, когда все попарно различны

Итого: 126 вариантов

^ 11. Предложить алгоритм бесповторного перечисления всех (n,n) перестановок чисел 1,2,…,n.

Может быть n вариантов первой цифры, n-1 второй и т.д. Следовательно число вариантов равно

1*2*3*…*n=n!

^ 12. Записать следующие графы матрицами инцидентности и смежности.(Рис.3.).



Х3


а) б) в)






Х1

Х2

Х3

Х4

Х5

Х1

0

1

0

0

0

Х2

1

0

1

0

0

Х3

0

1

0

1

0

Х4

0

0

1

0

1

Х5

0

0

0

1

0
а)матрица инцидентности матрица смежности






Е1

Е2

Е3

Е4

Х1

1

0

0

0

Х2

1

0

0

1

Х3

0

0

1

1

Х4

0

1

1

0

Х5

0

1

0

0



б)матрица инцидентности матрица смежности





Х1

Х2

Х3

Х4

Х5

Х1

0

1

0

0

0

Х2

1

0

1

0

0

Х3

0

1

0

1

0

Х4

0

0

1

0

1

Х5

0

0

0

1

0







Е1

Е2

Е3

Е4

Х1

1

0

0

0

Х2

1

1

0

0

Х3

0

1

1

0

Х4

0

0

1

1

Х5

0

0

0

1



в)матрица инцидентности матрица смежности





Х1

Х2

Х3

Х4

Х5

Х1

0

1

0

0

0

Х2

0

0

0

0

0

Х3

0

1

0

0

0

Х4

0

0

1

0

0

Х5

0

0

0

1

0







Е1

Е2

Е3

Е4

Х1

-1

0

0

0

Х2

+1

+1

0

0

Х3

0

-1

+1

0

Х4

0

0

-1

+1

Х5

0

0

0

-1



13. Даны графы типа дерева на рис.7. Для каждого графа выполнить следующее задание. Сколько вершин максимального типа имеется в данном графе? Какое цикломатическое число графа? Чему равно цикломатическое число графа G', являющегося лесом и представленного двумя одинаковыми деревьями рассматриваемого типа графа? Построить ориентированное дерево с корнем 0, являющимся вершиной максимального типа.






Рис. 7


Цикломатическое число v(G)= m-n+1

m- кол-во ребер

n- кол-во вершин


G1)v(G)=20-20+1 =1

G2)v(G)=18-19+1 =0 => G2 уже дерево

G3)v(G)=18-19+1 =0 => G3 уже дерево


Кол-во вершин максимального типа:

G1)7

G2)4

G3)2


Цикломатическое число леса:

G1)1*2=2

G2)0*2=0

G3)0*2=0


Ориентированные деревья:




^ 14. Найти ядро графа с помощью алгоритмов Магу (рис. 4.12).



1.Найдем множества внутренней устойчивости:




1

2

3

4

5

1







1







2










1




3













1

4

1













5




1











(1v3)(1v4)(2v4)(2v5)(3v5)

Перейдем к ДНФ

123v125v145v234v345

Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.

{4,5},{3,4},{2,3},{1,5},{1,2}

2.Найдем множества внешней устойчивости:




1

2

3

4

5

1

1




1







2




1




1




3







1




1

4

1







1




5




1







1

(1v3)(2v4)(3v5)(1v4)(2v5)

Перейдем к ДНФ

123v125v145v234v345

{1,2,3}{1,2,5},{1,4,5},{2,3,4},{3,4,5}


Совпадающих множеств нет.




Скачать 176,04 Kb.
оставить комментарий
Дата17.09.2011
Размер176,04 Kb.
ТипРешение, Образовательные материалы
Добавить документ в свой блог или на сайт

плохо
  1
отлично
  3
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх