Задача 1

Загрузка...





Скачать 85.51 Kb.
НазваниеЗадача 1
Дата публикации22.10.2013
Размер85.51 Kb.
ТипЗадача
top-bal.ru > Математика > Задача

Министерство образования российской федерации

Московский государственный институт электроники и математики

(технический институт)

Кафедра ИКТ




Домашняя работа по дисциплине

«Дискретная математика»


Руководитель

_________

«___» _______2008 г.

П.М. Маркин


Студент группы

С-34

_________

«___» _______2008 г.

С.Ю. Никитин










^

Теория множеств


Задача 1. Сколько различных трехбуквенных слов можно составить из букв русского алфавита, не обращая внимания на их смысл.

Решение:

В русском алфавите 33 буквы. A= {a, ... , я}

|А|=33. Трехбуквенное слово есть кортеж длины 3: , где x,y,z – элементы алфавита.

М-множество различных трехбуквенных слов (множество кортежей)

М=A x A x A=A3 ; |M| = |A|3 = 333 = 35937

Задача 4. Для написания цифр почтового индекса используют множество из девяти элементов, которые на рисунке 1 обозначены буквами. Запишите множества Ак (к = 0,9) элементов каждой из десяти цифр. Имеются ли среди этих множеств непересекающиеся ?



Рисунок 1

Решение:

A0={a,c,d,h,i,f};

A1={b,d,h};

A2={c,d,g,i};

A3={c,b,e,g};

A4={a,e,d,h};

A5={c,a,e,h,i};

A6={c,a,f,i,h,e};

A7={c,d,g};

A8={a,c,d,e,f,h,i};

A9={e,a,c,d,g}.

Нет непересекающихся множеств.

Задача 5. К каким видам относятся следующие множества : А - множество всех простых чисел натурального ряда N ; В - множество деревьев на луне ; С - множество всех решений уравнения 2х-3=0?

Решение:

А – множество всех простых натуральных бесконечных чисел.

В – пустое множество.

С – конечное множество всех корней уравнения

Задача 6. Сколько соответствий можно установить между элементами множеств A={k,l,m,n} и В= {b1,b2.bЗ} Какие из этих соответствий являются отображениями ? К каким типам относятся приведенные соответствия ?

По определению, соответствие S из мн-ва А в мн-во В называется подмножество декарт. Произведения Ах В => Sс АхВ.

Следовательно нужно найти мощность мн-ва всех подмножеств дек - произведения АхВ.

|b(AхВ)|

|b(AхВ)|= 2|AxB|=23х4 =212 =4096

Одно отображение имеет вид: <f (k)>; f (l)>; f (m)>; f (n)>>. Значит мн-во всех отображений можно представить в виде декартового произведения, элементами которого будет явл. кортежа вида (1); {1>;2>;3>;}х{1>;2>; 3>;}х{1>;2>;3>;}х{1>;2>;3>;} => Количество отображений будет |B||A|=34=81

Среди приведенных соответствий есть:

1) Всюду определенные;

2) Частично определённое;

3) Многозначные(число образов хотя бы одного элемента из А больше 1);

4) Функциональные;

5) Инъективные;

6) Сюръективные;

7) Биективные;

Задача 7. B каких отношениях находятся между собой множества А, В, С?

Решение:

A= { 1,3} ;

B= {x ; x- нечетное число} ;

C= {x; x2 – 4x+3=0 };

B= {x; x- целое число };

C= {x; x2-7x+10=0 }.

  1. C= { x; x2 – 4x+3=0 }= {1,3};

A=c {1,3}={1,3}

AcB, C B

  1. A= {2,3}; B= { x- целое }

C= {x2-7x+10 }

A=CcB

Задача 8. Покажите, что из соотношения следует С A и C B.

Решение:

AB=C

xC x и xB xA

CcA, аналогично CcB

( xA и xB )= U xA=U и xB=U

Задача 9. Равны ли между собой множества А и В (если нет, то почему?)

  1. A= { 1, (2,5), 6 }, B= { 1,2,5,6 };

  2. A= { 2,4,5 }, B= { 5,2,4} ;

  3. A= { 1,2,4,2 }, B= { 1,2,4};

  4. A= { 2,4,5 }, B= { 2,4,5};

  5. A= { 1,2,2,5,6 }, B= 1, { 5,2}, 6 };

  6. A= {1, {2,7}, 8}, B= {1, (2,7), 8 }.

Решение:

  1. не равны ; |A|=3; |B|=4;

  2. равны;

  3. не равны ; содержат два одинаковых элемента;

  4. не равны, так как не равны между собой последние элементы множества;

  5. равны;

  6. не равны;

Задача 10. Записать в виде теоретико-множественных соотношений следующие утвержде­ния:

a) среди деталей первого узла имеются все пластмассовые детали;

b) одинаковый детали, входящие в оба узла могут быть только пластмассовы­ми;

c) во втором узле нет пластмассовых деталей. При записи учесть, что M1 и М2, соответственно, множества деталей 1-го и 2-го узла, А – множество пластмассовых деталей.

Решение:

а) А  M1.

b) M1  М2  А.

c) А  М2 = 

Задача 11. Указать области определения и значения для соответствия "Больше", если А = {2,4,6}; B={1,4,6,7}?

Решение:

D(S) = {2, 4, 6}

Im(S) = {4, 6, 7}

Задача 12. Представьте в виде композиции функций следующую функцию:



Решение:

F(x) = (1+(x/(1-x))2)1/2

F(x) = F1(F2(F3))

F(x) = (1+ F2 (x2))1/2

F(x) = (F1 (F2))1/2 = F3 (F1 (F2 (x)))

Задача 20. На факультете 287 студентов. Из них 19 не сдали математику, 17 - физику, 11 - программирование, 12 студентов не сдали математику и физику, 7 - математику и программирование, 5 - физику и программирование; 237 сдали математику, физику, программирование. Сколько студентов безуспешно (т.е. не сдавшие 3-й экзамена) закончили сессию ?



Рисунок 2

U = 287

M = 19

Ф = 17

П = 11

М /\ Ф = 12

М /\ П = 7

Ф /\ П = 5

М \/ Ф \/ П = 237

М /\ Ф /\ П - ?

Решение:

U = (М \/ Ф \/ П) \/ М \/ Ф \/ П \ (М /\ Ф) \ (М /\ П) \ (Ф /\ П) \/ (М /\ Ф /\ П)

М /\ Ф /\ П = U \/ (М /\ Ф) \/ (М /\ П) \/ (Ф /\ П) \ М \ Ф \ П \ (М \/ Ф \/ П)

М /\ Ф /\ П = 287 +12 + 7 + 5 – 19 – 17 – 11 – 237 = 27

Задача 21. Найти число способов распределения студенческой группы из 23 человек на бригады по 3 и 5 человек.

Решение:

Можно поделить группу на бригады из 3 и 5 человек только двумя способами:

а) 4 группы по 5 человек и одна группа по 3 человека.

б) 1 группа из 5 человек и 6 групп по 3 человека.

По отдельности:






^

Алгебра логики


Задача 1. Упростить уравнение.

Решение:



Задача 2. Упростить уравнение.

Решение:



Задача 3. Упростить уравнение.

Решение:



Задача 5. Доказать, что

Решение:

x | y ||||| |

0 | 0 | 1 | 1 | 0 | 1 | 0 |

0 | 1 | 1 | 0 | 0 | 1 | 0 |

1 | 0 | 0 | 1 | 0 | 1 | 0 |

1 | 1 | 0 | 0 | 1 | 0 | 1 |

Как видно из таблиц истинности, приведенных выше равно

Задача 6. Доказать свойство отрицания

Решение:

x | 1 | |

0 | 1 | 1 |

0 | 1 | 1 |

1 | 1 | 1 |

1 | 1 | 1 |
x | | |

0 | 1 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 0 | 0 |

Задача 10. Доказать, что 2.10 Сколько имеется различных наборов длины n?

Решение:

Количество комбинаций n для функции c N аргументами равно 2N

Задача 11. Сколько имеется различных формул алгебраической логики от n переменных?

Решение:

Количество разных функций с N аргументами равно 22n

Задача 12. Сколько имеется различных К-местных предикатов на множестве M = n объектов?

Предикат: функция определенная на n-ой декартовой степени множества M.

Решение:

Если предикат k-местный, то он использует k элементов из множества М => Количество всех предикатов равно Mk

Задача 13. Сколько имеется различных Функций алгебры логики от n переменных?

Решение:

Число ф-ций алгебры логики от n переменных

|P2(n)|=2^(2^n)

P2 (n) – мн-во всех лог ф-ций от n переменных

Синтезируйте принципиальную схему работы лифта в трех этажном здании. Три состояния лифта соответствуют его пребыванию на этажах. Входами являются кнопки на этажах, а также сигнал, что ни одна из кнопок не нажата. Выходами схемы являются сигналами "вверх", "вниз" и "остановка". При отсутствии команд лифт должен двигаться на первый этаж.

Решение на рисунке 3.



Рисунок 3

Задача 23. Синтезировать принципиальную схему блока управления индикацией правильности ответов студентов, если:

- задаются пять вопросов, требующих установить истинность или ложность определенных утверждений;

- экзаменуемый отвечает, нажимая кнопки, соответствующие тем вопросам, на которые хочет дать ответ "истина";

- схема зажигает элемент индикации, соответствующий поставленному вопросу, при нажатии кнопки;

схема индицирует правильное число ответов.

Решение на рисунке 4.



Рисунок 4

Задача 30. Реализовать релейно-контактными схемами функции:

; ; .

Решение:

(рис. 5)


Рисунок 5

(рис. 6)



Рисунок 6

(рис. 7)



Рисунок 7
^

Теория графов


Задача 25. В каких случаях биекция множества |М|=7 является:

а) Циклом длины 7;

б) Двумя циклами длин 3 и 4;

в) Тремя циклами длин 1, 2, 4.

Решение:



Рисунок 8

Задача 27. Вычислить количество различных деревьев на множестве вершин при n=15.

Решение:

Пусть дано n пронумерованных вершин. Тогда количество деревьев на этих вершинах равняется n^(n-2).

n=15; Nдеревьев=15^(15-2) = 15^13.

Задача 34. Построить дерево по символу: Т=(7,4,4,8,2,2,2,5)

Решение:

Символ T отображает дерево с числом вершин |v| на 2 больше, чем * чисел в символе.

N=<1,2,3,4,5,6,7,8,9,10>

Алгоритм Пруффера:

  1. Находим наименьшее число натурального ряда N={1,2,3, ... , |v|}, которое не встречается в символе T

  2. Найденный номер вершины соединяем ребром с вершиной, которая записана в символе дерева первой.

  3. Удаляем номер найденной вершины в пункте 1) из натурального ряда и первый номер из символа.

  4. Повторяем последовательность 1-3. Пары чисел, оставшиеся в натуральном ряде, являются ребром искомого дерева.



Рисунок 9

Задача 35. Постройте символ дерева (рис. 10):



Рисунок 10

Решение:

По алгоритму Пруффера получим:

T=(2,2,4,4,6,6,6)

г. Москва

2008 год

Добавить документ в свой блог или на сайт

Похожие:

Задача 1 iconЗадача 1 22 Вариант 3 22 Задача 1 22 Вариант 4 23 Задача 1 23 Задача...
«Менеджмент». Дисциплина реализуется кафедрой экономики и управления. Дисциплина нацелена на формирование общекультурных компетенций...

Задача 1 iconУчебник По Математике и Ествознанию
Потому что в нашем учебнике будут задания разных сложностей для изучения,а конкретнее лёгкая задача, нормальная задача, !-сложная...

Задача 1 iconЗадача Дополнительное образование детей. Задача Культурно-досуговая...
«Культура Конды на 2011-2013 годы и на период до 2015 года» утверждена постановление администрации Кондинского района от 26 июня...

Задача 1 iconЗадача 10
Задача 1 Пусть в универсальном множестве заданы три непустые взаимно пересекающихся множества,, следующим образом

Задача 1 iconЗадача Вставь пропущенные знаки действий «+» или «-»
Задача Поставь между некоторыми цифрами знак «+» так, чтобы получилось верное равенство

Задача 1 iconТема: Игра-драматизация сказки «Теремок» Развивающая задача
Развивающая задача: Развивать умение имитировать характерные действия персонажей

Задача 1 iconВариант 4 Микроэкономика Задача 1
Задача Дана кривая спроса: Qd = 200 – 4P, кривая предложения: qs = 60 + 3P. Найти равновесный объем и равновесную цену

Задача 1 iconЗадача 11
Задача рдс I типа болезнь гиалиновых мембран. Соп: Гипоксическое поражение цнс III, острый период, синдром угнетения. Недоношенность:...

Задача 1 iconДоктор фаустус
Иными словами, посильна ли человеку моего склада эта задача, задача, на выполнение которой меня подвигло скорее сердце, нежели право...

Задача 1 iconЗадача планирования производства продукции (на максимизацию)
Задачей линейного программирования (злп) называется задача отыскания экстремума (максимума или минимума) линейной функции от нескольких...



Школьные материалы
Загрузка...


При копировании материала укажите ссылку © 2018
контакты
top-bal.ru

Поиск