Решение. Решение задачи осуществим с помощью диаграммы Эйлера-Венна (рис. 5)
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 будет дизъюнкция двух высказываний: (А→С) В и .Построим таблицу:
^ А)  Применим дистрибутивный закон  По закону исключения третьего  По закону идемпотентности пересечение множества с общим множеством дает это же множество  Б)         В)            Г)    Применим ассоциативный закон   ^ 
^  =  в)  = 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} Совпадающих множеств нет.
|
плохо
1отлично
3 Разместите кнопку на своём сайте или блоге: