Дискретная математика. 
Дискретная математика

Примеры решений заданий по дискретной математике.

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 (CAB) = m (U) — m (A)-(BC) — m© = 40−20−11−4 = 5 .

• 3. Построить истинностную таблицу сложного высказывания, заданного формулой:
  • S = (A>C) B

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

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

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

Применим дистрибутивный закон По закону исключения третьего По закону идемпотентности пересечение множества с общим множеством дает это же множество.

• Б)
• В)
• Г)

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

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

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

=.

• в) =
• 7. Получить СДНФ для формул:
• 8. Получить СДНФ, а затем перейти к СКНФ

.

?? ?

?? ?

? .

СКНФ —? ?? ? ?

? ?

.

• 9. Построить (синтезировать) автомат по содержательному описанию.
• 1.10. Автомат выдает сигнал 1, если на вход поступит слово МАМА, сигнал 2, если поступит слово МАМАЛЫГА, и 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.
Х2.
Х3.
Х4.
Х5.

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. Найдем множества внутренней устойчивости:

(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}.

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