Решение уравнений алгебры множеств.

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

Множеством S называется объединение в одно целое объектов, хорошо различимых нашей мыслью или интуицией. Эти объекты называется элементами множества S. Такое интуитивное определение дал немецкий математик Г. Кантор. В данном определении важны следующие два момента:

1. Множество- это нечто, состоящее из хорошо различимых объектов.

2. Это нечто мыслится как единое целое.

Множества бывают конечными и бесконечными, Количество элементов в конечном множестве называется мощностью множества. Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается Æ. Множество, включающее в себя в се рассматриваемые множества, называется универсальным множеством или универсумом и обозначается U. Символом Î обозначается отношение принадлежности. Запись xÎC означает, что элемент х принадлежит множеству Х. Если элемент х не принадлежит множеству Х, то пишут хÏХ.

Множества могут быть заданы следующими способами:

1. перечислением (списком своих элементов);

2. описанием свойств, которыми должны обладать его элементы;

3. порождающей процедурой.

 

ПРИМЕР

 

Множество экзаменационных оценок может быть задано:

1. перечислением А={2; 3; 4; 5}

2. описанием свойств: А={a| a- экзаменационная оценка}

3. порождающей процедурой: А={а| а=2+i, i= }

Подмножеством множества А называется множество В, если любой элемент множества В принадлежит множеству А:

(1)

Символом Í обозначается отношение включения. Запись АÍВ означает множество А является подмножеством множества В.

Не следует смешивать отношение принадлежности Î и отношение включения Í. Отношение принадлежности применяется к элементам множества, а отношение включения к множествам. Хотя 1Î{1},{1}Î{{1}}, не верно, что 1Î{{1}}, так как единственным элементом множества {{1}} является {1}.

Если АÍB и A¹B, то AÌB, то есть множество А строго включено в множество В. Символ Ì называется строгим включением.

Свойства подмножеств.

 

1. Рефлексивность. Множество А является подмножеством множества А:

. (2)

2. Транзитивность. Если множество А является подмножеством множества В, а множество В является подмножеством множества С, то множество А является подмножеством множества С:

(3)

3. Принцип объемности. Если множество А является подмножеством множества В, а множество В является подмножеством множество А, то множество А равно множеству В:

(4)

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

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

(5)

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

(6)

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

(7)

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

(8)

5. Дополнением множества А называется множество всех тех элементов, которые не принадлежат множеству А:

(9)

Для наглядного представления операций над множествами используют диаграммы Эйлера- Венна.

 

Рис 1. Диаграмма Эйлера-Венна

где - это области 1,2,3

- это область 3;

- это область 1;

- это область 1,3

- это области 2,4.

Алгебра теории множеств.

Для любых множеств А, В и С выполнимы следующие тождества:

1. Коммутативный закон

(9)

2. Ассоциативный закон

(10)

3. Дистрибутивный закон

(11)

4. Закон поглощения

(12)

5. Закон идемпотентности

(13)

6. Закон де Моргана

(14)

7. Закон исключенного третьего

(15)

8. Закон противоречия

(16)

9. Операции с универсумом:

(17)

10. Операции с пустым множеством:

(18)

11. (19)

12. Закон двойного дополнения

(20)

13. (21)

14. (22)

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

Кортеж.

Кортеж -это упорядоченный набор элементов. Кортеж характеризуется элементами и их порядком расположения. Элементы кортежа называются компонентами. Компоненты нумеруют слева направо. Число компонент определяет длину кортежа. Кортеж обозначается A=< а₁, а₂,..., а_n >.

Кортеж длиной в две компоненты называется парой, кортеж длиной в три компоненты - тройка, длиной в n - n-ка.

Проекцией кортежа на i-тую ось называется его i -тая компонента.

Проекцией кортежа на оси i₁, i₂,..., i_q оси называется кортеж, состоящий из i₁, i₂,..., i_q компонент, где .

Проекцией кортежа на пустое множество осей является пустой кортеж.

ПРИМЕР

Пусть дан кортеж А=< a,b,c,d>. Найти проекции на 1 ось, 3 ось, 5 ось, 1 и 4 оси, 4 и 2 оси.

Пр А₁=<a>

Пр А₃=<c>

Пр А₅ не определена

Пр А_1,4=<a,d>

Пр А_4,2 не определена.

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

 

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

Проекцией множества называется множество проекций соответствующих кортежей.

Пример.

А={<1,2,3>;<4,5,6>;<3,3,3>}

Пр А₁={<1>;<4>;<3>}

Пр А_1,3={<1,3>;<4,6>;<3,3>}

Пр А_3,1 не определена.

 

График и свойства графика

Графиком называется множество пар. Графики могут задаваться:

1. перечислением:

2. описанием свойств:

Пара <a,b> называется инверсией пары <c,d>, если a=d, b=c.

График P^-1 называется инверсией графика P, если он состоит из инверсий пар графика P.

 

 

ПРИМЕР.

P={<1,2>;<2,3>;<3,4>,<4,5>}.

P^-1={<2,1>;<3,2>;<4,3>;<5,4>}.

 

График называется симметричным, если вместе с каждой парой он содержит её инверсию.

(27)

Диагональным называется график вида:

, (28)

для всех x,yÎ M.

Композицией графиков называется график R, такой что для любой пары <x,y>ÎR есть такой элемент z, что <x,z,>ÎP, а <z,y>ÎQ.

, (29)

ПРИМЕР.

1. Пусть заданы графики P={<a,b>; <a,c>; <f,b>} и Q={<c,c>; <b,d>; <k,f>; <b,m>}. Найти композицию графиков P и Q.

P Q={<a,d>;<a,m>;<a,c>;<f,d>;<f,m>}.

2. Пусть заданы графики P и Q:

 

 

Рис 5. Композиция графиков.

 

Свойства графиков.

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

Инъективным графиком называется график, который не содержит пары с одинаковыми вторыми и различными первыми компонентами.

 

 

 

Рис 6. Примеры графиков.

P1-График функциональный, но не инъективный.

P2-График инъективный, но не функциональный.

P3- График функциональный и инъективный.

Возможно другое изображение графиков.. Пусть , а

 

Рис 7. Примеры графиков.

P1-График функциональный, но не инъективный.

P2-График инъективный, но не функциональный.

P3- График функциональный и инъективный.

 

Соответствия.

 

Соответствием называется тройка вида . При этом - область отправления (определения), - область прибытия (значений), - график соответствия.

 

ПРИМЕР.

 

Дано соответствие <P,X,Y> такое, что:

X={x| x ³ 2};

Y={y| y ³ 5};

P={<x,y>| y=x²}.

 

 

Рис. 9 График соответствия.

 

Если , то данное соответствие называется полным.

Если , то данное соответствие называется пустым.

 

Свойства соответствий.

 

1. Соответствие называется функциональным, если его график функционален.

2. Соответствие называется инъективным, если его график инъективен.

3. Соответствие называется всюду определенным, если проекция его графика на первую ось совпадает с областью отправления. Пр P₁=X.

4. Соответствие называется сюръективным, если проекция его графика на вторую ось совпадает с областью прибытия. Пр P₂=Y.

5. Соответствие называется биективным (взаимнооднозначным), если оно функционально, инъективно, всюду определенно, сюръективно.

 

ПРИМЕР.

 

Дано соответствие <P,X,Y>, где X - множество конфет, Y - множество фантиков, P - ”быть упакованным в фантик”. Какими свойствами обладает данное соответствие?

Данное соответствие

1. функциональное, так как две и более конфет не может быть упаковано в один фантик;

2. инъективное, так как одна конфета не может быть завернута в два антика одновременно (брак упаковочной техники не рассматривается);

3. не всюду определенное, так как существуют сорта конфет, которые продаются без фантиков (зефир, мармелад);

4. сюръективное, так как фантики без конфет - это мусор;

5. не биективное, так как является несюръективным соответствием.

 

Отношения.

 

Отношением называется пара вида такая, что ФÍM² (M²=M M), где Ф - график отношения, М - это множество, между элементами которого существует данное отношение.

 

ПРИМЕР.

 

Пусть дано , где , а график отношения определяется как . Это отношение ”X больше Y” на множестве натуральных чисел. Данное отношение задано описанием свойств. Перечислением данное отношение может быть задано следующим образом:

j=<F,N>,

где F={<2,1>;<3,1>;<3,2>;¼<4,1>;<4,2>;¼}

Отношение называется полным, если F=M².

Отношение называется отношением равенства, если F=DM={<x,x>;<y,y>;¼}.

Отношение называется отношением неравенства, если F=M²\DM.

Запись xjy означает, что между x и y существует отношение j.

 

Операции над отношениями.

Пусть даны два отношения j=<F,M> и r=<R,M>. Над данными отношениями могут быть выполнены следующие операции:

1. объединение j r=<F R,M>.

2. пересечение j r=<Ф R,M>.

3. дополнение `

4. разность j\r=<Ф\R,M>.

5. композиция j r=<Ф R,M>.

6. инверсия j^-1=<Ф^-1,M>.

 

Антирефлексивность.

Отношение называется антирефлексивным, если для всех x выполняется условие: ùxjx (символ “ ù“ означает “не выполняется”) или .

3. Симметричность.

Отношение называется симметричным, если для всех x выполняется условие: xjy Þ yjx или Ф=Ф^-1.

Антисимметричность.

Отношение называется антисимметричным, если для всех x выполняется условие: xjy и x¹y Þù yjx или ÍDM.

Асимметричность.

Отношение называется асимметричным, если для всех x выполняется условие: xjy Þù yjx или =Æ.

6. Связность (полнота).

Отношение называется связным (полным), если для всех x выполняется условие: x¹y Þ xjy или yjx или М²\DMÍ .

Транзитивность.

Отношение называется транзитивным, если для всех x выполняется условие: xjy и yjz Þ xjz или Ф ФÍФ.

 

ПРИМЕР

 

Какими свойствами обладает отношение j=<Ф,X>, где X={1; 2; а},

Ф={<1,1>;<a,a>;<a,2>;<2,2>}.

Определим Ф^-1, DX:

Ф^-1={<1,1>;<a,a>;<2,a>;<2,2>}

DX={<1,1>;<2,2>;<a,a>}.

Отношение является:

- рефлексивным, так как DXÍФ;

- антисимметричным, так как ÍDX;

- транзитивным, так как Ф Ф={<1,1>;<a,a>;<a,2>;<2,2>}ÍФ;

- несвязное, так как X²\DX={<1,2>;<1,a>;<2,1>;<2,a>;<a,1>;<a,2>}Ë Ф Ф^-1={<1,1>;<a,a>;<a,2>;<2,2>;<2,a>}.

Отношение называется отношением эквивалентности, если оно рефлексивное, симметричное и транзитивное.

Отношение называется отношением нестрогого (частичного) порядка (), если оно рефлексивное, антисимметричное и транзитивное.

Отношение называется совершенно нестрого порядка (),если оно рефлексивное, антисимметричное, транзитивное и связное.

Отношение называется строго порядка (), если оно антирефлексивное, антисимметричное и транзитивное.

Отношение называется совершенно строго порядка (), если оно антирефлексивное, транзитивное и связное.

Решетки.

Диаграммы Хассе.

Рассмотрим отношение частичного порядка: “быть подмножеством“ на множестве-степени М={1,2}.

j=<F,M>, где

Ф={<{Æ},{Æ}>;<{Æ},{1}>;<{Æ},{2}>;<{Æ},{1,2}>;<{1},{1}>;<{1},{1,2}>;<{2},{2}>;<{2},{1,2}>};<{1,2},{1,2}>}.

Графически данное отношение можно изобразить следующим образом:

 

 

РИС 10 Графическое изображения отношения

Отношение является рефлексивным (графически это отображается петлями), антисимметричным (графически - однонаправленные стрелки), транзитивным (графически - транзитивными замыканиями вида:

Для отношений частичного порядка применимы диаграммы Хассе, которые строятся на основе обыкновенной диаграммы следующим образом:

1. рефлексивные петли и транзитивные связи не изображаются;

2. большие элементы (элементы, в которые входят стрелки) располагают выше.

 

Таким образом, диаграмма Хассе для вышеприведенного примера будет выглядеть следующим образом:

 

РИС 11 Диаграмма Хассе

 

Для частично упорядоченного множества справедливо следующее:

1. Элемент аÎА называется наибольшим (наименьшим), если для всех хÎ А выполняется x a (a x). Если наибольший (наименьший) элемент существует, то он единственный.

2. Элемент аÎА называется максимальным (минимальным), если нет а множестве А элементов, больших (меньших), чем а. Максимальных (минимальных) элементов может быть несколько.

3. Пусть ВÍА. Элемент аÎА называется можарантой (минорантой), если для всех х Î В этот элемент является наибольшим (наименьшим).

4. Множество мажорант В образует верхнюю границу множества В. Множество минорант В образует нижнюю границу множества В.

5. Наименьший элемент верхней границы называется точной верхней границей, или supremum (sup) B. Наибольший элемент нижней границы называется точной нижней границей, или infimum (inf) B.

6. Частично упорядоченное множество, у которого для любой пары элементов определен и существует sup и inf, называется решеткой.

 

ПРИМЕР

Пусть дано отношение, представленное на диаграмме Хассе

 

 

РИС 12 Диаграмма Хассе

 

Отношение А не является решеткой, т.к. элементы 7 и 8 не имеют sup.

Отношение В является решеткой, т.к. любая пара имеет sup и inf.

 

Математическая логика

Формулы равносильности.

1) Коммутативность

АVВ º ВVА А&В º В&А

 

2) Ассоциативность

АV(ВVС) º (АVВ)VС А&(В&С) º (А&В) &С

 

3) Дистрибутивность

АV(В&С) º (АVВ)&(АVС) А&(ВVС) º (А&В)V(А&С)

 

4) Идемпотентность

АVА º А А&А º А

 

5) Поглощение

АV(А&В) º А А&(АVВ) º А

 

6) Закон де Моргана

º & º V

 

7) Закон исключающий третьего

АV1 º 1 А&1 º A

8) Закон противоречия

AVÆ º A A&Æ º Æ

 

9) Закон двойного отрицания

º A

 

10) º 1, º 0

11) A®B º VB

12) A«B º (A®B)&(B®A)

13) AÅB º A& V &B

14) A | B º º V

15) A¯B º º &

 

ПРИМЕР

 

Доказать:

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

Пусть - произвольная функция алгебры логики переменных.

Рассмотрим формулу

(2.1)

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

Вместе с тем формула (2.1) содержит в виде логических слагаемых всевозможные конъюнкции указанного вида.

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

Составление формул по таблице истинности. может быть представлена в виде:

(2.2)

 

ПРИМЕР Пусть функция имеет следующую таблицу истинности:

 

Тогда функция может быть определена в следующем виде:

Нетрудно заметить, что для определении функции берутся только те наборы переменных , при которых функция принимает значения 1, что значительно упрощает процедуру определения функции .

 

Формула (2.1) обладает свойствами:

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию .

2. Все логические слагаемые формулы различны.

3. Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.

4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

5. Перечисленные свойства называются свойствами совершенства.

 

Метод Квайна.

 

Алгоритм метода Квайна включает в себя следующие этапы:

1. Любая формула приводится к СДНФ.

2. СДНФ приводится к сокращенной ДНФ (СкДНФ). При получении СкДНФ используются следующие формулы равносильности:

а) Формула склеивания

б) Формула неполного склеивания

в) Формула поглощения

Применяя все возможные процедуры склеивания, СДНФ приводится к СкДНФ.

3. Минимальная форма формулы (МДНФ ) получается на основе импликантной матрицы путем нахождения минимального покрытия этой матрицы. Импликанта – это элементарная конъюнкция СкДНФ. Конституента единицы – это элементарная конъюнкция СДНФ. Импликантная матрица – это матрица импликант и констиуент единиц. (столбцы - конституенты единицы, строки – импликанты). МДНФ может быть несколько.

 

ПРИМЕР.

Необходимо найти МДНФ формулы:

1 2 3 4 5 6

Осуществляем всевозможные склеивания

1-2

1-4

2-3

3-6

4-5

5-6

СкДНФ имеет вид:

Составляем импликантную матрицу

	+	+
	+			+
		+	+
			+			+
				+	+
					+	+

 

По данной импликантной матрице можно выбрать следующие МДНФ

 

Метод минимизирующих карт.

Алгоритм метода минимизирующих карт включает в себя следующие этапы:

1. Любая формула приводится к СДНФ.

2. Составляется таблица всевозможных сочетаний переменных.

3. Из таблицы вычеркиваются те строки, которые не содержат конституенты СДНФ. Конъюнкции этих строк вычеркиваются в других строках.

4. В каждой строке оставляются конъюнкции с минимальным количеством переменных.

5. Из каждой строки выбирается олна конъюнкция и составляется ДНФ.

6. Из построенных ДНФ выбирается минимальная.

 

ПРИМЕР

 

Дана СДНФ

 

							*
							*

* - помечены строки, не содержащие конституенты СДНФ.

После соответствующих преобразований получаем следующую таблицу

 

							*
							*

 

После всевозможного перебора остаются следующие МДНФ:

 

Логика предикат.

 

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

ПРИМЕР

 

Предикатом является высказывание – быть четным числом на множестве натуральных чисел:

- быть четным числом;

Предикаты могут быть одноместные - , двухместные - и многоместные -

 

Квантовые операции.

 

Для предикатов кроме логических операций применимы кванторные операции: всеобщности и существования.

Пусть - предикат, определенный на множестве . Тогда - означает «для всякого (любого) истинно ». Символ называется квантором всеобщности.