Матрицы и графы

Вариант 3.

Задача № 1.

Выполнить перевод числа 22.

• а) в двоичную систему счисления;
• б) в 16-ю систему счисления.

Перевести полученные числа в десятичную систему счисления.

Решение.

а).

Ответ: а) 22 =10 110_2.

б) 22:16=1(частное) 6(остаток).

Ответ: б) 22 =16₁₆

• 10 110?=2?+2²+2¹=16+4+2=22₁₀
• 16₁₆=1· 16+6·1=22₁₀

Задача № 2.

Даны множества А, В, С. Количество элементов: |A|=32; |B|=35; |C|=23; |A?B|=28; |A?C|=17; |B?C|=19; |A?B?C|=15. Всего элементов в U 80. Найти количество элементов в дополнении к объединению всех трех множеств.

Решение. Найдем количество элементов в объединении.

32+35+23-(28+17+19)+15=41.

Следовательно, количество элементов в дополнении 80−41=39.

Задача № 3.

Инна переставляет книги на книжной полке. Сколько существует вариантов расставить 11 книг на полке (при условии, что все книги окажутся на полке).

Решение.

Задача № 4.

Для графа, изображённого на рисунке определить степени всех вершин графа. Определить расстояния между вершинами, радиусы и центры графа. Задать граф списком вершин и рёбер, матрицей смежности.

Решение. Граф является ориентированным, так как не содержит неориентированные ребра.

Матрица смежности графа имеет вид.

Список ребер: (2,1), (3,1), (3,4), (4,1), (4,2), (4,1).

1 = 0; 2 = 2; 3 = 2; 4 = 3 (полустепени входа).

1 = 3; 2 = 3; 3 = 1; 4 = 1 (полустепени выхода) Факторизованная запись.

Матрица расстояний r (G)=1, d (G)=2 Центр {2,4}.

десятичный счисление граф истинность Задача № 5.

Изобразить граф, заданный матрицей смежности.

Решение.

Задача № 6.

Построить таблицу истинности для формулы логики высказываний. Указать, является ли формула общезначимой:

Решение.

F (p, q) = (рq) (/ q).

Формула не является общезначимой, то есть истинной при любых значениях входящих в неё переменных.

Задача № 7.

7. Виновник дорожно-транспортного происшествия скрылся с места аварии.

Первый свидетель сообщил, что это были «Жигули», первая цифра номера — единица.

Второй свидетель сказал, что это была машина марки «Москвич», а номер начинался с семерки.

Третий заявил, что машина была иномарка, а номер начинался не с единицы.

При дальнейшем расследовании оказалось, что каждый из свидетелей указал правильно только либо марку машины, либо цифру номера.

Какой марки была машина, и с какой цифры начинался номер?

Решение. Составим таблицу, в которой отразим условия:

Ответ: Первый правильно сказал, что автомобиль был «Жигули», второй правильно сказал, что номер начинался с цифры «7», а третий правильно сказал, что номер не начинался с цифры «1».

Задача№ 8.

Следующие суждение преобразовать и представить в виде формулы логики высказываний: «Маша и Саша хотят дружить с Витей. Если Витя будет дружить с Машей, то не будет дружить с Сашей. А если он будет дружить с Сашей, то не будет дружить с Машей».

Решение.

Вариант № 5.

Задача № 1.

Выполнить перевод числа 24.

• а) в двоичную систему счисления;
• б) в 16-ю систему счисления.

Перевести полученные числа в десятичную систему счисления.

Решение.

а).

Ответ: а) 24 =11 000_2.

б) 22:18=1(частное) 8(остаток).

Ответ: б) 24 =16₁₆

• 11 000?=2?+2³=16+8=24₁₀
• 18₁₆=1· 16+8·1=24₁₀

Задача № 2.

Даны множества А, В, С. Количество элементов: |A|=35; |B|=25; |C|=40; |A?B|=18; |A?C|=20; |B?C|=19; |A?B?C|=15.Всего элементов в U 91. Найти количество элементов в дополнении к объединению всех трех множеств.

Решение. Найдем количество элементов в объединении.

35+25+40-(18+20+19)+15=58.

Следовательно, количество элементов в дополнении 91−58=33.

Задача № 3.

Для участия в лотерее необходимо выбрать четыре цифры (от 1 до 5), при этом цифры не повторяются. Сколько вариантов выбора комбинации цифр есть у участника лотереи?

Решение.

Задача № 4.

Для графа, изображённого на рисунке определить степени всех вершин графа. Определить расстояния между вершинами, радиусы и центры графа. Задать граф списком вершин и рёбер, матрицей смежности.

Решение. Граф ориентированным не является, так как содержит неориентированное ребро {3,4}, т. е. по данному ребру можно переходить в обе стороны.

Матрица смежности графа имеет вид.

Задача № 5.

Изобразить граф, заданный матрицей смежности.

Решение.

Задача № 6.

Построить таблицу истинности для формулы логики высказываний. Указать, является ли формула общезначимой:

Решение.

Формула не является общезначимой, то есть истинной при любых значениях входящих в неё переменных.

Задача № 7.

7. Виновник дорожно-транспортного происшествия скрылся с места аварии.

Первый свидетель сообщил, что это были «Жигули», первая цифра номера — единица.

Второй свидетель сказал, что это была машина марки «Москвич», а номер начинался с семерки.

Третий заявил, что машина была иномарка, а номер начинался не с единицы.

При дальнейшем расследовании оказалось, что каждый из свидетелей указал правильно только либо марку машины, либо цифру номера.

Какой марки была машина, и с какой цифры начинался номер?

Решение.

• 1. Т.к. в первом туре 3 партии, то врач не Андреев, не Борисов, не Григорьев, не Евдокимов.
• 2. Т.к. в втором туре 2 партии, то врач не Дмитриев. Значит, врач — Золотарев.
• 3. Т.к. учитель не Андреев, не Борисов, не Григорьев, не Евдокимов (по усл.1) и не Золотарев, значит, учитель — Дмитриев.
• 4. Т.к. инженер не Евдокимов, не Борисов, не Григорьев (по усл.4) и не Золотарев или Дмитриев, значит, инженер — Андреев.
• 5. Т.к. Борисов не слесарь (по усл.4), значит, он — шофер (по усл.4).
• 6. Т.к. Григорьев не слесарь (по усл.4), значит, он токарь. Тогда остается, что слесарь — Евдокимов.

токарь.	слесарь.	инженер	учитель.	врач.	шофер
Андреев.
Борисов.
Дмитриев.
Григорьев.
Евдокимов.
Золотарев.

Задача№ 8.

Следующие суждение преобразовать и представить в виде формулы логики высказываний: «Маша и Саша хотят дружить с Витей. Если Витя будет дружить с Машей, то не будет дружить с Сашей. А если он будет дружить с Сашей, то не будет дружить с Машей».

Решение.