Диаграммы Венна. Формула включений-исключений.

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

На первом рисунке выделено множество А. Если обозначить предикат хÎА за р, предикат уÎB за q и предикат zÎC за r, то первому рисунку соответствует область истинности предиката р.

На третьем рисунке отмечена область ВÈС и соответствует оно истинному значению дизъюнкции qÚr. На четвёртом рисунке закрашена область АÇВÇС и соответствует оно значению Т конъюнкции pÙqÙr.

Упражнение 4.

a) Каким множествам и истинным значениям каких предикатов соответствуют закрашенные области на втором и пятом рисунках?

b) Нарисуйте диаграммы Венна для множеств В\А, АDВ, A^сÇBÇC.

c) Нарисуйте диаграммы Венна соответствующего истинному значению для предиката pÙØqÙrÚpÙqÙØrÚØpÙqÙr.

Если мы имеем конечные множества А и В, то можно выразить число элементов АÈВ через числа элементов в А, в В, и в АÇВ. Обозначим число элементов в А через ½А½. Если мы рассмотри сумму ½А½+½В½, то увидим, что мы посчитали зелёные и оранжевые элементы по одному разу, а жёлтые – дважды (см. рис. 6). В объединение же ½АÈВ½ все эти элементы входят по одному разу. Поэтому имеет место формула включения-исключения для двух множеств: ½А½+½В½=½АÈВ½+½АÇВ½.