.RU

Решение. Решение задачи осуществим с помощью диа­граммы Эйлера-Венна (рис. 5)


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


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 будет дизъюнкция двух высказываний: (А→С) В и .

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

A

C

B

A→C

(A→C)B



A↔



S

1

1

1

1

1

0

0

1

1

1

1

0

1

0

1

1

0

0

1

0

1

0

0

0

0

1

1

1

0

0

0

0

1

1

0

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

0

1

1

1

0

1

0

1

0

0

0

1

0

1

0

1

1


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

А)



Применим дистрибутивный закон



По закону исключения третьего



По закону идемпотентности пересечение множества с общим множеством дает это же множество



Б)

















В)























Г)







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





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



А

В







0

0

1

1

0

0

1

1

1

0

1

0

0

0

1

1

1

0

0

1


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

=

в) =

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





^ 8. Получить СДНФ, а затем перейти к СКНФ

.

≡ ≡ ≡

≡ ≡ ≡ ≡ .

СКНФ - ≡ ≡ ≡ ≡ ≡

≡ ≡ ≡

.

^ 9. Построить (синтезировать) автомат по содержательному описанию.

1.10. Автомат выдает сигнал 1, если на вход поступит слово МАМА, сигнал 2, если поступит слово МАМАЛЫГА, и 0 во всех остальных случаях. Слова отделяются друг от друга пробелами.






Q0

Q1

Q2

мама

0

0

0

лыга

0

0

0

« «

0

1

2

Х

0

0

0

«х«/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.).



Х3


а) б) в)






Х1

Х2

Х3

Х4

Х5

Х1

0

1

0

0

0

Х2

1

0

1

0

0

Х3

0

1

0

1

0

Х4

0

0

1

0

1

Х5

0

0

0

1

0
а)матрица инцидентности матрица смежности






Е1

Е2

Е3

Е4

Х1

1

0

0

0

Х2

1

0

0

1

Х3

0

0

1

1

Х4

0

1

1

0

Х5

0

1

0

0



б)матрица инцидентности матрица смежности





Х1

Х2

Х3

Х4

Х5

Х1

0

1

0

0

0

Х2

1

0

1

0

0

Х3

0

1

0

1

0

Х4

0

0

1

0

1

Х5

0

0

0

1

0







Е1

Е2

Е3

Е4

Х1

1

0

0

0

Х2

1

1

0

0

Х3

0

1

1

0

Х4

0

0

1

1

Х5

0

0

0

1



в)матрица инцидентности матрица смежности





Х1

Х2

Х3

Х4

Х5

Х1

0

1

0

0

0

Х2

0

0

0

0

0

Х3

0

1

0

0

0

Х4

0

0

1

0

0

Х5

0

0

0

1

0







Е1

Е2

Е3

Е4

Х1

-1

0

0

0

Х2

+1

+1

0

0

Х3

0

-1

+1

0

Х4

0

0

-1

+1

Х5

0

0

0

-1



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




1

2

3

4

5

1







1







2










1




3













1

4

1













5




1











(1v3)(1v4)(2v4)(2v5)(3v5)

Перейдем к ДНФ

123v125v145v234v345

Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.

{4,5},{3,4},{2,3},{1,5},{1,2}

2.Найдем множества внешней устойчивости:




1

2

3

4

5

1

1




1







2




1




1




3







1




1

4

1







1




5




1







1

(1v3)(2v4)(3v5)(1v4)(2v5)

Перейдем к ДНФ

123v125v145v234v345

{1,2,3}{1,2,5},{1,4,5},{2,3,4},{3,4,5}


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

soderzhanie-razdelov-uchebnoj-programmi-akademicheskij-kalendar-studenta-ii-kursa-lechebnij-fakultet.html
soderzhanie-razvivayushego-aspekta-osnovnaya-obrazovatelnaya-programma-nachalnogo-obshego-obrazovaniya-na-20112012.html
soderzhanie-referat-stranica-3.html
soderzhanie-rolan-bart-izbrannie-raboti-semiotika-poetika.html
soderzhanie-samostoyatelnoj-raboti-i-forma-kontrolya-po-temam-disciplini.html
soderzhanie-setevogo-novostnogo-teksta-xiii-j-regionalnoj-nauchno-prakticheskoj-konferencii-s-mezhregionalnim-i.html
  • control.bystrickaya.ru/doklad-glavnogo-vracha-cgsen-v-primorskom-krae-na-soveshanii-stranica-2.html
  • bukva.bystrickaya.ru/razdel-5-pokazateli-harakterizuyushie-administraciya-goroda-novij-urengoj-postanovlenie.html
  • composition.bystrickaya.ru/polnoe-sobranie-russkih-letopisej-stranica-37.html
  • testyi.bystrickaya.ru/68-mezhdunarodnih-vstrech-i-sovmestnih-konsultacij.html
  • literatura.bystrickaya.ru/smichka-polyusov.html
  • laboratornaya.bystrickaya.ru/rabochaya-programma-disciplina-organizaciya-predprinimatelskoj-deyatelnosti-naimenovanie-disciplini-soglasno-uchebnomu-planu.html
  • urok.bystrickaya.ru/pravila-povedeniya-podozrevaemih-i-obvinyaemih-vpovestku-rasshirennogo-zasedaniya-soveta-vklyucheni-sleduyushie-voprosi.html
  • learn.bystrickaya.ru/fizika-matematika-baitindai-nazarbaev-ziyatkerlk-mekteb-esse.html
  • kolledzh.bystrickaya.ru/4-trebovaniya-k-znaniyam-i-umeniyam-specialistov-vipolnyayushih-raboti-po-razrabotke-razdela-podgotovka-arhitekturnih-reshenij.html
  • upbringing.bystrickaya.ru/krasnoyarskoe-blagochinie.html
  • uchebnik.bystrickaya.ru/usilitel-radiorelejnoj-linii-svyazi.html
  • abstract.bystrickaya.ru/1-zapolnite-tablicu-v-sootvetstvii-s-klassifikaciej-potrebitelskih-tovarovuslug.html
  • education.bystrickaya.ru/13-svedeniya-ob-auditore-auditorah-emitenta-125047-rossiya-g-moskva-4-j-lesnoj-pereulok-dom-4-informaciya.html
  • teacher.bystrickaya.ru/glava-12-vsegda-nosite-nechto-kak-govorit-s-kem-ugodno-i-o-chem-ugodno-naviki-uspeshnogo-obsheniya-i-tehnologii.html
  • znaniya.bystrickaya.ru/raschyot-i-analiz-pokazatelej-vipolneniya-plana-raboti-i-ispolzovaniya-podvizhnogo-sostava-dorogi.html
  • apprentice.bystrickaya.ru/vliyanie-osushitelnih-sistem-na-prirodu-prilegayushih-territorij.html
  • student.bystrickaya.ru/-2-krug-zadach-prikladnoj-lingvistiki-a-n-baranov-vvedenie-v-prikladnuyu-lingvistiku.html
  • studies.bystrickaya.ru/kompleksnaya-mehanizaciya-stf-s-razrabotkoj-linii-ventilyacii-i-otopleniya-chast-5.html
  • knowledge.bystrickaya.ru/multiplikaciya-k-uchebniku.html
  • paragraf.bystrickaya.ru/xviii-vserossijskaya-nauchno-tehnicheskaya-konferenciya-nerazrushayushij-kontrol-i-tehnicheskaya-diagnostika-analiz-i-osnovnie-itogi.html
  • essay.bystrickaya.ru/diplomnaya-rabota-tema-razrabotka-razdelov-biznes-plana-investicionnogo-proekta-po-proizvodstvu-profnastila-na-baze-umts-zao-ak-alrosa.html
  • institute.bystrickaya.ru/glava-11-pri-lechenii-raka-nelzya-pomogat-yadam-drugimi-lekarstvennimi-travami-i-sredstvami.html
  • abstract.bystrickaya.ru/12eko-effektivnost-kriterii-i-metodi-ocenki-nacionalnij-otchet-po-ispolzovaniyu-instrumentov-zelenogo-rosta.html
  • knigi.bystrickaya.ru/rekonstrukcii-proizvoditelnih-sil-i-socialnoj-strukturi-obshestv-paleolita-i-mezolita-po-materialam-predaltajskoj-chasti-zapadnoj-sibiri.html
  • tetrad.bystrickaya.ru/uchebnik-trete-izdanie-stranica-7.html
  • tetrad.bystrickaya.ru/v-v-nabokov-fedor-dostoevskij-lekcii-po-russkoj-literature-m-2001g-s-175-220-belinskij-v-pisme-k-gogolyu-1847-pisal-vi-ne-zametili-chto-rossiya-stranica-3.html
  • kanikulyi.bystrickaya.ru/xix-mezhdunarodnaya-nauchno-tehnicheskaya-konferenciya-po-fotoelektronike-i-priboram-nochnogo-videniya-23-26-maya-2006-stranica-6.html
  • education.bystrickaya.ru/2-stepen-nauchnoj-razrabotannosti-temi-anarho-individualizm-v-srede-otechestvennoj-intelligencii-vtoroj-polovini.html
  • institut.bystrickaya.ru/tema-10-ekonomicheskij-rost-i-ciklicheskie-kolebaniya-programma-kursa-ekonomicheskaya-teoriya.html
  • studies.bystrickaya.ru/frejya-asvinn-misterii-i-magiya-severa-runi-i-zhenskaya-sila-stranica-5.html
  • writing.bystrickaya.ru/7-sposobov-zaryadit-mobilnij-telefon-v-doroge.html
  • notebook.bystrickaya.ru/kniga-predstavlyaet-soboj-sbornik-ocherkov-o-naibolee-tyazhelih-katastrofah-na-more-za-poslednie-dva-veka-napisannaya-populyarno-ona-podrobno-osveshaet-takie-temi-stranica-15.html
  • knigi.bystrickaya.ru/sina-artillerista-iz-poemi-k-simonova.html
  • esse.bystrickaya.ru/radiorazvedka-vo-vremya-vtoroj-mirovoj-vojni-vnimanie-vknige-mogut-vstrechatsya-sushestvennie-oshibki-v-risunkah.html
  • grade.bystrickaya.ru/mozhno-mnogoe-uvidet-vsego-lish-nablyudaya-t-i-kurmanaliev-posvyashaetsya-90-letiyu-sluzhbi.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.