Методические указания по курсу Математика для студентов I курса исторического факультета (стр. 2 из 5)

Ответ: 100.

8) Т.к.

, то количество подмножеств - .

Задание 2 (Графы)

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

1)

Изобразить вершины графа точками, обозначить их и соединить ребрами так, чтобы получился а) полный граф - , б) двудольный граф - , в) полный двудольный граф - ,г) регулярный граф - (указать его степень), д) односвязный граф с одним “мостом” - , е) непростой граф - (т.е выполнить не менее шести рисунков).

2) Найти среди изображенных графов а) эйлеров граф, б) полуэйлеров граф, в) граф, имеющий циклы (если они есть на рисунках, подписать их; если нет, то изобразить такие графы).

3) Из множеств А, В и С предыдущей задачи выбрать множество с наименьшим числом букв (элементов) и, считая их вершинами графа, изобразить все возможные деревья с вершинами во всех этих точках.

Например.

b

a c полный граф с пятью вершинами; он же регулярный

(однородный), степень вершин r = 4; а также он эйлеров;

l d односвязный.

n двудольный и двусвязный граф; (двудольный -

m неполный).

l

k o

p q

s

t u непростой, односвязный с одним “мостом”,

полуэйлеров граф.

xv

z w

y

Задание 3 (Теория вероятностей)

Возьмем множества А и В из задания 1. Пусть каждая из букв написана на отдельной карточке и множества А и В – это две колоды карточек (все карточки положены буквами вниз, их не видно).

Вычислить вероятность того, что при выборе наугад по одной карточке из каждой колоды будут вынуты а) 2 одинаковые буквы; б) 2 разные буквы; в) хотя бы одна из букв такая, какую Вы задумали заранее (укажите, какую именно; если есть разные варианты решения, то покажите все решения).

Например, ) А={П, А, Ф, Н, У, Т, И, Й}, В={Л, Ь, В, О, В, И, Ч}. Тогда: а) общая буква только одна – И; вероятность ее выбора из А равна

, вероятность ее выбора из В равна ; вероятность ее выбора из А и из В – (правило произведения); б) т.к. во всех остальных случаях буквы будут различны, то вероятность выбора двух разных букв равна (можно ее найти и другим способом); в) если задумана буква “И”, то вероятность ее выбора хотя бы из одной колоды – это 3 случая: “И” из А и любая другая буква из В, “И” из В и любая другая буква из А, а также “И” – из А и В; сложив вероятности, получим: .Аналогично для других букв (2 случ.).

Внимание! В заданиях 4 и 5 каждый студент должен выполнить свой вариант. Номер варианта соответствует Вашему номеру зачетной книжки следующим образом: а) если две последние цифры номера зачетной книжки составляют число не больше тридцати, то это и есть номер Вашего варианта; б) если две последние цифры составляют число большее тридцати, то из него следует вычесть 30 столько раз, сколько возможно; остаток и есть номер Вашего варианта; если две последние цифры номера зачетной книжки 60 ли 90, то Вы выполняете вариант 30. Например, номер зачетной книжки …41 – вариант 11, т.к. 41=30+11, …62 – вариант 2, …97 – вариант 7; …208 – т.е. …08 – вариант 8.

Задание 4 (Математическая логика).

А. В вариантах 1 – 15 составить таблицу истинности формулы:

1. ùx & y Ú (ùy ºxÚùy); 2. ù(x &ù y )Ú (ùx &y) ºùy);

3. yÚùx & ( y &x®ùx); 4. x Úy º (ùx &ùy ®y );

5. x º ( x Úùy ®ùy&ùx); 6. (y ®ù x Ú ( x &y)) ºxÚy;

7. ù(x Úùy) ® (xÚùy); 8. x Ú ( y ®yÚù (xÚy));

9. x Úy ®ùy& ( x®y); 10. x & ( ù y®xÚy);

11. x º ( y ®ùxÚ ( x ºùy)); 12. (xÚy) ® ( y&ùx);

13. ( x®y) ® (ùx &ù (y Úx)); 14. x º ( ùy ® x) Ú ( x®ùy));

15. (x Úùy) & ( ùxÚy) ºùy;

Б. В вариантах 16-30 проверить, является ли формула тавтологией:

16. (y ® (xÚùy)) & ( x® ( y Úùx)); 17. ( x Úy)® ( yÚùx);

18. x º ( x Úùy ) &ùy); 19. x ® ( xÚ (ùy &x ));

20. x ® (( y&ùx) ®x); 21. (x ®y) ®xÚy ºù (ùx &ùy);

22. xÚy ºù (ùx &ùy); 23. ( ùxÚy ®y ) ºxÚy;

24. ( ùxÚy ®x ) ºx &y; 25. ù (x ®y) Ú ( ùy®ùx);

26. ù (x ®y) &ù ( y®ùx); 27. x &ù y ® (xÚy ºùx);

28. x Úùy ® (ùy&ùx)ºùx; 29. x º ( y ®x &ùy );

30. ùx º ( y Ú ( x®ùy)).

Примеры. А. Составить таблицу истинности формулы

(x ®ùy) & (xÚy)) ºx Úùy.

Решение. Порядок выполнения действий:

x ® t

Ú

& z º

y ùÚ v

x	y	ùy	x Úy	z ùy & (x Úy)	t (x®z)	v ( x Úùy )	Ответ: t ºv
И И Л Л	И Л И Л	Л И Л И	И И И Л	Л И Л Л	Л И И И	И И Л И	Л И Л И

Б. Проверить, является ли формула (x ®ùy) & (xÚy)) º (x ®ùy) тавтологией.