скачать Примеры решений заданий по дискретной математике 1. Упростить выражение: ![]() Решение. Выразив операцию разности двух множеств через их пересечение и дополнение, получим: ![]() далее используем закон 19 отрицания отрицания: ![]() затем на основании дистрибутивного закона 5 получим: ![]() применив закон 11 А ![]() ![]() ![]() на основании закона 7 де Моргана получим окончательно: ![]() Очевидно, что полученное выражение упростить нельзя. 2. В группе занимается 40 человек, из них 20 человек изучают французский язык, 20 человек - английский язык, 14 человек немецкий язык; английский и французский языки -9 человек; немецкий и английский языки - 7 человек; немецкий и французский - 5 человек, все три языка - 2 человека. Сколько человек не изучают ни одного языка. Решение. Решение задачи осуществим с помощью диаграммы Эйлера-Венна (рис. 1.5). ![]() Рис. 1.5. Введем обозначения: А - множество человек, изучающих английский язык; В - множество человек, изучающих французский язык; С - множество человек, изучающих немецкий язык. Тогда, мощности А, В и С равны: m(А) = 20, m(В) = 20, m(С) = 14. Из условия задачи известно, что все три языка изучают 2 человека. Следовательно, n(A ![]() ![]() Определим число человек, изучающих только два языка: m( ![]() ![]() ![]() ![]() ![]() ![]() m(А ![]() ![]() ![]() ![]() ![]() ![]() m(А ![]() ![]() ![]() ![]() ![]() ![]() Таким образом, только французский и немецкий языки изучают 3 человека, только английский и немецкий языки - 5 человек, только английский и французский языки - 7 человек. Число человек, изучающих только по одному языку: m(A ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() m( ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() m( ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() откуда получаем, что 6 человек изучают только английский язык, 8 человек - только французский язык, 4 человека -только немецкий язык. Тогда, число студентов, не изучающих ни одного языка: m( ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 3. Построить истинностную таблицу сложного высказывания, заданного формулой: S = (A→C) ![]() ![]() Очевидно, истинностная таблица будет содержать 23 = 8 строк. Скобки применяются, если нарушается естественный порядок операций: отрицание, конъюнкция, импликация, двойственная импликация. Скобки (А→С) указывают на то, что сначала нужно выполнить импликацию, а затем найти (А→С) ![]() ![]() ![]() ![]() Построим таблицу:
^ А) ![]() Применим дистрибутивный закон ![]() По закону исключения третьего ![]() По закону идемпотентности пересечение множества с общим множеством дает это же множество ![]() Б) ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() В) ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Г) ![]() ![]() ![]() Применим ассоциативный закон ![]() ![]() ^ ![]()
^ ![]() ![]() в) ![]() ![]() 7. Получить СДНФ для формул: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ^ ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() СКНФ - ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ^ 1.10. Автомат выдает сигнал 1, если на вход поступит слово МАМА, сигнал 2, если поступит слово МАМАЛЫГА, и 0 во всех остальных случаях. Слова отделяются друг от друга пробелами.
![]() ![]() «х«/0
10. Бросают три игральные кости (с шесть гранями каждая). Сколькими способами они могут упасть так, что либо все оказавшиеся вверху грани одинаковы, либо все попарно различны? 6 вариантов, когда все одинаковы и 6*5*4=120, когда все попарно различны Итого: 126 вариантов ^ Может быть n вариантов первой цифры, n-1 второй и т.д. Следовательно число вариантов равно 1*2*3*…*n=n! ^ ![]() ![]() Х3 а) б) в)
б)матрица инцидентности матрица смежности
в)матрица инцидентности матрица смежности
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 Ориентированные деревья: ![]() ^ ![]() 1.Найдем множества внутренней устойчивости:
(1v3)(1v4)(2v4)(2v5)(3v5) Перейдем к ДНФ 123v125v145v234v345 Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости. {4,5},{3,4},{2,3},{1,5},{1,2} 2.Найдем множества внешней устойчивости:
(1v3)(2v4)(3v5)(1v4)(2v5) Перейдем к ДНФ 123v125v145v234v345 {1,2,3}{1,2,5},{1,4,5},{2,3,4},{3,4,5} Совпадающих множеств нет.
|