.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
  • uchenik.bystrickaya.ru/grazhdanskij-pravoj-dogovor-chast-6.html
  • prepodavatel.bystrickaya.ru/tema-9-ekspertiza-affekta-2-chasa-programma-i-metodicheskie-ukazaniya-dlya-studentov-zaochnoj-formi-obucheniya-po.html
  • zadachi.bystrickaya.ru/realizaciya-norm-federalnogo-zakona-o-nesostoyatelnosti-bankrotstve.html
  • letter.bystrickaya.ru/o-kodeksa-tamozhennogo-soyuza-tk-ts-s-01-07-2010.html
  • shpargalka.bystrickaya.ru/voprosi-i-prakticheskie-zadaniya-dlya-konkursov-podgotovili-n-n-naplekova-d-r-biol-nauk-professor-zav-kafedroj-agroekologii-i-mikrobiologii-novosibirskogo-gau.html
  • textbook.bystrickaya.ru/karelskij-kadetskij-korpus-imeni-aleksandra-nevskogo.html
  • lecture.bystrickaya.ru/74-raschet-parametrov-tehnologicheskogo-cikla-harakteristika-rajona-i-mestorozhdeniya-11.html
  • knigi.bystrickaya.ru/sistema-obrazovaniya-chitinskoj-oblasti-pervaya-versiya-ezhegodnogo-analiticheskogo-doklada-chita-2006.html
  • znaniya.bystrickaya.ru/rabochaya-uchebnaya-programma-disciplini-upravlenie-personalom-napravlenie-podgotovki-210100.html
  • studies.bystrickaya.ru/internet-resursi-mayak-novosti-16-01-2006-bejlin-boris-21-00-20.html
  • tasks.bystrickaya.ru/2-doklad-novie-podhodi-k-lekarstvennomu-lecheniyu-melanomi-k-m-n-a-v-novik.html
  • control.bystrickaya.ru/delo-42-starikashka-edelvejs-skazka-o-trojke-2-niichavo-3-skazka-o-trojke-2.html
  • knowledge.bystrickaya.ru/o-dostignutih-znacheniyah-pokazatelej-dlya-ocenki-effektivnosti-deyatelnosti-organov-mestnogo-samoupravleniya-beloyarskogo-rajona-za-2009-god-i-ih-planiruemih-znacheniyah-na-3-letnij-period.html
  • klass.bystrickaya.ru/8-vliyanie-psihologicheskih-i-fizicheskih-faktorov-e-e-lalayan-glavnij-redaktor-izdatelstva-doktor-ekonomicheskih-nauk.html
  • college.bystrickaya.ru/-grani-sotrudnichestva-administracii-stolici-yakutii-i-merii-moskvi-informacionnij-byulleten-mestnogo-samoupravleniya.html
  • thesis.bystrickaya.ru/prichinnost-i-karma-v-buddizme-stranica-10.html
  • portfolio.bystrickaya.ru/organizacionnie-osnovi-postroeniya-apparata-upravleniya-banka.html
  • turn.bystrickaya.ru/pasport-federalnoj-celevoj-programmi-zhilishe-na-2011-2015godi-naimenovanie-programmi.html
  • prepodavatel.bystrickaya.ru/tema-uroka-chislennost-naseleniya-rossii.html
  • credit.bystrickaya.ru/perednij-kraj-v-obrazovanii-innovacii-v-metodah-i-tehnologiyah.html
  • school.bystrickaya.ru/istoriya-muzikoznaniya-bonfeld-msh-2-189-00-378-00-100-velikih-muzeev-mira-ionina-n-a.html
  • pisat.bystrickaya.ru/the-weekly-pulse-5-11-02-2010-a-new-decade-a-new-economic-growth-and-new-opportunities-for-kazakhstan-address-of-president-of-the-republic-of-kazakhstan-n-stranica-2.html
  • esse.bystrickaya.ru/rasskazi-hozyajki-muzeya-pro-les-i-ego-zhitelyah-nikogo-ne-ostavit-ravnodushnim.html
  • bukva.bystrickaya.ru/ocenka-dinamiki-sochetannoj-luchevoj-i-himioterapii-raka-molochnoj-zhelezi-po-rezultatam-rentgenomammografii-i-uzi.html
  • thesis.bystrickaya.ru/proektnaya-deklaraciya-zastrojshika-ooo-orion.html
  • grade.bystrickaya.ru/mihalevag-v-evolyuciya-mediaobrazovaniya-v-velikobritanii-tekst-g-v-mihaleva-integraciya-obrazovaniya-2-51-2008-s-70-75.html
  • reading.bystrickaya.ru/kontrolnaya-kartaprovedeniya-inspekcionnogo-kontrolya-gruzovogo-salona-i-raboti-bortoperatorovsoglasno-zadaniyu-n.html
  • crib.bystrickaya.ru/itogovaya-kontrolnaya-rabota-po-biologii-za-kurs-11-klassa.html
  • esse.bystrickaya.ru/razvitie-sfer-deyatelnosti-gorod-orenburg.html
  • write.bystrickaya.ru/g-v-volkova-takoj-abvgdezhzijklmnoprstufhcchshshieyuya-stranica-12.html
  • zadachi.bystrickaya.ru/n-a-artyomova-zamestitel-nachalnika-otdela-obrazovaniya.html
  • testyi.bystrickaya.ru/administrativnij-reglament-predostavleniya-municipalnoj-uslugi-stranica-2.html
  • shpora.bystrickaya.ru/vtoroj-posle-uembli-k-cvetam-bashkirii-podsadyat-kompleks-7-vyacheslav-dudka-vstretilsya-s-rukovodstvom-federacii.html
  • grade.bystrickaya.ru/mezhdunarodnaya-nauchno-prakticheskaya-konferenciya-g-ulyanovsk-rossiya-11-12-oktyabrya-2011g.html
  • essay.bystrickaya.ru/doneckij-nacionalnij-tehnicheskij-universitet-stranica-9.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.