.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
  • prepodavatel.bystrickaya.ru/tematicheskij-plan-lekcij-i-prakticheskih-zanyatij-po-farmakologii-v-vsemestre-dlya-farmacevticheskogo-fakulteta-ochnoe-obuchenie-.html
  • kontrolnaya.bystrickaya.ru/rabochie-programmi-uchebnih-kursov-predmetov-disciplin-modulej-otchyot-o-rezultatah-samoobsledovaniya-municipalnogo.html
  • urok.bystrickaya.ru/prikaz-ministerstva-finansov-rf-ot-2-iyulya-2010-g-66n-o-formah-buhgalterskoj-otchyotnosti-organizacij-prikaz.html
  • university.bystrickaya.ru/ganimed-paradoks-sovremennoj-astronomii-sostoit-v-udivitelno-nizkom-urovne-znanij-o-nashem-sobstvennom-dome-solnechnoj.html
  • lektsiya.bystrickaya.ru/pravitelstvo-respubliki-bashkortostan-postanovlenie-ot-3-marta-2010-g-n-64-o-respublikanskoj-programme-razvitiya-subektov-malogo-i-srednego-predprinimatelstva-v-respublike-bashkortostan-na-2010-2011-godi-stranica-2.html
  • write.bystrickaya.ru/glava-chetvertaya-kniga-bitiya.html
  • shpargalka.bystrickaya.ru/uchebno-metodicheskij-kompleks-detskaya-horovaya-literatura-dlya-studentov-specialnosti-070105-65-dirizhirovanie-akademicheskim-horom-poyasnitelnaya-zapiska.html
  • textbook.bystrickaya.ru/itogi-socialno-ekonomicheskogo-razvitiya-tyumenskogo-municipalnogo-rajona.html
  • klass.bystrickaya.ru/annotaciya-k-rabochej-programme-disciplini-latinskij-yazik-i-osnovi-terminologii-po-specialnosti-060100-65.html
  • university.bystrickaya.ru/glava-4-svet-na-poroge-mihalkov-m-v-dva-brata-dve-sudbi-mihalkov-s-v-mihalkov-m-v-dva-brata-dve-sudbi-memuari.html
  • kolledzh.bystrickaya.ru/63logicheskie-osnovi-postroeniya-evm-1-emkost-zhestkogo-diska-informatizaciya-obshestva.html
  • reading.bystrickaya.ru/krioterapiya-i-ee-vozmozhnosti-sovremennoe-oborudovanie-dlya-obshej-i-lokalnoj-krioterapii.html
  • spur.bystrickaya.ru/metodicheskie-rekomendacii-po-izucheniyu-kursa-ekonomika.html
  • predmet.bystrickaya.ru/sabati-tairibi-natural-sandardi-blngshtk-belgler-tairibin-ajtalauaa-esepter-shiaru-slteme.html
  • thesis.bystrickaya.ru/prilozhenie-17-struktura-otcheta-ob-issledovanii-bezopasnosti-lekarstvennogo-sredstva-razreshennogo-k-medicinskomu-primeneniyu-v-kirgizskoj-respublike.html
  • uchit.bystrickaya.ru/totem-i-tabu-psihologiya-pervobitnoj-kulturi-i-religii-zigmund-frejd-stranica-2.html
  • literatura.bystrickaya.ru/s-v-baeva-po-micelialnim-gribam-stranica-19.html
  • nauka.bystrickaya.ru/uchebno-metodicheskij-kompleks-po-discipline-metodika-prepodavaniya-matematiki-specialnost-05070-stranica-14.html
  • znaniya.bystrickaya.ru/rabochaya-programma-disciplini-tamozhennoe-delo-dlya-specialnosti-050509-finansi-forma-obucheniya-dnevnaya.html
  • uchit.bystrickaya.ru/stroitelnie-trebovaniya-tehnicheskie-specifikacii-razrabotani-na-osnove-dejstvuyushih-normativnih-dokumentov.html
  • uchebnik.bystrickaya.ru/uchebno-metodicheskij-kompleks-disciplini-ds-v-sociologiya-yazika-kod-i-nazvanie-disciplini-po-uchebnomu-planu-specialnosti.html
  • school.bystrickaya.ru/glava-2-analiz-strategii-razvitiya-kf-saratovskaya-teoreticheskie-osnovi-strategicheskogo-planirovaniya-na-predpriyatii.html
  • nauka.bystrickaya.ru/ustrojstva-ric-25-princip-izmereniya-smesheniya-udk-621-317528-08-informacionno-izmeritelnaya-i-upravlyayushaya.html
  • control.bystrickaya.ru/doklad-mitropolita-smolenskogo-i-kaliningradskogo-kirilla-na-konferencii-razvitie-biotehnologij-vizovi-hristianskoj-etike.html
  • studies.bystrickaya.ru/12-vidi-formi-i-sistemi-oplati-truda-diplomnaya-rabota.html
  • institut.bystrickaya.ru/tema-1-gosudarstvennoe-konstitucionnoe-pravo-rossijskoj-federacii-rabochaya-programma-disciplini-konstitucionnoe-pravo.html
  • teacher.bystrickaya.ru/glava-13-revelation.html
  • studies.bystrickaya.ru/issledovanie-dokumentov.html
  • predmet.bystrickaya.ru/specialist-v-ugolovnom-sudoproizvodstve.html
  • znanie.bystrickaya.ru/6-astronomicheskaya-datirovka-novih-antichnih-zodiakov-nedavno-popavshih-v-nashe-pole-zreniya-stranica-4.html
  • apprentice.bystrickaya.ru/zadachi-po-grazhdanskomu-pravu-4.html
  • university.bystrickaya.ru/glava-2-kak-pisat-novosti-uchebnoe-posobie-izd-8685-isbn-978-5-211-05510-0-izdatelstvo-moskovskogo-universiteta-2008.html
  • uchenik.bystrickaya.ru/biografiya-i-tvorchestvo-arhitektora-filippo-brunelleski.html
  • apprentice.bystrickaya.ru/valyutno-fnansov-operac-chast-3.html
  • crib.bystrickaya.ru/ispolzovanie-informacionnih-tehnologij-dlya-sbora-sociologicheskoj-informacii.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.