Історія

Визначення 1

Леонарду Ейлеру поставили запитання: чи можна, прогулюючись Кенігсбергом, обійти через всі мости міста, двічі не проходячи ні через один з них. План міста із сімома мостами додавався.

У листі знайомому італійському математику Ейлер дав коротке і красиве вирішення проблеми кенігсберзьких мостів: при такому розташуванні завдання не вирішене. При цьому він зазначив, що питання видалося йому цікавим, т.к. «для його вирішення недостатні ні геометрія, ні алгебра...».

При вирішенні багатьох завдань Л. Ейлер зображував множини за допомогою кіл, тому вони і отримали назву «кола Ейлера». Цим методом раніше користувався німецький філософ і математик Готфрід Лейбніц, який використовував їх для геометричного пояснення логічних зв'язків між поняттями, але при цьому частіше використовував лінійні схеми. Ейлер досить грунтовно розвинув метод. Особливо знаменитими графічні методи стали завдяки англійському логіку та філософу Джону Венну, який запровадив діаграми Венна та подібні схеми часто називають діаграмами Ейлера-Венна. Використовуються вони у багатьох областях, наприклад, у теорії множин, теорії ймовірності, логіки, статистики та інформатики.

Принцип побудови діаграм

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

Логічні операції задають таблиці істинності. На діаграмі зображається коло з назвою множини, яку він представляє, наприклад, $A$. Область у середині кола $A$ відображатиме істинність вираження $A$, а область поза коло - брехня. Для відображення логічної операції заштриховують ті області, у яких значення логічної операції при множинах $A$ і $B$ істинні.

Наприклад, кон'юнкція двох множин $A$ і $B$ істинна тільки в тому випадку, коли обидва множини істинні. У такому випадку на діаграмі результатом кон'юнкції $A$ і $B$ буде область в середині кіл, яка одночасно належить множині $A$ і множині $B$ (перетину множин).

Рисунок 1. Кон'юнкція множин $A$ та $B$

Використання діаграм Ейлера-Венна для підтвердження логічних рівностей

Розглянемо, як застосовується спосіб побудови діаграм Ейлера-Венна на підтвердження логічних рівностей.

Доведемо закон де Моргана, який описується рівністю:

Доведення:

Рисунок 4. Інверсія $A$

Рисунок 5. Інверсія $B$

Рисунок 6. Кон'юнкція інверсій $A$ та $B$

Після порівняння області для відображення лівої та правої частини бачимо, що вони рівні. З цього випливає справедливість логічної рівності. Закон де Моргана підтверджено за допомогою діаграм Ейлера-Венна.

Розв'язання задачі пошуку інформації в Інтернеті за допомогою діаграм Ейлера-Венна

Для пошуку інформації в Інтернет зручно використовувати пошукові запити з логічними зв'язками, аналогічними за змістом спілкам "і", "або" російської мови. Сенс логічних зв'язок стає зрозумілішим, якщо проілюструвати їх з допомогою діаграм Ейлера-Венна.

Приклад 1

У таблиці наведено приклади запитів до пошукового сервера. Кожен запит має свій код - буква від $ A $ до $ B $. Потрібно розмістити коди запитів у порядку зменшення кількості знайдених сторінок по кожному запиту.

Рисунок 7.

Рішення:

Побудуємо для кожного запиту діаграму Ейлера-Венна:

Малюнок 8.

Відповідь:БВА.

Розв'язання логічного змісту за допомогою діаграм Ейлера-Венна

Приклад 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$;

Тобто. тільки одна людина сходила і до театру, і до кіно, і до цирку.

ДІАГРАМИ ВЕННА - графічний спосіб завдання та аналізу логіко-математичних теорій та їх формул. Будуються шляхом розбиття частини площини на комірки (підмножини) замкнутими контурами (кривими Жордана). У осередках подається інформація, що характеризує аналізовану теорію чи формулу. Мета побудови діаграм не лише ілюстративна, а й операторна – алгоритмічна переробка інформації. Апарат діаграм Венна зазвичай використовується разом із аналітичним.

Спосіб розбиття, кількість осередків, а також проблеми запису в них інформації залежать від теорії, яка теж може вводитися (описуватися) графічно - деякими діаграмами Венна, що задаються спочатку, зокрема, разом з алгоритмами їх перетворень, коли одні діаграми можуть виступати як оператори , що діють інші діаграми. Наприклад, у разі класичної логіки висловлювань для формул, складених з п різних пропозиційних змінних, частина площини (універсум) ділиться на 2" осередків, відповідних конституентам (у кон'юнктивній або диз'юнктивній формі). Діаграмою Венна кожної формули вважається така площина, в осередках якої ставиться (або не ставиться) зірочка *. Так, формулу

(¬ а& ¬ b&c) V (а&¬ b&c) V (¬ a&b&¬ c)

з трьома пропозиційними змінними a, b і c визначає діаграма, зображена на малюнку, де зірочки в осередках відповідають кон'юнктивним складникам цієї досконалої нормальної диз'юнктивної формули. Якщо зазначених зірочками осередків немає, то діаграмі Венна зіставляється, напр., тотожно хибна формула, скажімо (a&¬a).

Індуктивний спосіб розбиття площини на 2" осередків перегукується з працями англійського логіка Дж. Венна, називається способом Венна і полягає в наступному:

1. При n = 1, 2, 3 очевидно використовуються кола. (На наведеному малюнку n = 3.)

2. Припустимо, що за n = k (k ≥ 3), вказано таке розташування до фігур, що площина розділена на 2k осередків.

Тоді для розташування k+1 фігури на цій площині достатньо, по-перше, вибрати незамкнену криву (пор без точок самоперетину, тобто незамкнуту криву Жордана, що належить кордонам всіх 2k осередків і має з кожною з цих меж тільки один спільний шматок. По-друге, обвести φ замкнутої кривої Жордана Ψ k+1 так, щоб крива Ψ k+1 проходила через всі 2k осередки і перетинала кордон кожного осередку лише двічі. Таким чином вийде розташування n=k+1 фігур таке, що площина розділиться на 2k+1 комірок.

Для подання інших логіко-математичних теорій метод венівських діаграм розширюється. Сама теорія записується так, щоб виділити елементи її мови у придатній для графічного зображення формі. Напр., атомарні формули класичної логіки предикатів записуються як слова виду P(Y1..Yr), де P - предикатна, а Y1,..., Yr - предметні змінні, необов'язково різні; слово Y1,..., Yr – предметний інфікс. Очевидний теоретико-множинний характер діаграм Венна дозволяє представляти та досліджувати за їх допомогою, зокрема, теоретико-множинні числення, напр., обчислення ZF теорії множин Цермело-Френкеля. Графічні методи у логіці та математиці розвивалися здавна. Такі, зокрема, логічний квадрат, кола Ейлера та оригінальні діаграми Л. Керролла. Однак метод діаграм Венна суттєво відрізняється від відомого методу кіл Ейлера, що використовується у традиційній силогістиці. У основі венновских діаграм лежить ідея розкладання булевської функції на конституенти - центральна в алгебрі логіки, що зумовлює їх оперативний характер. Свої діаграми Венн застосовував насамперед на вирішення завдань логіки класів. Його діаграми можна ефективно використовувати і для вирішення завдань логіки висловлювань та предикатів, огляду наслідків з посилок, вирішення логічних рівнянь, а також інших питань, аж до проблеми вирішення. Апарат діаграм Венна знаходить застосування у додатках математичної логіки та теорії автоматів, зокрема при вирішенні завдань, пов'язаних з нейронними ланцюгами та проблемою синтезу надійних схем із відносно мало надійних елементів.

А. С. Кузічов

Нова філософська енциклопедія. У чотирьох томах. / Ін-т філософії РАН. Науково-ред. порада: В.С. Степін, А.А. Гусейнов, Г.Ю. Семигін. М., Думка, 2010, т. I, А – Д, с. 645.

Література:

Venn J. Symbolic logic. L., 1881. Ед. 2, rev. L., 1894;

Кузічов А. С. Діаграми Венна. Історія та застосування. М., 1968;

Він же. Вирішення деяких задач математичної логіки за допомогою діаграм Венна. - У кн.: Дослідження логічних систем. М., 1970.

Рівність множин.

Безліч Аі Ввважаються рівними, якщо вони складаються з тих самихелементів.

Рівність множин позначають так: А = В.

Якщо множини не рівні, то пишуть А ¹ В.

Запис рівності двох множин А = Веквівалентна запису АÌ В, або ВÌ А.

Наприклад, безліч рішень рівняння x 2 - 5x+ 6 = 0 містить ті самі елементи (числа 2 і 3), що і безліч простих чисел, менших п'яти. Ці дві множини рівні. (Простим числом називається натуральне число, яке ділиться без залишку тільки на 1 і на себе; при цьому 1 - простим числом не є.)

Перетин (множення) множин.

Безліч D, що складається з усіх елементів, що належать і безлічі А і безлічі В, називається перетином множин Аі Ві позначається D = А Ст.

Розглянемо дві множини: X= (0, 1, 3, 5) та Y= (1, 2, 3, 4). Числа 1 і 3 і тільки вони належать одночасно обох множин Хі Y.Складене з них безліч (1, 3) містить усі загальні для множин Хі Yелементів. Таким чином, безліч (1, 3) є перетином розглянутих множин Хі Y:

{1, 3} = {0, 1, 3, 5} {1, 2, 3, 4}.

Для відрізка [-1; 1] та інтервалу ]0; 3[ перетином, тобто безліччю, що складається із загальних елементів, є проміжок ]0; 1] (рис. 1).

Рис. 1. Перетином відрізка [-1; 1] та інтервалу ]0; 3 є проміжок 0; 1]

Перетином безлічі прямокутників і безлічі ромбів є безліч квадратів.

Перетин безлічі учнів восьмих класів даної школи і безлічі членів хімічного гуртка тієї ж школи є безліч учнів восьмих класів, що є членами хімічного гуртка.

Перетин множин (та інші операції - див. нижче) добре ілюструється при наочному зображенні множин на площині. Ейлер запропонував для цього використати кола. Зображення перетину (виділено сірим) множин Аі Вза допомогою кіл Ейлера представлено на рис. 2.

Рис. 3. Діаграма Ейлера-Венна перетину (виділено сірим) множин Аі В, що є підмножинами деякого універсуму, зображеного у вигляді прямокутника

Якщо множини Аі Вне мають спільних елементів, то кажуть, що ці множини не перетинаються або що їх перетин - порожнє безліч, і пишуть А В = Æ.

Наприклад, перетин безлічі парних чисел з безліччю непарних чисел порожній.

Порожнім є і перетин числових проміжків ]-1; 0] та -1; 0] і )