.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
  • knigi.bystrickaya.ru/rim-bilalovich-ahmedov-odolentrava-stranica-23.html
  • write.bystrickaya.ru/finansirovanie-meropriyatij-programmi-osushestvlyat-v-predelah-sredstv-predusmotrennih-zakonom-voronezhskoj-oblasti-ob-oblastnom-byudzhete-stranica-4.html
  • lektsiya.bystrickaya.ru/prakticheskaya-znachimost-issledovaniya-filosofskie-problemi-genezisa-strukturi-i-soderzhaniya-sovremennoj-evolyucionnoj-teorii.html
  • shpora.bystrickaya.ru/zayavlenie-igorya-shuvalova-o-tom-chto-chinovniki-zasedayushie-v-sovetah-direktorov-goskompanij-dolzhni-ustupit-mesto-nechinovnikam-vizvalo-nemalij-entuziazm.html
  • crib.bystrickaya.ru/izderzhki-predpriyatiya-v-kratkosrochnom-i-dolgosrochnom-periode-chast-2.html
  • college.bystrickaya.ru/144-prognozirovanie-na-osnove-krivih-rosta-posobie-podgotovleno-kollektivom-prepodavatelej-kafedri-teorii.html
  • notebook.bystrickaya.ru/kalendarno-tematicheskoe-planirovanie-na-uchebnij-god-20092010-fizika7-klassperishkin-a-v-fizika-7-kl.html
  • bukva.bystrickaya.ru/socialnij-status-semi-obshih-rekomendacij-po-podgotovke-publichnih-dokladov-regionalnih-municipalnih-organov.html
  • lektsiya.bystrickaya.ru/postanovlenie-soveta-ministrov-respubliki-belarus.html
  • notebook.bystrickaya.ru/ii-kezen-badarlamasi-26-nauriz-2015zh.html
  • literature.bystrickaya.ru/byulleten-serii-ekologiya-ekonomika-bezopasnost-30-avtomatizirovannaya-sistema-monitoringa-vzveshennih-veshestv-v-atmosfernom-vozduhe.html
  • thescience.bystrickaya.ru/klubok-zmej-kniga-predstavlyaet-soboj-zapis-faktov-sobitij-vospominanij-i-razmishlenij-naveyannih-rabotoj-v-chernobilskoj.html
  • learn.bystrickaya.ru/glava-5-prolog.html
  • zanyatie.bystrickaya.ru/mezhdunarodnoe-sotrudnichestvo-regionov-evropejskogo-severa-s-zarubezhnimi-gosudarstvami-regiona-barencevo-morya.html
  • uchit.bystrickaya.ru/trebovaniya-k-urovnyu-podgotovki-vipusknikov-trebovaniya-k-urovnyu-podgotovki-po-matematike-vipusknikov-starshej-shkoli-virazheniya-i-ih-preobrazovaniya.html
  • assessments.bystrickaya.ru/doklad-zdorovesberegayushie-tehnologii-v-nachalnoj-shkole.html
  • credit.bystrickaya.ru/otkritie-profilnie-shkoli-informacionnie-tehnologii-v-profilnom-obuchenii.html
  • grade.bystrickaya.ru/novoe-gosudarstvo-izrail-vizhivet-stranica-9.html
  • control.bystrickaya.ru/doklad-osnovnie-dostizheniya-medicinskoj-nauki-2009-goda-stranica-13.html
  • testyi.bystrickaya.ru/bektld-kegoc-a-direktorlar-keesn.html
  • letter.bystrickaya.ru/metodika-sostavleniya-otcheta-o-dvizhenii-denezhnih-sredstv.html
  • composition.bystrickaya.ru/podsoedinenie-ustrojstv-hdmi-razemi-hdmi-ustrojstvo-radiopriemnoe-marantz-s-r50-04sr6004-rukovodstvo-po-ekspluatacii.html
  • assessments.bystrickaya.ru/doklad-amurstat-b2009-153s.html
  • uchit.bystrickaya.ru/spravochnoe-posobie-k-snip-23-01-99-udk-69-551-58035-stranica-10.html
  • znaniya.bystrickaya.ru/programma-s-izucheniem-anglijskogo-yazika-i-prozhivaniem-s-ekskursiyami-vstoimost-2-h-nedelnoj-programmi-vklyucheno-40-urokov.html
  • letter.bystrickaya.ru/moskva-sankt-peterburg-nizhnij-novgorod-voronezh-rostov-na-donu-ekaterinburg-samara-novosibirsk-kiev-harkov-minsk-stranica-8.html
  • doklad.bystrickaya.ru/v-razdele-v3-reinkarnaciya-idei-sada-v-postsimvolistskuyu-epohu-sad-v-russkoj-poezii-hh-veka-fenomen-kulturnoj-pamyati.html
  • control.bystrickaya.ru/cvekla-kartofel-morkov-ogurci-marinovannie-ogurci-svezhie-goroshek-konservirovannij-maslo-rastitelnoe.html
  • paragraf.bystrickaya.ru/zapove-d-stranica-34.html
  • literatura.bystrickaya.ru/s-vvedeniem-krepostnichestva-na-pravoberezhe-naselenie-nachalo-ubegat-ottuda-na-levoberezhe.html
  • ucheba.bystrickaya.ru/programma-dopolnitelnogo-professionalnogo-obrazovaniya-po-napravleniyu.html
  • zanyatie.bystrickaya.ru/princip-ekvivalentnosti-i-zakoni-sohraneniya.html
  • learn.bystrickaya.ru/glava-6-lechenie-vegetososudistoj-distonii-andrej-kurpatov-sredstvo-ot-vegetososudistoj-distonii-predislovie.html
  • laboratornaya.bystrickaya.ru/rabochaya-programma-disciplini-obshaya-teoriya-izmerenij-specialnost-072000-standartizaciya-i-sertifikaciya.html
  • thescience.bystrickaya.ru/hristianskij-spravochnik-po-apologetike-stranica-19.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.