Т. А. Таран
Н. А. Мыценко
Е. Л. Темникова


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ
«КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ»
Кафедра прикладной математики
Т. А. Таран, Н. А. Мыценко, Е. Л. Темникова
СБОРНИК ЗАДАЧ
ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
2-е издание,
переработанное и дополненное
Утверждено на заседании кафедры прикладной математики
НТУУсКПИ» (протокол № 1 от 29.08.2005)
Киев
Инрес
2005
ББК 22.176я73
Т19
Рецензенты:
А. А. Павлов, д-р техн, наук, проф.;
И. И. Коваленко, д-р техн, наук, проф.
Таран Т. А.
Т19	Сборник задач по дискретной математике / Т. А. Таран, Н. А. Мы-
ценко, Е. Л. Темникова. - 2-е изд., перераб. и доп. — К.: Инрес,
2005. — 64 с. — Библиогр.: с. 62.
Сборник составлен для проведения практических и самостоя-
тельных занятий по дискретной математике.
Для студентов очной и заочной форм обучения специальности
«Прикладная математика».
© Т. А. Таран, Н. А. Мыценко. Е. Л. Темникова, 2005
ВВЕДЕНИЕ
Методические указания содержат задания для самостоятельной работы
по дисциплине «Дискретная математика*. Задания охватывают следующие
темы.
•	Тема 1. Теория множеств. Алгебра множеств.
•	Тема 2. Теория отношений. Свойства бинарных отношений. Отношение
эквивалентности. Классы эквивалентности. Фактор множество.
•	Тема 3. Отображения и функции. Типы отображений: биекция, сюръекция,
инъекция. Композиция отображений.
•	Тема 4. Отношение порядка. Строгий, линейный, частичный порядок.
Диаграммы Хассе.
•	Тема 5. Решетки и их свойства: модулярность, дистрибутивность.
Отображения на частично упорядоченных множествах; изотонность,
гомоморфизмы.
•	Тема 6. Исследование графов. Матричные методы исследования графов.
Исследование типов связности орграфов. Компоненты сильной связности.
Конденсация орграфа. Вершинные базы.
•	Тема 7. Булева алгебра. Булевы формулы. Совершенные дизъюнктивная и
конъюнктивная нормальные формы. Полином Жегалкина. Функциональ-
но замкнутые классы булевых функций. Исследование систем булевых
функций на полноту.
•	Тема 8. Алгебра высказываний. Тавтологии. Логическое следование в
алгебре высказываний.
•	Тема 9. Формальные теории. Исчисление высказываний. Доказательство
и вывод в формальных теориях.
•	Тема 10. Теория предикатов первого порядка. Выполнимость и интерпрета-
ция формул логики предикатов. Логически общезначимые формулы.
•	Тема 11. Логическое следование в логике предикатов. Метод резолюций
доказательства логического следования.
Каждой теме соответствует глава в сборнике задач. Перед заданиями
приводится пример, показывающий, как нужно выполнять и оформлять
данное задание. Каждое задание содержит несколько вариантов.
3
1.	МНОЖЕСТВА
Упражнения
1.1.	Пусть U - множество точек плоскости, на которой задана декартова
система координат Найти пересечение множеств А п В, объединение
Ли В, разности множеств А\В, В\А, дополнения множеств А', В',
изобразить их на плоскости:
Пример. А = {<х, г/>| у < х3}, В - {<х, г/>| у > е*}.
По определению:
1.	А о В = {<х, у>[ у<х3 или у > е*};
2.	Асу В = {<х, у>\ у<х3иу>е*};
3.	А\В = {<х, у>1 у < х3, у < е*};
4.	В\А = {<х, у>\у>е*,у> х3};
5.	А' = {<х, i/>| у > х3};
6.В' = {<х,у>1у<е*}
Задания.
1)	А = {<х, у>10 < х < 1}, В = {<х, у>10 < у < 1 };
2)	А = {<х, у>\у< 2х+5},В ={<х,у>\ у > 0.5х-4};
3)	А = {<х, г/>| x^+i/2 < 4}, В = {<х, у>\ 1 < у < 2,1 < х < 5};
4
4)	A = {<x, y>\ (x-2)2 + (y-3)2 < 4}, В = {<x, y>l 2 <у < 6, 1 <x < 7};
5)	A = {<x, y>l (x-3)2 + (г/-3)2 < 9}, В = {<x, y>| у < x};
6)	A = {<x, y>\ |z/| < 4, 1 < x < 5}, В = {<x, у>1 у > -x};
7)	A = {<x, у>1 y>ex},B = {<x, г/>| x2 + y2 < 9};
8)	A = {<x, у>1 у >x2}, В = {<x, г/>| -3 <у < 5, -7 <x< 1};
9)	A = {<x, y>l x2 + y2< 4}, В = {<x, y>l (x-2)2 + y2> 9};
10)	A = {<x,y>[ -3<y<2},B = {<x,y>l (x+2)2 + (i/-3)2< 4};
11)	A = {<x,y>\y< e-r+2}, В = {<x, г/>| -4 <у < 5,3<x<6};
12)	A = {<x, y>\ у > 2x2-3}, В = {<x, y>l x2 + (z/-l)2 < 1};
13)	A = {<x, y>\ (x-5)2 + (z/-7)2 < 25}, В = {<x, y>j (x-7)2 + (г/-5)2 < 25};
14)	А = {<х,г/>| |x-1|<4},В = {<х,у>1 (х-4)2 + (у-10)2<9};
15)	Л = {<х, у>\ у>х3,х>0},В = {<х, у>\ х3 + у2< 9}.
II II II II II
1.2. Доказать тождества, используя основные теоремы и аксиомы алгебры
множеств (' - дополнение множества).
Пример. (А\В) п ((Л В)\(А п В)) = А\В.
Доказательство.
(А\В) п ((А и В)\(А п В)) = По определению: А\В = Аг\В'
(Л п В') п ((Л о В) n (А п В)') = Закон де Моргана: (А п В)' = А' о В'
(А п В') r\(A<j В)г\ (А' о В') =	Ассоциативность п
А п В' п (А о В) n (A' В') =	Коммутативность п
А п (А и В) г\ В? Г\ (А' и В7) =	Закон поглощения: А п (А о В) = А
АпВ' = А\В. ,	По определению: А п В' = А\В
Задания.
1) A (В\С) = (А В) n (А С)-,
2)(A\B)<j(AnB) =А;
3)	(A В)\(А п В) = (А\В) kj (В\Ау,
4)	(А\В) (AV') = (A u В)\(А п В);
5)	(А'\В') о (BV') = (Л В)\(А п В);
6)	(А\В') о (А\В) = (В и А') гЦАи ВУ
7)А\(А\В)=АпВ;
8)Bcj(A\B) = AcjB;
9) (А\В) п С= (А п С)\В;
10)(A<jB)\C=(A\Q<j(B\C);
11)	(A n В)\С = (А\С) п (В\С);
12)	(A В') п (А о С) = A (B'\Q;
13)	(А^В) о (Ап В') = В';
14)	(A nB)\(A<j В) = 0;
15)	(A В)\(А\В) = В.
5
1.3.	Упростить следующие выражения алгебры множеств ([7- универсальное
множество).
1)	((Л о В) п (Л kJ U)) kJ ((Л иВ)п(Ви 0));
2)	((Л о В) п (В kj U)) kJ (Л о 0);
3)	Л и (ЛпВ) kJ (ЛпВп0 kJ (ЛпВпСп/)) kJ (BnCnD) kJ (Cn0 kJ D,
4)	(Л kJ B) n (A kJ B');
5)	(A' n В' n C)' n (A' n В)' n (Л' n 0;
6)	A kJ В kJ (С n (Л kJ B' kJ C)’)\
7)	(Л\В) kJ (B\0 kJ (Л n В n 0;
8)	(Л n 0 kJ (B n 0 kJ (Л n D) kJ (B n D);
9)	(A kJ В) n (B kJ U) n (Л kJ 0);
10)	(Л kJ 0 n (B kJ 0 n (Л kJ D) n (B kJ D\,
11)(ЛпВ)и(Л\В);
12)	(Л kJ В) n (Л kJ B') n (A' kJ B);
13)	«Л kJ B') n (A' kJ 0)\(B' kJ 0;
14)((Л\В)п(Л'оВ))';
15)	(Л' kJ B' kJ 0' kJ (A' kJ B)' kJ (A' kJ 0.
1.4.	Доказать выполнимость соотношений теории множеств (символ <=>
означает «эквивалентно», символ => означает «влечет»).
Пример. A сС &АсВ' и С.
Доказательство.
Докажем, что если А п В с С, то А с В' kJ С.
Для каждого а е А либо ае В, либо а е В'. Если а е В, то а е А п В, а так
как А п В с С, то а е С. Тогда а е В' kJ С. Если а й В, то а е В'. Тогда
а е В' kJ С. Следовательно, каждый элемент а е А принадлежит и В' kJ С, т.е.
Л с В' kJ С.
Докажем теперь, что если А с В' kJ С, то А п В с С.
Пусть каждый элемент а е А принадлежит также В' kJ С. Тогда или а е
В', или а е С. Если каждый элемент а е В', то а й В, и А п В = 0, а так как
6
0 включено в любое множество, то 0 с С, следовательно, А п В с С. Если
а « В', то а е Си некоторые а е В. Тогда А п В * 0, и, если а е В, то а е С,
следовательно, А п В с С.
I
Задания.
1)	Л иВс С<=> Л с Си В с С;
2)	Л сВ п С<=> Л сВ и Л с С;
3)	Л с В и С<=> А\В с С;
4)(Л\В)оВ = Л <=>ВсЛ;
5) (Л п В) и С= Л п (Ви С) « СсЛ;
6)ЛсВ=>ЛиСсВиС;
7)ЛсВ=>ЛпСсВпС;
8) А а В =э (Л\0 с (В\С);
9)Л^В=?(С\В)с(С\Л);
10)	Л сВ=>В'сЛ';
11)	Л <J В = А п В => Л = В;
12)	Л/В = Л <=> В' с А (где Л/В=Л о В', т.е. A/B={xj хе А или х й В});
13)	А/В = U^BcA;
14)	Л = В <=> (Л\В) о (В\Л) = 0;
15)	Л = В'«ЛпВ = 0иЛиВ = U.
2.	ТЕОРИЯ ОТНОШЕНИЙ
Упражнения
2.1.	Доказать выполнимость следующих соотношений.
Пример. (Л п В) х (Сn D) = (Л х С) г>(Вх D).
Доказательство.
Пусть Л = {а| аеА}, В = {Z>| be В}, С = {с| се Q, D ={J| de £)}.
а)	Рассмотрим (Л n В)х(С n D). Найдем множества А п В и С n D. По
определению
Л п В = {a, b\ ае A, be В и а = b}-, С n D = { с, d\ се С, de D и с = d}.
Обозначим через х все элементы а и Ь, которые удовлетворяют следующим
условиям: а = Ь, ае А и be В, а через у - все элементы с и dтакие, что с = d, се С
и de D. Следовательно,
Л п В = {xj хе A nxeB};CriD = {z/| ye С и yeD}.
По определению декартового произведения множеств
(Л n В)х(С n D) = {л] хе А и хе В}х{ у\ ye С и ye D} =
= {<х,у>\хеА и хеВ,уеС nyeD}.	(1)
б)	Рассмотрим выражение (Л х С) п (В х D).
7
По определению декартового произведения множеств
А х С = {а| ае Л}х{с| се 0} = {<а, с>| ае А, се С}',
BxD = {b\be B}x{r/) de D} = {<b, d>\ be B, de D}.
Тогда (Л x C) n (B x D) состоит из множества всех упорядоченных пар
<а, с> и <b, d> таких, что а = b = х,с = d = у, т.е.
(А х 0 п (В х D) = { <х,у>\хеА ихеВ,уе CnyeD}. (2)
Из равенства правых частей соотношений (1) и (2) следует, что
(Л п В) х (Cr\ D) = (А х 0 п (В х £)).
Задания.
1)(ЛиВ)хС = (Лх0и(Вх0;
2)	(/ хВ) и (Схй)с(Л и С)х (Ви D) (при каких А, В, С и D имеет место
равенство?);
3)	А х (В и С) = (Л х В) о (Л х 0;
4)	(Л\В) х С = (Л х 0\(В х 0;
5)(ЛиВ)х(Сий) = (Лх0и(Вх0и(Лх£))и(ВхД);
6)	Л х (В\0 = (Л х В)\(Л х 0;
7)	Л х В = (Л х D) п (СхВ), где ЛсС и Bc,D\
8)	П2\(ЛхВ) = [(0Л)х0и[Пх([ДВ)];
9)	(Л п В) х С = (Л х 0 п (В х 0;
10)	(Л х В) и (Сх В) = (Л о 0 х В.
2.2.	Для бинарных отношений определить, какими свойствами они обладают.
Для отношений эквивалентности найти классы эквивалентности и
фактор-множества [Х/р].
Пример 1. Пусть отношение определено на множестве Z: хру <=>х=у (mod 3).
Это отношение сравнимости по модулю 3, которое означает, что разность х-
у делится на 3 без остатка. Будем обозначать это так: хру <^>(х-у)/3 = ke Z.
Решение. Выясним, какими свойствами обладает это отношение. Пусть
х,уе Z.
1.	Рефлексивность: хрх <=> (х-х)/3=0/3=0. Отношение рефлексивно.
2.	Симметричность: хру => урх, т.е. если хру, то урх.
Пусть (х-у)/3 = k eZ. Тогда урх <=> (г/-х)/3 = -(х-г/)/3 = - k е Z.
Следовательно, условие симметричности выполняется.
3.	Транзитивность: хру и ypz => xpz.
Пусть (х-г/)/3 = ^1 eZ,T.e.x-y = 3kt, и (y-z)/3 = k2eZ,x.e.y-z = 3k2. Решим
эту систему уравнений, сложив их: x-y+y-z = 3(ki+k2), т.е. x-z = 3(kt+k2)= 3k3,
k3 e Z. Условие транзитивности выполняется. Отношениех=у (mod3) являет-
ся отношением эквивалентности. Найдем его фактор-множество [Z/p].
8
Произвольное число х можно записать в виде 3q+r, 0 < г < 3, где q - частное,
г - остаток от деления числа х на 3. В один и тот же класс эквивалентности
попадут все числа, дающие при делении на 3 одинаковое число г в остатке.
Мы получим три класса эквивалентности: [0J = {0, 3,6,9,12,...}; [ 1 ] == {1,4, 7,
10,13,[2] = {2,5,8,11,14,...}.
Каждый класс можно охарактеризовать одним представителем этого
класса, и в данном случае таким представителем удобнее всего выбрать
остаток г. Следовательно, фактор-множество отношения х = у (mod 3) будет
[Z/p]={[0], [1], [2]}.
Указание. Пусть для данного отношения задано некоторое подмножество
Xмножества целых чисел: X = {-3, -6, -9,1,2,4,5,7, 10}: хру <=>(*- у)/3 = k,
ke Z. Построим матрицу отношения р на этом множестве.
\2/ X	-3	-6	-9	1	2	4	5	7	10
-3	1	1	1	0	0	0	0	0	0
-6	1	1	1	0	0	0	0	0	0
-9	1	1	1	0	0	0	0	0	0
1	0	0	0	1	0	1	0	1	1
2	0	0	0	0	1	0	1	0	0
4	0	0	0	1	0	1	0	1	1
5	0	0	0	0	1	0	1	0	0 .
7	0	0	0	1	0	1	0	1	1
10	0	0	0	1	0	1	0	1	1
По матрице отношений можно еще раз проверить свойства отношения.
Диагональные элементы матрицы равны 1; это говорит о том, что отношение
рефлексивно. Матрица симметрична относительно главной диагонали,
следовательно, отношение симметрично. Транзитивность также можно
проверить по матрице отношения. Если для всех пар <х,у>, <у, z> выполняется
также <х, z>, то отношение транзитивно. Например, на пересечении строки и
столбца <1,4> стоит 1, и на пересечении <4,7> стоит 1; проверим пересечение
строки и столбца < 1,7 >: здесь тоже стоит 1. Следовательно, для этих пар свойство
транзитивности выполняется. Для проверки транзитивности отношения нужно
рассмотреть все пары <х, у>, <у, z> и <х, z>.
Построим граф отношения. Элементы заданного множества являются вер-
шинами графа. Матрица отношения определяет, какие вершины графа связа-
ны друг с другом (это матрица смежности графа). По первой строке матрицы
находим, что вершина -3 связана сама с собой и с вершинами -6. -9.
Соединяем эти вершины дугами (на рисунке петли, соединяющие вершины
9
сами с собой, можно опускать). Элемент -6 также связан с элементами -3 и
-9, поэтому проведем дугу из вершины -6 в вершину -9. Третья строка
матрицы указывает, что элемент - 9 связан с -3 и -6. Элементы -3, -6, -9 не
связаны больше ни с какими другими вершинами, т.е. они образуют один класс
эквивалентности. Аналогично построим все остальные связи между
вершинами. В результате получим несвязный неориентированный граф (см.
рисунок), который состоит из трех связных компонент; каждая из них
соответствует одному классу эквивалентности.
Граф отношения х = у (mod 3).
Таким образом, классы эквивалентности на заданном множестве: {-3, -6,
-9}, {2, 5}, {1,4,7,10}. Внутри каждого класса любые два элемента находятся
в отношении х = у (mod 3) друг к другу: разность между ними делится на 3
без остатка. Между элементами различных классов это отношение не
выполняется. Каждый класс эквивалентности характеризуется остатком от
деления разности х - у на 3: в классе эквивалентности {-3, -6, -9} остаток
равен 0, в классе {2, 5} остаток равен 2, в классе {1, 4, 7, 10} остаток равен 1.
Фактор-множество [Х/р] = {[0], [1], [2]}.
Пример 2. Отношение определено на множестве R. хру <=>х-уе Z.
Решение. Пустьx,yeR. Определим свойства отношения.
1)	Рефлексивность: х - х = 0 е Z. Отношение рефлексивно.
2)	Симметричность: если х - у = k е Z, то у - х = -(х - у) = - k е Z.
Отношение симметрично.
3)	Транзитивность: если х - у = k{ е Z и у - г = k2 е Z, то (х - у)+(у - z) =
= x-y+y-z =х - z = kf + k2 = k3 e Z. Отношение транзитивно.
Данное отношение является отношением эквивалентности.
Найдем его фактор-множество. Разность двух действительных чисел
будет равна целому числу только тогда, когда их дробные части будут
одинаковы. Следовательно, в один класс эквивалентности попадают все
действительные числа, имеющие одинаковые дробные части. Например, [0] =
10
= {О, 1, 2; 3; ...}, [0,01] = {0,01; 1,01, 2,01; 3,01;[0,12] = {0,12; 1,12; 2,12;...},
и т. д Фактор-множество [Х/р] = [0. 1).
Задания.
1)	Отношение определено на множестве NxlV; <a,b>p<c.d> <=> [(а</ = be и
b*0, и d * 0) или (a = c, b = 0, d = 0)];
2)	Отношение определено на множестве Z: хру <=> х< г/+1;
3)	Отношение определено на множестве № хру <=> НОД(х,г/) * 1;
4)	Отношение определено на множестве R: хру <=> у = [г(;
5)	Отношение определено на множестве Z: хру <=> (х2 - г/2)/5;
6)	Отношение определено на множестве № хру <=> х/у (х делится на г/);
7)	Отношение определено на множестве R-. хру <=> [г - 2г/| g N;
8)	Отношение определено на множестве Z: хру <=> 2х = Зу,
9)	Отношение определено на множестве N: хру <=> |х+5| > |3 - г/|;
10)	Отношение определено на множестве R. хру <=> ху > 1;
11)	Отношение определено на множестве Z: хру 30/(х - у)\
12)	Отношение определено на множестве N: хру <=> (х - у)/т, т>д\
13)	Отношение определено на множестве Z: хру <=> 3/(х + у),
14)	Отношение определено на множестве N: хру <=> НОД(х,г/) = х;
15)	Отношение определено на множестве R: хру <=> х - у = k g Z;
16)	Отношение определено на множестве NxN:
<a,b>p<c,d> <=> р + d = b + с;
17)	Отношение определено на множестве {5, 7, 9,10, 13, 15, 18,19, 20}:
хру<±>[х-у\/5;
18)	Отношение определено на множестве {5,8, 9, 12,13, 16,18, 19, 20}:
хрг/<=> |х-z/|/4;
19)	Отношение определено на множестве {7,9,10,14, 15, 18,19, 21}:
хру^>\х-у\/7;
20)	Отношение определено на множестве {6, 9, 10, 12, 15, 18,19, 20}:
лрг/ <=> |х— г/|/6;
21)	Отношение определено на множестве {2,2.5,3, 3.5,5,5.5,8, 8.5}.
хру <=> [х - у\ = k g N;
22)	Отношение определено на множестве {1, 2, 3, 5, 6,8}:
хру <=> 90 Дх - г/| = k g N,x*y,
23)	Отношение определено на множестве {2,3,5,7,9,10}:
хру <~> 60/(х - у) = k g Z, х * у,
24)	Отношение определено на множестве {1, 2,3,4,5, 6, 7}:
хру <=> |2х - г/|/3 = ke N.
25)	Отношение определено на множестве {1, 2,3,4, 5,6, 7,8}:
хру |2х - Зг/|/4 = k g N.
11
3.	ОТОБРАЖЕНИЯ. ФУНКЦИИ
Упражнения
3.1.	Для каждого из отображений найти область определения и область
значений, исследовать, является ли оно инъективным, сюръективным
или биективным.
Схема исследования функции
1.	Нахождение области определения Е и области значений F функции.
2.	Нахождение точек пересечения графика с координатными осями.
3.	Исследование функции на периодичность, четность и нечетность.
4.	Нахождение интервалов монотонности, экстремальных точек (г/(х) = 0).
5.	Нахождение интервалов вогнутости и выпуклости кривой, которая
является графиком функции, точек перегиба (у"(х) = 0).
6.	Построение графика функции.
7.	Определение типа отображения.
Пример. Исследовать функцию /(х)-
(х+1)3
(х-1)2
и построить ее график.
1.	Найдем область определения и область значений функции.
При х= 1 функция не определена, следовательно, ее область определения:
Е= (-о°; 1) о (1; +«>). Очевидно, область значений F= R.
Проверим, является ли отображение £-»£функцией. Очевидно, что данное
отображение каждому элементу хе Е сопоставляет один и только один элемент
ye F, т.е. отображение является функцией.
2.	а) Найдем точки пересечения графика с осью Ох (/(х) = 0). Для этого
решим уравнение
^- = 0.
(х-1)2
Точка х - -1, у = 0 является точкой пересечения графика с осью Ох.
б)	Найдем точки пересечения графика с осью Оу: при х = 0,/(х) = 1.
3.	а) Проверим данную функцию на четность и нечетность.
Л-х) =
(-Х+1)3
(-Х-1)2
(х-1)3
(х+1)2
Данная функция не является ни четной, ни нечетной.
^Функция /(х)-
(х+1)3
(х-1)2
непериодична.
12
, _ (х+1)2(х —5)
4.	У -	(х-1)3	; у = 0 при х =-1 и х = 5.
24(х + 1)
5.	У (х-1)4 ’	= ®ПРИХ=_1-
-V	(—: -1)	-1	(1;1)	1	(1:5)	5	(5; +~)
У	f		0		не суще- ствует				13,5		
у'	+	0	+		-	0	+
у"	-	0	+		+		+
	возрастает, выпуклая	точка перегиба	возрастает, вогнута	верти- кальная асимптота	убывает, вогнута	точка минимума	возрастает, вогнута
' -(х+03 Функция пх)	на области определения (-<»; 1) и (1; +°=)							
является сюръекцией. На интервале (1; 5) она убывает, на (5; +<*>) - возрастает
и точка (5; 13,5) является точкой минимума, т.е. существуют такиех, и х„, что
/(*,)
Задания.
1)	у = х2 + Зх + 5;
2)у = х2 — х — 1;
16) у = Зх4 + 8г5 - 18Х2 + 7;
13
3) у = 22* +4;	Зх +х3
4) z/ = x7 + х + 1;	19) у = х + Vx +8 ;
5) у = log2(x2 + 4х + 5);	20) у = sin(-^-x+10)-2sinx ;
6)г/ = 2х5- 1;	л	х2+8	1 21)J'=	.	; х—1	5+х  „	з
7) у = 3х + х;	22) у = sm 2х +cos —х ;
8) у = х3 + Зх;	23) у = lg(cos 2х + 4);
7 9>^ = х+2;	24) У = -Зх4 + 16х3 -18х2 +—;
10) у = (х + sinx)2;	X 25) у = sin(2x)-cosy;
11) у = cos(x2 -х);	26) у = 6х3 -Vx +1 ;
2	27) у = е2*™51;
13) у = |sin х|;	28) у = cos(x + 3) + cos Зх;
14) у = Iglx4 + 2|;	29) г/= log)/2(-3x) - х3;
15) у=- + х+2; X	1 30> У= ’ X 1 к)Х
3.2. Построить композиции отображений g°/и f °g проверить, являются ли
они инъективными, сюръективными или биективными.
Пример, f: R^> R<=> у = х - 1; g. R-)R <=> у = е21.
Композиция функций g°f\ R—<=> у = е2(х“ ” не является сюръекцией, так
как нет ни одного элемента хе R, для которого у = 0 есть образ. Композиция
функций является инъекцией, так как каждый элемент у е R есть образ только
одного элемента хе R, либо вообще не имеет прообраза. Таким образом, g°f:
R—tR е у = е2(х“ ° - инъекция.
14
Задания.
1)/: R -> R, у = x2 + 5,g: R -» Z, у = [x];
2)/: C^R\у = И2 + 12,g:R^N,у = [x2 + 1];
3) /: R -» R, у = log2(x2 + 3), g: R -> R, у = x3 + Зх;
4)f-.R^R,y = 3xt,,g:R —»{0,1},г/ = [x] mod2;
5)	f: R—> R,y = x3 + 5x, g: R -> R,y = log2(x2 + 2);
6)	f: C -» R\ у = [x|2, g- R -»R. У = ^3;
7)	f: R —» Z, у = 4[x] + 5, g. Z —> Z, у = 4x + 5;
8)	/: Q -> Z, у = [ 17X3], g Z -> N, у = |x| + 1;
9)/: C—> R>, у = [x|2 + 2W + 1-g- R ->R, У ;
10)/: Я —» Z, г/= [x + 13], g:Z-> AT, y = |x| + 1;
11)	f: N—t N,y = x2 + 2,g: N-»{0,1}, у == (x + 7)2 mod 2;
12)/: Q -> Q, у = 1 lx + 2, g Q -> Z, у = [x2 + 14] - 2;
i3)f.R^R,y = ^ + 3x,gR-^C, у = 4^+3;
ii')f:N—>R,y = x2+44+2,gR-^R,y = ex;
i.5	) f.C—ь R\y = [x|2, g R -> R, у = Iog2(x2 + 3).
4. ОТНОШЕНИЕ ПОРЯДКА
Упражнения
4.1.	Для данных множеств и заданных на них отношений определить:
•	Является ли данное отношение отношением порядка? Строгого порядка?
•	Является ли данное множество, с заданным на нем отношением порядка,
цепью?
•	Найти, где это возможно, наименьший и наибольший элементы.
•	Найти минимальный и максимальный элементы.
•	Построить матрицу отношения, граф отношения или диаграмму Хассе.
•	Является ли данное множество решеткой?
Пример. На множестве Х= {-5, -3, -2,0,1,2,4,5, 6} задано отношение р:
{Ы <
Определим, какими свойствами обладает это отношение.
Отношение не рефлексивно, так как не выполняется |х| < |х|.
Если |х] < |г/|, то не выполняется |г/| < |х|, следовательно, отношение
асимметрично.
Если |х| < |г/| и |г/| < |г|, то [х| < |z|, следовательно, отношение транзитивно.
Отсюда следует, что отношение [х| < |г/| является отношением строгого порядка.
15
Построим матрицу отношения
х\г/	-5	-3	-2	0	1	2	4	5	6
-5	0	0	0	0	0	0	0	0	1
-3	1	0	0	0	0	0	1	1	1
-2	1	1	0	0	0	0	1	1	1
0	1	1	1	0	1	1	1	1	1
1	1	1	1	0	0	1	1	1	1
2	1	1	0	0	0	0	1	1	1
4	1	0	0	0	0	0	0	1	1
5	0	0	0	0	0	0	0	0	1
6	0	0	0	0	0	0	0	0	0
Множество X = {-5, -3, -2,0,1,2,4, 5,6} с заданным на нем
6 отношением строгого порядка не является цепью, так как в нем
.5у\5	есть элементы, несравнимые по отношению р. Это элементы -2
и 2: |-2| = |2|. Так как |1| < |-2| < |-3| и |1| < |2| < |-3|, то inf{-2,2} = 1,
[4	sup{-2, 2} = -3. Аналогично и для -5 и 5: |-5| = |5|, inf{-5, 5} = 4,
2 /а?	sup{-5, 5} = 6.
Намножес1веХ= {-5,-3,-2,0,1,2,4,5,6} элемент 6 является
If наибольшим и максимальным, а 0 - наименьшим и минималь-
0* ным элементом. Данное множество является решеткой. Его
диаграмма Хассе представлена на рисунке.
Задания.
1)	На множестве {2,3,5,8,9,12,15,16, 18,20} задано отношение
р: хру <=> х/у (х делится на г/);
2)	на множестве {1, 2,3,5,6,15,30} задано отношение
р:хру <=>х/у (хделится наг/);
3)	на множестве {1,2,3,4,6,12,15} задано отношение
р: хру <=> х/у (х делится на г/);
4)	на множестве {1,2,3,6,12,16, 18} задано отношение
р: хру <=> х/у (х делится на г/);
5)	на множестве X = {1, 2,5,6, 7,8, 9,10,13,16} задано отношение
р: {(х)шог/4<(г/)глог/4};
6)	на множестве X = {2,3, 4, 5, 6, И, 12,13} задано отношение
р: {х делится на у с остатком 1};
7)	на множестве X = {{a}, {ft}, {а, Ь}, {а, Ь, с}, {{а, Ь, с}}} задано отношение р:
{*<=!/};
16
8)	на множестве X = {88,65, 55,52,39, 26, 13,11} задано отношение
р: {х кратно у}\
9)	на множестве X = {-7, -6.2, -5, -4.3, -0.25, 0, 0.5, 1, 5.5, 10} задано
отношение р: {(-х2+х+10) < (- у2+у+10)};
10)	на множестве отрезков оси ОхХ= {(0,3), (0.5,3.5), (1,2), (1,3), (1.5, 2),
(2,3), (3,3), (7,0), (7,8)} задано отношение р. {длина отрезках> длины отрезка у}\
11)	на множестве X = {0,1, 2,3,4, 5,6,8,10,120} задано отношение
р: {х2 + 9 < у2 + 9};
12)	на множестве Х= {-5, -2.7, -1, -0.3,0,0.2,0.5,2,3,4.2} задано отношение
р: {log^x2 +0.1) < log^O2 +0.1)};
2	2
13)	на множестве X = {-л/2, -л/3, -л/12, 0, л/24, л/12, л/6, л/3, л/2, Зл/2,
2л, 5л/2, 7л/2} задано отношение р: {sin х < sin г/};
14)	на множестве X = {-7, -5, -3, -2, -1, 0, 1,3, 4, 9, 10,16, 18} задано
отношение р: {^(х2 + 3) < 1g (г/2 + 3)};
15)	на множестве Х= {-л, -л/2, -л/3, -л/6, -л/12,0, л/24, л/12, л/6, л/2, Зл/
2, 2л, 5л/2} задано отношение р: {cos х > cos у}\
16)	на множестве Х= {-7, -6, -5 -3, -1,0,2,4,8,9,10,15} задано отношение
5 < 5
Р’ ( 2^ ~ 2^
17)	на множестве X = {-5, -4, -3, -2, -1, 0, 2, 4, 6, 7, 8} задано отношение
Р- {е~х +1 х |> е~у +1 у | }‘>
18)	на множестве прямоугольников X = {{0 < х < 1, 2 < у < 3}, {0 < х < 3,
1 <г/<2}, {1<х<3,2 <г/<3}, {2<х<7,2<г/<6}, {3 <х<7,2 <у< 7}, {3<х<7,
5<у< 12}, {5<х<7,7 <у< 15}, {5<х<9,2<г/<6}, {6<х<9,3<у< 15}} задано
отношение р: {площадь прямоугольника а < ппощади прямоугольника Ь};
19)	на множествеХ = {-1,-1/2,0,1/2,1,2,3/2,3,4,5,7} задано отношение
4.2.	На множествах Л и В заданы отношения порядка р 1 и р2 соответственно
и задано отображение/{а?)=Ь., где а. е A, bj е В. Определить, является ли
оно изотонным, изоморфизмом или автоморфизмом.
Пример. А = {1,3,4,12,24}, В = {8,10, 12, 15, 20}; f(a) = b'
р 1\ < j {aj — делитель а.}; р 2: Vi <j b. < b..
Проверим, является ли отображение f'.A—t В изотонным.
Найдем образы функции f : А -» В. f (1) = 8 = bv f(3) = 10 = b2, f (4 ) = 12 = b3,
f(12) = 15 = b4, f(24) = 20 = b5. Множество A — решетка, в которой можно
выделить две цепи. Для цепи 1<3<12<24 отображение / сохраняет порядок,
17
так как 8 < 10 < 15 < 20, т.е. f (1) </(3) </(12) </(24). Для
цепи 1<4<12<24 отображение / также сохраняет порядок,
так как 8 < 12 < 15 < 20, т.е. /(1)</(4) </(12) </(24). Следо-
вательно, отображение изотонно. Однако, отображение не
является изоморфизмом, так как обратное отображение / не
сохраняет порядок: для значений /(3) </(4) (10 < 12) про-
образы 3,4 несравнимы.
Таким образом, отображение / изотонно, но не является
изоморфизмом.
Задания.
1)	А = {2,3,6,12, 24}, В = {1, 2, 3, 5,6, 10,15,30};/(2) = 1;/(3) = 1;/(6) = 5;
/(12) = 10;/(24) = 30; р1 = р2: {хделитель^};
2)	Л — {aQ, а(, а2, а3}, В — {fl0, ах, а2, а3}, fiaj —	Р^ ~ Р^- —J at ~ аг
3)	А = {1,3,4,12,24},В = {8,10,11,19,31}; f(a) = fe;pt X/i<j{at делитель а.};
р2: \/i <j fe. < Ь ;
4)	А = {6,7,14,15,35}, В = {0. -1,1,2,3,4,5}; /(а) = а, mod 6; р1: Vi <j а. < а\
p2:X/i<j\b\< |bj;
5)	А = {1,3, 4, 12, 24}, В {8, 10, И, 19, 31}; f(a) = b, р1 = р2: х< у;
6)	А = {-2, -1, 0, 1, 2}, В = {2, 1, 0, -1, -2}; /(а.) = -а- р1: Vi <jat< а:,
р2: <j b.> b',
7)A~ {25, 20,15,10, 5}, В = {5,4,3, 2, 1}; /(fl,.) = fl,./5; р1 = р2:х>у;
8)	А = {64, 8, 4, 2, 1}, В = {0, 81, 9, 3, 1};' /(а,) = bt_jf i = 0, 1, 2, 3, 4;
р1 = р2: {х делится на у}\
9)	А = {2, -3,4,6, -7,8}, В = {4,9,16,36,49,64}; /(а,) = a2- p1:\fi< j |а,| < |а |;
р2: <j fe. < b'
10)	A = {1,2,3,4,5}, В = {2,4, 8,16, 32,64}; f(a) = 2°' , p1 = p2:x< у
11)	A = {{1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}}, В = {{1}, {1, 2}, {1, 2, 3}, {1, 2, 3,4}};
/(a,) = fe,;p/ = p2:xcy
12)	A = {-л, -л/3, -л/6, 0}, В = {-л/18, -л/9, -л/3, -п/2, 0}; f(a.) = а,/3;
р1: <j cos(a.)<cos(a ); р2: <j b. < b;
13)	A = {-л/3, -п/ё, 0, n/6, л/3}, В = {-л/3, -n/6, 0, n/6, л/3}; /(fl.) = -a,;
p1 = p2:tgx<tgy,
14)	A = {0, л/4, л/2, Зл/4, л}, В = {0, 1/2, 1/	, -Л/2, 1}; f(a) = sin a-
p1 = p2:x<y
15)	A - {0, 1/5, 1/4, 1/3, 1/2, 1}, В = {0, 6, 15/2, 10, 15, 20, 30}; /(a,.) = 30a.;
pt. \fi<ja2.> a2-, p2: Xfi<jb.<bj.
18
5. РЕШЕТКИ
Упражнения
5.1. Для изображенных на рис. 5.1 решеток построить таблицы объединений
и пересечений; определить, какие из решеток модулярные (если решетка
немодулярна, выделить в ней подрешетку Ns), дистрибутивные, с
дополнениями, с относительными дополнениями, булевы. Выделить
некоторые подрешетки заданной решетки; найти среди них выпуклые
подрешетки; выделить верхнюю и нижнюю полурешетки.
19
Рис. 5.1. Задания к упражнению 5.1.
5.2. Какие из данных отображений (рис. 5.2) являются: изотонными; v -
гомоморфизмом; л - гомоморфизмом; гомоморфизмом; изоморфизмом;
эпиморфизмом; мономорфизмом; эндоморфизмом; автоморфизмом.
Пример. Для отображения <р, заданного на рисун-
ф:
v	ке, проверим выполнимость свойства изотонности.
\ а<Ь, ф(а) = А, <р(Ь) = С, А < С- выполняется,
/9^---------WC а<с, ф(а) = А, ф(с) = А, А <А - выполняется,
//	с^' ф(с) =	= В,А<В - выполняется,
(В	d<e, ф(d) =	В, ф(е) = С, В< С - выполняется,
с j >	b<e, ф(Ь) =	С, ф(е) = С, С < С - выполняется.
\	Отображение ф изотонно.
*---------*• А Проверим, является ли оно гомоморфизмом. Для
этого проверим выполнимость сохранения операций
v и л. Очевидно, что для элементов, лежащих на одной и той же цепи, операции
v и л сохраняются в силу изотонности отображения. Поэтому необходимо
проверить сохранение операций только для несравнимых элементов.
ф(Ь v с) = ф(е) = С; ф(Ь) v ф(с) = С v А = С - выполняется,
ф(Ь v d) = ф(е) = С; ф(Ь) v tp(d) = С v В = С - выполняется.
Отображение ф является v-гомоморфизмом.
Проверим сохранение операции л. Для элементов b и d ф(Ь л d) = ф(а) = А,
но ф(й) л ф(б/) = С л В = В. Следовательно, <р(Ь л d) ф(£>) л ф(г/), -
отображение не является л-гомоморфизмом.
Рис. 5.2. Задания к упражнению 5.2.
21
6. ГРАФЫ
Упражнения
6.1.	Для заданного орграфа D (рис. 6.1) найти, матрицу смежности A(D); все
пути длины 2 и 3; матрицу достижимости R(D\, сильные компоненты
орграфа D-, конденсацию графа D*, вершинную базу В* ; вершинную базу
графа В; матрицу расстояний (d\, матрицу инциденпий 1(РУ, определить
тип связности графа.
Пример. Орграф задан на рисунке.
1)	Найдем матрицу смежности и с ее помощью определим число путей
длины 2, 3, ведущих из ut в и.
	и	1	«2 м3 «4	«5 м6 м7	м8
		'0 0 0 0 1 0 0 0	
М2		1 0 0 0 0 0 0 0	
"з		1 1 0 0 0 1 0 0	
A(D) = «4		0 0 0 0 0 0 10	
«5		0 0 0 1 0 0 0 0	
м6		0 0 0 0 10 0 0	
«7		0 0 0 0 0 1 0 0	
ы8		,0 0 0 0 0 0 1 с	
«I		«2 Из «4 ы5 ы6 «7 «	8
«1		0 0 0 1 0 0 0 0'	
«2	0 0 0 0 10 0 0		
«3	1 0 0 0 2 0 0 0		
А2 =Ид	0 0 0 0 0 1 0 0		
«5	0 0 0 0 0 0 1 0		
Ы6	0 0 0 1 0 0 0 0		
«7	0 0 0 0 1 0 0 0		
«8		0 0 0 0 0 1 0 0,	
22
«1		“2	«3	«4	«5	«6	«7	«8
«1	'0	0	0	0	0	0	1	О'
«2	0	0	0	1	0	0	0	0
«3	0	0	0	2	1	0	0	0
Л3 =«4	0	0	0	0	1	0	0	0
«5	0	0	0	0	0	1	0	0
«6	0	0	0	0	0	0	1	0
«7	0	0	0	1	0	0	0	0
«8	Л	0	0	0	1	0	0	0,
Найдем в D все пути длины 2.								
Поскольку элемент (1,4) в матрице Л2 равен 1, в D существует путь длины
2изы( ви4. Это путь и г и 5, и 4. Элемент (2,5) в матрице Л2 равен 1, следовательно,
в D существует путь длины 2 из и2 в и5 - и2, uv и5. Элемент (3,5) в матрице Л2
равен 2, следовательно, в D существует 2 пути длины 2 из и3 в и5. Это и3, uv и5
и и3, и6, и5. Аналогично находятся следующие пути длины 2: из и3 в ut - иу и2, ut;
ИЗ U, ВИ - и,, U,, U', из и.ви,- щ, и., U' из и. в и - и., и,, и,; из м, в и. - U , U , U’
из и8 в и6 - ие, и7, и6.
Найдем в D пути длины 3.
Элемент (1,7) в матрице Л3 равен 1, следовательно, в D существует путь
длины 3 из uf в u7 - uv иу и4, иг Элемент (2,4) в матрице Л3 равен 1,
следовательно, в D существует путь длины 3 из и2 в ut - и2, uv и5, и4. Элемент
(3,4) в матрице Л3 равен 2, следовательно, в D существует 2 пути длины 3
из и3в и4- и3, uv и5, ил и и3, и6, и5, и4. Аналогично находятся остальные пути
ДЛИНЫ 3. Это ИЗ Изв И5- Uy и2, Uv Uy ИЗ и4 В U5 - Uy Uv Uy Uy ИЗ И5В U6- Uy Uy
Uv Uy ИЗ Ue В U7 - Uy Uy Uy U7; ИЗ U7 В U4 - U7, Uy Uy Uy ИЗ Ue В U5 - Uy U7, Uy Uy
2)	Матрицу достижимости R(D) можно построить следующим образом.
Пусть А - матрица смежности и R - матрица достижимости орграфа Den
вершинами. Тогда:
R = В(1 + Л + Л2 + ... + Л"1) = В[(7 + Л)”-1],
где п - количество вершин, / - единичная диагональная матрица, В -
булево отображение. Булево отображение для некоторой матрицы Xзадается
следующим образом: если xt] # 0, то B(xtj) = 1; если х. = 0, то В(х) = 0.
23
	'1	D 0 2 2 1 2 О'	
	1	1 0 2 2 1 1 0	
	2	1 8 6 4 3 0	
_	.7	.7	0	D 0 2 2 2 2 0	
1 + А + А2+... + А2 =			
	0	D 0 2 2 2 2 0	
	0	D 0 2 2 2 2 0	
	0	D 0 2 2 2 2 0	
	<0	D 0 1 2 2 2 1,	
		2, U2 U3 W4 U5	м6 ы7 ы8
	«1	'10 0 11	1 1 О'
	“2	110 11	1 1 0
	«3	11111	1 1 0
R(D) = B(I+A + A2+...+ A2) =	«4	0 0 0 1 1	1 1 0
	“5	0 0 0 1 1	1 1 0
	и6	0 0 0 1 1	1 1 0
	и7	0 0 0 1 1	1 1 0
«8		^0 0 0 1 1	1 1 1,
Используем матрицу достижимости для выявления сильных компонент
орграфа D. Вычислим матрицу Rx R' (R’ - транспонированная матрица R).
Эта матрица имеет блочно-диагональный вид. Каждый блок матрицы
определяет сильную компоненту. По нашей матрице находим, что вершина
w, составляет одну сильную компоненту. Аналогично, вершины w2 и w3,
которым соответствуют единицы на главной диагонали матрицы R х Я', также
являются сильными компонентами. Вершины w4, w5, w6, u7 составляют одну
сильную компоненту, так как им соответствует один блок в матрице R х R'.
Вершина и8 - еще одна сильная компонента.
Элемент (ц, wf) в матрице R2 показывает число элементов в той сильной
компоненте, в которую входит вершина иг
24
«1		«2	"3	«4	«5	«6	«7	"8
М1	Ч	0	0	0	0	0	0	o'
w2	0	1	0	0	0	0	0	0
w3	0	0	1	0	0	0	0	0
RxR' = и$	0	0	0	1	1	1	1	0
«5	0	0	0	1	1	1	1	0
«6	0	0	0	1	1	1	1	0
«7	0	0	0	1	1	1	1	0
w8	<0	0	0	0	0	0	0	
“1		м2	ы3	н4	и5	М6	ы7	w8	
М1	ч	0	0	5	5	5	5	О'	
«2	2	1	0	6	6	6	6	0	
м3	3	2	1	7	7	7	7	0	
R2 = Щ	0	0	0	4	4	4	4	0	
«5	0	0	0	4	4	4	4	0	
«6	0	0	0	4	4	4	4	0	
«7	0	0	0	4	4	4	4	0	
«8	<0	0	0	5	5	5	5	1,	•
Введем обозначения для сильных компонент и построим граф
конденсации О* орграфа D:
Сильные компоненты:
{ы'}	~К'	Ks
Ч)	~к2	/	\	-----*
-К3	А------
{иеи5,ие,и7} -К*	кг	К3
Граф конденсации D*
{п8}	— К5	Вершинная база в D*: В* = {К3, К5}
В вершинную базу орграфа D должны войти по одной вершине из сильных
компонент К3, К5. Поскольку каждая из компонент содержит только одну
вершину, то в орграфе D существует единственная вершинная база В = {uv
“«}•
3)	Построим матрицу расстояний орграфа D по матрице смежности
А. Если величина сЛ для i^j определена, то она равна наименьшему значению
25
k, для которого элемент (г, j) в матрице B(Ak) равен 1, где В — булево
отображение. Матрицу расстояний формируем последовательно по степеням
матрицы смежности. Диагональные элементы в матрице расстояний равны
нулю, так как каждая вершина достижима сама для себя по пути нулевой
длины. Из матрицы смежности А выписываем все пути длиной 1, — это
элементы d = 1. Из матрицы Л2 в оставшиеся пустыми клетки матрицы
расстояний запишем все пути длиной 2, — это элементы d.. = 2. Теперь в
матрицу расстояний будут внесены все расстояния длиной 0 (на диагонали),
1,2, и некоторые клетки останутся пустыми. Эти клетки будут последователь-
но заполняться числами 3, 4,..., 7 по матрицам А3, А4,..., А7. Клетки матрицы
расстояний, оставшиеся пустыми после этого процесса, заполняем символом
оо — для этих вершин расстояние не определено.
	«1	“2	«3	«4	«5	«6	«7	W8
«1	"0	00	оо 2	1	4	3	00
«2	1	0	00	3	2	5	4	00
«3	1	1	0 3	2	1	4	00
(^) = «4	00	00	00	0	3	2	1	00
«5	00	00	00	1	0	3	2	00
«6	00	00	00	2	1	0	3	00
«7	00	00	со 3	2	1	0	00
«8	<°°	00	оо 4	3	2	1	0
4) Построение матрицы инциденций.							
Обозначим дуги, как показано на рисунке. Элемент матрицы инциденций
(i, у) равен — 1, если дуга х выходит из вершины и., равен 1, если дуга х. входит
в вершину ujt и равен 0, если дуга х не инцидентна вершине
26
Матрица инциденций
*1		х2	*3	х4	х5	х6	х7	*8	х9	Л10	
«1	-1	1	1	0	0	0	0	0	0	(р	
ы2	0	-1	0	1	0	0	0	0	0	0	
"3	0	0	-1	-1	-1	0	0	0	0	0	
1(D) = "4	0	0	0	0	0	-1	1	0	0	0	
«5	1	0	0	0	0	0	-1	1	0	0	
116	0	0	0	0	1	0	0	-1	1	0	
«7	0	0	0	0	0	1	0	0	-1	1	
«8	1 0	0	0	0	0	0	0	0	0	-L	
5) Тип связности графа легко установить по его графу конденсации.
Поскольку в графе есть вершины, ни одна из которых не достижима из другой,
например, Kt и К5, то граф слабо связан.
Задания
27
Рис. 6.1. Задания к упражнению 6.1.
6.2.	Для графа G (рис. 6.2) найти диаметр графа, радиус графа, центр графа,
эйлеров обход, гамильтонов путь и цикл.
Пример. Граф G задан на рисунке. Диаметр
графа d(G) = max d(v., г ) = 3 для всех &., d е G.
Максимальным удалением в графе G от верши-
ны г. называется величина г(ц.) = max d(v., cd), для
всех г. е G. Вершина называется центром графа
G, если r(G) = min r[v^, для всех о е G. Макси-
мальное удаление r(G) от центра называется
радиусом графа.
Найдем максимальные удаления от каждой вершины графа: г(г() = 3,
г(п2) = 3, г(&3) = 2, г(п4) = 2, г(ц5) = 3, г(п6) = 3, г(п7) = 3, г(п8) = 3. Наименьшее
среди них r(G) = 2 - радиус графа G, а вершины v3, v4 - центры графа.
Проверим существование эйлеровых обходов в графе G. В данном графе
существует 4 вершины с нечетной степенью: v3, v5, v6, v7. Следовательно, по
теореме Эйлера в данном графе нет эйлеровою обхода.
Существование гамильтоновых путей можно проверить методом перебора.
Например, гамильтоновы пути: vt, v2, v3, &7, г8, v5, v6, &4; vt, v4, v6, v5, vs, v7, v3, v2 и др.
28
29
7. БУЛЕВА АЛГЕБРА
Упражнения
7.1.	Проверить эквивалентность формул А и В, используя основные аксиомы
и теоремы булевой алгебры (см. указания к примеру 7.2).
Задания.
1)	А = ху v -ir-iZ v х-12. В = x-iy-iZ v —ос v —iz;
2)	А = -oc—y-cz v -oc-yz v —осу, В = —ос,
3)	А = xy—cz v ху v z—cz, В = xy\
4)	А = х(у vz) v y—oc—cz v -cz(-y v х), В = х v у v -iz;
5)	А = x—cz v хух/ y—cz, В = x->(yz) v —.xz;
6)Л = х->(х2/->((х->г/)->з/) z), В = у -> (хz);
7)	А = -п((х -> у) v ((х -> z)y)), В = (х-у)(-у ->х-г);
8)	А = (х v у) (у v z) (z v х), В = ху v yz v zx;
9)	A = xv у\/ z—ь (x v y)(x v z),B = x = z\
10)	A = x(x —>y),B = xy;
11)	A = —i(x v y) v (ху), B = (xx/ —iZ/)(—ct v y)\
12)	A = x&y,B = —ocy v -yx;
13)	A —i(-iryz), В = x v -iz v -.г/;
14)	A = (x v y)(x v z)(y v w)(z v w), B=xwv yz\
15)	A = ((x®y)-+xxcy)((-oc-+y) -> (x®y)), B = -y(xy).
7.2.	Представить булевы функции в виде СДНФ, СКНФ и канонического
полинома Жегалкина; проверить, являются ли они линейными, монотон-
ными, самодвойственными, сохраняющими 0, сохраняющими 1.
Пример. (x—>(yvz))—txz.
Для построения СДНФ можно использовать метод эквивалентных
преобразований булевых формул, либо построить таблицу истинности.
Метод эквивалентных преобразований булевых формул.
СДНФ: (х—>(2/vz))->xz =	используем эквивалентность х—ьу = —ос v у
= —(—ос х/у х/z) x/xz= используем закон де Моргана и у v -у = 1
= (х—у—iz) v (xz(y v —12/)) = используем закон дистрибутивности
= Х-12/—1Z v xyz v x—yz.
СКНФ: (х-^ (г/vz)) -> xz = (-xvyvz) xz —i(-ov2/vz) v xz = x-y-cz v xz =
= x(—y —izx/z)=	закон полного склеивания и поглощения
-12/-1ZVZ = -12/-1ZVZV —12/ = —у V Z
= х(-у V z) = (х V 2/-.2/)(-.г/ V z V х-ос) =
= ((х V у) V Z-iZ)((x V —12/) V z—1Z)(—12/ V X V z)(—у V —iX vz) =
= (x V У V z)(x V У V —iZ)(x V -12/ V z)(x V -12/ V -CZ)(—OC x/-yx/z).
30
Таблица истинности
X	У	Z	f(x,y,z)	конституенты
0	0	0	0	xvyvz
0	0	1	0	XVi/V-iZ
0	1	0	0	xv^yvz
0	1	1	0	XV-iZ/V—tZ
1	0	0	1	x-y-z
1	0	1	1	x-^yz
1	1	0	0	
1	1	1	1	xyz
Выпишем все конституенты нуля и единицы (см. таблицу). Дизъюнкция
всех конституент единицы дает СДНФ: f(x, у, z) = x-y—z v xyz v x-yz.
Конъюнкция всех конституент нуля дает СКНФ:
f(x, y,z) = (i v у v z)(xvyv —iz)(x v -у v z)(x v-yv -z){—oc v-iy\/ z).
Проверим свойства функции.
1.	Функция сохраняет нуль, так как /(0,0,0) = 0.
2.	Функция сохраняет единицу, так как /(1,1,1) = 1.
3.	Самодвойственность. По определению, функция является самодвойствен-
ной, если /(—1Х, -у, —z) = —>f(x, у, z), т.е. на противоположных наборах функция
принимает противоположные значения. Набор 001 противоположен набору 110,
но/(0,0,1) = 0 и/(1,1,0) = 0, следовательно, функция несамодвойственна.
4.	Монотонность. Функция монотонна тогда, когда на возрастающих на-
борах она не убывает. Набор 100 предшествует набору 110, но
/(1, 0, 0) = 1 >/(1,1,0) = 0, следовательно, функция немонотонна.
5.	Линейность. Чтобы проверить, является ли функция линейной,
построим полином Жегалкина. Для этого в СДНФ данной функции заменим
все символы v на Ф и выразим отрицания как ->х = х Ф 1. Получим полином
Жегалкина:
/(х, у, z) = x-y—z vxyz vx—yz = (х(г/ Ф1)(гФ1))Ф {xzy) Ф (хг(г/ Ф 1)).
Приведем его к каноническому виду, используя закон дистрибутивности:
х(г/ Ф г) = ху Ф xz и тождества: х Ф х =0, х Ф 0 = х. Тогда
/(х, у, z) = (х(г/ Ф 1)(г Ф 1)) Ф (xzy) Ф (xz(y Ф 1)) =
= ((хт/Фх)(гФ 1)) ®хгу Ф (xzy®xz) = xyz® ху ®xz®x®xzy ®xzy Фхг =
= xyz Ф ху Ф х.
Функция нелинейна, так как в каноническом полиноме Жегалкина есть
нелинейные элементы: xyz, ху.
Задания.
1) (х v -й/ v z)(—x—y—z)\
31
2) (—х—у V -^-.z) S (х V z -> у);
3)хг/vx(zvy)z;
4)	х -> (х -> z);
5)(x->(x->2/))->z;
^)<x = y)=r,
7)(-^x^>-,y)->(xy-> xz);
8)	((x -> г/) -» -cr) -> (x -» yx);
9)	—i((x л y)	-x) -,(xy -> -,y)\
10)	(z -» x) -> (-,(2/ v z) -> x);
И) ->(хг/ ->x) v (х(г/ vx));
12)	-1(х(г/ v z)) -> (xy v z);
13)	((x -> г/) -> (z -> -nx)) -> (-,2/ -»-nz);
14)	((( (x ->£)-» -er) -> -.у) -> -г) -> z;
15)	(x —> (2/ —> z)) —> ((x ->-£)-> (x -> -,2/)).
7.3. Проверить полноту систем функций.
Пример. Проверить полноту системы функций Z = {-., —>}.
Согласно теореме Поста, для полноты системы функций необходимо и
достаточно, чтобы в нее входили хотя бы одна немонотонная, хотя бы одна
нелинейная, хотя бы одна несамодвойственная, хотя бы одна не сохраняющая
нуль и хотя бы одна не сохраняющая единицу функции. Обозначим:
То - класс функций, сохраняющих 0;
1\	- класс функций, сохраняющих 1;
5	- класс самодвойственных функций;
М	- класс монотонных функций;
L	— класс линейных функций.
Для исследуемой системы составим таблицу Поста. Если функция входит
в функционально замкнутый класс, то в таблице Поста в соответствующей
ячейке ставится знак «+», иначе - знак «-».
Для исследования системы Z = {—1, —>) на полноту построим таблицы
истинности функций -1 и —
1.	Обозначим/,(х)= —а.
X	f{x)
0	1
1	0
Функция/,(х) не сохраняет 0 и 1, так как на нулевом наборе она принимает
значение 1, а на единичном - 0. Очевидно, что данная функция немонотонна.
Функция самодвойственна, так как на противоположных наборах функция
32
принимает противоположные значения. Функция линейна - ее полином
Жегалкина: ->х = хФ1.
2.	Обозначим /2(х, у) = х->г/.
У	X	/2(х, уУ
0	0	1
0	1	1
1	0	0
1	1	1
По таблице истинности видим, что/2(х, у) = х-^у не сохраняет 0 и сохраняет
1. Эта функция немонотонна, так как набор (0,0) предшествует набору (1,0), но
/2(0,0) >/2(1,0).На противоположных наборах (0,0) и (1,1) функция принимает
одинаковые значения 1, следовательно, она несамодвойственна.
Для проверки линейности построим канонический полином Жегалкина:
/г(х,у)= (х® 1)(у Ф 1) ® (хФ 1)у Ф ху = ху ® хФ 1. Функция нелинейна,
так как содержит элемент ху.
3.	Построим таблицу Поста для заданной системы.
	т о	г.	5	м	L
—I	—	—	+	—	+
	-	+	-	-	-
Система функций будет полна, если в каждом столбце таблицы Поста
стоит хотя бы один знак «-». Система функций Е = {-,, —>} полна.
Задания.
!){->> 0};
2)	{л, Ф, 1};
3)	{->, 1};
4)	{|}, где х|у = -п(х л у) — штрих Шеффера;
5)	{>1}, где хХу = ->(х v у) — стрелка Пирса;
6){->, Ф};
7)	{=, а, 0};
8)	{ху v xz v yz, —х};
9)	{Ф, 1};
10)	{Ф, V, 0};
il){xy,(x=y)=z}\
12)	Н. I—>}- где х \~^у = -,(х -> у);
13)	{Н,Ч;
14НН-Н;
15) {v,4-
33
ЧА. Найти минимальные ДНФ и КНФ булевых функций.
Пример. f(x, у, z,t)= 1 на наборах 0,1,2,3,6,7,8,15. Используем диаграммы
Вейча для нахождения минимальных форм.
Каждая клетка диаграммы соответствует одному набору переменных,
номер клетки — это двоичный код набора. При задании булевой функции в
соответствующую номеру набора клетку записывается единица, и, таким
образом, каждая клетка диаграммы с 1 представляет собой одну конституенту
единицы.
Диаграмма Вейча для заданной функции представлена на рисунке. Едини-
цы функции, стоящие в соседних клетках, отличаются значением только
одной переменной, следовательно, они склеиваются по этой переменной и
образуют импликанту. В этом случае говорят, что имп ли канта покрывает
соответствующие единицы булевой функции. Например, две единицы на
наборах 7 и 15, покрываются импликантой yzt, четыре единицы на наборах 2,
3, 7, 6 — импликантой —jcz. При этом соседними считаются также клетки,
стоящие вдоль левого и правого края диаграммы (отличаются значением у)
и вдоль верхнего и нижнего края (отличаются значением х).
34
При минимизации булевой функции на диаграмме Вейча сначала находят
покрытия, содержащие максимальное число единиц (8,4,2), а затем покрытия,
накрывающие оставшиеся единицы таким образом, чтобы они также были
максимальны по величине и при удалении этого покрытия хотя бы одна
единица функции осталась непокрытой. При этом некоторые единицы могут
быть покрыты неоднократно. Для функции, представленной на рисунке,
минимальная ДНФ: —x—iy v -xz v yzt v
Минимальная КНФ строится аналогично по диаграмме Вейча, заполнен-
ной конституентами нуля в соответствующих клетках. Для данной функции
минимальная КНФ: (—iz/vz)(-ixv—izv£)(-ov?/v—!£).
Задания.
1)	f(x,y,z, Г) = 1 на наборах 0, 3, 4,6, 8,9,10, 11, 13, 15;
2)	f(x,y,z, t) = 1 на наборах 1, 2,4,6,7,9,10,13,14
3)	f(x,y,z. t) = 1 на наборах 1, 3, 5, 7, 8, 10, 12,14,15;
4)	f(x, у, z,t) = 1 на наборах 5, 7,8,9,10,11, 12,14, 15;
5)	f(x,y,z, t) = 1 на наборах 1,8, 10,11, 13, 14, 15;
6)	f(x,y,z, t) = 1 на наборах 0, 1, 2,3,5, 6, 9, 10,12, 14, 15;
7)	f(x,y,z, t) = 1 на наборах 0,3, 5,7,8,9, И, 12, 14,15;
8)	f{x,y,z, t) = 1 на наборах 1, 3, 6, 7, 8, 9, 10, 13, 14, 15;
9)	f(x,y,z, f) = 1 на наборах 2,4,5, 7,8,9,10, И, 12,13, 15;
10)	f(x, у, z,t) = 1 на наборах 1,4,5,7, 9,10,12,14;
11)	f(x,y,z, t) = 1 на наборах 2,4,6, 7, 10, 12, 14, 15;
12)	f(x, у, z,t) = l на наборах 2,4,6,9, 11,13, 15;
13)	f(x, у, z,t)= 1 на наборах 0,3,5,7,8, 9,10, 11, 12, 14;
14)	f(x, у, z, t) = 1 на наборах 0,1,2,3,8,10, 11;
15)	f(x, у, z, t) = 1 на наборах 1, 3, 6,7,8,9, 10, 15;
16)	f(x,y,z, t) = 1 на наборахО, 1,4,5,8,9, И, 12,15;
17)	f(x, у, z,t) = 1 на наборах 2, 3, 10, 11, 14,15;
18)	f(x, у, z,t) = 1 на наборах 0, 1,2,3,6, 7,8,9, 13;
19)	f(x, у, z, t) = 1 на наборах 2,3,4,5,8, 9,11,15;
20)	f(x, у, z,t)^l на наборах 1,3, 5, 6, 7,10, 11,12, 14;
21)	f(x, у, z, t) = 1 на наборах 0, 3, 7,8,9, 13,12;
22)	f(x, у, z,t) = 1 на наборах 0, 2, 4,6, 8, 10,12,14;
23)	f(x,y,z, t) = 1 на наборах 1, 3,4, 5,9, И, 12;
24)	f(x,y,z, t) = 1 на наборах 3,4, 5,6, 7, И, 14, 15;
25)	f(x, у, z,t) = 1 на наборах 4,6,8,9, 10, 12,14.
35
8. АЛГЕБРА ВЫСКАЗЫВАНИЙ
Упражнения
8.1. Определить, являются ли формулы тавтологиями.
Пример 1. Является ли формула ((А	В)~^ В тавтологией?
Решение. 1 способ — построение таблицы истинности.
Л	В	А->В	(А-^В)^В	{{А^В)^В)^В
F	F	Т	F	Т
F	Т	т	Т	Т
Т	F	F	Т	F
Т	Т	Т	Т	Т
Формула не является тавтологией, так как существует интерпретация
|Л| = Т, |В| = F, на которой она принимает ложное значение.
2 способ. Исследование формулы методом редукции.
Предположим, что существует набор, на котором формула принимает
значение, равное F:
|((Л->В)->В)->В| = Е
Тогда |((Л -> В) -> В) | = Т, | В | = F. Подставим найденное значение | В | = Fв
первое равенство: |(Л —> В) —> = Т. Решим это уравнение относительной:
если |Л| = Т, то |(7'—> F) —> F\ = Т. Следовательно, при |Л| = Т, |В| = Fформула
принимает значение, равное F. Таким образом, она не является тавтологией.
Пример 2. Является ли формула (Л -> В) & (В —» С) & А —> Ставтологией?
Решение. Исследование формулы методом редукции.
Предположим, что существует такая интерпретация, на которой формула
принимает ложное значение. Тогда
| А -+В | = Т, | В -> С| = Т, | А | = Г, | С\ = В. Тогда:
| В -э С| = | В -> В| =	| В | = В;
IЛ —> ВI = IЛ ->F\ = T=*\A\ = F.
Отсюда | А | = F, что противоречит третьему равенству | А | = Т Полученное
противоречие показывает, что формула не может принимать ложных
значений. Следовательно, формула (Л-> В)&(В->С)&А->С является
тавтологией.
Задания.
1)(Л^В)-^((В-^С)^(Л->С));
2)	(Л -> В) -> ((С -> В) (Л v С -> В));
3)	(Л -> (В -> С)) -> ((А -> В) -> (А -> Q);
36
4)	(-И -> -.В) -> (Л -> В);
5)	((Л —> В)-> А)-> ((А-» В)->В);
6)	(А -> С) -» (А -» В v С);
7)	(-Л -> В) -> (-1В -4 Л);
8)	((Л -> В) -> (А -> С)) -> (А -> (В -> Q);
9)(В->О)->(В->(А->0);
10)(В->А)->(А vB->A);
11)А&В-»(С->В);
12)	(В-> A v 0->((В-> С)->((£>-> С)->(В v/)4 0));
13)	((В —> А) —> С) —> (А —> С);
14)	(Л & В) v (С & D) -> (Л v В) & (С v В>);
15)	(А -> В) & (С-> D) -+ (A v С-+ В v D);
16)	(Л v В -> С) -> (Л -> Q v (В -> СУ,
17)	(Л & В -> С) -> ((А -> С) (В -> 0);
18)	(А В) & (С-ч> £>) -> (А & С-> В & D)-,
19)	(А -> В) -> ((-.А -> В) -> В);
20)	(А -> (В С)) (В -> (А -> 0);
21)	(-.В -> -^4) -> ((-.В -> А) -> В);
22)	А —> (—>В —> —,(Л —> В));
23)	-,(Л & В) -г (А & В В);
24)	(В —> 0 -> (A v С-> (В -> 0);
25)	(А -> (В С» -4 (Л v В Q.
8.2. Вывести (если возможно) заключение из каждого набора посылок.
Пример. Малые дети неразумны. Тот, кто может укрощать крокодилов,
заслуживает уважения. Неразумные люди не заслуживают уважения.
Получим возможные логические следования из данного множества
посылок. Обозначим каждое простое высказывание пропозициональными
буквами. Пусть Л — «малые дети», В - «разумны», С — «заслуживают
уважения», D — «может укрощать крокодилов». Построим дедуктивный
вывод, используя следующие правила вывода:
А-» В, В С\= А —> С - правило силлогизма.
А —> В |=-iB -> -Л - правило контрапозиции.
Вывод:
1.	Л -> ->В гипотеза Г(
2.	D —> С	гипотеза Г2
3.	->В —»—iC	гипотеза Г3
4.	Л—>-iC	правило силлогизма (1,3)
(Малые дети не заслуживают уважения).
37
5.	С —> В	правило контрапозиции (3)
(Только разумные люди заслуживают уважения).
6.	D —» В	правило силлогизма (2,5)
(Разумно укрощать крокодилов).
7.	—iB—>—iD правило контрапозиции (6)
(Неразумные люди не укрощают крокодилов).
8.	А —> —>D правило силлогизма (1,7)
(Малые дети не укрощают крокодилов).
Задания.
1)	Устрицы молчаливы. Молчаливые существа не очень-то забавны. Я не
люблю не забавных существ.
2)	Разумные люди ходят на ногах. Неразумные люди ходят на руках.
3)	Музыка, которую слышно, вызывает колебания воздуха. Музыка,
которую не слышно, не стоит того, чтобы за нее платили деньги.
4)	Если я поеду автобусом, а автобус опоздает, то я опоздаю на занятия
Если я опоздаю на занятия, то я начну огорчаться. Если я огорчен, то мне не
следует ехать домой.
5)	Если Смит победит на выборах, он будет доволен, а если он будет
доволен, то он плохой борец в предвыборной кампании. Но если он
провалится на выборах, то потеряет доверие партии. Если он плохой борец в
предвыборной кампании, ему следует выйти из партии. Смит или победит в
предвыборной кампании, или провалится. Он плохой борец, если потеряет
доверие партии.
6)	Если Петров член нашей команды, то он обязательно храбрый и хорошо
владеет техникой удара. Но он не входит в состав нашей команды.
7)	Зарплата возрастает только, если будет инфляция. Если будет
инфляция, то увеличится стоимость жизни. Если стоимость жизни возрастает,
то люди несчастны.
8)	Джон или устал, или он болен. Если он устал, то он раздражен. Он не
раздражен.
9)	Если конгресс отказывается принять новые законы, то забастовка не
будет окончена, кроме случая, когда она длится более года. Забастовка также
будет окончена, если президент фирмы уйдет в отставку. Конгресс
отказывается действовать, забастовка оканчивается, и президент фирмы не
уходит.
10)	Если человек стремится постичь смысл жизни, то он умеет вышивать
крестиком. Боксеры не умеют вышивать крестиком.
38
11)	В день дождливый Боб не ходит на прогулку. Без свежего воздуха у
него пропадает аппетит.
12)	Рыбак ловит рыбу. Тот, кто ловит рыбу — оптимист. Оптимист не
предается отчаянию.
13)	В хорошую погоду кошка ходит гулять. Если кошка больна, то она
сидит дома.
14)	Деревья, которые растут в этом саду, плодоносят. Деревья, которые
плодоносят, дают хороший урожай. Деревья, дающие хороший урожай,
получают тщательный уход. Ни одно дерево в этом саду не получает тщатель-
ного ухода.
15)	Если человек достоин славы, то он получает награду. Если человек не
храбрый, то он не достоин славы.
16)	Если идет дождь, то это наводит скуку. Осенью идет дождь.
17)	Лекарства противны на вкус. Настои из трав — это лекарства.
18)	Битвы сопровождаются страшным шумом. Если что-то происходит
без шума, то оно может ускользнуть от нашего внимания.
19)	Рыбы умеют плавать. Если это морская звезда, то она тоже — рыба.
20)	Книги с острым сюжетом не подходят для чтения легко возбудимым
людям. От книг со спокойным сюжетом клонит в сон.
21)	Если я читал статью, то она была напечатана в газете. Если что-то
напечатано в газете, то это может быть небылицей.
22)	Если человек не обладает чувством юмора, то он скучен. Скучных
людей не приглашают в компании. Если человека не приглашают в компании,
то его жизнь становится невыносимой.
23)	Мука пригодна для пищи. То, что пригодно для пищи, продается в
продуктовых магазинах.
24)	Если человек добился успеха, то он прилежен. Прилежные люди
счастливы.
25)	Если студент прогуляет много занятий, то он получит двойку на
экзамене. Если он получит двойку на экзамене, то пропадут каникулы.
Студент может хорошо отдохнуть, если у него будут каникулы.
39
9.	ФОРМАЛЬНЫЕ ТЕОРИИ
Упражнения
9.1.	С помощью метатеоремы о дедукции доказать теоремы в теории L.
Пример. Доказать теорему: |-Л —> (А —> В).
Воспользуемся обратной теоремой о дедукции: -Л|—А —> В, и еще один
раз: -Л, А|—В. Построим вывод —Л, А|—В
1. -А	И
2. А	Г2
3. (-1В->-А)-» ((-1В-> А)-» В)	АЗ
4. -Л^0В^-Л)	А1
5. А —> (—1В —> А)	А1
6. -пВ^-Л	МР(1,4)
7. -,В^А	МР(2,5)
8. (-.В-^А)->В	МР(3,6)
9. В	МР(7,8)
Применяя к полученному выводу два раза теорему о дедукции, получаем
доказательство теоремы.
Задания.
1)|- ((А -» В) -> А) -> ((А -»В) -> В);
2)|- (А —> 0 —> (А —> В v 0;
3)|- (-^1->В)->ЬВ->А);
4) |- ((А -> В) -> (А -> 0) -> (А -> (В -> 0);
5)|- (В —» 0 —> (В —> (А —» 0);
6)	|- (B->A)->(AvB->A);
7)|-А &В->(С^>В);
8)	|- (B->Av0 -> ((В->0 -> ((D->0 -> (BvD—>0));
9)	|—((В-> А)-> 0-> (А-> 0;
10)	|- (А -> В) &(В -> 0 -> (А -> 0;
И) |- (А -> (В -> 0) -> (В -> (А -> 0);
12)	|-—Л —> (В -i(B —> А));
13)	|- ((А-> В)-» А)-> А;
14)	|—В-» ((А-> (В-> 0)-> (А-> 0);
15)	|— (А & В —> 0 —> (А —> (В —> 0);
16)	|— (А —» (В -» 0) -» (А & В -> 0;
17)	|- (А -> В) ((А -> ->В) -> -Л);
18)	|- -,(А v В) -> -A f^-iB;
19)	|—A v (В v 0 -> (A v В) v С;
40
20)	|— (A & В) v (A & 0 —> Л & (В v 0;
21)	|- (А -> ->В) -> ((А -> В) -> -Л);
22)	|- (Л -> В) -> ((С-> В) -> (Л v С -> В));
23)	|- (Л -> ^В) -> (В -> -А);
24)|-(а->(в->-,(А->-В)));
25)	|- (С-> (Л -> В)) -> (С-> (-,В -> -Л)).
9.2.	Построить выводы и доказательства в теории Ц.
Теория Lt. Основные связки: v, -i.
Метаопределение: Л —> В = -Л v В.
Схемы аксиом:
Л1: Л vA -> Л
Л2:А->А vB
ЛЗ: Л v В —> В v А
А4: (В -> 0 -> (A v В -> A v 0
Правило вывода: МР.
Задания.
1)	A->B|-CvA->CvB;
2)	|-(Л->В)->((С->Л)->(С->В));
3)	С-> А, А-> В |—С-> В;
4)	|— Л -> Л (т.е. |-iA v А);
5)	|—Av—Л;
6)	|-А->-г-Л;
7)	|-^_>(В->0;
8)	|-Av(Bv0->((Bv(A v0)vA);
9)	|—(Bv(A v0)vA—>Bv(A v 0;
10)	|— A v (В v 0 -> В v (A v 0;
11)|—(A->(B-»0)->(B-»(A->0);
12)	I- (C-> A) -> ((A -> В) -> (С -> B));
13)A->(B-»0,A^B|-A^(A^0;
14)A^(B-^0,A^B|-A^C;
15)B^A,-1B-^A|-A;
16)	Г, A |— В => Г |— A -> В (метатеорема дедукции).
9.3.	Построить выводы и доказательства в теории Ь2.
Теория LT Основные связки: &, -i.
Метаопределение: Л —> В = -,(А & -iB).
Схемы аксиом:
А1:А^(А&А)
41
А2: (А&В)-*А
ЛЗ: (Л -> В) -> Ь(В & С) -> -.(С & Л))
Правило вывода; МР.
Задания.
1)	А -> В, В -> С |- —.(—.С & Л);
2)	|-1(—А &Л);
3)	|—-1-1А-4Л;
4)	|- -,(Л & В) —> (В —> -Л);
5)	|— А
6)	(Л->В)->ЬВ->-Л);
7)	-Л —>-,В|—В—>Л;
8)	Л-»В|- С&А->В&С;
9)	Л->В,В->С, С->О|-Л->О;
10)|—Л—>Л;
11) |—Л & В —> В & Л;
i2)A^>B,B->C\-A->C;
13)	Л —» В, С—> D |—Л & С—> В & D;
14)	ВС\—А & В А & С;
15)	|- (Л -> (В -> 0) -> ((Л & В) -4 0;
16)	Л -» В, Л -4 (В -> 01— Л -» С;
17)|-Л->(В-»Л & В);
18)	Л—>(В—»Л);
19)	Г, Л |— В => Г |— Л —> В (метатеорема о дедукции);
20)	|- (-Л->Л)->Л;
21)	АВ,—АВ\— В.
10.	ТЕОРИЯ ПРЕДИКАТОВ ПЕРВОГО ПОРЯДКА
S(x): х - студент,
R(x, у): х пишет у,
N(y):y - роман,
С (у): у - стихи,
L(y)'-y ~ письмо,
Упражнения
10.1.	Пусть х е {люди}, у е {вещи, которые можно читать и писать}. На этих
областях определения заданы предикаты:
Р(х). х - профессор,
\ '(х): х - поэт,
W(x, у): х любит читать у,
К(у) '- у - конспект,
U(y): у - учебник,
Н(у).у - шпаргалка.
Следующие высказывания записать в виде формул логики предикатов.
42
Пример.
Некоторые учебники представ-
ляют собой конспекты —
Ни один роман не является
учебником —
Каждый читает какие-нибудь
учебники —
Некоторые студенты читают
только учебники —
Пушкин писал и стихи,
и романы —
Студент Боб не пишет письма —
Студент Боб читает только
конспекты —
Любой поэт пишет письма —
Задания.
3y(U(y) & Kfj/));
Vy(N(y) ^>-iU(y));
Vx3y(U(y) & W(x,y))\
3x(5(x) & V«/(lV(x, y) -> [/(«/)));
Vi/( С(г/) v N(y) -> /^(Пушкин, y))\
5(Боб) & Vj/(Z(z/) -> -п/?(Боб,«/));
5(Боб) & Vi/( W(Bo6, y) -> K(z/));
Vx(V(x) -> Vj/(Z(z/) -> R(x,«/))).
1)	Некоторые романы написаны в стихах.
2)	Ни один учебник не написан в стихах.
3)	Все конспекты - учебники.
4)	Некоторые стихи - письма.
5)	«Евгений Онегин» - это роман в стихах.
6)	Никто не любит писать письма.
7)	Некоторые люди пишут стихи.
8)	Те, кто пишет стихи, — поэты.
9)	Все поэты любят читать стихи.
10)	Все студенты любят читать учебники.
И) Все студенты пишут конспекты.
12)	Некоторые студенты пишут только шпаргалки.
13)	Никто из студентов не пишет учебники.
14)	Некоторые профессора, а также студенты, пишут стихи.
15)	Некоторые не любят читать никаких учебников.
16)	Студент Том любит читать учебники.
17)	Профессор Джонс- поэт.
18)	Шекспир писал только стихи.
19)	Каждый любит читать какие-либо стихи.
20)	Каждый, кто любит читать ка,ше-либо стихи, любит читать стихи
Шекспира.
21)	Только студенты пишут конспекты.
22)	Профессора пишут учебники.
23)	Ни один профессор не пишет шпаргалки.
43
24)	Студенты, которые пишут конспекты, не пишут шпаргалки.
25)	Поэты пишут стихи.
26)	Поэты пишут только стихи.
27)	Некоторые поэты пишут и стихи, и романы.
28)	Все пишут письма.
29)	Только поэты пишут только стихи.
30)	Любой поэт любит читать свои стихи.
10.2. Построить таблицы истинности на области интерпретации D = {1, 2}.
Пример. Е = Vx3y(P(x) v Q(y) -» R).
Предикаты P(x), Q(y) на области интерпретации D = {1, 2} принимают
следующие значения:
X	P>	P.		P<		У	Q,	q?	Q.	Q.
1	F	F	T	T		1	F	F	T	T
2	F	T	F	T		2	F	T	F	T
R - замкнутая формула, т.е. высказывание, которое принимает значение Tn F.
Поскольку предикат Р(х) принимает 4 значения, предикат Q(y) - 4
значения, формула R — 2 значения, и в формуле Е нет свободных переменных,
ее таблица истинности будет состоять из 4x4x2 = 32 строк. Очевидно, что
если |Р| = Т, то = Т, поэтому остается вычислить значение формулы на
оставшихся 16 интерпретациях формулы при |Р| = F.
Пусть |Р| = F. Рассмотрим вычисление значения формулы на интерпрета-
ции Р = Р, и Q = Q2.
х=1з l>'=1/’i(1)ve2(i)->p
VV = 2P,(l)ve2(2)->P
jy=ip1(2)ve2(i)->p
х = 2 Зу-<
qy=2P1(2)ve2(2)->p
= Vx-
(FvF—>F = 7’|
x = 13y<	I
|Fv7’->F = Fj
[FvF—»F = 7’1
x = 2 3y	[
[Fv7’->F = F]
= T
= T
Пусть P = P2 и Q = Тогда
л э fy=ip2(i)ve,(i)->p
yV=2p2(i)ve1(2)->p
2 э fy=ip2(2)ve,(i)^p
VV = 2P2(2)ve,(2)->P
44
(FvF—>F = P1
x = 1ЭуЧ	>
[FvF->F = 7J
(7'vF->F = Fl
x = 2 3y<	r
|Z’vF->F = F|
= T
= F
fr]
= Vx< > = F
[fJ
Аналогично находятся остальные значения формулы Е, которые
приведены ниже в таблице.
p			p,		Pi	Pi	Pi	Pi	P3	P3	P3	P3	P<	P<	Pt	Pt
Q	Q,		Qb	Q.	Q,	Qi	Qb	Qb	Q,	Qi	Q3		Q,	Qi	Q3	Qb
E	T	t	t	F	F	F	F	F	F	F	F	F	F	F	F	F
Задания.
1) HxVi/(P(x) v Q(y) -> R);
2)Vx(By(R->P(x)vQ(y»y
3)3x(P->V«/(P(x)->QG/)));
4)Vx(P->Vz/(Q(y)^P(x)));
5)3x(P(x)->3«/(F^Q(z/)));
6) 3x(P(x) -» Vy(Q(y) -> P(x)));
7)3x(P(x)&3j/(Q(«/)->P));
8) Vx(P(x) v 3y(Q(y) ^R)^S);
9) 3x(P(x) & Vy Q(y)) -> Vx P(x);
10)3xVz/(P(x)vQ(//)->Q(y));
11) 3x(P(x) & 3y(Q(y) -> P(x))).
12)3x(Vy(P(x)->P(y))~Q);
13) Vx(P(x) & 3zP(z) -> 3yQ(y));
ii)\fx((P(x)~3yQ(y))&P(x)y,
15) 3y(P(y) v Vx-iQ(x) -> P(z/));
16)3y(P(«/)->VxP(x))-Q;
17) 3xVy(P(x) v Q(y)) -» R',
18)3xP(x)vVz/Q(j/)->P;
19)	3x(P(x) v VyQ(y) -»R);
20)3x(Vz/(P->P(x)vQ(«/)));
21)	Vx(P(x) -> Vy(Q(y) -> P(x)));
22)	Vy(3xP(x) v Q(y) -> Q(y));
23)	3x(P(x) & Vy(Q(y) -> P(x)));
24)3x(Vz/(P(x)^(P-Q(v))));
25)	3x((P(x) -> VyQ(z/)) & P(x)).
45
10.3.	Проверить логическую общезначимость следующих формул.
Пример 1. Дана формула: Vx(P(x) -» Q(x)) v Vx-iQ( г). Если формула
общезначима, она принимает истинное значение на всех возможных
интерпретациях.
Для проверки общезначимости используем метод нахождения контрпримера.
Предположим, что формула Vx(P(x) -> Q(x)) v Vx—iQ(x) не является логически
общезначимой. Тогда существует такое множество М, интерпретации Р*(х), Q*(x)
предикатов Р(х), Q(x) соответственно, что |Vx(P*(x) -> Q*(x)) v Vx-iQ*(x)| = F.
Отсюда следует, что
|Vx(P*(x)->Q*(x))| = f	(1)
|Vx-.Q*(x)| = F	(2)
Формула (2) принимает ложное значение, если на области интерпретации
существует хотя бы одно значение ае М, при котором |—>(2*(я)| = F, т.е. |Q*(a)| =
Т. Для того, чтобы формула (1) приняла значение Р, достаточно, чтобы
существовало хотя бы одно значение х, например, х = с, такое, что |Р*(с)| = Т,
а lQ*(c)| = F (с не обязательно совпадает с я), Следовательно, мы нашли
контрпример: достаточно на некотором n-элементном множестве М (п > 2)
найти такую интерпретацию, при которой |Р*(с)| = Т, |Q*(c)| = Fn |(2*(я)| = Т.
Таким образом, формула Vx(P(x) -> Q(x)) v Vx-iQ(x) не является
логически общезначимой.
Пример 2. Зх(Р(х) v Q(x)) -> ЗхР(х) v 3xQ(x).
Предположим, что существует множество М и интерпретация на нем Р*(х),
Q*(x) такая, что формула на этой интерпретации принимает значение F:
|3x(P*(x) v Q*(x)) -> ЗхР*(х) v 3xQ*(x)| = F. Тогда:
|3xP* (х) v 3xQ* (х)|= F,	(1)
|3x(P(x)vQ(x))|=F.	(2).
Формула (1) ложна, если |ЗхР*(х) |= Fn |3xQ*(x)|= F, а отсюда следует,
что
|Р*(х)|= F для любого хе М	(3)
и |Q*(x)|= Рдля любого хе М. (4)
Из (2) следует, что существует такое ае М, что |Р*(я) v (2*(я)|= Т. Возмож-
ны три варианта: а) |Р*(я)| = Т, |Q*(a)| = Г; Ь) |Р*(я)| = Т, |(2*(я)| = F; с) |Р*(а)| = F,
|Q*(«)I=F.
Вариант а) противоречит условиям (3), (4). Однако, это противоречие еще
не доказывает общезначимость формулы - следует проверить все варианты.
Вариант Ь). Если |Р*(я)| = Т, то это противоречит условию (3).
Вариант с). Если |(2*(я)| = Т, то это противоречит условию (4).
Следовательно, не существует такой интерпретации, на которой формула
Зх(Р(х) v Q(x)) —> ЗхР(х) v 3xQ(x) принимает ложное значение, т.е. она
логически общезначима.
46
Задания.
1)	Зх(Р(х) v (Зх(Р(х) -> Q(x)) -> 3xQ(x));
2)	(В -> ЗхР(х)) - Эх(В —>Р(х)У,
3)	Vx(P(x) v Q(x)) -> VxP(x) v VxQ(x);
4)	3x(P(x) v Q(x)) - 3xP(x) v 3xQ(x);
5)	(3xP(x) -> 3xQ(x)) -> 3x(P(x) -> Q(x));
6)	Vx(P(x) & Q(x)) - VxP(x) & VxQ(x);
7)	3x(P(x)	Q(x)) -> (3xP(x) -> 3xQ(x));
8)	(3x(P(x) -> Q(x)) & Vxft(x)) (Vx(P(x) & P(x)) v 3xQ(x));
9)	Зх(Л(х) -> B(x)) ~ (ЗхЛ(х) v 3xB(x));
10)	(3xP(x) - 3xQ(x)) - 3x(P(x) - Q(x));
11)	Vx(P(x) -> (Q(x) -> P(x)) -> (3x(P(x) v Q(x)) -> VxP(x));
12)	3x(P(x) -> Q(x)) ~ (VxP(x) v 3rQ(x));
13)	3x(P(x) -> (Q(x) -> P(x))) -> Vx(P(x) v Q(x) -» P(x));
14)	Vx(P(x) v Q(x) -> P(x)) -> Vx(P(x) (Q(x) -> P(x)));
15)	Vx(P(x) -> (Q(x) -> P(x))) -> Vx(P(x) v Q(x) -> P(x));
16)	VxP(x) v VxQ(x) -> Vx(P(x) v Q(x));
17)	3x(P(x) v Q(x)) -> 3xP(x) v 3xQ(x);
18)	Vx(P(x) & Q(x)) VxP(x) & VxQ(x);
19)	3x(P(x) & Q(x)) 3xP(x) & 3xQ(x);
20)	3xP(x) & 3xQ(x) 3x(P(x) & Q(x))-,
21)	Vx(P(x) Q(x)) (VxP(x) VxQ(x));
22)	(VxP(x) VxQ(x)) -> Vx(P(x) -> Q(x));
23)	Vx(P(x) - Q(x)) -> (VxP(x) - VxQ(x));
24)	(VxP(x) - VxQ(x)) Vx(P(x) - Q(x));
25)	Vx(P(x) & Q(x)) -> 3xP(x) v 3xQ(x).
47
11. АВТОМАТИЧЕСКОЕ ДОКАЗАТЕЛЬСТВО ТЕОРЕМ
Упражнения
Проверить логическое следование в логике предикатов 1-го порядка.
Пример. Некоторые студенты любят своих преподавателей. Никто не
любит невежественных людей. Следовательно, ни один преподаватель не
является невежественным.
Все предикаты заданы на области D = {люди}. Пусть Р(х): х — студент,
D(x)'. х — преподаватель, Q(x): х — невежественный, L(x, у) — х любит у.
Формализуем посылки:
F1: Зх(Р(х) & Чу(Р(у) Цх, у})).
F2-. Vx(P(x) -> Vy(Q(i/) -> -i£(x,«/))).
Следствие G: Vy(D(y) -> -^Q(y)).
Для доказательства логического следования можно использовать метод
от противного, формальный вывод и метод резолюций.
Метод от противного.
Предположим, что при истинности посылок |F1| = Т, |F2| = Тзаключение
принимает ложное значение: |G| = F.
Из |Vi/(£)(z/) —> -iQ(i/))| = F следует, что существует такое у = а, что
|П(С) -> -<(О)| = F. Тогда |£>(«)| = Т, HQ(«>I “ Р. т.е. |Q(a)| = Т.
Из |Зх(Р(х) & (0(a) —> £(х, а)))| = Т следует, что существует такое х = Ь,
что |(P(fe) & (О(а) -> L(b, а))| = Т. Тогда |P(fe)|= Т и |П(а) —> L(b, а)| = Т, а так
как |£>(а)|= Т, то \L(b, а)|= Т.
Посылка F2: |Vx(P(x) -> (Q(a) -> -i£(x, с)))| = Тдля всех х, в том числе для
х = Ь, следовательно, |P(Z>) —> (Q(a) —» ->L(b, а))| = Т, а так как |P(fe)| = Т,
|Q(a)| = Т, то из |Q(a) -> -,L(b, а)| = Тследует |	|= Т .
Таким образом, получаем, что истинны оба утверждения: |Т—>L(b, о)|= Т и
|Г—>—<L(b, а)|= Т, т.е. \L(b, а)|= Т и |-i£(fc, й)|= Т. Полученное противоречие
доказывает логическое следование.
Формальный вывод.
1.	3x(P(x)&V!/(D(y)->£(x,«/)))	Г1
2.	Vx(P(x) Vi/(QG/) -> -п£(х, у)))	Г2
3.	P(b) & Vy(D(y) ЦЬ, у))	ЭК(1)
4.	Р(6)	уд. &(3)
5-	-> L(b, у))	уд. &(3)
6.	P(b) -> V^(Q(t/) -> ^L(b, у))	УК(2)
7-	^y(Q(y) -> -£(й, У))	МР(4,6)
8.	Q(z)->-.£(&, г)	УК(7)
48
9. D(z) -» L(b, г)
W.L(b,z)->^Q(z)
11 £)(z)->->Q(z)
\2.\/y(D(y) ->-.QQ/))
УК(5)
контрапозиция (8)
силлогизм (9,10)
Gen (И)
Метод резолюций.
Найдем предваренные нормальные формы (ПНФ) для посылок.
F1:3x(P(x)&Vz/(D(j/)->£(x, «/))) = 3x(P(x)&Vy(-nD(^)v£(x, у))) =
= 3x(Vr/(-^D(i/)vI(x, г/))&Р(х)) = 3xVz/((^D(z/)v£(x, г/)) & Р(х)) - ПНФ.
F2: Vx(P(x)-»Vi/(QG/)-^Z(x,y))) = Vx(^P(x)vVz/(-nQ(z/)v^£(x,^))) =
- Vx(V^(^Q(«/)v^L(x, у)) v ^Р(х)) = VxV,y(-QG/)v-.Z(x. у) v -пР(х)) -
ПНФ.
Найдем скулемовскую стандартную форму (ССФ) посылок.
F1: Элиминируем квантор 3 в формуле 3xV«/((-iD(z/)v£(x, г/)) & Р(х)).
Положим х = а, получим ССФ посылки F1:
Vy(^D(y)vL(a,y))&P(a),
F2: X/xX/y(->Q(y)v-lL(x,y)v-iP(x)) находится в скулемовской стандартной
форме.
Возьмем отрицание от следствия G:
-Wy(D(y) -> -QG/)) = Эу -,(-<D(y) v -.QG)) = 3y(D(y)&Q(y)). Это ПНФ.
Элиминируем квантор 3, положив у = Ь:
D(b)&Q(F) - ССФ.
Получим множество дизьюнктов:
S - {->D(z/)v£(c, у), Р(а), -,Q(y)v-,L(x, y)v-,P(x), D(b), Q(b)}.
Построим резолютивный вывод:
1.
2.	Р(а)
3.	-.Q(z/)v-lL(x,v) v-.P(x)
4. D(b)
5. Q(b)
6. —>Z(x, b) v —iP(x)
7. -,£.(a,£)
{b/y}, резольвента 5,3
{a/x}, резольвента 2,6
8. -.D(fe)
9. □
{b/y}, резольвента 1,7
резольвента 4,8
49
Построение логической программы.
Запишем множество дизъюнктов в виде клауз.
Predicates
Р(х~)	/* х - студент
О(х)	/* х - преподаватель
Q(x)	/* х - невежественный
1(х,г/)	/* х любит у.
Clauses
Pip)
D(b)
Q(.y), L(x,y), P(x)
L(a,y):- D(y)
Goal: ? - not Q(b)
Дерево выполнения логической программы приве-
дено на рисунке.
Задания
11.1. Проверить логическое следование.
Q(b)
:-Q(y\L(x,y),P(x)
| {b/y}
Цх, b), P(x)
i
L(a,y):-D(y)
{а/х, Ыу}
:—D(b),P{a)
I
0(6)
i
:-Р(а)
i
Р(а)
I
1) Области определения: множество людей и множество книг. Все студенты
читают учебники. Некоторые студенты не читают стихов. Следовательно, ни
один учебник не написан в стихах.
2) Область определения:люди. Ни один торговец подержанными автомоби-
лями не покупает подержанные автомобили для своей семьи. Некоторые лю-
ди, которые покупают подержанные автомобили для своих семей, абсолютно
нечестны. Следовательно, некоторые абсолютно нечестные люди не являются
торговцами подержанными автомобилями.
3)	Область определения: люди. Каждый, кто идет в кино, покупает билет.
Следовательно, если не существует билетов, то никто не ходит в кино.
4)	Область определения:люди. Ни один лентяй не достоин славы. Некоторые
художники не лентяи. Следовательно, некоторые художники достойны славы.
5)	Область определения: студенты. Некоторые первокурсники любят всех
второкурсников. Ни один первокурсник не любит никого из студентов пред-
последнего курса. Следовательно, ни один второкурсник не является студен-
том предпоследнего курса.
6) Область определения: животные. 1. Я люблю всех животных, которые
принадлежат мне. 2. Собаки грызут кости. 3. Ни одно животное я не пускаю к
себе в кабинет, если оно не «служит», когда его об этом просят. 4. Все животные
во дворе принадлежат мне. 5. Всем животным, которых я люблю, разрешается
входить ко мне в кабинет. 6. Единственные животные, которые «служат», если
их попросить,- собаки. Следовательно, все животные в этом дворе грызут кости.
50
7)	Область определения: дни. 1. Я не называю день «несчастливым», если
Робинсон вежлив со мной 2. Среды всегда бывают пасмурными днями. 3. Если
люди берут с собой зонты, день никогда не бывает солнечным. 4. Единственный
день недели, когда Робинсон невежлив со мной,— среда. 5. Всякий возьмете собой
зонт, если идет дождь. 6. Мои «счастливые» дни неизменно оказываются
солнечными. Следовательно, дождливые дни пасмурны.
8)	Область определения: люди. 1. Никто не забудет причесаться, если он
отправляется на бал. 2. Нельзя сказать, что человек выглядит превосходно,
если он неопрятен. 3. Курильщики опиума утрачивают контроль над собой.
4. Причесанный человек выглядит превосходно. 5. Никто не наденет белых
лайковых перчаток, если он не отправляется на бал. 6. Человек всегда неопря-
тен, если он утратил контроль над собой. Следовательно, курильщики опиума
никогда не носят белых лайковых перчаток.
9)	Область определения- представленные здесь картины 1. Ни одна из
представленных здесь картин, кроме батальных, не представляет ценности.
2. Ни одна из картин, вывешенных без рам, не покрыта лаком. 3. Все баталь-
ные картины написаны маслом. 4. Все распроданные картины представляют
ценность. 5. Все картины английских мастеров покрыты лаком. 6. Все карти-
ны, которые были вывешены в рамах, проданы. Следовательно, все представ-
ленные здесь картины английских мастеров написаны маслом.
10)	Область определения: мои мысли. 1. Любая мысль, которую нельзя
выразить в виде силлогизма, поистине смешна. 2. Моя мечта о сдобных булоч-
ках не стоит того, чтобы ее записывать на бумаге. 3. Ни одну мою несбыточ-
ную мечту нельзя выразить в виде силлогизма. 4. Мне не приходило в голову
ни одной действительно смешной мысли, о которой бы я не сообщил своему
поверенному. 5. Я только и мечтаю, что о сдобных булочках. 6. Я никогда не
высказывал своему поверенному ни одной мысли, если она не стоила того,
чтобы ее записать на бумагу. Следовательно, все мои мечты сбылись.
11)	Область определения: предметы. 1. Я с отвращением отношусь ко
всему, что не может служить мостом. 2. Все, что можно воспеть в стихах, для
меня приятный подарок. 3. Радуга не выдержит веса тачки. 4. Все, что может
служить мостом, выдержит вес тачки. 5. Я не принял бы в качестве подарка
то, что вызывает у меня отвращение. Следовательно, радугу не стоит воспевать
в стихах.
12)	Область определения: авторы литературных произведений. 1. Все авторы
литературных произведений, постигшие природу человека, умные люди. 2. Ни
одного автора нельзя считать истинным поэтом, если он не способен волновать
сердца людей. 3. Шекспир написал «Гамлета». 4. Ни один автор, не постигший
природу человека, не способен волновать сердца людей. 5. Только истинный поэт
мог написать «Гамлета». Вывод: Шекспир был умным человеком.
51
13)	Область определения:люди этого колледжа. 1. Все выпускники Итона
в этом колледже играют в крикет. 2. Никто, кроме преподавателей, не обедает
за верхним столом. 3. Ни один из тех, кто играет в крикет, не умеет грести. 4.
Все мои друзья в этом колледже — выпускники Итона. 5. Все преподаватели —
прекрасные гребцы. Вывод: все мои друзья обедают за нижним столом.
14	) Область определю шя.люди. 1. Те, кто i арушает свои обеща! i ия, не заслужт шаюг
доверия. 2. Любители выпить очень общительны. 3. Человек, выполняющий свои
обещания, честен. 4. Ни один трезвенник не ростовщик. 5. Тому, кто очень общителен,
всегда можно верить. Вывод: ни один ростовщик не бывает нечестен.
15)	Область определения: плоды на этой выставке. 1. Все плоды на этой
выставке, которые не будут удостоены награды, являются собственностью
организационного комитета. 2. Ни один из представленных мной персиков не
удостоен награды. 3. Ни один из плодов, распроданных после закрытия выстав-
ки, не был незрелым. 4. Ни один из спелых плодов не был выращен в теплице. 5.
Все плоды, принадлежащие оргкомитету выставки, были распроданы после ее
закрытия. Вывод: ни один из моих персиков не был выращен в теплице.
16)	Область определения: поэмы. 1. Ни одна интересная поэма не останется
непризнанной людьми с тонким вкусом. 2. Ни одна современная поэма не
свободна от аффектации. 3. Все ваши поэмы написаны о мыльных пузырях.
4. Ни одна аффектированная поэма не находит признания у людей с тонким
вкусом. 5. Ни одна древняя поэма не написана о мыльных пузырях. Вывод:
все ваши поэмы не интересны.
17)	Область определения: книги в этой библиотеке. 1. Единственные книги в
этой библиотеке, которые я не рекомендую читать, безнравственны по своему
содержанию. 2. Все книги в твердых переплетах обладают выдающимися литера-
турными достоинствами. 3. Все романы вполне нравственны по своему содержа-
нию. 4. Я не рекомендую вам читать ни одну из книг в мягкой обложке. Вывод:
все романы в этой библиотеке обладают выдающимися литературными
достоинствами.
18)	Область определения: вещи. 1. Все вещи, продаваемые на улице, не имеют
особой ценности. 2. Только дрянь можно купить за грош. 3. Яйца большой гагарки
представляют большую ценность. 4. Лишь то, что продается на улице, и есть
настоящая дрянь. Вывод: яйцо большой гагарки за грош не купишь.
19)	Область определения: мои дети. 1. Все мои сыновья стройны. 2. Никто
из моих детей не здоров, если он не делает утренней зарядки. 3. Все обжоры
среди моих детей страдают ожирением. 4. Ни одна из моих дочерей не делает
утренней зарядки. Вывод; все мои дети-обжоры не здоровы.
20)	Область определения:люди. 1. Ни один ребенок не обладает терпением.
2. Ни один нетерпеливый человек не может сидеть спокойно. Вывод: любой
ребенок не усидит на месте.
52
21)	Область определения: люди. 1. Ни одна из моих кузин не справедлива.
2. Все судьи справедливы. Вывод: среди моих кузин нет судей.
22)	Область определения: живые существа. 1. Ни одно толстое создание
не бегает хорошо. 2. Некоторые гончие бегают хорошо. Вывод: гончих трудно
назвать толстыми.
23)	Области определения: множество людей и множество книг. 1. Некото-
рые люди пишут стихи. 2. Те, кто пишет стихи — поэты. 3. Все поэты любят
читать стихи. Вывод: некоторые люди любят читать стихи.
24)	Области определения: множество людей и множество литературных
произведений. 1. Некоторые студенты читают стихи. 2. Ни один студент не
читает шпаргалки. Вывод: ни одна шпаргалка не рифмована.
25)	Области определения: множество людей и множество литературных
произведений. 1. Некоторые студенты пишут некоторые учебники. 2. Все
студенты пишут только письма. Вывод: некоторые учебники можно отнести
к эпистолярному жанру.
26)	Область определения:литературные произведения. 1. Некоторые рома-
ны написаны в стихах. 2. Ни один учебник не написан в стихах. Вывод: ни
один учебник не является романом.
27)	Область определения: студенты. 1. Некоторые студенты прилежны,
но плохо учатся. 2. Плохо учатся не очень умные студенты. Вывод: некоторые
прилежные студенты не очень умны.
28)	Области определения: множество людей и множество литературных
произведений. 1. Все студенты пишут конспекты. 2.11и один студент не пишет
романы. 3. Некоторые люди учатся в институте. 4. Все, кто учится в институте,
студенты. Вывод: конспекты — не романы.
29)	Область определения:люди. 1. Ни один император не дантист. 2. Всех
дантистов боятся дети. Вывод: дети не боятся императоров.
30)	Область определения:люди. 1. Все осмотрительные люди остерегаются
гиен. 2. Ни одному банкиру не свойственна неосмотрительность. Вывод:
банкиры остерегаются гиен.
11.2.	Составить логическую программу и проверить логические следования.
1)	Каждое небесное тело является либо звездой, либо кометой, либо
планетой. Венера — небесное тело, не являющееся звездой. У комет, располо-
женных недалеко от солнца, есть хвосты. Венера недалеко от Солнца, но у
нее нет хвоста. Следствие: Венера — планета.
2)	Каждый, кто силен и умен, добьется успеха в карьере. Джон силен и
умен. Следствие: Джон добьется успеха в карьере.
3)	Ни один дракон, который живет в зоопарке, не является счастливым. Любой
зверь, который встречает добрых людей, является счастливым. Люди, которые
53
встречаются в зоопарке - добрые. Звери, которые живут в зоопарке, встречают людей,
которые посещают зоопарк. Следствие: ни один дракон не живет в зоопарке.
4)	Боб счастлив, если всем его студентам нравится логика. Следствие: Боб
счастлив, если у него нет студентов.
5)	Брадобреи бреют всех тех, кто не бреется сам, и не бреют тех, кто бреется
сам. Брадобреи существуют. Должен ли брадобрей брить самого себя?
6)	Джону нравится любой, кто не нравится самому себе. Джону не нравится
никто, кто нравится себе. Нравится ли Джон сам себе?
7)	Нечто, несущее в себе черты чего-то хорошего, хорошо само по себе.
Нечто, несущее в себе черты чего-то плохого, плохо само по себе. Война несет
в себе черты мира и страдания. Мир хорош, а страдание плохо. Следствие:
некоторые вещи и хороши и плохи.
8)	Каждый восхищается героем. Неудачник восхищается каждым.
Каждый, кто не является героем - неудачник. Найти пары, которые
восхищаются друг другом.
9)	Для любого множества X существует множество Yбольшей мощности.
Если X содержится в Y, то мощность X не превышает мощности У. Каждое
множество содержится в Z. Следствие: Z не является множеством.
10)	Каждый любит какую-нибудь книгу. «Мастера и Маргариту» любит
каждый, кто любит какую-либо книгу. Следовательно, «Мастера и Маргари-
ту» любит каждый.
11)	Шекспир писал только стихи. Те, кто пишет только стихи,— поэты.
Все поэты любят читать стихи. Каждый, кто любит читать какие-либо стихи,
любят читать стихи Шекспира. Следовательно, Шекспир любил почитывать
свои произведения.
12)	Все склонные к горячности люди неразумны. Ораторы выступают с
речью перед аудиторией. Во время выступления любому из ораторов трудно
оставаться спокойным. Цицерон был оратором. Разумен ли Цицерон?
13)	Все драконы — нелукавые. Все шотландцы — лукавые. Следовательно,
среди шотландцев нет драконов.
14)	Джон находится в этом доме. У всех, кто находится в этом доме, болят
зубы. Следовательно, у Джона болят зубы.
15)	У бедных нет автомобиля. Том — беден. Все хотят быть компаньонами
только богатых предпринимателей. У всех богатых есть автомобиль. Следова-
тельно, никто не хочет взять в компаньоны Тома.
16)	Все мои друзья простудились. Джон — мой друг. Тому, кто простужен,
нельзя петь. Следовательно, Джону нельзя петь.
17)	Кроссворды, напечатанные в этом журнале, очень интересные. Ни один
кроссворд, который легко разгадывается, не интересует меня. В журнале
напечатан кроссворд о животных. Смогу ли я его быстро разгадать?
54
18)	Все неправдоподобные истории вызывают сомнение. Любая история,
рассказанная человеком с фантазией, выглядит неправдоподобно. Барон
Мюнхгаузен был большим фантазером. Следовательно, истории барона
вызывают сомнения.
19)	Утки при ходьбе переваливаются с боку на бок. Все, что переваливается
с боку на бок, не изящно. Все, что не изящно, не участвует в конкурсах красо-
ты. Следовательно, утки не выставляются на конкурсе.
20)	Ни один добрый поступок не является незаконным. Все, что законно,
можно делать без страха. Перевести старушку через дорогу — дело доброе.
Следовательно, совсем не страшно переводить старушек через дорогу.
21)	Ни у одного ископаемого животного не может быть несчастной любви.
У устрицы может быть несчастная любовь. Следовательно, устрицы не иско-
паемые животные.
22)	Ни одна исследованная до сих пор страна не кишит драконами. Неис-
следованные страны пленяют воображение. В Бамбургском королевстве
драконы встречаются на каждом шагу. Следовательно, Бамбург мог бы нас
заинтересовать.
23)	Ни одна оригинальная работа не пишется по заказу. Стихи Льюиса
Кэрролла очень оригинальны. Следовательно, стихи Кэрролла написаны не
по заказу.
24)	Зонтики бывают очень полезны в пути. Все, что не нужно в пути,
следует оставить дома. Следовательно, зонтики надо брать с собой в дорогу.
25)	Все бледные люди флегматичны. Только те, кто бледен, имеют поэтиче-
скую внешность. Пушкин отличался бурным темпераментом. Имел ли он поэ-
тическую внешность?
26)	Ни одно успешное путешествие не остается забытым. Путешествие,
закончившееся неудачно, не заслуживает того, чтобы о нем писали книгу. О
путешествии Афанасия Никитина написана книга. Помним ли мы об этом
путешествии?
27)	Все трезвенники любят сахар. Ни один соловей не пьет вина. Тех, кто
пьет вино, не назовешь трезвенниками. Следовательно, все соловьи любят
сахар.
28)	То, что трудно, требует внимания. Если любому предмету уделять
много внимания, то он становится доступным для понимания. Физика дается
с большим трудом. Стала ли физика более доступной?
29)	Здесь все цветы красные. Некоторые герани — красного цвета. Следо-
вательно, среди этих цветов есть несколько гераней.
30)	Никто из студентов не пишет учебники. Некоторые студенты пишут
стихи. Следовательно, ни один учебник не написан в стихах.
55
12. ТЕОРИЯ АЛГОРИТМОВ
Упражнения
Построить машину Тьюринга и нормальный алгоритм Маркова.
1)	Построить алгоритм, распознающий свойство слов в алфавите А={а, Ь}
быть палиндромом. Пример: aba, аа, baab— палиндромы, abb, ba — не
палиндромы.
2)	Построить алгоритм, вычисляющий предикат Р(х,у) = Т, если х > у, и
Р(х,у) = если Х^У< в алфавите А={1, 0, *}, где х и у — двоичные числа с
одинаковым количеством разрядов.
3)	Построить алгоритм, вычисляющий предикат Р(х,у) = Т, если х > у, и
Р(х,у) = F, если х< у, в алфавите А={1, 0, *}, где х и у — двоичные числа с
разным количеством разрядов.
4)	Построить алгоритм, вычисляющий предикат Р(х,у) = Т, если х > у, и
Р(х,у) = F, если х < у, в алфавите А={ 1, 0, *}, где х и у — двоичные числа с
разным количеством разрядов.
5)	Построить алгоритм, подсчитывающий количество вхождений буквы
а в слово Wв алфавите А={а, Ь, *, |}. Пример: исходная конфигурация: baabaa,
конечная: baabaa*\\\\.
6)	Построить алгоритм вычисления функции f(x) = х/1 (с остатком) в
алфавите А = {|, *, =}. Пример. Исходная конфигурация: ||||, конечная: ||;
исходная конфигурация: |||||, конечная: ||*|;
7)	Построить алгоритм вычисления функции/(х) = Зх в алфавите А = {|, *}.
8)	Построить алгоритм вычисления дизъюнкции двух двоичных чисел с
одинаковым числом рарядов f(x,y) = х v у в алфавите А={1,0, v, =}. Пример.
Исходная конфигурация: 10011 v 11010, конечная: 10011 v 11010= 11011.
9)	Построить алгоритм вычисления конъюнкции двух двоичных чисел с
одинаковым числом рарядов f(x,y) = х & у в алфавите А={ 1,0, &, =}. Пример.
Исходная конфигурация: 10011 v 11010, конечная: 10011 v 11010 = 10010.
10)	Построить алгоритм вычисления функции сложения f(x,y) = х + у двух
двоичных чисел в алфавите А = {1,0,+}. Пример. Исходная конфигурация:
10011 + 1101,конечная: 100000.
11)	Построить алгоритм вычисления функции/(х) = х/2 (с остатком) для
двоичных чисел в алфавите А = {1, 0, *}. Результат должен иметь вид:
<х/2>*<остаток>. Пример. Исходная конфигурация: 1001, конечная: 100*1.
12)	Построить алгоритм вычисления функции/(нд) = пх в алфавите А={|,
*, =}. Пример. Исходная конфигурация: ||*|||, конечная: ||*||Н|||||.
13)	Построить алгоритм получения остатка от деления х/у для про-
извольных чисел х, у в алфавите А={|, /, =}. Пример. Исходная конфигурация:
ПИНИИ. конечная: |||||||/|||=||; исходная конфигурация: |||/|||||, конечная: ИИИ1НИ-
56
14)	Построить алгоритм для вычисления функции f(x,y) = х®у (сложения
по модулю два) в алфавите А={1,0, ®, =}. Пример. Исходная конфигурация:
10011 © 11010, конечная: 10011 © 11010 = 01001.
15)	Построить алгоритм сортировки слова в алфавите А=(а, Ь}. Пример.
Исходная конфигурация: baaabbbaba, конечная: aaaaabbbbb.
16)	Построить алгоритм вычисления функции модуля разности /(х,у) =
- mod(x - у) в алфавите А={|, -, =}. Пример. Исходная конфигурация: |||||||-|||,
конечная: ||||||Н|Ц||; исходная конфигурация: |||-|||||, конечная: |||-||Ц|.
17)	Построить алгоритм вычисления функции вычитания f(x,y) =х-у в
двоичной системе счисления в алфавите А={1, 0,	=}. Пример. Исходная
конфигурация: 111 - 101, конечная: 111 - 101 = 010.
18)	Построить алгоритм, подсчитывающий количество букв в исходном слове
в алфавите А={а, Ь, |, *}. Пример. Исходная конфигурация: abb, конечная: abb*|||.
19)	Построить алгоритм циклического сдвига на один символ вправо слова в
алфавите А={а, Ь, *}. Пример. Исходная конфигурация: abb, конечная: abb*bab.
20)	Построить алгоритм циклического сдвига на один символ влево слова в
алфавите А={а, Ь, *}. Пример. Исходная конфигурация: abb, конечная: abb*bba.
21)	Построить алгоритм, осуществляющий замену первого вхождения
подслова Р на подслово Q в слове IVв алфавите А={с, Ь, *}. Пример. Исходная
конфигурация:bab*aba*abbabaa, конечная: bab*aba*ababaaa.
22)	Построить алгоритм упорядочения слова в алфавите А = {а, Ь, с}.
Пример. Исходная конфигурация: bacbcab, конечная: aabbbcc.
23)	Построить алгоритм копирования слова в алфавите А = {а, Ь, с, *}.
Пример. Исходная конфигурация: bacbcab, конечная: bacbcab* bacbcab.
24)	Построить алгоритм, подсчитывающий количество вхождений подслова
Р в слове W в алфавите А = {а, Ь, *, |, =}. Исходная конфигурация: P*W. Пример.
Исходная конфигурация: ab*abbabaa, конечная: ab*abbabaa= ||.
25)	Построить алгоритм обращения слова в алфавите А = {а, Ь, *}. Пример.
Исходная конфигурация: abbab, конечная: abbab*babba.
26)	Построить алгоритм вычисления функции f(x,y) = х — у чисел в
алфавите А={|, - , =}. Пример. Исходная конфигурация: ||||||-||||, конечная: ||||||-
||||=||; исходная конфигурация: |||-|||||, конечная: |||-|||||=Л (пустой символ).
27)	Построить алгоритм циклического сдвига вправо двоичного числа W
на заданное число разрядовр в алфавите А={1,0, |, *}. Исходная конфигурация:
Р* Ж Пример. Исходная конфигурация: |||* 11010, конечная: 10110.
28)	Построить алгоритм циклического сдвига вправо двоичного числа IV
на заданное число разрядов Р в алфавите А={ 1,0, *}. Исходная конфигурация:
P*W. Пример. Исходная конфитурация: |||* 11010, конечная: 10100.
29)	Построить алгоритм определения максимума из двух чисел в двоичной
системе счисления в алфавите А={1,0, *}.
57
ОТВЕТЫ
1.3. 1)ЛиВ; 2)ЛиВ; 3)ЛиО; 4) Л; 5) 0;	6)ЛиВ;	11)Л; 7)Ли(ВпС);	12)Лг>В; 8)(ЛиВ)л(Си£)); 13)0; 9) Л;	14) U; 10) (А г> В) u (С r> D); 15) [7.
2.2.	1) эквивалентность; 2)	не эквивалентность; 3)	не эквивалентность; 4)	не эквивалентность; 5)	эквивалентность; 6)	не эквивалентность; 7)	эквивалентность;	8)	не эквивалентность; 15) эквивалентность; 9)	не эквивалентность; 16) эквивалентность; 10)	не эквивалентность; 17) эквивалентность; 11)	не эквивалентность; 18) эквивалентность; 12)	эквивалентность; 19) эквивалентность; 13)	не эквивалентность; 20) эквивалентность. 14)	не эквивалентность;
3.1. 1) отображение; 2) отображение; 3)инъекция; 4)биекция; 5) отображение; 6)биекция; 7)биекция; 8)биекция;	16)	отображение; 17)	частичная функция, отображение; 18)	сюръекция; 19)биекция; 20)	отображение; 21)	частичная функция, отображение; 22)отображение; 23)	отображение;
9) частичная функция, биекция; 24) частичная функция, сюръекция;
10)	отображение; 11)	отображение; 12)	отображение; 13)	отображение; 14)	отображение;	25)	отображение; 26)	отображение; 27)	отображение; 28)	отображение; 29)	частичная функция, отображение;
15) частичная функция, отображение; 30) частичная функция, отображение.
3.2. 1) отображение; 2)	отображение; 3)	отображение; 4)	сюръекция; 5)	отображение;	6)	отображение;	11) сюръекция; 7)	отображение;	12) сюръекция; 8)	сюръекция;	13) биекция; 9)	отображение;	14)	отображение; 10)	сюръекция;	15) отображение.
4.1. 1) Отношение не строгого частичного порядка.
2)	Отношение не строгого частичного порядка.
58
3)	Отношение не строгого частичного порядка.
4)	Отношение не строгого частичного порядка.
5)	Отношение строгого частичного порядка.
6)	Не является отношением порядка.
7)	Отношение строгого частичного порядка.
8)	Отношение не строгого частичного порядка.
9)	Отношение квазипорядка.
10)	Отношение строгого частичного порядка.
11)	Отношение не строгого линейного порядка.
12)	Отношение не строгого линейного порядка.
13)	Отношение квазипорядка.
14)	Отношение строгого частичного порядка.
15)	Отношение строгого частичного порядка.
16)	Отношение не строгого линейного порядка.
17)	Отношение строгого частичного порядка.
18)	Отношение квазипорядка.
19)	Отношение квазипорядка.
4.2.	1) изотонно;
2)	не изотонно;
3)	изотонно;
4)	изотонно;
5)	изоморфизм;
6)	изоморфизм;
7)	изоморфизм;
8)	дуальный изоморфизм;
9)	изоморфизм;
10)	изотонно;
И) автоморфизм;
12)	изотонно;
13)	дуальный изоморфизм;
14)	не изотонно;
15)антитонно.
5.1. 1) модулярная, недистрибутивная, с дополнениями, с относительными
дополнениями, не булева;
2)	модулярная, дистрибутивная, без дополнений, не булева;
3)	модулярная, дистрибутивная, без дополнений, не булева;
4)	немодулярная, недистрибутивная, без дополнений, не булева;
5)	немодулярная, недистрибутивная, без дополнений, не булева;
6)	немодулярная, недистрибутивная, с дополнениями, не булева;
7)	немодулярная, недистрибутивная, с дополнениями, не булева;
8)	модулярная, дистрибутивная, с дополнениями, булева;
9)	немодулярная, недистрибутивная, с дополнениями, не булева;
10)	модулярная, дистрибутивная, без дополнений, не булева;
И)	немодулярная, недистрибутивная, без дополнений, не булева;
12)	немодулярная, недистрибутивная, с дополнениями, не булева;
13)	немодулярная, недистрибутивная, с дополнениями, не булева;
14)	немодулярная, недистрибутивная, с дополнениями, не булева;
59
15)	модулярная, дистрибутивная, без дополнений, не булева.
5.2.	1) v - гомоморфизм;
2)	изоморфизм;
3)	мономорфизм;
4)	v - гомоморфизм;
5)	изоморфизм;
6)	не гомоморфизм;
7)	v - гомоморфизм;
8)	автоморфизм;
9)	v - гомоморфизм;
10)	v - гомоморфизм;
11)	не гомоморфизм;
12)	автоморфизм;
13)	не гомоморфизм;
14)	v - гомоморфизм;
15)	не гомоморфизм.
7.2. 1) не сохраняет 0, не сохраняет 1, несамодвойственна, немонотонна,
нелинейна;
2)	не сохраняет 0, не сохраняет 1, несамодвойственна, немонотонна,
нелинейна;
3)	сохраняет 0, сохраняет 1, несамодвойственна, монотонна, нелинейна;
4)	не сохраняет 0, сохраняет 1, несамодвойственна, немонотонна, нелинейна;
5)	сохраняет 0, сохраняет 1, несамодвойственна, немонотонна, нелинейна;
6)	сохраняет 0, сохраняет 1, самодвойственна, немонотонна, линейна;
7)	не сохраняет 0, сохраняет 1, несамодвойственна, немонотонна, нелинейна;
8)	не сохраняет 0, сохраняет 1, несамодвойственна, немонотонна,
нелинейна;
9)	сохраняет 0, сохраняет 1, несамодвойственна, монотонна, нелинейна;
10)	сохраняет 0, сохраняет 1, несамодвойственна, монотонна, нелинейна;
11)	сохраняет 0, сохраняет 1, самодвойственна, монотонна, линейна;
12)	сохраняет 0, сохраняет 1, несамодвойственна, монотонна, нелинейна;
13)	не сохраняет 0, сохраняет 1, несамодвойственна, немонотонна,
нелинейна;
14)	сохраняет 0, сохраняет 1, самодвойственна, монотонна, линейна;
15)	не сохраняет 0, сохраняет 1, несамодвойственна, монотонна, линейна.
7.3. 1) Система функций полна.
2)	Система функций полна.
3)	Система функций не полна.
4)	Система функций полна.
5)	Система функций полна.
6)	Система функций полна.
7)	Система функций полна.
8)	Система функций не полна.
9)	Система функций не полна.
10)	Система функций не полна.
11)	Система функций не полна.
12)	Система функций полна.
13)	Система функций полна.
14)	Система функций полна.
15)	Система функций полна.
8.1. 1) тавтология;
2)тавтология;
3)тавтология;
10)тавтология;
11)тавтология;
12)тавтология;
19)тавтология;
20) тавтология;
21)тавтология;
60
4) не тавтология;
5)тавтология;
6)тавтология;
7)тавтология;
8) тавтология;
9)тавтология;
13)тавтология;
14) не тавтология;
15)тавтология;
16)	тавтология;
17)	не тавтология;
18)	тавтология;
22) тавтология;
23) тавтология;
24)тавтология;
25) не тавтология.
10.3. 1) не логически общезначима;
2)	логически общезначима;
3)	не логически общезначима;
4)	логически общезначима;
5)	логически общезначима;
6)	логически общезначима;
7)	не логически общезначима;
8)	не логически общезначима;
9)	не логически общезначима;
10)	не логически общезначима;
11)	не логически общезначима;
12)	не логически общезначима;
13)	не логически общезначима;
14)	логически общезначима;
15)	не логически общезначима;
16)	логически общезначима;
17)	логически общезначима;
18)	логически общезначима;
19)	логически общезначима;
20)	не логически общезначима;
21)	логически общезначима;
22)	не логически общезначима.
23)	логически общезначима;
24)	не логически общезначима;
25)	логически общезначима.
61
ЛИТЕРАТУРА
1.	Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математи-
ке.— М : Наука, 1977.
2.	Гиндикин С. Г. Алгебра логики в задачах,— М.: Наука, 1972.
3.	Горбатов В. А. Основы дискретной математики: Учеб, пособие для
студентов вузов.— М.: Высшая школа, 1986.
4.	Гохман А. В., Спивак М. А., Розен В. В. и др. Сборник задач по математиче-
ской логике и алгебре множеств.— Саратов, 1969.
5.	Жеребкш В. С. Лопка.: [Пщруч. для юрид. вуз!в i фак.].— Харьков: Основа,
1995.
6.	Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для
инженера,— М.: Энергоатомиздат, 1988.
7.	Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математиче-
ской логике и теории алгоритмов,— М.: Наука, 1975.
8.	Луцький Г. М., Кривий С. Л., Печурш М. К. Основи дискретно! матема-
тики: Навч. поНбник,— К.: 1СДО, 1995.
9.	Мендельсон Э. Введение в математическую логику,— М.: Наука, 1976.
10.	Методичш вказ!вки до практичних занять з математично! лопки для сту-
денпв спещал ьносп «Математика»/Укладачг В. Н. Свладенко, С. Д. Па-
ращук.— Юровоград: КДП1,1990.
11.	Нефедов В. Н., Осипова В. А. Курс дискретной математики,— М.: МАИ,
1992.
12.	Новиков П. С. Элементы математической логики,— М.: Физматгиз, 1959.
13.	Оре О. Теория графов,— М.: Наука, 1968.
14.	Робертс Ф. С. Дискретные математические модели с приложениями к со-
циальным, биологическим и экологическим задачам,— М.: Наука, 1986.
15.	Столл Р. Множество, логика, аксиоматические теории,— М.: Просвеще-
ние, 1968.
16.	Таран Т. А. Основы дискретной математики: Учебное пособие - К.:
Просвпа, 1998.
17.	Харари Ф. Теория графов,— М.: Мир, 1973.
18.	Хаусдорф Ф. Теория множеств,— М.: Мир, 1973.
19.	Хромой Я.В. Математична лопка,— К.: Вища школа, 1981.
20.	Чень Ч., Ли Р. Математическая логика и автоматическое доказательство
теорем,— М.: Наука, 1983.
21.	Черч А. Введение в математическую логику. - М.: ИЛ. т.1.1961.
22.	Яблонский С. В. Введение в дискретную математику,— М.: Наука, 1979.
62
СОДЕРЖАНИЕ
Введение.................................................3
1.	Множества................................................4
2.	Теория отношений.........................................7
3.	Отображения. Функции....................................12
4.	Отношение порядка...................................... 15
5.	Решетки.................................................19
6.	Графы...................................................22
7.	Булева алгебра..........................................30
8.	Алгебра высказываний....................................36
9.	Формальные теории...................................... 40
10.	Теория предикатов первого порядка.......................42
11.	Автоматическое доказательство теорем....................48
12.	Теория алгоритмов.......................................56
Ответы..................................................58
Литература..............................................62
63
Навчальне видання
Таран Тетяна Архишвна, д-р техн, наук, проф.
Миценко Натгиия Анатолпвна
Темшкова Олена Леониивна
Зб1рник задач з дискретно! математики
2-ге видання, перероблене i доповнене
Рос1йською мовою
В авторсъкш редакци
Комп’ютерна верстка i орипнал-макет М. €. Шгурнов
Подписано до друку 19.09.2005. Формат 60x90/16. Гарштура Petersburg.
Ум. друк. арк. 4,00. Обл.-вид. арк. 1,68.
ПГО УС1 «1нрес»
Свщоцтво про внесения суб’екта видавничо! справи до Державного реестру
видавщв, вигопвниюв i розповсюджувач!в видавничо! продукт!
ДК № 2225 вщ 25.06.2005 р.
03067, Ки!‘в-67, вул. Машинобуд!вна, 36
тел. (044) 458-04-46, факс 458-04-29, e-mail: office@axiom.net.ua
e/W J/.