Примеры дискретная математика – Страница не найдена | Алматинский филиал Санкт-Петербургского Гуманитарного университета профсоюзов

ДИСКРЕТНАЯ МАТЕМАТИКА • Большая российская энциклопедия

ДИСКРЕ́ТНАЯ МАТЕМА́ТИКА, раз­дел ма­те­ма­ти­ки, изу­чаю­щий свой­ст­ва дис­крет­ных струк­тур, ко­то­рые воз­ни­ка­ют как в са­мой ма­те­ма­ти­ке, так и в её при­ло­же­ни­ях. При этом дис­крет­ны­ми струк­ту­ра­ми на­зы­ва­ют­ся объ­ек­ты, для ко­то­рых важ­ней­шие ха­рак­те­ри­сти­ки при­ни­ма­ют ко­неч­ное или счёт­ное чи­сло зна­че­ний. К чис­лу та­ких струк­тур от­но­сят­ся, напр., ко­неч­ные груп­пы, ко­неч­ные гра­фы, не­ко­то­рые ма­те­ма­тич. мо­де­ли пре­об­ра­зо­ва­те­лей ин­фор­ма­ции, ко­неч­ные ав­то­ма­ты, Тью­рин­га ма­ши­ны. Это при­ме­ры струк­тур фи­нит­но­го (ко­неч­но­го) ха­рак­те­ра. Часть Д. м., изу­чаю­щая их, ино­гда на­зы­ва­ет­ся ко­неч­ной ма­те­ма­ти­кой. По­ми­мо фи­нит­ных струк­тур, Д. м. изу­ча­ет так­же дис­крет­ные бес­ко­неч­ные струк­ту­ры (напр., бес­ко­неч­ные ал­геб­ра­ич. сис­те­мы, бес­ко­неч­ные гра­фы, бес­ко­неч­ные ав­то­ма­ты).

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

Зна­чит. часть клас­сич. ма­те­ма­ти­ки за­ни­ма­ет­ся изу­че­ни­ем свойств объ­ек­тов не­пре­рыв­но­го ха­рак­те­ра. Ис­поль­зо­ва­ние дис­крет­ной или не­пре­рыв­ной мо­де­ли изу­чае­мо­го объ­ек­та свя­за­но как с са­мим объ­ек­том, так и с тем, ка­кие за­да­чи ста­вит пе­ред со­бой ис­сле­до­ва­тель. Са­мо де­ле­ние ма­те­ма­ти­ки на Д. м. и ма­те­ма­ти­ку, за­ни­маю­щую­ся не­пре­рыв­ны­ми мо­де­ля­ми, в зна­чит. ме­ре ус­лов­но, по­сколь­ку, с од­ной сто­ро­ны, про­ис­хо­дит об­мен идея­ми и ме­то­да­ми ме­ж­ду ни­ми, а с дру­гой – час­то воз­ни­ка­ет не­об­хо­ди­мость ис­сле­до­ва­ния мо­де­лей, об­ла­­даю­щих как дис­крет­ны­ми, так и не­пре­рыв­ны­ми свой­ст­ва­ми од­но­вре­мен­но. В ма­те­ма­ти­ке су­ще­ст­ву­ют раз­де­лы, ис­поль­зую­щие сред­ст­ва Д. м. для изу­че­ния не­пре­рыв­ных мо­де­лей (напр., ал­геб­раи­че­ская гео­мет­рия), и на­обо­рот, час­то ме­то­ды, раз­ви­тые для ана­ли­за не­пре­рыв­ных мо­де­лей, ис­поль­зу­ют­ся при изу­че­нии дис­крет­ных струк­тур (напр., асим­пто­ти­че­ские ме­то­ды в тео­рии чи­сел, в пе­ре­чис­ли­тель­ных за­да­чах ком­би­на­то­ри­ки). Од­на­ко спе­ци­фи­ка мн. раз­де­лов Д. м. свя­за­на с не­об­хо­ди­мо­стью от­ка­за от та­ких фун­дам. по­ня­тий клас­сич. ма­те­ма­ти­ки, как пре­дел и не­пре­рыв­ность, в свя­зи с чем для мн. за­дач Д. м. не­ко­то­рые ме­то­ды клас­сич. ма­те­ма­ти­ки ока­зы­ва­ют­ся не­при­ме­ни­мы­ми.

На­ря­ду с вы­де­ле­ни­ем Д. м. пу­тём ука­за­ния её пред­ме­та мож­но так­же опи­сать Д. м. пе­ре­чис­ле­ни­ем со­став­ляю­щих её час­тей. К ним от­но­сят­ся ком­би­на­тор­ный ана­лиз, гра­фов тео­рия, тео­рия ко­ди­ро­ва­ния, тео­рия функ­цио­наль­ных сис­тем, тео­рия управ­ляю­щих сис­тем, ав­то­ма­тов тео­рия, ал­го­рит­мов тео­рия. При бо­лее ши­ро­ком тол­ко­ва­нии к Д. м. мо­гут быть от­не­се­ны как це­лые раз­де­лы ма­те­ма­ти­ки, напр. ма­те­ма­тич. ло­ги­ка, так и час­ти та­ких раз­де­лов, как тео­рия чи­сел, ал­геб­ра, вы­чис­ли­тель­ная ма­те­ма­ти­ка, тео­рия ве­ро­ят­но­стей, в ко­то­рых изу­чае­мые объ­ек­ты име­ют дис­крет­ный ха­рак­тер.

Исторический очерк

Эле­мен­ты Д. м. воз­ник­ли в глу­бо­кой древ­но­сти; раз­ви­ва­ясь па­рал­лель­но с др. раз­де­ла­ми ма­те­ма­ти­ки, они яв­ля­лись их со­став­ной ча­стью. Ти­пич­ны­ми бы­ли за­да­чи, свя­зан­ные со свой­ст­ва­ми це­лых чи­сел, позд­нее эти за­да­чи при­ве­ли к соз­да­нию тео­рии чи­сел. При­ме­ры та­ких за­дач: оты­ска­ние ал­го­рит­мов сло­же­ния и ум­но­же­ния на­ту­раль­ных чи­сел у древ­них егип­тян, во­про­сы де­ли­мо­сти на­ту­раль­ных чи­сел и за­да­чи сум­ми­ро­ва­ния в пи­фа­го­рей­ской шко­ле, а в бо­лее позд­нее вре­мя – воп­ро­сы, свя­зан­ные с раз­ре­ши­мо­стью урав­не­ний в це­лых чис­лах. Этот этап раз­ви­тия Д. м. свя­зан с име­на­ми Дио­фан­та, Евли­да, Пифа­го­ра­ и Эрато­сфе­на­. В 17–18 вв., в осн. в свя­зи с иг­ро­вы­ми за­да­ча­ми, поя­ви­лись эле­мен­ты ком­би­на­тор­но­го ана­ли­за и дис­крет­ной тео­рии ве­ро­ят­но­стей, а в свя­зи с об­щи­ми про­бле­ма­ми тео­рии чи­сел, ал­геб­ры и гео­мет­рии в 18–19 вв. воз­ник­ли та­кие важ­ней­шие по­ня­тия ал­геб­ры, как груп­па, по­ле, коль­цо, оп­ре­де­лив­шие даль­ней­шее раз­ви­тие и со­дер­жа­ние ал­геб­ры и имев­шие, по су­ще­ст­ву, дис­крет­ную при­ро­ду. На про­тя­же­нии 17–19 вв. раз­ви­тие Д. м. свя­за­но с име­на­ми Н. 
Абеля
­, Э. Варин­га­, У. Гамиль­то­на­, Э. Га­луа, А. Кэли­, Ж. Лаг­ран­жа, А. Лежан­дра­, П. Фер­ма, Л. Эйле­ра­. В 19–20 вв. стрем­ле­ние к стро­го­сти ма­те­ма­тич. рас­су­ж­де­ний и ана­лиз ме­то­дов ма­те­ма­ти­ки при­ве­ли к вы­де­ле­нию ещё од­но­го раз­де­ла – ма­те­ма­тич. ло­ги­ки. В это вре­мя проб­ле­ма­ми Д. м. за­ни­ма­лись Л. Брау­эр, Дж. Буль, Н. Винер­, К. Гёдель­, Д. Гиль­берт, А. Чёрч, К. Шеннон­. В со­з­да­нии рос. шко­лы Д. м. участ­во­ва­ли И. М. Вино­гра­дов­, А. Н. Колмо­го­ров­, О. Б. Лупа­нов­ и С. В. Яблон­ский­.

Современные задачи дискретной математики

В 20 в. раз­ви­тие Д. м. оп­ре­де­ля­лось гл. обр. за­про­са­ми прак­ти­ки. Воз­ник­ла но­вая нау­ка – ки­бер­не­ти­ка и её тео­ре­тич. часть – ма­те­ма­тич. ки­бер­не­ти­ка, изу­чаю­щая ма­те­ма­тич. ме­то­да­ми раз­но­об­раз­ные про­бле­мы, ко­то­рые ста­вит пе­ред ки­бер­не­ти­кой прак­тич. дея­тель­ность че­ло­ве­ка. Ма­те­ма­тич. ки­бер­не­ти­ка яв­ля­ет­ся по­став­щи­ком идей и за­дач Д. м. Так, при­клад­ные во­про­сы, тре­бую­щие боль­ших вы­чис­ле­ний, сти­му­ли­ро­ва­ли по­яв­ле­ние и раз­ви­тие чис­лен­ных ме­то­дов ре­ше­ния за­дач, что при­ве­ло к соз­да­нию вы­чис­ли­тель­ной ма­те­ма­ти­ки. Ана­лиз по­ня­тий «вы­чис­ли­мость» и «ал­го­ритм» при­вёл к соз­да­нию тео­рии ал­го­рит­мов. За­да­чи хра­не­ния, об­ра­бот­ки и пе­ре­да­чи ин­фор­ма­ции спо­соб­ст­во­ва­ли воз­ник­но­ве­нию

ин­фор­ма­ции тео­рии, тео­рии ко­ди­ро­ва­ния и тео­ре­тич. крип­то­гра­фии. Эко­но­мич. за­да­чи, за­да­чи элек­тро­тех­ни­ки, рав­но как и внут­рен­ние про­бле­мы ма­те­ма­ти­ки, по­тре­бо­ва­ли раз­ви­тия тео­рии гра­фов. За­да­чи опи­са­ния ра­бо­ты и кон­ст­руи­ро­ва­ния слож­ных управ­ляю­щих сис­тем со­ста­ви­ли пред­мет тео­рии управ­ляю­щих сис­тем и тео­рии ав­то­ма­тов.

Од­на из осо­бен­но­стей Д. м. со­сто­ит в том, что вме­сте с за­да­ча­ми ти­па за­дач су­ще­ст­во­ва­ния, имею­щи­ми об­ще­ма­те­ма­тич. ха­рак­тер, важ­ное ме­сто в Д. м. за­ни­ма­ют за­да­чи, свя­зан­ные с ал­го­рит­мич. раз­ре­ши­мо­стью и по­строе­ни­ем кон­крет­ных ре­шаю­щих ал­го­рит­мов. Др. осо­бен­но­стью Д. м. яв­ля­ет­ся то, что в ней впер­вые на­ча­лись ис­сле­до­ва­ния т. н. дис­крет­ных мно­го­экс­тре­маль­ных за­дач. Со­от­вет­ст­вую­щие ме­то­ды по­ис­ка экс­тре­му­мов, ис­поль­зую­щие глад­кость функ­ций, в этих слу­ча­ях ока­зы­ва­ют­ся непри­ме­ни­мы­ми. Ти­пич­ны­ми за­да­ча­ми та­ко­го ро­да в Д. м. яв­ля­ют­ся, напр., за­да­чи оты­ска­ния в не­ко­то­ром смыс­ле оп­ти­маль­ных стра­те­гий в шах­ма­тах, а так­же за­да­чи по­строе­ния ми­ни­маль­ных дизъ­юнк­тив­ных нор­маль­ных форм для бу­ле­вых функ­ций (см. так­же Ал­геб­ра ло­ги­ки).

Осо­бен­но­стью Д. м., свя­зан­ной с за­да­ча­ми для ко­неч­ных струк­тур, яв­ля­ет­ся то, что для мно­гих из них су­ще­ст­ву­ют ал­го­рит­мы ре­ше­ния, в то вре­мя как для за­дач с эле­мен­та­ми не­пре­рыв­но­сти, как пра­ви­ло, пол­ное ре­ше­ние воз­мож­но лишь при весь­ма жё­ст­ких ог­ра­ни­че­ни­ях. При­ме­ром та­ко­го ал­го­рит­ма мо­жет слу­жить ал­го­ритм про­смот­ра всех воз­мож­ных ва­ри­ан­тов, т. е. ал­го­ритм пол­но­го пе­ре­бо­ра. К за­да­чам, в ко­то­рых мо­жет быть при­ме­нён ал­го­ритм пол­но­го пе­ре­бо­ра, от­но­сят­ся упо­мя­ну­тые за­да­чи о стра­те­ги­ях в шах­мат­ной пар­тии с ог­ра­ни­чен­ным чис­лом хо­дов и о ми­ни­ми­за­ции дизъ­юнк­тив­ных нор­маль­ных форм для бу­ле­вых функ­ций. Ал­го­рит­мы пол­но­го пе­ре­бо­ра тру­до­ём­ки и час­то не мо­гут быть реа­ли­зо­ва­ны на прак­ти­ке, в свя­зи с чем воз­ни­ка­ет ряд за­дач, свя­зан­ных с на­хо­ж­де­ни­ем ус­ло­вий, ог­ра­ни­чи­ваю­щих пе­ре­бор.

bigenc.ru

Примеры Дискретная математика. диаграммы Эйлера-Венна

 |   |   |   |  Примеры Дискретная математика.  |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | 

 Примеры предназначены для самостоятельного изучения Дискретной математики

 

Если некоторые задачи по Дискретной математике все-таки вызывают у Вас затруднения и Вы не можете разобраться с их решением самостоятельно, 

то Вы можете  заказать у нас помощь в решении задач по Дискретной математике

 


 

 

 

 

 Группа студентов из 25 человек сдала экзаменационную сессию следующими результатами: 2 человека получили только «отлично», 3 человека получили отличные, хорошие и удовлетворительные оценки; 4 человека только “хорошо”; 3 человека только хорошие и удовлетворительные оценки; число студентов, сдавших сессию только на “отлично”, «хорошо», равно числу студентов, сдавших сессию только на «удовлетворительно». Студентов, получивших только отличные и удовлетворительные оценки — нет. Удовлетворительные или хорошие оценки получили 22 студента. Сколько студентов не явилось на экзамены? Сколько студентов сдали сессию только на удовлетворительно?  Посмотреть решение
  Посмотреть решение
 В графе, представленном следующей матрицей смежности, найти все максимальные независимые множества

1

2

3

4

5

6

7

8

9

10

 

0

0

0

0

1

1

0

1

0

1

1

0

0

0

1

1

0

1

0

0

0

2

0

0

0

0

0

1

1

0

0

0

3

0

1

0

0

1

0

0

0

1

1

4

1

1

0

1

0

0

1

0

1

0

5

1

0

1

0

0

0

0

1

1

1

6

0

1

1

0

1

0

0

0

0

0

7

1

0

0

0

0

0

0

0

0

0

8

0

0

0

1

1

1

0

0

0

1

9

1

0

0

1

0

1

0

0

1

0

10

 Посмотреть решение
 Получить минимальную систему ДНФ для следующей системы полностью определённых булевых функций:

Х1

Х2

Х3

Х4

 

f1

f2

f3

0

0

1

1

1

1

0

1

1

0

1

1

2

1

0

0

1

0

0

0

3

0

1

0

0

0

1

0

4

0

0

1

0

0

0

0

5

1

0

0

0

0

0

1

6

1

1

0

1

0

0

1

7

1

1

0

1

1

0

0

8

0

0

1

 Посмотреть решение
 Упростить выражение. Задача на множества
 Посмотреть решение


  



Если все же Вы не смогли разобраться самостоятельно с какими-либо задачами по Дискретной математике,

то Вы можете заказать у нас решение задач по Дискретной математике


zadanie.by

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

Министерство образования и науки

Российской Федерации

Российский химико-технологический университет

им. Д.И. Менделеева

Новомосковский институт

Издательский центр

T.П. Тюрина, В.И. Емельянов

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

(часть 3)

Учебное пособие

Новомосковск 2004

Содержание

Часть 3. Элементы алгебры логики…………………………………………………… 3

3.1 Введение в алгебру логики…………………………………………………………….. 3

3.2 Основные функции алгебры логики………………………………………………… 5

3.3 Формулы алгебры логики……………………………………………………………… 9

Контрольные вопросы………………………………………………………………………. 12

3.4 Законы алгебры логики и следствия из них……………………………………. 12

Контрольные вопросы………………………………………………………………………. 16

3.5 Логические функции многих переменных………………………………………. 16

3.6 Построение формул алгебры логики по заданной таблице истинности 18

Контрольные вопросы и упражнения…………………………………………………. 26

3.7 Некоторые замкнутые классы (классы Поста). Понятие базиса………… 26

Контрольные вопросы и упражнения…………………………………………………. 34

3.8 Методы минимизации логических функций……………………………………. 34

Контрольные вопросы………………………………………………………………………. 39

3.9 Неполностью определенные логические функции…………………………… 40

3.10 Формы представления булевых функций…………………………………….. 41

3.10.1 Семантические деревья……………………………………………………………. 42

3.10.2 Бинарные диаграммы решений (БДР)……………………………………….. 45

3.11 Построение логических схем………………………………………………………. 45

Контрольные вопросы………………………………………………………………………. 45

3.12 Логические конечные автоматы…………………………………………………… 46

3.12.1 Процессы……………………………………………………………………………….. 50

3.12.2 Конечные автоматы…………………………………………………………………. 52

Контрольные вопросы………………………………………………………………………. 55

БИБЛИОГРАФИЧЕСКИЙ СПИСОК………………………………………………….. 60

3.1 Введение в алгебру логики

Алгебру логики иначе еще называют алгеброй высказываний, логикой высказываний. Алгебра логики начала формироваться в 19 веке в трудах английского математика Дж. Буля.

Прежде всего, благодаря труду английского логика Джорджа Буля «Математический анализ логики», был достигнут подлинный прогресс науки, называемый математической логикой. Он перенёс на логику законы и правила математических действий, ввёл логические операции, предложил способ записи высказываний в символической форме.

В трудах Джорджа Буля и О. де Моргана математическая логика представлена как своеобразная алгебра – алгебра логики (алгебра высказываний).

Алгебра логики (алгебра высказываний) – раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.

Джордж Буль (1815–1864) родился в Линкольне (Англия). Сын сапожного мастера. Окончил только начальную школу и дальнейшие знания приобретал самоучкой. С 1849 г. Буль – профессор математики в Куинс – колледже в Корке (Ирландия), где преподавал до конца жизни. Буля почти в равной степени интересовали логика, математический анализ, теория вероятностей, этика Б. Спинозы, философские работы Аристотеля и Цицерона. Он считается несомненным создателем современной символической (математической) логики.

Огастес де Морган (1806–1871) родился в Индии в семье полковника английских войск. Получил образование в Кембриджском университете. Был профессором математики Лондонского университета. Математику и логику де Морган назвал азами точного знания и выражал сожаление, что математики не более заботятся о логике, чем логики о математике. Сам он стремился сблизить обе науки, и его главной заслугой явилось построение логики по образу и подобию математических наук. Независимо от Дж. Буля он открыл основные идеи алгебры логики.

«Логика Буля» основывается на отношении эквивалентности, при котором правая часть равенства всегда содержит ровно столько же «истин», сколько и левая.

Высказывание – это имеющее смысл языковое выражение (повествовательное предложение), относительно которого в данной ситуации можно утверждать, что оно либо истинно, либо ложно, т. е. каждому высказыванию можно приписать истинное значение И (истина) или Л (ложь), но не то и другое одновременно.

Примеры:

1. НГТУ – крупнейший «вуз Новосибирска».

2. «Снег зелёный».

3. Р= «Чтобы подключиться к Интернету с домашнего компьютера, необходим модем и соответствующее ПО».

4. Крокодилы летают очень низко.

«А ты любишь информатику?» – это предложение не является высказыванием.

Уравнение 2+х=4 не является высказыванием. Однако, всякий раз, придавая переменной х определенное числовое значение, будем получать высказывание. Используя частицу «не», а также союзы «и», «или», связки «если …., то…», «тогда и только тогда, когда…» и т. п., можно из одних высказываний строить другие высказывания.

Изучением высказываний занимается Булева алгебра, в которой предполагается, что уже имеется некоторый запас высказываний, для каждого из которых известно истинно оно или ложно. Такие высказывания называют элементарными высказываниями. Из элементарных высказываний могут быть построены сложные с помощью операций алгебры логики.

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

В алгебре логики логические операции чаще всего описываются при помощи таблиц истинности, содержащих все наборы значений переменных и значения функции этих наборов. Алгебра логики не занимается обоснованием того, почему тому или иному элементарному высказыванию приписано значение истины или лжи. Этот вопрос решается за пределами алгебры логики.

Например: сумма углов в треугольнике – 180 градусов. Алгебра логики отвлекается и от смысловой содержательности высказывания. Она интересуется только одним свойством сложных высказываний: быть истинным (True – 1) или ложным (False – 0).

Основной задачей теории булевых функций является разработка систематического метода построения сложных функций из более простых. Этот метод основан на изучении свойств булевых функций.

Основными символами алгебры высказываний являются:

а) пропозиционные переменные Р1, Р2, Р3 , …;

б) одноместная связка – (ù) и двуместные связки Ù (и), Ú (или), ®, Þ, Û;

в) скобки ().

Переменная, значениями которой являются высказывания, называется пропозиционной переменной.

Пусть А, В- некоторые элементарные высказывания.

Определим новое высказывание Ā (т. е. не А ), будем называть его отрицанием (инверсия:

, Ā ), представим таблицы значений функции отрицания:

Рассмотрим наборы истинных значений элементарных функций на наборах аргументов:

Таблица 1

mirznanii.com

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

\bookfoldsheets0Федеральное агентство по образованию РФ

«ДИСКРЕТНАЯ МАТЕМАТИКА»

(КОНСПЕКТ ЛЕКЦИЙ)

Преподаватель: профессор,
Архипов Игорь Константинович

1. МНОЖЕСТВА

Множество – совокупность элементов, обладающих каким-то одним общим свойством. (Это определение не является строгим, оно лишь показывает особенности построения множеств, т.е. для построения множества важно указать свойство, которым обладают все его элементы).

Если каждому элементу множества можно присвоить номер и этот номер не повторяется, то такое множество называется счетным или конечным .

Если такого номера для каждого элемента не существует, то такое множество называется бесконечным .

Бесконечное множество часто называют континуумом (например: совокупность точек на плоскости).

Если можно пересчитать все число элементов в счетном множестве, то эта сумма называется мощностью множества.

Множества задаются различными способами:

1. С помощью перечисления всех его элементов.

{0,1,2,3,4,5,6,7,8,9}

2. Алгоритмическая форма (в виде последовательности или фомул).

а) конечное

М ={2;4;6;8} <=> М ={m|2n;n-целое;1<=n<=4}

б) бесконечное

А ={х| |х-1|<3}

2. СВОЙСТВА СЧЕТНЫХ МНОЖЕСТВ

1. Всякое подмножество счетного множества конечно или счетно

Подмножеством множества А называется множество А` все элементы которого принадлежат множеству А

Пример:

2. Сумма конечного или счетного числа конечных или счетных множеств есть конечное или счетное множество.

3. Множество всех рациональных чисел счетно .

4. Алфавитом называется любое непустое множество.

Пустое множество – множество, которое не содержит ни одного элемента.

Элементы множества под названием АЛФАВИТ называют буквами (символами) .

Символом в данном алфавите любая конечная последова­тель­ность букв.

Для каждого множества А существуют множества, элементами которого являются только все его подмножества.

Такое подмножество называют семейством множеств А или булеаном. (обозначается В(А) )

Будем называть вектором (кортежем) упорядоченный набор элементов и обозначать его

, заметим, что в отличие от множества, элементы в векторе могут повторяться. Эти элементы называются координатами или проекциями.

Количество элементов в векторе называется его длиной, если в векторе 2 элемента, то двойка, если n элементов, то n-ка.

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

1. Аксиома существования: Существует по крайней мере одно множество.

2. Аксиома объемности: Если множества А и В составлены из одних и тех же элементов, то они совпадают.

3. Аксиома объединения: Для произвольных множеств А и В существует множество, элементами которого являются все элементы множества А и все элементы множества В и никакие другие элементы множество не содержит.

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

5. Аксиома существования пустого множества: Существует множество не содержащее ни одного элемента.

3. ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

1. Включение (объединение)

Множество А входит (включено) в множество В , или А является подмножеством В .

Если всякий объект, обладающий свойством

, также обладает свойством , то говорят, что свойство включает свойство , т.е.

2. Сумма

Сумма множеств А и В есть множество С , включающее в себя все элементы множество А и В .

Объект входит во множество если он входит во множество А или во множество В .

3. Пересечение (произведение)

Пересечением множество А и В называется новое множество С . Элементы множества С принадлежат множеству А (обладают его свойствами) и множеству В (обладают его свойствами).

4. Вычитание (разность)

Разность множеств А и В есть множество С , элементы которого обладают свойствами множества А и не обладают свойствами множества В или принадлежат множеству А и не принадлежат множеству В .

5. Дополнение

Если имеется некоторое универсальное множество (универсум) U и все рассматриваемые множества есть его подмножества, то дополнением

называется такое множество, элементы которого не входят в А , но принадлежат U .

ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ

(Диаграммы Эймера, Венна)

1.

2.


3.
4.

4. ПРЯМОЕ ПРОИЗВЕДЕНИЕ А х В

Прямым произведением множеств А и В называется множество М всех пар (

), таких, что

Если А=В , то такое произведение называется

Аналогично можно вывести операцию прямого произведения большего числа множеств.

Если в частности

одинаковы то получаем

(Например, множество точек на плоскости являются прямым произведением двух множеств).

Если множества конечные, мощность произведений

равна мощности произведений

5. ОСНОВНЫЕ ТОЖДЕСТВА АЛГЕБРЫ МНОЖЕСТВ

Независимость расположения:

(1) (2)

Ассоциативно

mirznanii.com

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

Задача1. Решить рекуррентное соотношение методом производящих функций:

$$u_{n+2}-15u_{n+1}+56u_n=42 \cdot 5^n,\:n=0,1,2,…;$$ $$n_0=3,\:u_1=9$$

Решение, скачать (формат .docx)

Задача2. Решить рекуррентное соотношение с помощью характеристических чисел:

$$u_{n+2}-15u_{n+1}+56u_n=-35 \cdot 7^n,\:n=0,1,2,…;$$ $$n_0=-3,\:u_1=9$$

Решение, скачать (формат .docx)

ЗАДАНИЯ
по контрольной работе
«СПЕЦИАЛЬНАЯ МАТЕМАТИКА»

Все варианты СКАЧАТЬ

В каждом варианте подробно решены все задачи. Контрольные работы  выполнены в формате Word.  Стоимость решения одного варианта, или аналогичной работы  от 500р,, срок выполнения не более 1 дня (можно заказать задачи выборочно, из любого варианта), ОФОРМИТЬ ЗАКАЗ


Карта Карно — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями. Представляет собой операции попарного неполного склеивания и элементарного поглощения.

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы. В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

 

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.

  • Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули.

Алгоритм минимизации по методу карт Карно:

… Смотреть решение »

  • Определение. Двойственной для функции f(x1, x2, …, xn) называется функция$f^*(x_1, x_2,…, x_n)=\overline{f\left ( \bar{x_1}, \bar{x_2},… \bar{x_n} \right )}$

Пример. Построить функцию, двойственную данной:

$1.\,  f=x\vee y;$
$2. \, f=x\rightarrow y.$

Решение.

$1. f^*=\overline{\bar{x}\vee \bar{y}}=\bar{\bar{x}}\wedge\bar{\bar{y}} ;$
$2. f^*=\overline{\bar{x}\rightarrow \bar{y}}=\overline{\bar{\bar{x}} \vee  \bar{y}}=\bar{\bar{\bar{x}}}\wedge \bar{\bar{y}}=\bar{x}\wedge y.$

  • Определение. Функция, совпадающая со своей двойственной, называется самодвойственной.
  • Утверждение. Если функция f(x1, x2, …, xn) самодвойственна, то функция $\bar{f}  тоже самодвойственна.
  • Утверждение. Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.
  • Противоположными называются те наборы, которые в сумме дают двоичный код числа (2n-1).


Пример. Выяснить являются ли функции самодвойственными:

$1.\,  f=\left ( \bar{x} \approx y\right )\rightarrow \bar{z};$
$2\, f … Смотреть решение »


www.reshim.su

ДИСКРЕТНАЯ МАТЕМАТИКА • Большая российская энциклопедия

ДИСКРЕ́ТНАЯ МАТЕМА́ТИКА, раз­дел ма­те­ма­ти­ки, изу­чаю­щий свой­ст­ва дис­крет­ных струк­тур, ко­то­рые воз­ни­ка­ют как в са­мой ма­те­ма­ти­ке, так и в её при­ло­же­ни­ях. При этом дис­крет­ны­ми струк­ту­ра­ми на­зы­ва­ют­ся объ­ек­ты, для ко­то­рых важ­ней­шие ха­рак­те­ри­сти­ки при­ни­ма­ют ко­неч­ное или счёт­ное чи­сло зна­че­ний. К чис­лу та­ких струк­тур от­но­сят­ся, напр., ко­неч­ные груп­пы, ко­неч­ные гра­фы, не­ко­то­рые ма­те­ма­тич. мо­де­ли пре­об­ра­зо­ва­те­лей ин­фор­ма­ции, ко­неч­ные ав­то­ма­ты, Тью­рин­га ма­ши­ны. Это при­ме­ры струк­тур фи­нит­но­го (ко­неч­но­го) ха­рак­те­ра. Часть Д. м., изу­чаю­щая их, ино­гда на­зы­ва­ет­ся ко­неч­ной ма­те­ма­ти­кой. По­ми­мо фи­нит­ных струк­тур, Д. м. изу­ча­ет так­же дис­крет­ные бес­ко­неч­ные струк­ту­ры (напр., бес­ко­неч­ные ал­геб­ра­ич. сис­те­мы, бес­ко­неч­ные гра­фы, бес­ко­неч­ные ав­то­ма­ты).

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

Зна­чит. часть клас­сич. ма­те­ма­ти­ки за­ни­ма­ет­ся изу­че­ни­ем свойств объ­ек­тов не­пре­рыв­но­го ха­рак­те­ра. Ис­поль­зо­ва­ние дис­крет­ной или не­пре­рыв­ной мо­де­ли изу­чае­мо­го объ­ек­та свя­за­но как с са­мим объ­ек­том, так и с тем, ка­кие за­да­чи ста­вит пе­ред со­бой ис­сле­до­ва­тель. Са­мо де­ле­ние ма­те­ма­ти­ки на Д. м. и ма­те­ма­ти­ку, за­ни­маю­щую­ся не­пре­рыв­ны­ми мо­де­ля­ми, в зна­чит. ме­ре ус­лов­но, по­сколь­ку, с од­ной сто­ро­ны, про­ис­хо­дит об­мен идея­ми и ме­то­да­ми ме­ж­ду ни­ми, а с дру­гой – час­то воз­ни­ка­ет не­об­хо­ди­мость ис­сле­до­ва­ния мо­де­лей, об­ла­­даю­щих как дис­крет­ны­ми, так и не­пре­рыв­ны­ми свой­ст­ва­ми од­но­вре­мен­но. В ма­те­ма­ти­ке су­ще­ст­ву­ют раз­де­лы, ис­поль­зую­щие сред­ст­ва Д. м. для изу­че­ния не­пре­рыв­ных мо­де­лей (напр., ал­геб­раи­че­ская гео­мет­рия), и на­обо­рот, час­то ме­то­ды, раз­ви­тые для ана­ли­за не­пре­рыв­ных мо­де­лей, ис­поль­зу­ют­ся при изу­че­нии дис­крет­ных струк­тур (напр., асим­пто­ти­че­ские ме­то­ды в тео­рии чи­сел, в пе­ре­чис­ли­тель­ных за­да­чах ком­би­на­то­ри­ки). Од­на­ко спе­ци­фи­ка мн. раз­де­лов Д. м. свя­за­на с не­об­хо­ди­мо­стью от­ка­за от та­ких фун­дам. по­ня­тий клас­сич. ма­те­ма­ти­ки, как пре­дел и не­пре­рыв­ность, в свя­зи с чем для мн. за­дач Д. м. не­ко­то­рые ме­то­ды клас­сич. ма­те­ма­ти­ки ока­зы­ва­ют­ся не­при­ме­ни­мы­ми.

На­ря­ду с вы­де­ле­ни­ем Д. м. пу­тём ука­за­ния её пред­ме­та мож­но так­же опи­сать Д. м. пе­ре­чис­ле­ни­ем со­став­ляю­щих её час­тей. К ним от­но­сят­ся ком­би­на­тор­ный ана­лиз, гра­фов тео­рия, тео­рия ко­ди­ро­ва­ния, тео­рия функ­цио­наль­ных сис­тем, тео­рия управ­ляю­щих сис­тем, ав­то­ма­тов тео­рия, ал­го­рит­мов тео­рия. При бо­лее ши­ро­ком тол­ко­ва­нии к Д. м. мо­гут быть от­не­се­ны как це­лые раз­де­лы ма­те­ма­ти­ки, напр. ма­те­ма­тич. ло­ги­ка, так и час­ти та­ких раз­де­лов, как тео­рия чи­сел, ал­геб­ра, вы­чис­ли­тель­ная ма­те­ма­ти­ка, тео­рия ве­ро­ят­но­стей, в ко­то­рых изу­чае­мые объ­ек­ты име­ют дис­крет­ный ха­рак­тер.

Исторический очерк

Эле­мен­ты Д. м. воз­ник­ли в глу­бо­кой древ­но­сти; раз­ви­ва­ясь па­рал­лель­но с др. раз­де­ла­ми ма­те­ма­ти­ки, они яв­ля­лись их со­став­ной ча­стью. Ти­пич­ны­ми бы­ли за­да­чи, свя­зан­ные со свой­ст­ва­ми це­лых чи­сел, позд­нее эти за­да­чи при­ве­ли к соз­да­нию тео­рии чи­сел. При­ме­ры та­ких за­дач: оты­ска­ние ал­го­рит­мов сло­же­ния и ум­но­же­ния на­ту­раль­ных чи­сел у древ­них егип­тян, во­про­сы де­ли­мо­сти на­ту­раль­ных чи­сел и за­да­чи сум­ми­ро­ва­ния в пи­фа­го­рей­ской шко­ле, а в бо­лее позд­нее вре­мя – воп­ро­сы, свя­зан­ные с раз­ре­ши­мо­стью урав­не­ний в це­лых чис­лах. Этот этап раз­ви­тия Д. м. свя­зан с име­на­ми Дио­фан­та, Евли­да, Пифа­го­ра­ и Эрато­сфе­на­. В 17–18 вв., в осн. в свя­зи с иг­ро­вы­ми за­да­ча­ми, поя­ви­лись эле­мен­ты ком­би­на­тор­но­го ана­ли­за и дис­крет­ной тео­рии ве­ро­ят­но­стей, а в свя­зи с об­щи­ми про­бле­ма­ми тео­рии чи­сел, ал­геб­ры и гео­мет­рии в 18–19 вв. воз­ник­ли та­кие важ­ней­шие по­ня­тия ал­геб­ры, как груп­па, по­ле, коль­цо, оп­ре­де­лив­шие даль­ней­шее раз­ви­тие и со­дер­жа­ние ал­геб­ры и имев­шие, по су­ще­ст­ву, дис­крет­ную при­ро­ду. На про­тя­же­нии 17–19 вв. раз­ви­тие Д. м. свя­за­но с име­на­ми Н. Абеля­, Э. Варин­га­, У. Гамиль­то­на­, Э. Га­луа, А. Кэли­, Ж. Лаг­ран­жа, А. Лежан­дра­, П. Фер­ма, Л. Эйле­ра­. В 19–20 вв. стрем­ле­ние к стро­го­сти ма­те­ма­тич. рас­су­ж­де­ний и ана­лиз ме­то­дов ма­те­ма­ти­ки при­ве­ли к вы­де­ле­нию ещё од­но­го раз­де­ла – ма­те­ма­тич. ло­ги­ки. В это вре­мя проб­ле­ма­ми Д. м. за­ни­ма­лись Л. Брау­эр, Дж. Буль, Н. Винер­, К. Гёдель­, Д. Гиль­берт, А. Чёрч, К. Шеннон­. В со­з­да­нии рос. шко­лы Д. м. участ­во­ва­ли И. М. Вино­гра­дов­, А. Н. Колмо­го­ров­, О. Б. Лупа­нов­ и С. В. Яблон­ский­.

Современные задачи дискретной математики

В 20 в. раз­ви­тие Д. м. оп­ре­де­ля­лось гл. обр. за­про­са­ми прак­ти­ки. Воз­ник­ла но­вая нау­ка – ки­бер­не­ти­ка и её тео­ре­тич. часть – ма­те­ма­тич. ки­бер­не­ти­ка, изу­чаю­щая ма­те­ма­тич. ме­то­да­ми раз­но­об­раз­ные про­бле­мы, ко­то­рые ста­вит пе­ред ки­бер­не­ти­кой прак­тич. дея­тель­ность че­ло­ве­ка. Ма­те­ма­тич. ки­бер­не­ти­ка яв­ля­ет­ся по­став­щи­ком идей и за­дач Д. м. Так, при­клад­ные во­про­сы, тре­бую­щие боль­ших вы­чис­ле­ний, сти­му­ли­ро­ва­ли по­яв­ле­ние и раз­ви­тие чис­лен­ных ме­то­дов ре­ше­ния за­дач, что при­ве­ло к соз­да­нию вы­чис­ли­тель­ной ма­те­ма­ти­ки. Ана­лиз по­ня­тий «вы­чис­ли­мость» и «ал­го­ритм» при­вёл к соз­да­нию тео­рии ал­го­рит­мов. За­да­чи хра­не­ния, об­ра­бот­ки и пе­ре­да­чи ин­фор­ма­ции спо­соб­ст­во­ва­ли воз­ник­но­ве­нию ин­фор­ма­ции тео­рии, тео­рии ко­ди­ро­ва­ния и тео­ре­тич. крип­то­гра­фии. Эко­но­мич. за­да­чи, за­да­чи элек­тро­тех­ни­ки, рав­но как и внут­рен­ние про­бле­мы ма­те­ма­ти­ки, по­тре­бо­ва­ли раз­ви­тия тео­рии гра­фов. За­да­чи опи­са­ния ра­бо­ты и кон­ст­руи­ро­ва­ния слож­ных управ­ляю­щих сис­тем со­ста­ви­ли пред­мет тео­рии управ­ляю­щих сис­тем и тео­рии ав­то­ма­тов.

Од­на из осо­бен­но­стей Д. м. со­сто­ит в том, что вме­сте с за­да­ча­ми ти­па за­дач су­ще­ст­во­ва­ния, имею­щи­ми об­ще­ма­те­ма­тич. ха­рак­тер, важ­ное ме­сто в Д. м. за­ни­ма­ют за­да­чи, свя­зан­ные с ал­го­рит­мич. раз­ре­ши­мо­стью и по­строе­ни­ем кон­крет­ных ре­шаю­щих ал­го­рит­мов. Др. осо­бен­но­стью Д. м. яв­ля­ет­ся то, что в ней впер­вые на­ча­лись ис­сле­до­ва­ния т. н. дис­крет­ных мно­го­экс­тре­маль­ных за­дач. Со­от­вет­ст­вую­щие ме­то­ды по­ис­ка экс­тре­му­мов, ис­поль­зую­щие глад­кость функ­ций, в этих слу­ча­ях ока­зы­ва­ют­ся непри­ме­ни­мы­ми. Ти­пич­ны­ми за­да­ча­ми та­ко­го ро­да в Д. м. яв­ля­ют­ся, напр., за­да­чи оты­ска­ния в не­ко­то­ром смыс­ле оп­ти­маль­ных стра­те­гий в шах­ма­тах, а так­же за­да­чи по­строе­ния ми­ни­маль­ных дизъ­юнк­тив­ных нор­маль­ных форм для бу­ле­вых функ­ций (см. так­же Ал­геб­ра ло­ги­ки).

Осо­бен­но­стью Д. м., свя­зан­ной с за­да­ча­ми для ко­неч­ных струк­тур, яв­ля­ет­ся то, что для мно­гих из них су­ще­ст­ву­ют ал­го­рит­мы ре­ше­ния, в то вре­мя как для за­дач с эле­мен­та­ми не­пре­рыв­но­сти, как пра­ви­ло, пол­ное ре­ше­ние воз­мож­но лишь при весь­ма жё­ст­ких ог­ра­ни­че­ни­ях. При­ме­ром та­ко­го ал­го­рит­ма мо­жет слу­жить ал­го­ритм про­смот­ра всех воз­мож­ных ва­ри­ан­тов, т. е. ал­го­ритм пол­но­го пе­ре­бо­ра. К за­да­чам, в ко­то­рых мо­жет быть при­ме­нён ал­го­ритм пол­но­го пе­ре­бо­ра, от­но­сят­ся упо­мя­ну­тые за­да­чи о стра­те­ги­ях в шах­мат­ной пар­тии с ог­ра­ни­чен­ным чис­лом хо­дов и о ми­ни­ми­за­ции дизъ­юнк­тив­ных нор­маль­ных форм для бу­ле­вых функ­ций. Ал­го­рит­мы пол­но­го пе­ре­бо­ра тру­до­ём­ки и час­то не мо­гут быть реа­ли­зо­ва­ны на прак­ти­ке, в свя­зи с чем воз­ни­ка­ет ряд за­дач, свя­зан­ных с на­хо­ж­де­ни­ем ус­ло­вий, ог­ра­ни­чи­ваю­щих пе­ре­бор.

dev.bigenc.ru

Конспект лекций (Описание основных понятий и методов решения задач дискретной математики, относящихся к теории множеств, отношениям на множествах, теории графов и комбинаторике)

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

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

______________________________________________________________________

С.В. РЕНИН

ДИСКРЕТНАЯ МАТЕМАТИКА

Конспект лекций для студентов II курса

Института социальной реабилитации

Новосибирск

2002

УДК 51 (076.1)

Рецензент ………………………………………………..

Работа выполнена на кафедре
автоматизированных систем управления
для студентов II курса Института социальной реабилитации

Ренин С.В.

Дискретная математика. Конспект лекций. – Новосибирск:
Изд-во НГТУ, 2000.

Конспект лекций содержит описание основных понятий и методов решения задач дискретной математики, относящихся к теории множеств, отношениям на множествах, теории графов и комбинаторике и предназначается студентам Института социальной реабилитации НГТУ , обучающимся по направлению 5528 «Информатика и вычислительная техника», для использования при подготовке к практическим занятиям и при самостоятельной работе над курсом.

УДК 51 (076.1)

© Новосибирский государственный
технический университет, 2000 г.

ОГЛАВЛЕНИЕ

1. МНОЖЕСТВА. ОТНОШЕНИЯ НА МНОЖЕСТВАХ

1.1. Основные понятия теории множеств

Множество – совокупность объектов любой природы, называемых элементами данного множества.

Обозначение – большие буквы латинского алфавита для множеств, малые – для его элементов.

Способы задания: 1) перечисление элементов; 2) указание свойства, которым обладают все элементы множества.

Примеры.       1) Множество Х, состоящее из элементов х1, х2, х3, обозначают:

Х = {х1, х2, х3}

              2) Множество простых чисел Х = {x|x — простое число}.

Принадлежность элемента х множеству Х записывается как хÎХ.

Если элемент х не принадлежит Х, то пишут хÏХ.

Множество называется конечным, если оно состоит из конечного числа элемен­тов. Например, множество жителей г. Новосибирска, множество студентов группы ВИ-51.

Множество называется бесконечным, если число его элементов бесконечно. Например, множество натуральных чисел N = {1,2,3,…}.

Бесконечное множество называется счетным, если его элементы можно перечислять. Например, множество натуральных чисел N, множество целых чисел
Z = {…,-3,-2,-1,0,1,2,3,…}.

В противном случае оно называется несчетным. Например, множество точек плоскости, множество вещественных чисел.

Если множество не содержит ни одного элемента, то оно называется пустым и обозначается Æ. Например, пусто множество людей, имеющих рост выше 3 метров. Пусто множество студентов группы ВИ-51, имеющих диплом о высшем образовании.

Множество А называется подмножеством множества В, если любой элемент А является и элементом множества В. Это обозначается так:

АÌВ. Например, множество студентов группы ВИ-51 есть подмножество множества студентов ИСР и НГТУ.

Если множество А является подмножеством множества В и при этом может совпадать с В, то знак Ì подчеркивают: Í.

Множество называется универсальным, если все другие рассматриваемые в данной задаче множества являются его подмножествами. Обозначается такое множество латинской буквой I. Например, если в задаче рассматриваются множество вещественных чисел R, множество целых чисел Z, множество натуральных чисел N и множество рациональных чисел F, то для всех этих множеств множество R является универсальным, так как ZÌR, NÌR и FÌR. Т.е. в данном случае I=R.

1.2. Операции над множествами

1.2.1. Объединение

Обозначение:

Определение. Объединением двух множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые входят во множество А или во множество В или в оба вместе, причем элементы, принадлежащие обоим множествам одновременно, входят в объединение только один раз.

   Если С = А В, то С = {c| cÎА или сÎВ или сÎА и В одно­временно}.

Операции над множествами можно наглядно изобразить с помощью диаграмм Эйлера-Венна. На этих диаграммах универсальное множество изображается в виде прямоугольника, а множества, участвующие в операции — кругами.

Представление объединения на диаграмме Эйлера-Венна (результат объединения закрашен):

Примеры:

1) А = {a, b, c, d}, B = {c, d, e, f}, C=A B={a, b, c, d, e, f}

2) Z+ – множество целых положительных чисел;

  Z – множество целых отрицательных чисел;

  О = {0};

  C = Z+ ZO = Z – множество всех целых чисел.

3) А – множество студентов гр. ВИ-51, учащихся на отлично;

  В – множество студентов гр. ВИ-51, учащихся без троек;

  С – множество студентов гр. ВИ-51, имеющих удовлетворительные оценки;

  D – множество студентов гр. ВИ-51, имеющих неудовлетворительные оценки;

  E = A B C D — множество всех студентов группы ВИ-51.

Свойства: 1) коммутативность (переместительный закон)

               А В = В А

     2) ассоциативность (сочетательный закон)

           А В С = (А В) С = А (В С)

     3) если АÌВ, то А В=В;

vunivere.ru

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *