Дискретна математика. Дискретно математическо доказване с примери за диаграма на Вен

История

Определение 1

На Леонард Ойлер беше зададен въпросът: възможно ли е, докато се разхождате из Кьонигсберг, да заобиколите всички мостове на града, без да преминете два пъти през нито един от тях. Приложен е план на града със седем моста.

В писмо до италиански математик, когото познава, Ойлер дава кратко и красиво решение на проблема с мостовете в Кьонигсберг: при такова разположение проблемът е неразрешим. В същото време той посочи, че въпросът му се струва интересен, т.к. "Нито геометрията, нито алгебрата са достатъчни за неговото решение...".

При решаването на много задачи Л. Ойлер изобразява множества с помощта на кръгове, поради което се наричат "окръжности на Ойлер". Този метод е използван още по-рано от немския философ и математик Готфрид Лайбниц, който ги използва за геометрично обяснение на логическите връзки между понятията, но по-често използва линейни диаграми. Ойлер, от друга страна, разработи метода доста задълбочено. Графичните методи станаха особено известни благодарение на английския логик и философ Джон Вен, който въведе диаграми на Вен и подобни схеми често се наричат Диаграми на Ойлер-Вен. Те се използват в много области, например в теорията на множествата, теорията на вероятностите, логиката, статистиката и компютърните науки.

Принцип на диаграмиране

Досега диаграмите на Ойлер-Вен са широко използвани за схематично изобразяване на всички възможни пресичания на няколко набора. Диаграмите показват всички $2^n$ комбинации от n свойства. Например за $n=3$ диаграмата показва три окръжности с центрове във върховете на равностранен триъгълник и същия радиус, който е приблизително равен на дължината на страната на триъгълника.

Логическите операции дефинират таблици на истинност. Диаграмата показва кръг с името на набора, който представлява, например $A$. Областта в средата на кръга $A$ ще покаже истинността на израза $A$, а областта извън кръга - false. За да се покаже логическа операция, само онези области са засенчени, в които стойностите на логическата операция за множествата $A$ и $B$ са верни.

Например конюнкцията на две множества $A$ и $B$ е вярна само ако и двете множества са верни. В този случай резултатът от конюнкцията на $A$ и $B$ на диаграмата ще бъде областта в средата на кръговете, която едновременно принадлежи на множеството $A$ и множеството $B$ (пресечната точка на комплекти).

Фигура 1. Конюнкция на множества $A$ и $B$

Използване на диаграми на Ойлер-Вен за доказване на логически равенства

Нека разгледаме как методът за конструиране на диаграми на Ойлер-Вен се използва за доказване на логически равенства.

Нека докажем закона на де Морган, който се описва от равенството:

Доказателство:

Фигура 4. $A$ инверсия

Фигура 5. $B$ инверсия

Фигура 6. Конюнкция на $A$ и $B$ инверсии

След като сравним площта за показване на лявата и дясната част, виждаме, че те са равни. От това следва валидността на логическото равенство. Законът на Де Морган се доказва с помощта на диаграми на Ойлер-Вен.

Решаване на проблема с търсенето на информация в Интернет чрез диаграми на Ойлер-Вен

За търсене на информация в Интернет е удобно да използвате заявки за търсене с логически връзки, подобни по значение на съюзите "и", "или" на руския език. Значението на логическите връзки става по-ясно, ако ги илюстрираме с помощта на диаграми на Ойлер-Вен.

Пример 1

Таблицата показва примери за заявки към сървъра за търсене. Всяка заявка има свой код - буква от $A$ до $B$. Трябва да подредите кодовете на заявките в низходящ ред на броя страници, намерени за всяка заявка.

Фигура 7

Решение:

Нека изградим диаграма на Ойлер-Вен за всяка заявка:

Фигура 8

Отговор: BVA.

Решаване на логически значим проблем с помощта на диаграми на Ойлер-Вен

Пример 2

През зимната ваканция от $36$ ученици в $2$ клас не са ходили на кино, театър и цирк. $25$ хора отидоха на кино, $11$ на театър, $17$ на цирк; както в киното, така и в театъра - $6$; и в киното и в цирка - $10$; и на театър и на цирк - 4$.

Колко души са посетили киното, театъра и цирка?

Решение:

Нека обозначим броя на момчетата, които са били на кино, театър и цирк - $x$.

Нека изградим диаграма и да разберем броя на момчетата във всяка област:

Фигура 9

Не бяхте на театър, нито на кино, нито в цирка - 2$ на човек.

Така че $36 - 2 = $34 души. посетени събития.

$6$ души са ходили на кино и театър, което означава, че само ($6 - x)$ души са ходили на кино и театър.

$10$ хора отидоха на кино и цирк, така че само на кино и цирк ($10 - x$) хора.

$4$ души отидоха на театър и цирк, което означава, че само театър и цирк ($4 - x$) души отидоха на театър и цирк.

$25$ души са отишли на кино, което означава, че само $25 - (10 - x) - (6 - x) - x = (9+x)$ са отишли на кино.

По същия начин само ($1+x$) хора отидоха на театър.

Само ($3+x$) души отидоха на цирк.

И така, отидохме на театър, кино и цирк:

$(9+x)+(1+x)+(3+x)+(10-x)+(6-x)+(4-x)+x = 34$;

Тези. само един човек е ходил и на театър, и на кино, и на цирк.

История

Определение 1

Принцип на диаграмиране

Фигура 1. Конюнкция на множества $A$ и $B$

Използване на диаграми на Ойлер-Вен за доказване на логически равенства

Нека докажем закона на де Морган, който се описва от равенството:

Доказателство:

Фигура 4. $A$ инверсия

Фигура 5. $B$ инверсия

Фигура 6. Конюнкция на $A$ и $B$ инверсии

Решаване на проблема с търсенето на информация в Интернет чрез диаграми на Ойлер-Вен

Пример 1

Фигура 7

Решение:

Нека изградим диаграма на Ойлер-Вен за всяка заявка:

Фигура 8

Отговор: BVA.

Решаване на логически значим проблем с помощта на диаграми на Ойлер-Вен

Пример 2

Колко души са посетили киното, театъра и цирка?

Решение:

Нека обозначим броя на момчетата, които са били на кино, театър и цирк - $x$.

Нека изградим диаграма и да разберем броя на момчетата във всяка област:

Фигура 9

Не бяхте на театър, нито на кино, нито в цирка - 2$ на човек.

Така че $36 - 2 = $34 души. посетени събития.

$6$ души са ходили на кино и театър, което означава, че само ($6 - x)$ души са ходили на кино и театър.

$10$ хора отидоха на кино и цирк, така че само на кино и цирк ($10 - x$) хора.

$4$ души отидоха на театър и цирк, което означава, че само театър и цирк ($4 - x$) души отидоха на театър и цирк.

$25$ души са отишли на кино, което означава, че само $25 - (10 - x) - (6 - x) - x = (9+x)$ са отишли на кино.

По същия начин само ($1+x$) хора отидоха на театър.

Само ($3+x$) души отидоха на цирк.

И така, отидохме на театър, кино и цирк:

$(9+x)+(1+x)+(3+x)+(10-x)+(6-x)+(4-x)+x = 34$;

Тези. само един човек е ходил и на театър, и на кино, и на цирк.

Някои проблеми могат да бъдат удобно и визуално решени с помощта на диаграми на Ойлер-Вен. Например задачи по набори. Ако не знаете какво представляват диаграмите на Ойлер-Вен и как да ги построите, първо прочетете.

Сега нека анализираме типични задачиотносно комплектите.

Задача 1.

Проведено е проучване сред 100 ученици в училище със задълбочено изучаване на чужди езици. На учениците беше зададен въпросът: Какво чужди езициучиш ли?". Оказа се, че 48 ученици учат английски, 26 - френски, 28 - немски. 8 ученици учат английски и немски, 8 - английски и френски, 13 - френски и немски. 24 ученици не учат нито английски, нито френски, нито немски Колко ученици в проучването изучават три езика едновременно: английски, френски и немски?

Отговор: 3.

Решение:

много ученици, които учат английски ("A");
много ученици, учещи френски („F“);
много ученици, които учат немски език ("N").

Нека изобразим с помощта на диаграмата на Ойлер-Вен това, което ни е дадено по условие.

Нека означим желаната област A=1, F=1, H=1 като "x" (в таблицата по-долу, област № 7). Изразяваме останалите региони по отношение на x.

0) Област A=0, F=0, H=0: 24 ученици - дадени според условието на задачата.

1) Регион A=0, F=0, H=1: 28-(8-x+x+13-x)=7+x ученици.

2) Регион A=0, F=1, H=0: 26-(8-x+x+13-x)=5+x ученици.

3) Регион A=0, F=1, H=1: 13 ученици.

4) Регион A=1, F=0, H=0: 48-(8-x+x+8-x)=32+x ученици.

5) Регион A=1, F=0, H=1: 8 ученици.

6) Регион A=1, F=1, H=0: 8 ученици.

№ области	А	Е	з	Количество ученици
0	0	0	0	24
1	0	0	1	7+x
2	0	1	0	5+x
3	0	1	1	13-ти
4	1	0	0	32+x
5	1	0	1	8-ки
6	1	1	0	8-ки
7	1	1	1	х

Нека дефинираме x:

24+7+(x+5)+x+(13-x)+(32+x)+(8-x)+(8-x)+x=100.

x=100-(24+7+5+13+32+8+8)=100-97=3.

Оказа се, че 3 ученици учат три езика едновременно: английски, френски и немски.

Ето как ще изглежда диаграмата на Ойлер-Вен с известно x:

Задача 2.

На олимпиадата по математика учениците трябваше да решат три задачи: една по алгебра, една по геометрия и една по тригонометрия. В олимпиадата участваха 1000 ученици. Резултатите от олимпиадата бяха следните: 800 участници решиха задачата по алгебра, 700 по геометрия, 600 по тригонометрия.600 ученици решиха задачи по алгебра и геометрия, 500 по алгебра и тригонометрия, 400 по геометрия и тригонометрия. 300 души решаваха задачи по алгебра, геометрия и тригонометрия. Колко ученици не са решили нито един проблем?

Отговор: 100.

Решение:

Първо, дефинираме множества и въвеждаме нотация. Има три от тях:

набор от задачи по алгебра ("А");
набор от задачи по геометрия ("G");
набор от задачи по тригонометрия ("Т").

Нека изобразим какво трябва да намерим:

Нека определим броя на учениците за всички възможни области.

Нека обозначим желаната област A=0, G=0, T=0 като "x" (в таблицата по-долу, област № 0).

Нека намерим останалите области:

1) Регион A=0, D=0, T=1: няма ученици.

2) Регион A=0, D=1, T=0: няма ученици.

3) Регион A=0, D=1, T=1: 100 ученици.

4) Регион A=1, D=0, T=0: няма ученици.

5) Регион A=1, D=0, T=1: 200 ученици.

6) Регион A=1, D=1, T=0: 300 ученици.

7) Регион A=1, D=1, T=1: 300 ученици.

Нека напишем стойностите на областите в таблицата:

№ области	А	Ж	T	Количество ученици
0	0	0	0	х
1	0	0	1	0
2	0	1	0	0
3	0	1	1	100
4	1	0	0	0
5	1	0	1	200
6	1	1	0	300
7	1	1	1	300

Нека начертаем стойностите за всички области с помощта на диаграма:

Нека дефинираме x:

x=U-(A V G V T), където U е вселената.

A V G V T \u003d 0 + 0 + 0 + 300 + 300 + 200 + 100 \u003d 900.

Получихме, че 100 ученици не са решили нито една задача.

Задача 3.

На олимпиадата по физика учениците трябваше да решат три задачи: една по кинематика, една по термодинамика и една по оптика. Резултатите от олимпиадата бяха следните: 400 участници решиха задачата по кинематика, 350 по термодинамика, 300 по оптика.300 ученици решиха задачи по кинематика и термодинамика, 200 по кинематика и оптика, 150 по термодинамика и оптика. 100 души решаваха задачи по кинематика, термодинамика и оптика. Колко ученици решиха две задачи?

Отговор: 350.

Решение:

Първо, дефинираме множества и въвеждаме нотация. Има три от тях:

набор от задачи по кинематика ("К");
набор от задачи по термодинамика ("Т");
набор от задачи по оптика ("О").

Нека изобразим с помощта на диаграмата на Ойлер-Вен това, което ни е дадено от условието:

Нека изобразим какво трябва да намерим:

Нека определим броя на учениците за всички възможни области:

0) Област K=0, T=0, O=0: не е дефинирана.

1) Регион K=0, T=0, O=1: 50 ученици.

2) Регион K=0, T=1, O=0: няма ученици.

3) Регион K=0, T=1, O=1: 50 ученици.

4) Регион K=1, T=0, O=0: няма ученици.

5) Регион K=1, T=0, O=1: 100 ученици.

6) Регион K=1, T=1, O=0: 200 ученици.

7) Регион K=1, T=1, O=1: 100 ученици.

Нека напишем стойностите на областите в таблицата:

№ области	ДА СЕ	T	ОТНОСНО	Количество ученици
0	0	0	0	-
1	0	0	1	50
2	0	1	0	0
3	0	1	1	50
4	1	0	0	0
5	1	0	1	100
6	1	1	0	200
7	1	1	1	100

Нека начертаем стойностите за всички области с помощта на диаграма:

Нека дефинираме x.

х=200+100+50=350.

Получено, 350 ученици решаваха две задачи.

Задача 4.

Сред минувачите проведе анкета. Беше зададен въпросът: "Какъв домашен любимец имате?". Според резултатите от проучването се оказа, че 150 души имат котка, 130 имат куче, а 50 имат птица. 60 души имат котка и куче, 20 имат котка и птица, 30 имат куче и птица. 70 души изобщо нямат домашен любимец. 10 души имат котка, куче и птица. Колко минувачи участваха в анкетата?

Отговор: 300.

Решение:

Първо, дефинираме множества и въвеждаме нотация. Има три от тях:

много хора, които имат котка ("K");
много хора, които имат куче ("C");
много хора, които имат птица ("P").

Нека изобразим с помощта на диаграмата на Ойлер-Вен това, което ни е дадено от условието:

Нека изобразим какво трябва да намерим:

Нека определим броя на хората за всички възможни области:

0) Зона K=0, S=0, P=0: 70 души.

1) Зона K=0, S=0, P=1: 10 души.

2) Зона K=0, S=1, P=0: 50 души.

3) Зона K=0, S=1, P=1: 20 души.

4) Зона K=1, S=0, P=0: 80 души.

5) Зона K=1, T=0, O=1: 10 души.

6) Регион K=1, T=1, O=0: 50 души.

7) Регион K=1, T=1, O=1: 10 души.

Нека напишем стойностите на областите в таблицата:

№ области	ДА СЕ	° С	П	Количество Човек
0	0	0	0	70
1	0	0	1	10
2	0	1	0	50
3	0	1	1	20
4	1	0	0	80
5	1	0	1	10
6	1	1	0	50
7	1	1	1	10

Нека начертаем стойностите за всички области с помощта на диаграма:

Нека дефинираме x:

x=U (вселена)

U=70+10+50+20+80+10+50+10=300.

Стана ясно, че в анкетата са участвали 300 души.

Задача 5.

В една специалност в един от университетите са постъпили 120 души. Абитуриентите се явиха на три изпита: по математика, по информатика и руски език. Математика са издържали 60 души, информатика - 40. 30 кандидати са издържали математика и информатика, 30 - математика и руски език, 25 - информатика и руски език. 20 души са издържали и трите изпита, а 50 са се скъсали. Колко кандидати са преминали руски език?