Дискретная математика
Характеристика основных методов упрочения выражения, сущность закона отрицания и дистрибутирования. Порядок решения задач с помощью диаграммы Эйлера-Венна. Особенности построения таблицы истинности. Матрицы инцидентности и смежности, их сущность.
| Рубрика | Математика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 24.02.2014 |
| Размер файла | 250,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Примеры решений заданий по дискретной математике
1. Упростить выражение:
Решение. Выразив операцию разности двух множеств через их пересечение и дополнение, получим:
далее используем закон отрицания:
затем на основании дистрибутивного закона 5 получим:
применив закон 11 А А= U и закон 14 U В = В, получим:
на основании закона Моргана получим окончательно:
Очевидно, что полученное выражение упростить нельзя.
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 |
|
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.).
|
Х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}
Совпадающих множеств нет.
Размещено на Allbest.ru
...Подобные документы
Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Построение диаграммы псевдографа, матрицы инцидентности и матрицы соседства вершин. Восстановление дерева по вектору с помощью алгоритма Прюфера. Построение таблицы истинности для функции и совершенной конъюнктивной и дизъюнктивной нормальной форм.
контрольная работа [181,9 K], добавлен 25.09.2013Изобретение Леонардом Эйлером геометрической схемы, с помощью которой можно изобразить отношения между подмножествами. Изучение частного случая кругов Эйлера — диаграммы Эйлера—Венна, изображающей все 2^n комбинаций n свойств (конечную булеву алгебру).
презентация [595,0 K], добавлен 16.02.2015Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
учебное пособие [702,6 K], добавлен 29.04.2009Алгоритм построения многочлена Жегалкина по совершенной дизъюнктивной нормальной форме. Диаграмма Эйлера-Венна, изображение универсального множества и подмножества. Проверка самодвойственности, монотонности и линейности логической функции двух переменных.
контрольная работа [227,5 K], добавлен 20.04.2015Решения задач дискретной математики: диаграммы Эйлера-Венна; высказывание в виде формулы логики высказываний и формулы логики предикатов; СДНФ и СКНФ булевой функции. При помощи алгоритма Вонга и метода резолюции выяснить является ли клауза теоремой.
контрольная работа [133,5 K], добавлен 08.06.2010Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
курсовая работа [951,4 K], добавлен 22.01.2014Понятия теории графов. Понятия смежности, инцидентности и степени. Маршруты и пути. Матрицы смежности и инцедентности. Алгоритм поиска минимального пути в ненагруженном ориентированном орграфе на любом языке программирования, алгоритм фронта волны.
курсовая работа [466,3 K], добавлен 28.04.2011Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Методы доказательства клаузы: с помощью резолюций и таблиц истинности. Определение ложности и истинности клаузы. Особенности составления легенды по клаузе. Составление клаузы по легенде. Определение истинности логического выражения путем конкретизации.
контрольная работа [29,9 K], добавлен 14.06.2009Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа [225,5 K], добавлен 14.05.2012Оптимизация как раздел математики, ее определение, сущность, цели, формулировка и особенности постановки задач. Общая характеристика различных методов математической оптимизации функции. Листинг программ основных методов решения задач оптимизации функции.
курсовая работа [414,1 K], добавлен 20.01.2010Методы решения комбинаторных задач детьми на уроках математики. Определение уровня логического и алгоритмического мышления учащихся. Ознакомление школьников с методом организованного перебора, с помощью графа, таблицы и дерева возможных вариантов.
курсовая работа [1,3 M], добавлен 24.11.2014Сущность и математическое обоснование булевой функции, ее назначение и пути решения. Порядок составления таблицы истинности для определенного количества переменных. Связь всех дизъюнкций в конъюнкцию. Разработка и листинг программы представления.
курсовая работа [837,6 K], добавлен 27.04.2011Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление.
задача [53,0 K], добавлен 24.07.2009История возникновения булевой алгебры, разработка системы исчисления высказываний. Методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Дизъюнкция, конъюнкция и отрицание, таблицы истинности.
презентация [1,9 M], добавлен 22.02.2014Поиск собственных чисел и построение фундаментальной системы решений. Исследование зависимости жордановой формы матрицы А от свойств матрицы системы. Построение фундаментальной матрицы решений методом Эйлера, решение задачи Коши и построение графиков.
курсовая работа [354,7 K], добавлен 14.10.2010Изучение нестандартных методов решения задач по математике, имеющих широкое распространение. Анализ метода функциональной, тригонометрической подстановки, методов, основанных на применении численных неравенств. Решение симметрических систем уравнений.
курсовая работа [638,6 K], добавлен 14.02.2010Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
лабораторная работа [42,2 K], добавлен 11.03.2012
