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

Основные логические связки. Формулы алгебры высказываний. Равносильность. Множества истинности. Полные системы связок. Варианты импликации. Функции алгебры логики. Фиктивные и существенные переменные.

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

Построение формул алгебры высказываний по заданной функции. Релейно-контактные схемы и алгебра высказываний. Логика предикатов. Одноместные, двуместные, многоместные предикаты. Основные операции над предикатами. Кванторы. Обобщенный закон де Моргана.

Тема 3. Графы.

Основные понятия, связность, изоморфизм. Эйлеровы и Гамильтоновы линии на графе. Теоремы Эйлера. Матрицы для графов. Числа, характеризующие граф (цикломатическое, хроматическое число графа, числа внутренней и внешней устойчивости графа). Планарность, гомеоморфизм графов. Теорема Понтрягина - Куратовского. Операции над графами.

Деревья, свойства деревьев. Задача о кратчайшем дереве, ее экономическая интерпретация. Алгоритм Краскала.

Задачи об определении путей минимальной и максимальной длины на графе, их экономическая интерпретация. Алгоритм Форда. Сетевое планирование, параметры сетевого графа. Критический путь и критическое время сетевого графа.

Начальные сведения

Множества

1. Понятие множества. Понятие множества является одним из наиболее общих математических понятий. Его определение не удается свести к другим понятиям. Поэтому для понятия множества дается описательное определение, содержание и смысл которого раскрываются при изучении теории множеств. Множество – это набор, совокупность каких-либо объектов, называемых его элементами, обладающих некоторым общим для них характеристическим свойством. В качестве примеров можно привести множество действительных чисел, множество решений заданного алгебраического уравнения, множество прямых, проходящих через заданную точку. В принципе никаких ограничений на природу элементов, их количество и свойства не налагается, так что допустимо рассмотрение таких множеств, как множество налогоплательщиков, множество процентных ставок и т. п.

Элементы, составляющие множество, обычно обозначаются малыми латинскими буквами, а само множество – большой латинской буквой. Знак ∈ используется для обозначения принадлежности элемента множеству. Запись a∈A означает, что элемент a принадлежит множеству A. Если некоторый объект x не является элементом множества A, пишут x∉A. Например, если A – это множество четных чисел, то 2∈A, а 1∉A. Множества A и B считаются равными (пишут A=B), если они состоят из одних и тех же элементов.

Если множество содержит конечное число элементов, его называют конечным; в противном случае множество называется бесконечным. Если множество A конечно, символом |A| будет обозначаться число его элементов. Множество, не содержащее ни одного элемента, называется пустым и обозначается символом ∅. Очевидно, |∅|=0.

Пример. Пусть A – множество действительных решений квадратного уравнения x²+px+q=0. Множество A конечно, |A|≤2. Если дискриминант D = p²–4q отрицателен, множество A пусто. Множество действительных решений квадратичного неравенства x²+px+q≤0 конечно, если D≤0, и бесконечно, если D>0.􀀀

Конечное множество может быть задано перечислением всех его элементов. Если множество A состоит из элементов x, y, z, …, пишут A={x, y, z, …}. Например, A={0, 2, 4, 6, 8} – множество четных десятичных цифр; B={2, 3} – множество решений уравнения x²–5x+6=0; C={0, 1, 2, 3, 4, 5, 6} – множество остатков при делении целых чисел на 7.

Иногда перечислением элементов задают и бесконечное множество. Это делают в тех случаях, когда ясен алгоритм последовательного порождения элементов. Например, A={0, 1, 4, 9, 16, …} – множество квадратов целых чисел.

В общем случае множества можно определять по так называемой схеме свертывания. При заданном характеристическом свойстве F и заданном классе элементов K множество A определяется как множество, которое содержит все элементы из K, обладающие свойством F. Для определения по схеме свертывания используется следующая запись:

A = {x | x обладает свойством F}.

Применяя сокращение F(x) для обозначения того, что элемент x обладает свойством F, будем писать

A = {x | F(x)}.

Класс K может быть указан явно; в этом случае используется запись

A = {x∈K | F(x)}.

Множество четных чисел P можно определить как

P = {x | x – четное целое число},

или как

P = { x∈ Z | x четно},

где через Z обозначено множество целых чисел.

Неограниченное применение схемы свертывания ведет к противоречиям. Например, можно получить «множество всех множеств»:

M = {x | x – множество}.

Если считать M множеством, то получаем M∈M.

Рассмотрим парадокс Рассела, открытый в 1902 году. Назовем множество правильным, если оно не является своим элементом, и неправильным в противном случае. Определим множество R как множество всех правильных множеств. Более формально:

R = {x | x∉R}.

В соответствии с определением для любого множества A справедливо утверждение:

A∈R тогда и только тогда, когда A∉A.

В частности, если считать R множеством, то его само можно взять в качестве A, но тогда мы придем к противоречию:

R∈R тогда и только тогда, когда R∉R.

Более подробно. Если R правильное, то есть не является своим элементом, то оно должно находиться в R, то есть быть своим элементом. Если же R неправильное, то оно является своим элементом, то есть содержится в R, но R содержит только правильные множества. Таким образом, R не может быть ни правильным, ни неправильным.

Введем используемое в дальнейшем понятие индексированного семейства множеств. Пусть I – некоторое множество, каждому элементу которого i сопоставлено однозначно определенное множество A_i. Элементы множества I называют индексами, а совокупность множеств A_i называют индексированным семейством множеств и обозначают через (A_i)_i∈I.

2. Подмножества. Говорят, что множество B является подмножеством (или частью) множества A и пишут B⊂A, если всякий элемент множества B является элементом множества A. Например, множество натуральных чисел N является подмножеством множества целых чисел Z, а последнее в свою очередь является подмножеством множества рациональных чисел Q, то есть N⊂Z и Z⊂Q, или, короче, N⊂Z⊂Q. Легко видеть, что если B⊂A и A⊂B, то множества A и B состоят из одних и тех же элементов, и, значит, A=B. Нарядус обозначением B⊂A используется также A⊃B, имеющее тот же смысл.

Вообще говоря, подмножество множества A может быть задано определяющим свойством. Например, свойство быть четным числом определяет в множестве целых чисел подмножество четных чисел. Каково бы ни было множество A, пустое множество и само A являются его подмножествами: ∅⊂A, A⊂A. Пустое множество может быть задано свойством, которым не обладает ни один элемент множества A, например, x≠x. Возможны и более содержательные ситуации. Например, свойство быть корнем уравнения x²+1=0 задает в множестве действительных чисел пустое подмножество. Множество A может быть задано как свое подмножество каким-нибудь свойством, которым обладают все элементы множества A, например, x=x. Подмножества множества A, отличные от ∅ и A, называются собственными. Для заданного множества A обозначим через 2^A множество всех его подмножеств.

Пример. Пусть A={a, b, c}. Тогда множество 2^A состоит из следующих элементов:

{∅}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}.􀀀

Далее будет показано, что если множество A конечно и содержит n элементов, то это множество имеет 2ⁿ подмножеств, то есть |2^A |=2^|A|.

3. Пересечение и объединение множеств. Пересечение множеств A и B, обозначаемое A∩B, – это множество, состоящее из всех тех элементов, которые принадлежат обоим множествам A и B. Например, если A={1,2,3} и B={2,3,4}, то A∩B={2,3}. В соответствии с определением

A∩B⊂A и A∩B⊂B,

причем A∩B является в определенном смысле наибольшим множеством, обладающим этими свойствами:

если C⊂A и C⊂B, то C⊂A∩B.

Далее, A∩B=B тогда и только тогда, когда B⊂A. Если множества A и B не имеют общих элементов, их пересечение пусто, A∩B=∅; в этом случае говорят, что множества A и B не пересекаются.

Объединение множеств A и B, обозначаемое A∪B, – это множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств A и B. Например, если A={1,2,3} и B={2,3,4}, то A∪B={1,2,3,4}. В соответствии с определением

A⊂A∪B и B⊂A∪B,

причем A∪B является наименьшим множеством, обладающим этими свойствами:

если A⊂C и B⊂C, то A∪B⊂C.

Далее, A∪B=B тогда и только тогда, когда A⊂B.

Операции пересечения и объединения можно обобщить на случай произвольного индексированного семейства множеств.

Если множество индексов состоит из натуральных чисел, используются и другие обозначения. Например, AПересечением семейства множеств (A_i)_i∈I называется множество A, состоящее из всех тех элементов, которые принадлежат каждому из множеств A_i. Пишут A=∩_i∈IA_i1∩A₂∩A₃, если I={1,2,3}; A₁∩A₂∩…∩A_n или, если I={1,2,…,n};, если I – это множество всех натуральных чисел, и т. п. Аналогично объединением семейства множеств (AIniiA1=I∞=1iiA_i)_i∈I называется множество A, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств A_i. Для объединения используют обозначение A=∪_i∈IA_i и другие, подобные тем, которые используются для пересечения.

Пример. Пусть +=1;0nnAn, где n=1,2,… пробегает множество натуральных чисел. Тогда, очевидно, =∞=21;01InnA, поскольку A₁⊂A₂⊂…. Покажем, что. В самом деле, если x∈[0; 1), то x∈A)1;0[1=∞=UnnA_n, когда x>1/n, то есть при n>1/x. Если же x<0 или x>1, то x не попадает ни в одно из A_n, а значит, и в их объединение.􀀀

4. Разность множеств. Дополнение множества. Разность множеств A и B, обозначаемая A\B, – это множество, состоящее из всех тех элементов, которые принадлежат множеству A, но не принадлежат множеству B. Например, если A={1,2,3} и B={2,3,4}, то A\B={1}. В соответствии с определением

A\B⊂A и (A\B) ∩B=∅,

причем A\B является в определенном смысле наибольшим множеством, обладающим этими свойствами:

если C⊂A и C∩B=∅, то C⊂A\B.

Далее, A\B=A тогда и только тогда, когда A∩B=∅, и A\B=∅ тогда и только тогда, когда A⊂B. Если B⊂A, то разность A\B называют также дополнением (или относительным дополнением) множества B в множестве A. Иногда относительное дополнение будет обозначаться через AB. Любое собственное подмножество B множества A вместе со своим относительным дополнением образует разбиение множества A на два непересекающихся множества:

∅=∩ABB, ABBA=∪.

Часто в теоретико-множественных конструкциях используется универсальное множество U. Считается, что все рассматриваемые множества являются его подмножествами. Относительное дополнение множества A до универсального множества называется дополнением (без прилагательного «относительное») и обозначается через A. Очевидно, ∅=U и U=∅.

Симметрическая разность множеств A и B, обозначаемая AΔB, – это множество, состоящее из всех тех элементов, которые принадлежат одному из множеств A и B, но не принадлежат другому. Более формально,

AΔB = (A\B) ∪ (B\A).

Например, если A={1,2,3} и B={2,3,4}, то AΔB={1,4}.

5. Свойства операций над множествами. Приведем основные тождества так называемой алгебры множеств (будем предполагать, что используемые в тождествах множества A, B, C являются подмножествами универсального множества U).

Коммутативность:

1. A∩B=B∩A; 1’. A∪B=B∪A.

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

2. (A∩B) ∩C=A∩ (B∩C); 2’. (A∪B) ∪C=A∪ (B∪C).

Дистрибутивность:

3. (A∪B) ∩C=(A∩B) ∪ (B∩C); 3’. (A∩B) ∪C=(A∪B) ∩ (B∪C).

Идемпотентность:

4. A∩A=A; 4’. A∪A=A.

Законы поглощения:

5. A∩ (A∪B)=A; 5’. A∪ (A∩B)=A.

Законы нуля и единицы:

6. A∩U=A; 6’. A∪∅=A.

7. A∩∅=∅; 7’. A∪U=U;

8. ∅=∩AA; 8’. UAA=∪.

Инволютивность дополнения: 9. A=A.

Законы де Моргана:

10. BABA∪=∩; 10’. BAB∩=∪A.

Убедиться в справедливости перечисленных свойств можно путем несложной непосредственной проверки.

Пример. Проверим первый из законов де Моргана. Покажем сначала, что BABA∪⊂∩. Предположим, что BAx∩∈. Тогда x∉A∩B, так что x не принадлежит хотя бы одному из множеств A и B. Таким образом, x∉A или x∉B, то есть Ax∈ или Bx∈. Это означает, что BAx∪∈BA∩. Мы показали, что произвольный элемент множества является элементом множества BA∪. Следовательно, BA∪⊂BA∩. Обратное включение BABA∪⊃∩ доказывается аналогично. Достаточно повторить все шаги предыдущего рассуждения в обратном порядке.􀀀

6. Диаграммы Эйлера–Венна. Для наглядного представления операций над подмножествами некоторого универсального множества используются диаграммы Эйлера–Венна. На таких диаграммах фон рисунка соответствует универсальному множеству, а фигуры изображают множества, участвующие в операциях. Например, на следующем рисунке:

круги изображают множества A и B. Объединение двух кругов соответствует объединению A∪B; область 3 соответствует пересечению A∩B; область 1 – множеству A\B=BA∩; область 2 – множеству BAAB∩=\; область 4 – множеству BA∪; объединение областей 1 и 2 соответствует симметрической разности AΔB. Легко видеть, что имеет место следующее соотношение:

AΔB = (A∪B)\(A∩B).

7. Прямое произведение множеств. Из любой пары элементов a и b (не обязательно различных) можно составить новый элемент – упорядоченную пару (a,b). Упорядоченные пары (a,b) и (c,d) считают равными и пишут (a,b)=(c,d), если a=c и b=d. В частности, (a,b)=(b,a) лишь в том случае, когда a=b. Элементы a и b называют координатами упорядоченной пары (a,b) (соответственно первой и второй).

Прямым (декартовым) произведением множеств A и B называется множество всех упорядоченных пар (a,b), где a∈A и b∈B. Прямое произведение множеств A и B обозначается через A×B. В соответствии с определением имеем

A×B = {(a,b)| a∈A, b∈B}.

Пример. Пусть A={1,2,3} и B={2,3,4}. Тогда множество A×B состоит из следующих девяти элементов: (1,4), (2,4), (3,4), (1,3), (2,3), (3,3), (1,2), (2,2), (3,2). Графически элементы произведения множеств A×B удобно помещать на «координатной плоскости», считая, что первый множитель A расположен на горизонтальной полуоси, а второй множитель B – на вертикальной. Например,

(1,4) (2,4) (3,4)

(1,3) (2,3) (3,3)

(1,2) (2,2) (3,2)

􀀀

Подобно парам, можно рассматривать упорядоченные тройки, четверки и, вообще, упорядоченные наборы элементов произвольной длины. Упорядоченный набор элементов длины n обозначается через (a₁,a₂,…,a_n). Для таких наборов используется также название кортеж длины n. Допускаются в том числе и кортежи длины 1 – это просто одноэлементные множества. Кортежи (a₁,a₂,…,a_n) и (b₁,b₂,…,b_n) считаются равными, если a₁=b₁, a₂=b₂,…,a_n=b_n.

По аналогии с произведением двух множеств определим прямое произведение множеств A₁, A₂, …, A_n как множество всех кортежей (a₁,a₂,…,a_n) таких, что a₁∈A₁, a₂∈A₂, …, a_n∈A_n. Обозначается прямое произведение через A₁×A₂×…×A_n.

Понятие прямого произведения может быть обобщено на случай произвольного семейства множеств (A_i)_i∈I. Назовем I-кортежем набор элементов (A_i)_i∈I такой, что a_i∈A_i для каждого i∈I. Прямое произведение семейства множеств (A_i)_i∈I – это множество, состоящее из всех I-кортежей. Для обозначения этого множества используется символ Π_i∈IA_i и его разновидности, подобные тем, которые применяются для обозначения пересечения и объединения семейства множеств.

В случае, когда множество A умножается само на себя, произведение называют (декартовой) степенью и используют экспоненциальные обозначения. Так, в соответствии с определением A×A=A², A×A×A=A³ и т. д. Считается, что A¹=A и A⁰=∅.

Непосредственно из определений следует справедливость следующих соотношений:

(A∪B)×C=(A×C) ∪ (B×C); (A∩B)×C=(A×C) ∩ (B×C);

(A\B)×C=(A×C)\(B×C).

Не нашли, что искали? Воспользуйтесь поиском: