Автор: Темникова Е. Л Таран Т.А. Мыценко Н.А.
Теги: физико-математические науки математика
Год: 2005
Текст
Т. А. Таран
Н. А. Мыценко
Е. л. Темникова
@Ш@[рШШШ
Щ
Ш@
m
Ш
<>
1
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ
.КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ.
Кафедра прикладной математики
Т. А. Таран, Н. А. Мьщенко, Е. Л. Темникова
СБОРНИК ЗАДАЧ
ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
2
e издание,
переработанное и дополненное
Утверждено на заседании кафедры nрик.ладной математики
нтуу -«КПИ» (протокол М 1 от 29.08.2005)
Киев
Инрес
2005
ББК 22.t76я73
Т19
Рецензенты:
А. А. Павлов, д
p техн. наук, проф.;
И. И. Коваленко, д
p техн. наук, проф.
Таран Т. А.
Т19 Сборник задач по дискретной математике/Т. А. Таран, Н. А. Mы
ценко, Е. Л. Темникова.
2
e изд., перераб. и доп.
К: Инрес,
2005.
64 с.
Библиоrр.: с. 62.
Сборник составлен для проведения практических и самостоя
тельных занятий по дискретной математике.
Для студентов очной и заочной форм обучения специальности
.Прикладная математика
.
@ Т. А. Таран, Н. А. Мьщенко, Е. Л, Темникова, 2005
ВВЕДЕНИЕ
Методические указания содержат задания для самостоятельноЙ работы
по дисциплине .Дискретная математика.. Задания охватывают следующие
темы.
. Тема 1. Теория множеств. Алrебра множеств.
. Тема 2. Теория отношениЙ. Свойства бинарных отношений. Отношение
эквивалентности. Классы эквивалентности. Фактор множество.
. Тема 3. Отображения и функuии. Типы отображений: биекuия, сюръекция,
инъекция. Композиция отображений.
. Тема 4. Отношение порядка. Строrий, линейный, частичный порядок.
Диаrраммы Хассе.
. Тема 5. Решетки и их своЙства: модулярность, дистрибутивность.
Отображения на частично упорядоченных множествах; изотонность,
rомоморфизмы.
. Тема 6. Исследование rрафов. Матричные МtТОДЫ исследования rрафов.
Исследование типов связности орrрафов. Компоненты сильной связности.
Конденсация орrpафа. Вершинные базы.
. Тема 7. Булеваалrебра. Булевы формулы. Совершенные дизъюнктивная и
конъюнктивная нормальные формы. Полином Жеrалкина. Функциональ
но замкнутые классы булевых функций. Исследование систем булевых
функций на полноту.
. Тема 8. Алrебра высказываний. Тавтолоrии. Лоrическое следование в
алrебре высказываний.
. Тема 9. Формальные теории. Исчисление высказываний. Доказательство
и вывод в формальных теориях.
. Тема 10. Теория предикатов первоro порядка. Выполнимость и интерпрета
ция формул лоrики предикатов. Лоrически общезначимые формулы.
. Тема 11. Лоrическое следование в лоrике предикатов. Метод резолюций
доказательства лоrическоrо следования.
Каждой теме соответствует rлава в сборнике задач. Перед заданиями
при водится пример, показывающий, как нужно выполнять и оформлять
данное задание. Каждое задание содержит несколько вариантов.
11
3
1. МНОЖЕСТВА
Упражнения
1.1. Пусть U
множество точек плоскости на которой задана декартова
система координат. НаЙти пересечение множеств А f1 В, объединение
А u В, разности множеств А\В, В\А, дополнения множеств А', В',
изобразить их на плоскости:
Прu.мер. А
{<х, y>ly 5.r}, В
{<x,y>ly > е'}.
По определению:
1. А u В
{<x,y>ly5.r или у > е'};
2. А f1 В
{<x,y>ly5.r и у> е'};
3. А\В
{<x,y>ly 5.r, у5. е'};
4. В\А
{<х, у>1 у > е', У > r};
5. А'
{<х, у>1 у> r};
6. В'
{<х, у>1 у 5. е'}.
1 у
,
\" х
1
4
х
2
х
1r
5
Задания.
1) А
{<х, y>1 о 5.х5. 1}, В
{<x,y>1 О 5. У 5. 1};
2) А
{<x,y>ly 5. 2х+5}, В
{<x,y>ly > 0.sx
4};
3) А
{<х, y>1 х2+у2:5: 4}, В
{<х, y>11 5. У 5. 2, 15. х 5. 5};
4
3
r
'"
6
II
I
l
4) А
{<х, y>1 (x
2)2 + (y
3)25. 4}, В
{<х, y>12 5.у 5. 6, 1 5.х 5. 7};
5) А
{<х, y>1 (x
3)2 + (y
3)2 5. 9}, В
{<х, y>1 у 5. х};
6) А
{<х, у>1 lцl 5.4, 15.х5. 5}, В
{<х, y>1 у
x};
7) А
{<х, y>1 у
е'}, В
{<х, y>1 х2 + у2 5. 9};
8) А
{<х, y>ly
x2}, В
{<x,y>1
3 5.у 5. 5,
7 5.х5. 1};
9) А
{<х, y>1 х2 + у2 5. 4}, В
{<х, y>1 (x
2)2 + у2 > 9};
10) А
{<х, y>1
3 5.у < 2}, В
{<х, y>1 (х+2)2 + (y
3)2 5. 4};
11) А
{<х, y>1 у 5. e
P2}, В
{<х, y>1
4 5. у 5. 5, 35. х 5. 6};
12) А
{<х, у>1 у
2x2
3}, В
{<х, y>1 х2 + (y
1)2 5. 1};
13) А
{<х, у>1 (X
5)2 + (y
7)2 < 25}, В
{<х, y>1 (x
7)2 + (y
5)2 5. 25};
14) А
{<х, у>1
115. 4}, В
{<х, y>1 (x
4)2 + (y
10)25. 9};
15) А
{<х, y>1 у
х2, х
О}, В
{<х, у>1 х2 + у2 5. 9}.
1.2. Доказать тождества, используя основные теоремы и аксиомы алrебры
множеств ('
дополнение множества).
Пример. (А\В) f1 «А u В)\(А f1 В»
А\В.
Доказаmел.ъс',пво.
(А\В) f1 «А u В)\(А f1 В»
(А f1 В') f1 «А u В) f1 (А f1 В)')
(А f1 В') f1 (А u В) f1 (А' u В')
А f1 В' f1 (А u В) f1 (А' u В')
Aп (AuB) пВ' f1 (A'ug)
А f1 В'
A\B.
По определению: А\В
А f1 В'
Закон де MopraHa: (А f1 В)'
А' u В'
Ассоциативность f1
Коммутативность f1
Закон поrлощения: А f1 (А u В)
А
По определению: А f1 В'
А\В
Задания.
1) А u (В\С)
(А u В) f1 (А u С);
2) (А\В) u (А f1 В)
А;
3) (А u В)\(А f1 В)
(А\В) u (В\А);
4) (А\В) u (А,\В')
(А u В)\(А f1 В);
5) (А'\В') u (В,\А')
(А u В)\(А f1 В);
6) (А\В') u (А,\В)
(В uA') f1 (А u В');
7) А\(А\В)
А f1 В;
8) В u (А\В)
А u В;
9) (А\В) f1 С
(А f1 С)\В;
10) (А u B)\C
(А\С) u (В\С);
11) (А f1 B)\C
(А\С) f1 (В\С);
12) (А u В') f1 (А u С)
А u (В'\С);
13) (А,\В) u (А f1 В')
В';
14) (А f1 В)\(А u В)
0;
15) (А u В)\(А\В)
В.
5
1.3. Упростить следующие выражения алrебры множеств ( и
универсальное
множество ).
1) «А u В) n (А u u» u «А u В) п (В u 0»;
2) «А u В) п (В u u» u (А u 0);
3) А u (АпВ) u (АпВпС) u (АпВпСпD) u (ВnСпD) u (СпD) u D;
4) (А u В) п (А u В');
5) (А' п В' п С)' п (А' п В)' п (А' п С);
6) А u В u (С п (А u В' u С)');
7) (А\В) u (В\С) u (А п В п С);
8) (А п С) u (В п С) u (А п D) u (В n D);
9) (А u В) п (В u U) п (А u 0);
10) (А u С) п (В u С) п (А u D) n (В u D);
11) (А п В) u (А\В);
12) (А u В) п (А u В') п (А' u В);
13) «А u В') п (А' u С»\(В' u С);
14) «А\В) п (А' u В»,;
15) (А' u В' u С)' u (А' u В)' u (А' u С).
1.4. Доказать выполнимость соотношений теории множеств (символ <=>
означает «эквивалентно
, символ =:) означает «влечет
).
При.мер. А п В !;; С <=> А !;; В' u С.
Доказательство.
Докажем, что если А п В !;; С, то А !;; В' u С.
Для каждоrо а Е А либо а Е В, либо а Е В'. Если а Е В. то а Е А п В, а так
как А п В !;; С, то а Е С. Тоrда а Е В' u С. Если а
В, то а Е В'. Тоrда
а Е В' u С. Следовательно, каждый элемент а Е А принадлежит и В' u С, Т.е.
А !;; В' u С.
с
Докажем теперь, что если А !;; В' u С, то А п В !;; С.
Пусть каждый элемент а Е А принадлежит также В' u С. Тоrда или а Е
В', или а Е С. Если каждый элемент а Е В', то а
В, и А п В
0, а так как
6
o включено в любое множество, то 0 !;; С, следовательно, А n В !;; С. Если
а
В', то а Е С и некоторые а Е В. Тоrда А n В ":1; 0, и, если а Е В, то а Е С,
следовательно, А п В !;; С.
\
Задания.
1) А u В!;; С<=> А!;; С и В!;; С;
2) А !;; В п С <=> А !;; В и А !;; С;
3)А!;; В u С<=>А\В!;; С;
4) (А\В) u В
А <=> В !;;А;
5) (А п В) u С
А п (В u С) <=> С!;; А;
6) А!;; В =:) А u С!;; В u С;
7) А !;; В =:) А п С!;; В n С;
8) А !;; В =:) (А\С) !;; (Е\С);
9) А
В =:) (С\В)!;; (С\А);
10) А !;; В =:) В' !;; А';
11) А u В
А п В =:) А
В;
12) А/В
А <=> В'!;;А (rде A/B
A u В', Т.е. A/B
{.xjXE А ИЛИХ
В});
13) А/В
u <=> В!;; А;
14) А
В <=> (А\В) u (В\А)
0;
15) А
В' <=> А п В
0 и А u В
и.
2. ТЕОРИЯ ОТНОШЕНИЙ
Упражнения
2.1. Доказать выполнимость следующих соотношений.
При.мер. (А п В) х (С п D)
(А х с) п (В х D).
Доказательство.
Пусть А
{аl аЕА}, В
{bl ЬЕ В}, С
{CI СЕ С}, D
{dJ dE D}.
а) Рассмотрим (А п В)х( Сп D). Найдем множества А п В и Сп D. По
определению
А пВ
{а, Ь! аЕА, ЬЕВ иа
Ь}; СпD
{с, dJCE С, dED и C
d}.
Обозначим через Х все элементы а и Ь, которые удовлетворяют следующим
условиям: а
Ь, аЕ А и ЬЕ В, а через У
все элементы С и dтакие, что С
d, СЕ С
И dE D. Следовательно,
А п В
{.xjxEA и ХЕВ}; Сп D
{yIYE С И YED}.
По определению декартовоrо произведения множеств
(А п В)х( Сп D)
{.xj ХЕА и ХЕ В}х{ уl УЕ С и УЕ D}
{<X,y>IXEA и ХЕВ,УЕСИУЕD}. (1)
6) Рассмотрим выражение (А х с) п (В х D).
7
11
По определению декартовоro произведения множеств
А х С {al аЕА}х{сl СЕ с} {<а, c>1 аЕА, СЕ С};
В Х D {ы bEB}x{d] dED} {<Ь, d>1 ЬЕВ, dED}.
Тоrда (А х С) п (В х D) состоит из множества всех упорядоченных лар
<а. с> и <Ь, d> таких, что а Ь Х, с d у' Т.е.
(А х С) п (В х D) {<x,y>lxEA ИХЕВ,УЕ СИУЕD}. (2)
Из равенства правых частей соотношений (1) и (2) следует, что
(А п В) х (С п D) (А х С) п (В х D).
3адаиuя.
1) (А u В) х С (А х С) u (В х С);
2) (AxB)u(CxD)!;;(A u C)x(Bu D) (при какихА,В, СиD имеет место
равенство?);
3) А х (В u С) (А х В) u (А х С);
4) (А\В) х С (А х С)\(В х С);
5) (А uB) х (CuD) (А х С) u (Вх С) u (А xD) u (BxD);
6) А х (Е\С) (А х В)\(А х С);
7) А х В (А х D) п (С хВ), [де А!;;С и B!;;D;
8) и\(А х В) [(ll\A) х U] u [их (ll\B)];
9) (А п В) х С (А х С) п (В х С);
10) (А х В) u (Сх В) (А u С) х В.
2.2. Для бинарных отношений определить, какими свойствами они обладают.
Для отношений эквивалентности найти классы эквивалентности и
фактор множества [Х/р].
Прu.мер 1. Пусть отношение определено на множестве Z:xpy (:::) Х == у (тod 3).
Это отношение сравнимости по модулю 3, которое означает, что разность X
у делится на 3 без остатка. Будем обозначать это так: хру (:::)(x y)/3 k Е Z.
Решение. Выясним, какими свойствами обладает это отношение. Пусть
х,УЕ Z.
1. Рефлексивность: хрх (:::) (х х)/з о/з о. Отношение рефлексивно.
2. Симметричность: хру =:) урх, Т.е. если хру, то урх.
Пусть (x y)/3 k EZ. Тоrда урх (:::) (y x)/3 (x y)/3 k Е Z.
Следовательно, условие симметричности выполняется.
3. Транзитивность: хру и ypz =:) xpz.
Пусть (x y)/3 k, EZ, T.e.X y 3k l , и (y z)/3 k2EZ, T.e.y z 3k2' Решим
эту систему уравнений, сложив их: x y+y z 3(k l +k 2 ), Т.е. x z 3(k l +k2) 3k з ,
k з Е Z. Условие транзитивности выполняется. Отношениех==у (тod3) являет
ся отношением эквивалентности. Найдем ero фактор множество [Z/p].
8
11
Произвольное число Х можно записать в виде 3q+r, О 5. r < 3, [де q частное,
r остаток от деления числа Х на 3. В один и тот же класс эквивалентности
попадут все числа, дающие при делении на 3 одинаковое число r в остатке.
Мы получим три класса эквивалентности: [О] {О, 3, 6, 9,12, ...}; [1] {1, 4, 7,
10, 13, ...}; [2] {2, 5, 8, 11, 14, ...}.
КаждыЙ класс можно охарактеризовать одним представителем этоrо
класса, и в данном случае таким представителем удобнее Bcero выбрать
остаток У. Следовательно, фактор множество отнощения Х== у (тod 3) будет
[Z/p] {[O], [1], [2]}.
Указание. Пусть для данноro отнощения задано некоторое подмножество
Х множества целых чисел: Х { 3, 6, 9, 1,2,4,5,7, 10}: хру (:::) (х у)/3 k,
k Е Z. Построим матрицу отношения р на этом множестве.
х 3 6 9 1 2 4 5 7 10
3 1 1 1 О О О О О О
6 1 1 1 О О О О О О
9 1 1 1 О О О О О О
1 О О О 1 О 1 О 1 1
2 О О О О 1 О 1 О О
4 О О О 1 О 1 О 1 1
5 О О О О 1 О 1 О О.
7 О О О 1 О 1 О 1 1
10 О О О 1 О 1 О 1 1
По матрице отношениЙ можно еще раз проверить свойства отношения.
Диаrональные элементы матрицы равны 1; это rоворит о том, что отношение
рефлексивно. Матрица симметрична относительно rлавной диаrонали,
следовательно, отношение симметрично. Транзитивность также можно
проверить по матрице отношения. Если для всех пар <х,у>, <у, z> выполняется
также <х, z>, то отнощение транзитивно. Например. на пересечении строки и
столбца <1,4> стоит 1, и на пересечении <4,7> стоит 1; проверим пересечение
строки и столбца < 1, 7>: здесь тоже стоит 1. Следовательно, для этих пар свойство
транзитивности выполняется. Для проверки транзитивности отношения нужно
рассмотреть все пары <х, у>, <у, z> и <х, z>.
Построим rpаф отношения. Элементы заданноrо множества являются Bep
шинами rpафа. Матрица отношения определяет, какие вершины rpафа связа
ны друr с друrом (это матрица смежности rpафа). По первой строке матрицы
находим, что вершина 3 связана сама с собой и с вершинами 6 9.
Соединяем эти вершины дуrами (на рисунке петли, соединяющие верщины
9
сами с собоЙ, можно опускать). Элемент 6 также связан с элементами 3 и
9, поэтому проведем дуrу из вершины 6 в вершину 9. Третья строка
матрицы указывает, что элемент 9 связан с 3 и 6. Элементы 3, 6, 9 не
связаны больше ни с какими друrими верщинами, Т.е. они образуют один класс
эквивалентности. Аналоrично построим все остальные связи между
вершинами. В результате получим несвязный неориентированный rраф (см.
рисунок), который состоит из трех связных компонент; каждая из них
соответствует одному классу эквивалентности.
4 V9 2
3 /
5
Fраф отношения х == у (тod З).
Таким образом. классы эквивалентности на заданном множестве: { 3, 6,
9}, {2, 5}, {1, 4, 7, 10}. Внутри каждоrо класса любые два элемента находятся
в отношении х == у (тod 3) друr к друry: разность между ними делится на 3
без остатка. Между элементами различных классов это отношение не
выполняется. Каждый класс эквивалентности характеризуется остатком от
деления разности х у на 3: в классе эквивалентности { 3, 6, 9} остаток
равен О, в классе {2, 5} остаток равен 2. в классе {1, 4, 7, 10} остаток равен 1.
Фактор множество [Х/р] {[О], [1], [2]}. .
Прu.мер 2. Отнощение определено на множестве R: хру (:::) х у Е Z.
Решение. Пусть х, у Е R. Определим свойства отношения.
1) Рефлексивность: х х О Е Z. Отнощение рефлексивно.
2) Симметричность: если х у k Е Z, то У х (x у) k Е Z.
Отношение симметрично.
3) Транзитивность: если х у kt Е Z И У z k 2 Е Z, то (х у)+(у z)
x y+y z x z k. + k 2 k з Е Z. Отношение транзитивно.
Данное отношение является отношением эквивалентности.
Найдем ero фактор множество. Разность двух действительных чисел
будет равна целому числу только тоrда, коrда их дробные части будут
одинаковы. Следовательно, в один класс эквивалентности попадают все
действительные числа, имеющие одинаковые дробные части. Например, [О]
10
I I
{о; 1; 2; 3; ...}, [0,01] {О,01; 1.01; 2.01; 3.01; ...}, [0,12] {0,12; 1,12; 2,12; ...},
и т. д. Фактор множество [Х/ р] [о; 1).
Задания.
1) Отношение определено на множестве NxN: <a.b>p<c.d> (:::) [( ad Ьс и
Ь:/:.О, и d:/:.O) или (а с. Ь О, d О)];
2) Отношение определено на множестве z: хру (:::)х5.у+1;
3) Отношение определено на множестве N: хру (:::) НОД(х,у):/:. 1;
4) Отношение определено на множестве R: хру (:::) у и
5) Отношение определено на множестве z: хру (:::) (х 2 у2)/5;
6) Отношение определено на множестве N: хру (:::) х/у (х делится на у);
7) Отношение определено на множестве R: хру (:::) 2yl Е N;
8) Отношение определено на множестве z: хру (:::) 2х 3у;
9) Отношение определено на множестве N: хру (:::) +51 13 yl;
1 О) Отношение определено на множестве R: хру (:::) ху > 1;
11) Отношение определено на множестве z: хру (:::) 30/(х у);
12) Отношение определено на множестве N: хру (:::) (х у)/т, т>О;
13) Отношение определено на множестве z: хру (:::) 3/(х + у);
14) Отношение определено на множестве N: хру (:::) НОД(х,у) х;
15) Отношение определено на множестве R: хру (:::) х у k Е Z;
16) Отношение определено на множестве NxN:
<a,b>p<c,d> (:::) (1 + d Ь + с; .
17) Отношение определено на множестве {5. 7, 9,10,13,15.18, 19, 20}:
хру (:::) yl/5;
18) Отношение определено на множестве {5, 8,9, 12, 13. 16, 18, 19, 20}:
хру (:::) yl/4;
19) Отношение определено на множестве {7, 9,10,14,15, 18,19, 21}:
хру (:::) yl/7;
20) Отношение определено на множестве {6, 9, 10, 12, 15, 18, 19, 20}:
хру (:::) yl/6;
21) Отношение определено на множестве {2, 2.5, 3, 3.5, 5, 5.5, 8, 8.5}:
хру (:::) yl k Е N;
22) Отношение определено на множестве {1, 2, 3, 5, 6, 8}:
хру (:::) 90/ yl k Е N, х:/:. у;
23) Отношение определено на множестве {2, 3, 5, 7, 9, 10}:
хру (:::) 60/(х у) k Е Z, х:/:. у;
24) Отношение определено на множестве {1, 2, 3, 4, 5, 6, 7}:
хру (:::) 12х yl/3 k Е N.
25) Отношение определено на множестве {1, 2, 3, 4, 5, 6, 7, 8}:
хру (:::) 12х 3yl/ 4 k Е N.
11
3. ОТОБРАЖЕНИЯ. ФУНКЦИИ
УпраЖilСНИЯ
3.1. Для каждоrо из отображений найти область определения и область
значений, исследовать, является ли оно инъективным, сюръективным
или биективным.
Схема исследования фуюсции
1. Нахождение области определения Е и области значений F функции.
2. Нахождение точек пересечения rрафика с координатными осями.
3. Исследование функции на периодичность, четность инечетность.
4. Нахождение интервалов монотонности, экстремальных точек (у' (х) О).
5. Нахождение интервалов воrнутости и выпуклости кривой, которая
является rрафиком функции, точек переrиба (у"(х) О).
6. Построение rpафика функции.
7. Определение типа отображения.
(х + 1)3
Прu.мер. Исследовать функцию f(x) = (х li и построить ее rрафик.
1. Найдем область определения и область значений функции.
При х 1 функция не определена, следовательно, ее область определения:
E ( oo; 1) u (1; +00). Очевидно, область значениЙ F R.
Проверим, является ли отображение E F функцией. Очевидно, что данное
отображение каждому элементу ХЕ Е сопоставляет один и только один элемент
УЕ F, Т.е. отображение является функцией.
2. а) Найдем точки пересечения rрафика с осью Ох (/(х) О). ДЛЯ этоrо
решим уравнение
(х+l)3 =0
(х 1)2 .
Точка Х 1, у О является точкой пересечения rрафика с осью Ох.
6) Найдем точки пересечения rpафика с осью Оу: при Х О,/(х) 1.
3. а) Проверим данную функцию на четность инечетность.
л х)= ( x +1)3 (х 1)3
( x 1)2 (x+li'
Данная функция не является ни четной, ни нечетной.
(х +1)3
6) Функция Лх) = (х 1)2 непериодична.
12
11
, (x+li(x 5)
4.У== (x I)3 ;у' Оприх 1их 5.
w 24(x+l)
5 У= у" О
. (x I)4; прих 1.
х ( 00' 1) 1 ( 1; 1) 1 (1; 5) 5 (5; +00)
,
У ,.... О J не СУЩС 13.5 J
ствуст
у' + О + О +
у" О + + +
возрастаст, точка возрастаст, ВСрПI убывает, точка возрастаст.
выпуклая IIсрсrи6а BorllYTa калыlя BorнYTa МИlIимума BorHYTa
асимптота
f
(х + 1)3
Функция ЛХ)== 2 на области определения ( oo; 1) u (1; +00)
. (х 1)
является сюръекциеЙ. На интервале (1; 5) она убывает, на (5; +00) возрастает
и точка (5; 13,5) является точкой минимума, Т.е. существуют такие Х и х что
. .. \ 2'
/(Х\) /(Х 2 ) У.
у
5
х
Задания.
1) у х2 + 3х + 5;
16) У 3.х4 + 8,r 18х2 + 7;
х 2 +з
17) y== ;
х+l
2)y x2 x 1;
13
3) ")2X+4.
y ,
3х + х 3
18) у .
х 2 +1 '
4)y x7 +х+ 1;
19) y=X+ VX+8 ;
20) y=sin(.!..x+l0) 2sinx;
2
х 2 +8 1
21) y= + ;
x 1 5+х
. 2 3
22) у = sш х + cos '2 х ;
5) у logz(x2 + 4х + 5);
6)y 2.x5 1;
7) У 3 '" + х;
8) у х3 + 3х;
7
9)Y ;
х+2
23) У 19(cos 2х + 4);
4 3 2 1
24) У = 3х + 16х 18х + ;
х
10) У (х + sin x)Z;
25) у = sin(2x). cos ;
26) у = 6х 3 Vx +1 ;
11) У cos(x2 х);
2
12) У 2 3 10 ;
х + х+
27) У e2+cos x ;
13) У Isin.xj;
28) У cos(x + 3) + COS 3х;
14) У 19lxl + 21;
1
15) у = +x +2.
х '
29) У log,/2( 3x) х3;
1
30) У = 4 16 2 .
х х
1.
3.2. Построить композиции отображений gO f и f О g; проверить, являются ли
они инъективными, сюръективными или биективными.
При.мер. f: R R (:::) У х 1; g: R R (:::) У e2.r.
Композиция функций gl: R R (:::) У e2(x 1) не является сюръекцией, так
как нет ни одноrо элемента х Е R, дЛЯ KOToporo у О есть образ. Композиция
функций является инъекцией, так как каждый элемент у Е R есть образ толь о
одноrо элемента х Е R, либо вообще не имеет прообраза. Таким образом, g 1:
R R Е У e2(x 1) инъекция.
11
I
11
14
I I
Задания.
1)!: R R,y x2+ 5,g: R Z,y [х];
2)!: C Jr,y 2 + 12,g: R N,y [х 2 + 1];
3)!: R R,y 10g2(x2 + 3),g: R R, У x3 + 3х;
4)!: R R,y З х + ' ,g: R {0,1},у [х] тod2;
5)f: R R,y x3 + 5x,g: R R,y log2(x2 + 2);
6)f: C R+.y 12,g: R R,y е' З;
7)!: R Z,y 4[х] + 5,g: Z Z,y 4х+ 5;
8)f: Q Z,y [17x3],g: Z N,y + 1;
1
9)f: C R+,y 12+ 2 + 1,g:R R, У ;
е
10)!: R Z,y [х+ 13],g:Z N,y + 1;
11)!: N N,y x2 + 2,g: N {О, 1},у (х+ 7)2 тod2;
12)!: Q Q,y 11х+ 2,g: Q Z,y [х7 + 14] 2;
13)!: R R,y x3 + 3x,g: R С, у=Б+з;
14)j:N R, y=x 2 + Vx+2 ,g:R R,y e';
15) j: С R+, У 12, g: R R, У logz(x2 + 3).
4. ОТНОШЕНИЕ ПОРЯДКА
Упражнения
4.1. Для данных множеств и заданных на них отнощений определить:
· Является ли данное отношение отношением порядка? CTpororo порядка?
. Является ли данное множество, с заданным на нем отношением порядка,
цепью?
. Найти, [де это возможно, наименьший и наибольший элементы.
. Найти минимальный и максимальный элементы.
. Построить матрицу отношения, rpаф отношения или диаrрамму Хассе.
. Является ли данное множество решеткой?
При.мер. На множестве Х { 5, 3, 2, 0,1,2,4,5. 6} задано отношение р:
{ < lцl}.
Определим, какими свойствами обладает это отношение.
Отнощение не рефлексивно, так как не выполняется < .
Если l.xj < Iyl, то не выполняется Iyl < Ixl, следовательно, отношение
асимметрично.
Если < lцl и lцl < 1zI, то < Iz!, следовательно, отношение траНЗИТИВIIО.
Отсюда следует, что отношение < lцl является отношением cTpororo порядка.
15
Построим матрицу отношения
х\у 5 3 2 О 1 2 4 5 6
5 О О О О О О О О 1
3 1 О О О О О 1 1 1
2 1 1 О О О О 1 1 1
О 1 1 1 О 1 1 1 1 1
1 1 1 1 О О 1 1 1 1
2 1 1 О О О О 1 1 1
4 1 О О О О О О 1 1
5 О О О О О О О О 1
6 О О О О О О О О О
Множество Х { 5, 3, 2, 0,1,2,4,5, 6} с заданным на нем
6 отношением cтpororo порядка не является цепью, так как в нем
есть элементы, несравнимые по отношению р. Это элементы 2
и 2: 1 21 121. Так как 111 < 1 21 < 1 31 и 111 < 121 < 1 31, то inf{ 2, 2} 1,
sир{ 2, 2} 3. Лналоrично и для 5 и 5: 1 51 151, inf{ 5, 5} 4,
sup{ 5, 5} 6.
НамножеСlвеХ { 5, 3, 2,O,1,2,4, 5,6} элемент 6 является
наибольшим и максимальным, а О наименьшим и минималь
ным элементом. Данное множество является решеткой. Ero
диаrрамма Хассе представлена на рисунке.
I
11
Задания.
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) на множестве Х {1, 2, 5, 6, 7, 8, 9, 10, 13, 16} задано отношение
р: {(x)тod4«y)тod4};
6) на множестве Х {2, 3,4,5,6, 11, 12, 13} задано отношение
р: {х делится на у с остатком 1};
7) на множестве Х {{а}, {Ь}, {а, Ь}, {а, Ь, С}, {{а, Ь, С}}} задано отнощение р:
{хсу};
111
16
"
I
8) на множестве Х {88, 65, 55, 52, 39. 26, 13, 11} задано отношение
р: {х кратно у};
9) на множестве Х { 7, 6.2, 5, 4.3, 0.25, о, 0.5, 1,5.5, 10} задано
отношение р: {( x2+x+10) 5. ( y2+y+10)};
10) на множестве отрезков оси ОхХ {(о, 3), (0.5,3.5), (1, 2), (1, 3), (1.5, 2),
(2,3), (3, 3), (7, о), (7, 8)} задано отношение р; {длина отрезках> длины отрезка у};
11) на множестве Х {о, 1,2,3,4,5,6,8, 10, 120} задано отношение
р: {х2 + 9 5.у2 + 9};
12) на множестве Х { 5, 2.7, 1, 0.3, о, 0.2, 0.5, 2, 3, 4.2} задано отношение
р: { log I (х 2 + 0.1) 5. log I (у2 + 0.1) };
2 2
13) на множестве Х { п/2, п/3, п/12, о, п/24, п/12, п/6, п/3, п/2, 3п/2,
2п, 51t/2, 7п/2} задано отношение р: {siп х 5. siп у};
14) на множестве Х { 7. 5, 3, 2, 1, о, 1.3,4,9. 10,16, 18} задано
отношение р: {lg(x2 + 3) < 19 (у2 + 3)};
15) на множестве Х { п, п/2, п/3, п/6, п/12, О, п/24,п/12, п/6, п/2, 3п/
2, 2п, 5п/2} задано отношение р: {cos х > cos у};
16) намножествеХ { 7, 6, 5 3, 1,O, 2, 4, 8, 9,10, 15} задано отношение
5 5
р: { 5. 2iYi};
17) на множестве Х { 5, 4, 3, 2, 1, о, 2, 4, 6, 7, 8} задано отношение
1 1
р: {e X +lxl>e Y +IYI};
18) на множестве прямоуrольников Х {{о 5. х 5. 1,25. У 5. 3}, {о 5. х 5. 3,
1 5.у 5. 2}, {15.х5.3, 2 5.у 5.3}, {2 5.х5. 7, 2 5.у 5. 6}, {3 5.х5. 7,2 5.у5. 7}, {3 5.х5. 7,
5 5.у 5. 12}, {5 5.х5. 7, 75. У 5. 15}, {5 5.х5. 9,2 5.у 5. 6}, {6 5.х5. 9, 3 5.у 5. 15}} задано
отношение р: {площадь прямuуrольника а 5. площади прямоуrольника Ь};
19) намножествеХ { 1, 1/2, 0,1/2,1,2,3/2,3,4,5, 7} задано отношение
х У
p:{ 5. }.
х +5 У +5
4.2. На множествах А и В заданы отношения порядка р 1 и Р 2 соответственно
и задано отображениеf(а) Ьj' [де а ; Е А, Ь ; Е В. Определить, является ли
оно изотонным, изоморфизмом или автоморфизмом.
Прu.мер. А {1, 3, 4, 12, 24}, В {8, 10, 12, 15, 20}; f(a j ) b j ;
р 1: Vi 5.j {а, делитель а.}; р 2: Vi 5.j Ь, < Ь..
, } , }
Проверим, является ли отображение f: А В изотонным.
Найдем образы функцииf:А B.f(1) 8 b.,f(3) 10 b2,f(4) 12 Ь з ,
f(12) 15 Ь 4 , f(24) 20 b s . Множество А решетка, в которой можно
выделить две цепи. Для цепи 1 5. 3 5. 12 5. 24 отображение f сохраняет порядок,
17
20 так как 8 < 10 < 15 < 20, Т.е. f (1) 5.f(3) 5./(12) 5.f(24). Для
цепи 15. 45. 125. 24 отображениеf также сохраняет порядок,
15 так как 8 < 12 < 15 < 20, Т.е. f( 1) 5.f(4) 5.f( 12) 5.f(24). Следо
вательно, отображение изотонно. Однако, отображение не
12 является изоморфизмом, так как обратное отображение f не
сохраняет порядок: для значений f(3) 5.f(4) (105. 12) про
10 образы 3, 4 несравнимы.
Таким образом, отображение f изотонно, но не является
8 изоморфизмом.
11
Заданuя.
1) А
{2, 3, 6 ,12, 24}, В
{1, 2, 3, 5,6, 10,15, 30};/(2)
1;/(3)
1;/(6)
5;
f(12)
10;/(24)
30; р1
р2: {х делитель у};
2) А
{а о , аl' а 2 , аз}, в
{а о , a l , а 2 , аз}; f(a;)
а«/+2)тod4); р1
р2: Vi 5.j а/5. а.;
3)А
{1,3,4, 12, 24},B
{8,10, 11,19, 31};f(a)
Ь,;р1:Vi5.j{а,делитель aJ
р2: Vi 5.j Ь/ < b j ;
4) А
{6, 7,14.15, 35}, В
{О,
1, 1,2,3,4, 5}; f(a)
a;тod6; р1: Vi 5.j а/5. а};
р2: Vi 5.j Ib,1 < Ib);
5) А
{1, 3, 4, 12, 24}, В
{8, 10, 11, 19, 31}; f(a,}
Ь,; р1
р2: х < у;
6) А
{
2,
1, О, 1, 2}, Н
{2, 1, О,
1,
2}; f(a)
a;; р1: Vi 5.j а, 5. a j ;
р2: Vi 5.j Ь/ > Ь/;
7) А
{25, 20, 15, 10, 5}, В
{5, 4, 3, 2, 1}; f(a)
а/5; р1
р2: х
у;
8) А
{64, 8, 4, 2, 1}, В
{О, 81, 9, 3, 1}; f(a)
ЬН' i
О, 1, 2, 3, 4;
р1
р2: {х делится на у};
9) А
{2,
3, 4, 6,
7, 8}, В
{4, 9, 16,36,49, 64}; f(a;)
а 2 /; р1: Vi 5.j la.l5. la);
р2: Vi 5.j Ь/ 5. b j ;
10) А
{1, 2,3,4, 5}, В
{2, 4, 8, 16,32, 64}; f(a;)
20,; р1
р2: х < у;
11) А
{{1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}}, В
{{1}, {1, 2}, {1, 2, 3}, {1, 2, З, 4}};
f(a;)
Ь;; р1
р2: х
у;
12) А
{
n,
n/3,
n/6, О}, В
{
n/18,
n/9,
n/3,
n/2, О}; f(a)
а;/3;
р1: Vi 5.j cos(a)5.cos(a); р2: Vi 5.j Ь; 5. b j ;
13) А
{
n/3,
n/6, О, п/6, п/3}, в
{
n/3,
n/6, О, п/6, п/3}; f(a)
a;;
р1
р2: tgx5. tgy;
14) А
{О, п/4, п/2, 3п/4, п}, В
{О, 1/2, 1/ ,.J3 /2, 1}; f(a)
sin а/;
р1
р2: х5. у;
15) А
{О, 1/5, 1/4, 1/3, 1/2, 1}, В
{О, 6,15/2,10, 15,20, 30}; f(a/)
30а/;
р1: Vi 5.j а 2 . > а 2 ; р2: Vi 5.j Ь. 5. Ь.
'} , }
' I
11
18
5. РЕШЕТКИ
Упражнения
5.1. Для изображенных на рис. 5.1 решеток построить таблицы объединений
и пересечений; определить. какие из решеток модулярные (если решетка
немодулярна, выделить в ней подрещетку N
), дистрибутивные, с
дополнениями. с относительными дополнениями, булевы. Выделить
некоторые подрешетки заданной решетки; найти среди них выпуклые
подрешетки; выделить верхнюю и нижнюю полурешетки.
Е F
вф D Е
В С
А
А
1) 2)
Е F
Е
С
В С
В
А
5) 6)
Н
n
А
9)
н
F
G
С
В
З) 4)
8)
Е
А
7)
10)
12) А
19
14) 15)
Рис. 5.1. Задания к упражнению 5.1.
5.2. Какие из данных отображений (рис. 5.2) являются: изотонными; v
rомоморфизмом; л rомоморфизмом; rомоморфизмом; изоморфизмом;
эпиморфизмом; мономорфизмом; эндоморфизмом; автоморфизмом.
Пример. Для отображения <р, заданноrо на рисун
ке, проверим выполнимость свойства изотонности.
а5.Ь, <р(а) А, <р(Ь) с, А 5. С выполняется,
а5.с, <р(а) А, <р(с) А. А 5. А выполняется,
c5.d, <р(с) А, q>(d) В, А 5. В выполняется,
d5.e, q>(d) В. <р(е) с, в 5. С выполняется,
Ь5.е, <р( Ь) с, <р( е) с, с 5. С выполняется.
Отображение q> изотонно.
Проверим, является ли оно rомоморфизмом. Для
этоrо проверим выполнимость сохранения операциЙ
v и л. Очевидно, что для элементов, лежащих на одной и тоЙ же цепи, операции
v и л сохраняются в силу изотонности отображения. Поэтому необходимо
проверить сохранение операциЙ только для несравнимых элементов.
<р(Ь v с) <р(е) с; <р(Ь) v <р(с) Cv А С выполняется,
<р(Ь v d) <р(е) с; <р(Ь) v q>(d) Cv в с выполняется.
Отображение q> является v rомоморфизмом.
Про верим сохранение операции л. Для элементов Ь и d <р( ь л d) <р(а) А,
но <р(Ь) л q>(d) С л В В. Следовательно, <р(Ь л d) :f;. <р(Ь) л q>(d),
отображение не является л rомоморфизмом.
н
G
А
(3)
<р:
ь
а
е
J:
а
1)
1
С
в
А
j:
j:
5)
J:
Е
8)
9)
с
d
ь
11)
12)
j:
ь
J:
13)
14)
Рис. 5.2. Задания к упражнению 5.2.
15)
2)
21
6. rРАФЫ
Упражнения
6.1. Для заданноrо орrрафа D (рис. 6.1) найти: матрицу смежности А( D); все
пути длины 2 и 3; матрицу достижимости R(D); сильные компоненты
орrрафа D; конденсацию rрафа D*, вершинную базу В* ; вершинную базу
rрафа В; матрицу расстояний (d.); матрицу инциденuий I(D); определить
тип связности rрафа.
Пример. Орrраф задан на рисунке.
и] uj u4
и
Ц
1) Найдем матрицу смежности и с ее помощью определим число путей
длины 2,3, ведущих из и в и..
. J
и. и2 иЗ и 4 lIs и6 и7 ив
и. О О О О 1 О О О
и2 1 О О О О О О О
иЗ 1 1 О О О 1 О О
A(D) == и 4 О О О О О О 1 О
lIs О О О 1 О О О О
и6 О О О О 1 О О О
и7 О О О О О 1 О О
ив О О О О О О 1 О
и. и2 иЗ и4 lIs и6 и7 ив .
и. О О О 1 О О О О
и2 О О О О 1 О О О
иЗ 1 О О О 2 О О О
А 2 == и 4 О О О О О 1 О О
lIs О О О О О О 1 О
и 6 О О О 1 О О О О
и7 О О О О 1 О О О
ив О О О О О 1 О О
22
и. и2 иЗ и 4 115 и6 и7 ив
11. О О О О О О 1 О
112 О О О I О О О О
llЗ О О О 2 1 О О О
АЗ == 114 О О О О 1 О О О
llS О О О О О 1 О О
и6 О О О О О О 1 О
и7 О О О I О О О О
llв О О О О 1 О О О
Найдем в D все пути длины 2.
Поскольку элемент (1,4) в матрице А2 равен 1, в D существует путь длины
2 из И\ В И 4' Это путь и р И 5 ' и 4' Элемент (2,5) в матрице А 2 равен 1, следовательно,
в D существует путь длины 2 из И 2 В И 5
И 2 ' Ир И 5 . Элемент (3,5) в матрице А2
равен 2, следовательно, в D существует 2 пути длины 2 из иЗ в и 5 . Это из, И\' И 5
и ИЗ' и 6 , и 5 . Аналоrично находятся следующие пути длины 2: из ИЗ в и\
из, и 2 , " l ;
из И 4 В и 6
и 4 , и 7 , И 6 ; из и 5 в и 7
и 5 , и 4 , и 7 ; из и 6 в И 4
и 6 , и 5 , И 4 ; из И 7 в И 5
и 7 , и 6 , и 5 ;
из и 8 в и 6
и 8 , И 7 ' и 6 .
Найдем в D пути длины 3.
Элемент (1,7) в матрице АЗ равен 1, следовательно, в D существует путь
длины 3 из и\ в И 7
и\, И 5 ' И 4 ' и 7 . Элемент (2,4) в матрице АЗ paB.fH 1,
следовательно, в D существует путь длины 3 из и 2 в и 4
и 2 , и\, и 5 , и 4 . Элемент
(3,4) в матрице АЗ равен 2, следовательно, в D существует 2 пути длины 3
из иЗ в и 4
из, и р и 5 , и 4 и из, и 6 , и 5 , и 4 . Аналоrично находятся остальные пути
длины 3. Это из иЗ в и 5
из, И 2 ' и\, И 5 ; из и 4 в и 5
и 4 , и 7 , И 6 ' и 5 ; из и 5 в и 6
и 5 , и 4 ,
и 7 , и 6 ; из И 6 в И 7
И 6 ' И 5 ' И 4 ' И 7 ; из И 7 в И 4
И 7 ' И 6 ' И 5 ' И 4 ; из и 8 в И 5
И 8 ' И 7 ' и 6 , И 5 .
2) Матрицу достижимости R(D) можно построить следующим образом.
Пусть А
матрица смежности и R
матрица достижимости орrрафа D с n
вершинами. Тоrда:
R
B(l + А + А2 +... + A"
\)
в[(l + A)п
\],
rде n
количество вершин, 1
единичная диаrональная матрица, В
булево отображение. Булево отображение для некоторой матрицы Х задается
след у ющим об р азом: если х. :F- О, то В ( х.. )
1; если х
О, то В ( х.. )
О.
IJ IJ IJ IJ
23
1 О 022 1 2 О
11022110
21186430
О О О 2 2 2 2 О
О О О 2 2 220
О О О 2 2 2 2 О
О О О 2 2 2 2 О
О О О 1 222 1
и8
Используем матрицу достижимости для выявления сильных компонент
орrрафа D. Вычислим матрицу R х R' (R' транспонированная матрица R).
Эта матрица имеет блочно диаrональный вид. Каждый блок матрицы
определяет сильную компоненту. По нашей матрице находим, что вершина
И I составляет одну сильную компоненту. Аналоrично, вершины И 2 и ИЗ'
которым соответствуют единицы на rлавноЙдиаrонали матрицы R х R',-также
являются сильными компонентами. Вершины И 4 , И S ' И б , И 7 составляют одну
сильную компоненту, так как им соответствует один блок в матрице R х R'.
Вершина Ив еще одна сильная компонента.
Элемент (И i , И i ) в матрице R2 показывает число элементов в той сильноЙ
компоненте, в которую входит вершина И j .
I+A+A 2 +...+A 7 =
и.
и2
из
R(D) = B(I +А+А 2 +...+ А7) = и 4
us
и6
и 7
и.
1
1
1
О
О
О
О
О
24
и2
О
1
1
О
О
О
О
О
из и 4 u s и6 и7 и 8
011 1 1 О
011 1 1 О
1 1 1 1 1 О
О 1 1 1 1 О
О 1 1 1 1 О
О 1 1 1 1 О
011 1 1 О
01111 1
иl
и2
из
RxR' = и 4
us
и6
и7
и8
иl
и. 1
и2 2
из 3
R 2 = и 4 О
us О
и6 О
и7 О
и8 О
Введем обозначения для
конденсации D* орrрафа D:
Сильные компоненты:
{И 1 }
{И 2 }
{ИЗ}
{И 4 , И S ' И б , И 7 }
KI
K2
КЗ
K4
{Ив}
Ks
и. и 2 из и 4 u s и6 и 7 и8
1 О О О О О О О
О 1 О О О О О О
О О 1 О О О О О
О О О 1 1 1 1 О
О О О 1 1 1 1 О
О О О 1 1 1 1 О
О О О 1 1 110
00000001
и2
О
1
2
О
О
О
О
О
из и4 us
055
066
177
044
044
044
044
055
и6 и 7 и8
550
660
770
440
440
440
440
551
сильных компонент и построим rраф
N
К2 Кз
[раф конденсации D*
Вершинная база в D*: В* {К З ' Ks}
Ks
.
В верщинную базу орrрафа D должны войти по одной вершине из сильных
компонент К З ' Ks' Поскольку каждая из компонент содержит только одну
вершину, то в орrрафе D существует единственная вершинная база В {ИЗ'
ив},
3) Построим матрицу расстояний (d) орrрафа D по матрице смежности
9
А. Если величина dJj для i:F-j определена, то она равна наименьшему значению
11
25
k, для KOToporo элемент (i, j) в матрице B(Ak) равен 1, [де В булево
отображение. Матрицу расстояниЙ формируем последовательно по степеням
матрицы смежности. Диаrональные элементы в матрице расстояний равны
нулю, так как каждая вершина достижима сама для себя по пути нулевой
длины. Из матрицы смежности А выписываем все пути длиной 1, это
элементы dij 1. Из матрицы А2 в оставшиеся пустыми клетки матрицы
расстояний запишем все пути длиной 2, это элементы d 2. Теперь в
'}
матрицу расстояний будут внесены все расстояния длиной О (на диаrонали),
1,2, и некоторые клетки останутся пустыми. Эти клетки будут последователь
но заполняться числами 3, 4, ..., 7 по матрицам АЗ, А4,..., А7. Клетки матрицы
расстояний, оставшиеся пустыми после этоrо процесса, заполняем символом
00 для этих вершин расстояние не определено.
и\ и2 Uз и 4 U S и6 и7 и8
и\ О 00 00 2 1 4 3 00
и2 1 О 00 3 2 5 4 00
Uз 1 1 О 3 2 1 4 00
(dij)==u 4 00 00 00 О 3 2 1 00
Us 00 00 00 1 О 3 2 00
и6 00 00 00 2 1 О 3 00
и7 00 00 00 3 2 1 О 00
и8 00 00 00 4 3 2 1 О
4) Построение матрицы инциденциЙ.
Обозначим дуrи, как показано на рисунке. Элемент матрицы инциденциЙ
(i,j) равен 1, если дуrа выходит из вершины U i , равен 1, если дуrа входит
в вершину И;, И равен О, если дуrа не инцидентна вершине и;.
иl
26
Матрица инциденций
Х. Х2 Хз Х 4 Xs Х6 Х7 Х8 Х 9 Х\О
и. 1 1 1 О О О О О О О
и 2 О 1 О 1 О О О О О О
Uз О О 1 I 1 О О О О О
I(D) == и4 О О О О О 1 ] О О О
Us 1 О О О О О ] 1 О О
J и6 О О О О 1 О О ] 1 О
и7 О О О О О 1 О О 1 1
и8 О О О О О О О О О I
5) Тип связности rрафа леrко установить по ero rрафу конденсации.
Поскольку в rрафе есть вершины, ни одна из которых не достижима из друrой,
например, К I и Ks' то rраф слабо связан.
Задания
И] [М' *=
А и, И. и 1
и 1 И 6 ·
и, и. И 1 И, и 6
И, 2) и, 3) 4)
и 2 И 6 W
U'
и 6 И 6 1 и]
И 1 и
] и. и в и, и.
5) 6) 7)
И. и 2 и 6 и 1 И.
и.
, И 2
И 2
и. 9) И, И 1
10)
27
G) U 4 и, <й и4 и6 О . и2 и]
7 и] и
7 ·
] 7
и 2 и
6 и, 2 и 7 и 6 и, и 4
13) и l 14) 15)
Рис. 6.1. Задания к упраЖ1lению 6.1.
6.2. Для rрафа G (рис. 6.2) наЙти диаметр rрафа, радиус rрафа, центр rрафа,
эйлеров обход, rамильтонов путь и цикл.
Пример. [раф G задан на рисунке. Диаметр
rрафа d( С) тах d( V i ' v) 3 для всех V i ' V j Е С.
Максимальным удалением в rрафе G от верши
ныv.называетсявеличинаr(v.) maxd(v., v.),для
I l' J
всех v. Е С. Вершина называется центром rрафа
J .
С, если r(G) тzn r(v.), для всех v. Е С. Макси
J J
мальное удаление r( С) от центра называется
радиусом rрафа.
Найдем максимальные удаления от каждой вершины rрафа: r(v l ) 3,
r(v 2 ) 3, r(v з ) 2, r(v 4 ) 2, r(v s ) 3, r(v 6 ) 3, r(v 7 ) 3, r(v 8 ) 3. Наименьшее
среди них r( С) 2 радиус rрафа С, а вершины v з ' v 4 центры rрафа.
Проверим существование эЙлеровых обходов в rрафе С. В данном rрафе
существует 4 вершины с нечетной степенью: v з ' v s ' v 6 ' v T Следовательно, по
теореме Эйлера в данном rрафе нет эйлеровоrо обхода.
Существование rамильтоновых путей можно проверить методом перебора.
Например, rамильтоновы пути: vl' v 2 ' v з ' v 7 . v 8 ' v s ' v 6 ' v 4 ; vl' v 4 ' v 6 ' v s ' v 8 ' v 7 . v з ' v 2 И др.
v 7 V] V. v 6
V.
v 6 V, v 2 v 7 v 1 v 6 V, \
1) 2) 3)
и,
и 4
12)
V2
Vj
V4
Vз
28
V]
V]
4)
7)
V 6
V.
V,
10)
13)
V 2
V.
V.
V 6
V 7
11)
V 4
V,
V 4
V 2
V]
6)
V 4
9)
v,
V.
V.
12)
V 6
V,
V 6
V 7
V 4
14)
Рис. 6.2. Задания к упражнению 6.2.
15)
29
7. БУЛЕВА АлrЕБРА
Упражнения
7.1. Проверить эквивалентность форму л А и В, используя основные аксиомы
и теоремы булевой алrебры (см. указания к примеру 7.2).
Задания.
1) А
ху V ...x....,z V x....,z. В
x
y....,z V -..У V ....,z;
2) А
...x
y....,z V ...x
yz V --,ху, В
-.x;
3) А
xy
zv ху v z....,z, В
xy;
4) А
x(y V z) V y...x....,z v....,z(
y V х), В
xv yv....,z;
5) А
x
z V ху V y....,z, В
x
(yz) v...xz;
6) А
х
(ху
«х
у)
у) z), В
У
(х
z);
7) А
«x
у) V «x
z)y», В
(x
y)(
y
x....,z);
8) А
(xvy) (yv z) (zvx). В
xy vyzv zx;
9) А
xv yv z
(xvy)(xv z), В
x==z;
10) А
x(x
у). В
xy;
11) А
(xv у) v (ху). В
(xv
y)(...xv у);
12) А
xEe у' В
--,xyv
yx;
13) А
(...xyz), В
xv....,z v
y;
14) А
(xv y)(xv z)(y v w)(zv w), В
XW V yz;
15) А
«х Ее у)
х v у)«...х
у)
(х Ее у», в
(xy).
7.2. Представить булевы функции в виде СДНФ, СКНФ и каноническоrо
полинома Жеrалкина; проверить, являются ли они линейными, MOHOTOH
ными, самодвойственными. сохраняющими О, сохраняющими 1.
Пример. (x
(yvz»
xz.
Для построения СДНФ можно использовать метод эквивалентных
преобразований булевых формул, либо построить таблицу истинности.
Метод эквивалентных преобразований булевых формул.
СДНФ: (x
(yvz»
xz
используем эквивалентность x
y ==...х v у
(...x v у v z) v xz
используем закон де MopraHa и у v
y == 1
(x
y....,z) v (xz(y v
y»
используем закон дистрибутивности
x
y
z v xyz v x
yz.
СКНФ: (x
(yvz»
xz
(....,xvyvz)
xz
(....,xvyvz) v xz
x
y....,zv xz
х(
y ....,z v z)
закон полноrо склеивания и поrлощения
y....,z v z
y....,zvzv
y
yv Z
x(
y v z)
(х v y
y)(
y v Z v х...х)
«xv у) v z....,z)«xv
y) v z....,z)(
y v х v z)(
y v ...xvz)
(xv у v z)(xv у v ....,z)(xv
y v z)(xv
y v ....,z)(...xv
y v z).
30
Таблица истинности
х .ч z f(х, .ч, z) конституенты
О О О О XVl/vz
О О 1 О xvyv-.z
О 1 О О xv--.yvz
О 1 1 О xv--.yv-.z
1 О О 1 х --.y-.z
1 О 1 1 х --.у z
1 1 О О --.xv--.yvz
1 1 1 1 xyz
Выпишем все конституенты нуля и единицы (см. таблицу). Дизъюнкция
всех конституент единицы дает СДН Ф: /(х, у, z)
x
y....,z v xyz v x
yz.
Конъюнкция всех конституент нуля дает СКНФ:
f(x,y,z)
(xv у v z)(xvy v....,z)(xv
y v z)(xv
y v....,z)(...xv
y v z).
Проверим свойства функции.
1. Функция сохраняет нуль, так KaKf(O,O,O)
О.
2. Функция сохраняет единицу, так как f( 1,1,1)
1.
3. Самодвойственность. По определению, функция является самодвойствен
ной, если f(...x,
y, ....,z)
:f(x, у, z), Т.е. на противоположных наборах функция
принимает противоположные значения. Набор 001 противоположен набору 11 О,
Hof(O, О, 1)
Оиf(1, 1, О)
О, следовательно, функция несамодвойственна.
4. Монотонность. Функция монотонна тоrда, коrда на возрастающих Ha
борах она не убывает. Набор 100 предшествует набору 110, но
f(1, О, О)
1> f(1, 1, О)
О, следовательно, функция немонотонна.
5. Линейность. Чтобы проверить, является ли функция линейной,
построим полином Жеrалкина. Для этоro в СДН Ф данноЙ функции заменим
все символы v на Ее и выразим отрицания как
x
х Ее 1. Получим полином
Жеrалкина:
f(x, y,z)
x
y....,z v xyzvx
yz
(х(у Ее 1)(zEe 1» Ее (xzy) Ее (xz(y Ее 1».
Приведем ero к каноническому виду, используя закон дистрибутивности:
х(у Ее z)
ху Ее xz и тождества: х Ее х
o, х Ее О
х. Тоrда
f(x, у' z)
(х(у Ее 1)(z Ее 1» Ее (xzy) Ее (xz(y Ее 1»
«ху Ее x)(z Ее 1» Ее xzy Ее (xzy Ее xz)
xyz Ее ху Ее xz Ее х Ее xzy Ее xzy Ее xz
xyz Ее ху Ее х.
Функция нелинейна, так как в каноническом полиноме Жеrалкина есть
нелинейные элементы: xyz, ху.
Задания.
1) (xv
y v z)(-..'t"
y....,z);
I
I
31
2) (-.х-.у v ..y-.z) == (х v Z у);
3) ху v x(z v y)z;
4)x (x z);
5) (x (x у» z;
6)(x==y)==z;
7) (-.x ..у) (ху xz);
8) «х у) -.х) (х ух);
9) ..«х л у) -.х) ..(ху ..у);
10) (z х) (..(у v z) x);
11) ..(ху х) v (х(у v х»;
12) ..(х(у v z» (ху v z);
13) «x y) (z -.x» (..у -.z);
14) ««х у) -.х) ..у) -.z) z;
15) (x (у z» «x -.z) (х ..у».
7.3. Проверить полноту систем функuий.
Пример. Проверить полноту системы функций L {.., }.
Соrласно теореме Поста, для полноты системы функций необходимо и
достаточно, чтобы в нее входили хотя бы одна немонотонная, хотя бы одна
нелинейная, хотя бы одна несамодвоЙственная, хотя бы одна не сохраняющая
нуль и хотя бы одна не сохра: яющая единицу функции. Обозначим:
То класс функциЙ, сохраняющих о;
Т\ класс функций, сохраняющих 1;
S класс самодвоЙственных функций;
М класс монотонных функций;
L класс линеЙных функциЙ.
Для исследуемоЙ системы составим таблицу Поста. Если функция входит
в функционально замкнутый класс, то в таблице Поста в соответствующеЙ
ячейке ставится знак «+ , иначе знак « .
Для исследования системы L {.., } на полноту построим таблицы
истинности функций.. и .
1. Обозначимf\(х) -.х.
х
О
1
f l (x)
1
О
Функция f\ (х) не сохраняет О и 1, так как на нулевом наборе она принимает
значение 1, а на единичном О. Очевидно, что данная функция немонотонна.
Функция самодвойственна, так как на противоположных наборах функция
32
принимает противоположные значения. Функция линейна ее полином
Жеrалкина: ..х хЕИ.
2. Обозначимf2(х, у) x y.
у х f,(x, у)
о о 1
О 1 1
1 О О
1 1 1
"
1,
;'
По таблице истинности видим, что f 2 (x, у) x y не сохраняет О и сохраняет
1. Эта функция немонотонна, так как набор (0,0) предшествует набору (1,0), но
f 2 (0,0) > f 2 ( 1,0).на противоположных наборах (о, о) и (1, 1) функция принимает
одинаковые значения 1, следовательно, она несамодвоЙственна.
Для проверки линейности построим канонический полином Жеrалкина:
f2(X'Y) (хЕе 1)(у Ее 1) Ее (хЕе 1)у Ееху ху Ее хЕе 1. Функция нелинейна,
так как содержит элемент ху.
3. Построим таблицу Поста для заданной системы.
EET'I:I:IMEВ
Система функциЙ будет полна, если в каждом столбце таблицы Прста
стоит хотя бы один знак « . Система функций L {.., } полна.
11
,
Задания.
1){ , о};
2) {л, Ее, 1};
3){ , 1};
4) {I}, rде.xjy ..(х л у) штрих Шеффера;
5) {.J,}, [де x.J,y ..(х v у) стрелка Пирса;
6) { , Ее};
7) {==, л, о};
8) {ху v xz v yz, -.х};
9) {Ее, 1};
10) {Ее, v, о};
11) {ху, (х==у) ==z};
12) { , }, [дex y ..(x y);
13) { , ..};
14) { , ==};
15) {v, ..}.
33
7.4. Найти минимальные ДНФ и КНФ булевых функций.
Прим.ер./(х,у,z,t) 1 на наборах О, 1,2,3,6,7,8,15. Используемдиаrраммы
Вейча для нахождения минимальных форм.
Каждая клетка диаrраммы соответствует одному набору переменных,
номер клетки это двоичный код набора. При задании булевой функции в
соответствующую номеру набора клетку записывается единица, и, таким
образом, каждая клеткадиаrраммы с 1 представляет собой одну конституенту
единицы.
у
{ }
Х { }.
}....,z
О 1 5 4
2 3 7 6
10 II 15 14
8 9 13 12
IOYI IOYI
t t ,
Диаrрамма ВеЙча для заданной функции представлена на рисунке. Едини-
цы функции, стоящие в соседних клетках, отличаются значением только
одной переменной, следовательно, они склеиваются по этой переменной и
образуют импликанту. В этом случае rоворят, что импликанта nокрывает
соответствующие единицы булевой функции. Например, две единицы на
наборах 7 и 15, покрываются импликантоЙ yzt, четыре единицы на наборах 2,
3,7, 6 импликантой -.xz. При этом соседними считаются также клетки
,
стоящие вдоль левоro и правоrо края диаrраммы (отличаются значением у)
и вдоль BepxHero и нижнеrо края (отличаются значением х).
...,t
yzt
34
При минимизации булевой функции на диаrрамме Вейча сначала находят
покрытия, содержащие максимальное число единиц (8, 4,2), а затем покрытия,
накрывающие оставшиеся единицы таким образом, чтобы они также были
максимальны по величине и при удалении этоrо по крыт ия хотя бы одна
единица функции осталась непокрытой. При этом некоторые единицы MorYT
быть покрыты неоднократно. Для функции, представленной на рисунке,
минимальная ДНФ: -.x y v -..'t"z v yzt v y-.z t.
Минимальная КН Ф строится аналоrично по диаrрамме Вейча, заполнен
ной конституентами нуля в соответствующих клетках. Для данноЙ функu ии
минимальная КНФ: ( yvz)( -.xv-.zvt) ( -.xvyv t).
Заданuя.
1)j(x,y,z,t) 1 нанаборахО.3,4,6,8,9,10, 11. 13,15;
2) j(x, у, z, t) 1 на наборах 1,2,4,6,7,9,10, 13, 14
3) j(x, у, z. t) 1 на наборах 1,3,5,7,8, 10, 12, 14, 15;
4) /(х, у, z, t) 1 на наборах 5,7,8,9,10, 11, 12, 14, 15;
5)j(x,y,z,t) 1 на наборах 1,8.10,11,13,14,15;
6)/(x,y,z,t) 1 на наборах О, 1,2,3,5,6,9,10, 12,14,15;
7)/(x,y,z, t) 1 на наборах О, 3, 5, 7, 8, 9,11,12,14,15;
8) j(x, у, z, t) 1 на наборах 1,3,6,7,8,9, 10, 13, 14, 15;
9)j(x,y,z,t) 1 на наборах 2,4,5, 7,8,9,10,11,12,13,15;
10) j(x, у, z, t) 1 на наборах 1,4,5,7,9, 10, 12, 14;
11) j(x, у, z, t) 1 на наборах 2,4,6,7, 10, 12, 14, 15;
12) /(х, у, z, t) 1 на наборах 2, 4, 6, 9, 11, 13, 15;
13) j(x, у, z, t) 1 на наборах О, 3, 5, 7, 8, 9, 10, 11, 12, 14;
14) j(x, у, Z, t) 1 на наборах О, 1,2,3,8, 10, 11;
15) j(x, у, Z, t) 1 на наборах 1,3,6,7,8,9, 10. 15;
16) /(х, у, z, t) 1 на наборах О, 1,4,5,8,9, 11, 12, 15;
17) j(x, у, z, t) 1 на наборах 2, 3, 10, 11, 14, 15;
18) /(х, у, z, t) 1 на наборах О, 1,2,3,6,7,8,9, 13;
19)j(x,y,z,t) 1 нанаборах2,3,4,5,8,9,11, 15;
20) j(x, у, z. t) 1 на наборах 1,3,5,6,7,10, 11, 12, 14;
21)j(x,y,z,t) 1 на наборах О, 3, 7,8,9,13,12;
22) j(x, у, z, t) 1 на наборах О, 2, 4, 6, 8, 10, 12, 14;
23) j(x, у, Z, t) 1 на наборах 1,3,4,5,9, 11, 12;
24) /(х, у, z, t) 1 на наборах 3, 4,5,6,7, 11, 14, 15;
25)j(x,y, z, t) 1 на наборах 4, 6, 8, 9,10,12,14.
35
8. АлrЕБРА ВЫСКАЗЫВАНИЙ
Упражнения
8.1. Определить, являются ли формулы тавтолоrиями.
ПриJltер 1. Является ли формула «А
В)
В)
В тавтолоrией?
Решение. 1 способ
построение таблицы истинности.
А В A
B (A
B)
B «А
В)
В)
В
F F Т F Т
F Т Т Т Т
Т F F Т F
Т Т Т Т Т
Формула не является тавтолоrией, так как существует интерпретация
IAI
T,IBI
F, на которой она принимает ложное значение.
2 способ. Исследование формулы методом редукции.
Предположим, что существует набор. на котором формула принимает
значение, равное F:
'«А
B)
B)
BI
F
Тоrда '«А
В)
В) I
Т,' В 1
F. Подставим найденное значение I В I
FB
первое равенство: '(А
F)
11
Т. Решим это уравнение относительно А:
если IAI
т, то '(Т
F)
11
т. Следовательно, при IAI
т, /BI
Fформула
принимает значение, равное F Таким образом, она не является тавтолоrией.
ПриJltер 2. Является ли формула (А
В) & (В
С) & А
Ставтолоrией?
Решение. Исследование формулы методом редукции.
Предположим, что существует такая интерпретация, на которой формула
принимает ложное значение. Тоrда
I А
В I
т, I В
С I
T,I А 1
т, I С I
F. Тоrда:
'B
CI
IB
FI
T
IBI
F;
IA
BI
IA
FI
T
IAI
F.
Отсюда I А I
F, что противоречит третьему равенству I А 1
т Полученное
противоречие показывает, что формула не может принимать ложных
значений. Следовательно, формула (A
В) & (В
с) & А
С является
тавтолоrией.
Задания.
1) (А
B)
«B
с)
(A
С»;
2) (А
В)
«С
В)
(А v С
В»;
3) (А
(В
С»
«А
В)
(А
С»;
36
4) (...,А
....,В)
(А
В);
5) «А
В)
А)
«А
В)
В);
6) (А
С)
(А
В v С);
7) (...,А
В)
(....,В
А);
8) «А
B)
(А
С»
(A
(В
С»;
9) (В
с)
(В
(А
С»;
10) (В
A)
(А v В
A);
11)А & B
(C
B);
12) (В
А v C)
«B
C)
«D
C)
(B v D
С»);
13) «В
A)
С)
(А
С);
14) (А & В) v (С & D)
(А v В) & (Cv D);
15) (А
B) & (C
D)
(A v C
В v D);
16) (А v В
С)
(А
с) v (В
С);
17) (А & В
С)
«А
С)
(В
С»;
18) (А
В) & (С
D)
(А & С
В & D);
19) (А
В)
«...,А
В)
В);
20) (А
(В
С»
(В
(А
С»;
21) (....,В
...,A)
«....,В
А)
В);
22) А
(....,В
....,(А
В»;
23) ....,(А & В)
(А & В
В);
24) (В
С)
(А v С
(В
С»;
25) (А
(В
С»
(А v В
С).
8.2. Вывести (если возможно) заключение из каждоrо набора посылок.
ПриJltер. Малые дети неразумны. ют, кто может укрощать крокодилов,
заслуживает уважения. Неразумные люди не заслуживают уважения.
Получим возможные лоrические следования из данноrо множества
посылок. Обозначим каждое простое высказывание пропозициональными
буквами. Пусть А
«малые дeти
, В
<l.раЗУМНbl
, С
<l.заслуживают
уважения
, D
<l.может укрощать крокодилов
. Построим дедуктивный
вывод, используя следующие правила вывода:
А
В, В
С I
А
С
правило силлоrизма.
А
В I
....,B
...,А
правило контрапозиции.
Вывод:
1. А
....,B rипотеза [.
2. D
С rипотеза [2
3. ....,В
....,С rипотеза [з
4. А
....,C правило силлоrизма (1,3)
(Малые дети не заслуживают уважения).
37
5. С В правило контрапозиции (3)
(Только разумные люди заслуживают уважения).
6. D В правило силлоrизма (2,5)
(Разумно укрощать крокодwюв).
7....,В ...,D правило контрапозиции (6)
(Неразумные люди не укрощают крокодwюв).
8. А ...,D правило силлоrизма (1,7)
(Малые дети не укрощают крокодwюв).
Задания.
1) Устрицы молчаливы. Молчаливые существа не очень то забавны. я не
люблю не забавных существ.
2) Разумные люди ходят на Horax. IIеразумные люди ходят на руках.
3) Музыка, которую слышно, вызывает колебания воздуха. Музыка,
которую не слышно, не стоит Toro, чтобы за нее платили деньrи.
4) Если я поеду автобусом, а автобус опоздает, то я опоздаю на занятия.
Если я опоздаю на занятия, то я начну оrорчаться. Если я оrорчен, то мне не
следует ехать домой.
5) Если Смит победит на выборах, он будет доволен, а если он будет
доволен, то он плохой борец в предвыборной кампании. Но если он
провалится на выборах, то потеряет доверие партии. Если он плохой борец в
предвыборноЙ кампании, ему следует выйти из партии. Смит или победит в
предвыборной кампании, или провалится. Он плохой борец, если потеряет
доверие партии.
6) Если Петров Член нашей команды, то он обязательно храбрый и хорошо
владеет техникой удара. Но он не входит в состав нашей команды.
7) Зарплата возрастает только, если будет инфляция. Если будет
инфляция, то увеличится стоимость жизни. Если стоимость жизни возрастает,
то люди несчастны.
8) Джон или устал, или он болен. Если он устал, то он раздражен. Он не
раздражен.
9) Если KOHrpecc отказывается принять Новые законы, то забастовка не
будет окончена, кроме случая, коrда она длится более [ода. Забастовка также
будет окончена, если президент фирмы уйдет в отставку. KOHrpecc
отказывается действовать, забастовка оканчивается, и президент фирмы не
уходит.
10) Если человек стремится постичь смысл жизни, то он умеет вышивать
крестиком. Боксеры не умеют вышивать крестиком.
38
11) В день дождливый Боб не ходит на проryлку. Без свежеrо воздуха у
Hero пропадает аппетит.
12) Рыбак ловит рыбу. Тот, кто ловит рыбу оптимист. Оптимист не
предается отчаянию.
13) В хорошую поroду кошка ходит ryлять. Если кошка больна, то она
сидит дома.
14) Деревья, которые растут в этом саду, плодоносят. ДepeBЬ , KOTopь e
плодоносят, дают хороший урожай. Деревья, дающие хорошии урожаи.
получают тщательный уход. Ни одно дерево в этом саду не получает тщатель
HOro ухода.
15) Если человек достоин славы, то он получает наrраду. Если человек не
храбрый, то он не достоин славы.
16) Если идет дождь, то это наводит скуку. Осенью идет дождь.
17) Лекарства противны на вкус. Настои из трав это лекарства.
(8) Битвы сопровождаются страшным шумом. Если что то происходит
без шума, то оно может ускользнуть от нашеrо внимания.
19) Рыбы умеют плавать. Если это морская звезда, то она тоже рыба.
20) Книrи с острым сюжетом не подходят для чтения леrко возбудимым
людям. От книr со спокойным сюжетом клонит в сон.
21) Если я читал статью, то она была напечатана в rазете. Если что то
напечатано в rазете, то это может быть небылицей.
22) Если человек не обладает чувством юмора, то он скучен. Скуч ых
людей не приrлашают в компании. Если человека не приrлашают в компании,
то ero жизнь становится невыносимой.
23) Мука приrодна для пищи. То, что приrодно для пищи, продается в
продуктовых маrазинах.
24) Если человек добился успеха, то он прилежен. Прилежные люди
счастливы.
25) Если студент проrуляет MHoro занятий, то он получит двойку на
экзамене. Если он получит двойку на экзамене, то пропадут каникулы.
Студент может хорошо отдохнуть, если у Hero будут каникулы.
39
9. ФОРМАЛЬНЫЕ ТЕОРИИ
20) I
(А & В) v (А & С)
А & (В v С);
21) I
(А
....,В)
«А
В)
....,А);
22) I
(А
В)
« С
В)
(А v С
В»;
23) I
(А
....,В)
(В
....,А);
24) I
(А
(В
....,(А
....,В»);
25) I
(C
(А
В»
(С
(....,В
....,А».
Упражнения
9.1. С ПОМОЩЬЮ метатеоремы о дедукции доказать теоремы в теории L.
Пример. Доказать теорему: I
....,А
(А
В).
Воспользуемся обратной теоремой о дедукции: ....,AI
A
В, и еще один
раз:....,А, AI
B. Построим ВЫВОД....,А, AI
B
1. ....,А [1
2. А [2
3. ( ....,В
....,А)
« ....,В
А)
В) А3
4. ....,А
(....,В
....,A) А1
5. A
(....,B
A) А1
6. ....,В
....,A МР(1,4)
7. ....,В
А МР(2,5)
8. (....,B
A)
B МР(3,6)
9. В МР(7,8)
Применяя к полученному выводу два раза теорему о дедукции, получаем
доказательство теоремы.
9.2. Построить выводы и доказательства в теории LJ"
Теория LJ' Основные связки: v,....,.
Метаопределение: А
В
....,А v В.
Схемы аксиом:
А1:А vA
A
А2: А
А v В
А3:А vB
BvA
А4: (B
С)
(A v B
A v С)
Правило вывода: МР.
Задания.
1)1
«А
B)
A)
«A
B)
B);
2) I
(А
С)
(А
В v С);
3) I
(....,А
В)
(....,В
А);
4) '
«А
B)
(A
С»
(А
(B
С»;
5) I
(В
С)
(В
(А
С»;
6) I
(В
А)
(А v В
А);
7) I
A &B
(C
B);
8) '
(B
AvC)
«B
C)
«O
C)
(BvD
C»);
9) '
«В
А)
С)
(А
С);
10) I
(А
В) &(В
С)
(А
С);
11) '
(А
(B
C»
(B
(А
С»;
12) '
....,A
(В
....,(В
А»;
13) I
«А
В)
A)
A;
14) '
B
«А
(B
C»
(А
С»;
15) I
(А & В
С)
(А
(В
С»;
16) I
(A
(B
C»
(А &B
С);
17) '
(А
В)
«А
....,В)
....,А);
18) '
....,(А v В)
....,A & ....,В;
19)I
A v (Bv C)
(А v В) v С;
Задания.
1) А
В I
С v А
С v В;
2) I
(А
B)
«C
A)
(C
В»;
3) C
A,A
BI
C
B;
4) I
A
A (T.e.I
....,A v А);
5) I
А v....,A;
6) I
А
....,....,А;
7) I
....,B
(В
С);
8) I
А v (В v С)
«В v (А v С» v А);
9) I
(В v (А v С» v А
В v (А v С);
10) I
А v (В v С)
В v (А v С);
11) '
(А
(B
С»
(B
(А
С»;
12) I
(C
A)
«А
В)
(C
B»;
13) А
(В
С), А
В '
А
(А
С);
14)A
(B
C),A
BI
A
С;
15) В
А,.......в
АI
А;
16) r, А I
В::::) [I
А
В (метатеорема дедукции).
9.3. Построить выводы и доказательства в теории L 2 .
Теория L 2 . Основные связки: &, ....,.
Метаопределение: А
В
....,(А & ....,В).
Схемы аксиом:
А1:А
(А &А)
40
41
Пример.
Некоторые учебники npeдcтaв
ляют собой конспекты
Ни один роман не является
учебником
Каждый читает какие
нибудь
учебники
Некоторые студенты читают
только учебники
Пушкин писал и стихи,
и романы
Vy(C(y) v N(y)
R(Пушкин,у»;
Студент Боб не пишет письма
S(Боб) & Vy(L(y)
....,R(Боб, у»;
Студент Боб читает только
конспекты
Любой поэт пишет письма
Задания.
1) Некоторые романы написаны в стихах.
2) Ни один учебник не написан в стихах.
3) Все конспекты
учебники.
4) Некоторые стихи
письма.
5)
Евlений OHelUH
это роман в стихах.
6) Никто не любит писать письма.
7) Некоторые люди пишут стихи.
8) Те, кто пишет стихи,
поэты.
9) Все поэты любят читать стихи.
10) Все студенты любят читать учебники.
11) Все студенты пишут конспекты.
12) Некоторые студенты пишут только шnарlалкu.
13) Никто из студентов не пишет учебники.
14) Некоторые профессора, а также студенты, пишут стихи.
15) Некоторые не любят читать никаких учебников.
16) Студент юм любит читать учебники.
17) Профессор Джонс
поэт.
18) Шекспир писал только стихи.
19) Каждый любит читать какие
либо стихи.
20) Каждый, кто любит читать как.ие
либо стихи, любит читать стихи
Шекспира.
21) ЮЛЬКО студенты пишут конспекты.
22) Профессора пишут учебники.
23) Ни один профессор не пишет шnарzaлки.
А2: (А & В)
А
А3: (А
В)
(....,(В & с)
....,(C &А»
Правило вывода: МР.
Задания.
1) A
B,B
CI
....,(....,C&A);
2) I
....,(....,A & А);
3) I
....,....,A
А;
4) I
....,(А & В)
(В
....,А);
5) '
A
....,....,A;
6) I
(А
В)
(....,В
....,А);
7) ....,А
....,В I
В
А;
8) А
В '
С & А
В & С;
9) А
В, В
С, С
D '
А
D:
10)I
A
A;
11) I
A &B
B &А;
12) А
В, В
С '
А
С;
13)A
B, C
DI
A & C
B &D;
14)B
CI
A&B
A & С;
15) I
(А
(В
с»
«А & В)
С);
16) А
В, А
(В
с) I
А
С;
17) I
A
(B
A & В);
18) I
А
(В
A);
19) r,A '
В::::) rl
A
В (метатеорема о дедукции);
20) '
(....,А
А)
А;
21) А
В.....,А
В I
В.
10. ТЕОРИЯ ПРЕДИКАТОВ ПЕРвоrо ПОРЯДКА
Упражнения
10.1. Пусть х Е {люди}, У Е {вещи, которые можно читать и писать}. На этих
областях определения заданы предикаты:
Р(х): х
профессор, S(x): х
студент,
V(x): х
поэт, R(x, у): х пишет у,
W(x, у): х любит читать у, N(y): у
роман,
К(у): у
консnект, С(у): у
стихи,
И(у): у
учебник, L(y): у
письмо,
Н(у): у
шnарlалка.
Следующие высказывания записать в виде формул лоrики предикатов.
42
3у(И(у) & К(у»;
Vy(N(y)
....,U(y»;
Vx3y( и(у) & W(x, у»:
3x(S(x) & Vy(W(x,у)
И(у»);
S(Боб) & Vу(W(Боб, у)
К(у»;
Vx(V(x)
Vy(L(y)
R(x, у»).
43
24) Студе-нты, которые пишут конспекты, не пишут шпарlШlки.
25) Поэты пишут стихи.
26) Поэты пишут только стихи.
27) Некоторые поэты пишут и стихи, и романы.
28) Все пишут письма.
29) ЮЛЬКО поэты пишут только стихи.
30) Любой поэт любит читать свои стихи.
{ { FVF
F=T } т}
х
13у =
='dx
FvF
F=T ='dx { T } =F
{ TVF
F=F }
F F
х=23у
TvF
F=F
Аналоrично находятся остальные значения формулы Е, которые
приведены ниже в таблице.
10.2. Построить таблицы истинности на области интерпретации D
{1, 2}.
Пример. E
'dx3y(P(x)vQ(y)
R).
Предикаты Р(х), Q(y) на области интерпретации D
{1, 2} принимают
следующие значения:
Р Р. Р\ Р\ Р 1 Р 2 Р 2 Р 2 Р 2 Р З Р З Р З Р З Р 4 Р 4 Р 4 Р 4
Q QI
Qз
Q.
Q.!
QI
Qз
QI
Qз
Е Т Т IT F F F F F F F F IF F F F F
х Р, Р 2 Р, P
1 F F Т Т
2 F Т F Т
у QI Q2 Q,
1 F F Т Т
2 F Т F Т
Задания.
1) 3xV'y(P(x) v Q(y)
R);
2) 'dx(3y (R
Р(х) v Q(y»);
3) 3x(R
'dy(P(x)
Q(y»);
4) V'x(R
V'y(Q(y)
Р(х»);
5) 3х(Р(х)
3y(R
Q(y»);
6) 3х(Р(х)
'dy(Q(y)
Р(х»);
7) 3х(Р(х) & 3y(Q(y)
R»;
8) V'x(P(x) v 3y(Q(y)
R)
5);
9) 3х(Р(х) & V'y Q(y»
V'x Р(х);
10) 3xV'y(P(x) v Q(y)
Q(y»;
11) 3х(Р(х) & 3y(Q(y)
Р(х»);
12) 3x(V'y(P(x)
R(y»
Q);
13) V'x(P(x) & 3zR(z)
3yQ(y»;
14) V'x«P(x)
3yQ(y» & Р(х»;
15) 3у(Р(у) v V'x...,Q(x)
Р(у»;
16) 3у(Р(у)
V'xR(x»
Q;
17) 3xV'y(P(x) v Q(y»
R;
18) 3хР(х) v V'yQ(y)
R;
19) 3х(Р(х) v V'yQ(y)
R);
20) 3x(V'y(R
Р(х) v Q(y»);
21) V'x(P(x)
V'y(Q(y)
Р(х»);
22) V'y(3xP(x) v Q(y)
Q(y»;
23) 3х(Р(х) & V'y(Q(y)
Р(х»);
24) 3x(V'y(P(x)
(R
Q(y»»;
25) 3х«Р(х)
V'yQ(y» & Р(х».
R
замкнутая Формула, Т.е. высказьmание, которое принимает значение Ти F.
Поскольку предикат Р(х) принимает 4 значения, предикат Q(y)
4
значения, формула R
2 значения, и в формуле Енет свободных переменных,
ее таблица истинности будет состоять из 4х4х2
32 строк. Очевидно, что
если IRI
т, то 11:1
т, поэтому остается вычислить значение формулы на
оставшихся 16 интерпретациях формулы при IRI
F.
Пусть IRI
F. Рассмотрим вычисление значения формулы на интерпрета
ции Р
Р\ И Q
Q2'
! { y=Ifi(1)vQz(I)
R { { FVF
F=T } }
х = 1 3 х = 13у = Т
!у y=2fj(1)vQz(2)
R
FvT
F=F
T
'dx
'dx { }
{ У = 1 fj (2) v Qz (1)
R F v F
F = Т
х = 2 3у х = 23у = Т
У = 2 fj (2) v Qz (2)
R F v Т
F = F
Пусть Р
Р 2 И Q
Q\. Тоrда
{ { У = 1 Pz(l)v Q((1)
R
х = 1 3у
у = 2Pz(l)v Q(2)
R
'dx =
{ У = 1 Pz (2) v Q, (1)
R
х = 2 3у
у = 2 Pz (2) v Q, (2)
R
44
45
11
10.3. Про верить лоrическую общезначимость следующих формул.
Пример 1. Дана формула: 'v'x(P(x)
Q(x» v 'v'x...,Q(x). Если формула
общезначима, она принимает истинное значение на всех возможных
интерпретаЦИ5iХ,
Для проверки общезначимости используем метод нахождения контрпримера.
Предположим, что Формула 'v'x(P(x)
Q(x» v 'v'x...,Q(x) не ЯlВляется лоrически
общезначимой. Torдa существует такое множество М, интерпретации
(x), Q*(x)
предикатов Р(х), Q(x) соответственно, что I'v'x(
(x)
Q*(x» v 'v'x...,Q*(x)1
F.
Отсюда следует, что
I'v'x(p*(x)
Q*(x»1
F (1)
I'v'x..., Q* (х)1
F (2)
Формула (2) принимает ложное значение, если на области интерпретации
существует хотя бы одно значение а Е М, при котором I...,Q* (a)1
F, T.e.IQ* (а)1
Т. ДЛЯ Toro, чтобы формула (1) приняла значение F, достаточно, чтобы
существовало хотя бы одно значениех, например,Х
с, такое, что 1P*(c)1
Т,
а IQ*(c)1
F (с не обязательно совпадает с а), Следовательно, мы нашли
контрпример: достаточно на некотором n
элементном множестве М (n
2)
найти такую интерпретацию, при которой IP*(c)1
т, IQ*(c)1
Fи IQ*(a)1
Т.
Таким образом, формула 'v'x(P(x)
Q(x» v 'v'x...,Q(x) не является
лоrически общезначимой.
Пример 2. 3х(Р(х) v Q(x»
3хР(х) v 3xQ(x).
Предположим, что существует множество М и интерпретация на нем
(x),
Q*(x) такая, что формула на этой интерпретации принимает значение F:
13х(Р*(х) v Q*(x»
3хР*(х) v 3xQ*(x)1
F. Тоrда:
13xP*(x)v3xQ*(x)I
F, (1)
13x(P(x) v Q(x»l
т. (2).
Формула (1) ложна, если 13хР*(х) I
F и I3xQ*(x)l
F, а отсюда следует,
что
1
(x)l
F для любоrо х Е М (3)
и IQ*(x)l
Fдля любоrОХЕ М. (4)
Из (2) следует, что существует такое а Е М, что 1P*(a) v Q*(a)l
т. Возмож
нытри варианта: а) IР*(а)1
T,IQ*(a)1
Т; Ь) IP*(a)1
Т, IQ*(a)1
F; с) IP*(a)1
F,
IQ*(a)1
т.
Вариант а) противоречит условиям (3), (4). Однако, это противоречие еще
не доказывает общезначимость формулы
следует проверить все варианты.
Вариант Ь). Если 1P*(a)1
Т, то это противоречит условию (3).
Вариант с). Если IQ*(a)1
Т, то это противоречит условию (4).
Следовательно, не существует такой интерпретации, на которой формула
3х(Р(х) v Q(x»
3хР(х) v 3xQ(x) принимает ложное значение, Т.е. она
лоrически общезначима.
Задания.
1) 3х(Р(х) v (3х(Р(х)
Q(x»
3xQ(x»;
2) (В
3хР(х»
3х(В
P(x»;
3) 'v'x(P(x) v Q(x»
'v'xP(x) v'v'xQ(x);
4) 3х(Р(х) v Q(x»
3хР(х) v 3xQ(x);
5) (3хР(х)
3xQ(x»
3х(Р(х)
Q(x»;
6) 'v'x(P(x) & Q(x»
'v'xP(x) & 'v'xQ(x);
7) 3х(Р(х)
Q(x»
(3хР(х)
3xQ(x»;
8) (3х(Р(х)
Q(x» & 'v'xR(x»
('v'x(P(x) & R(x» v 3xQ(x»;
9) 3х(А(х)
В(х»
(3хА(х) v 3хВ(х»;
10) (3хР(х)
3xQ(x»
3х(Р(х)
Q(x»;
11) 'v'x(P(x)
(Q(x)
R(x»
(3х(Р(х) v Q(x»
'v'xR(x»;
12) 3х(Р(х)
Q(x»
('v'xP(x) v 3xQ(x»;
13) 3х(Р(х)
(Q(x)
R(x»)
'v'x(P(x) v Q(x)
R(x»;
14) 'v'x(P(x) v Q(x)
R(x»
'v'x(P(x)
(Q(x)
R(x»);
15) 'v'x(P(x)
(Q(x)
R(x»)
'v'x(P(x) v Q(x)
R(x»;
16) 'v'xP(x) v 'v'xQ(x)
'v'x(P(x) v Q(x»;
17) 3х(Р(х) v Q(x»
3хР(х) v 3xQ(x);
18) 'v'x(P(x) & Q(x»
'v'xP(x) & 'v'xQ(x);
19) 3х(Р(х) & Q(x»
3хР(х) & 3xQ(x);
20) 3хР(х) & 3xQ(x)
3х(Р(х) & Q(x»;
21) 'v'x(P(x)
Q(x»
('v'xP(x)
'v'xQ(x»;
22) ('v'xP(x)
'v'xQ(x»
'v'x(P(x)
Q(x»;
23) 'v'x(P(x)
Q(x»
('v'xP(x)
'v'xQ(x»;
24) ('v'xP(x)
'v'xQ(x»
'v'x(P(x)
Q(x»;
25) 'v'x(P(x) & Q(x»
3хР(х) v 3xQ(x).
11
I
46
47
11. АВТОМАТИЧЕСКОЕ ДОКАЗАТЕЛЬСТВО ТЕОРЕМ
Упражнении
Проверить лоrическое следование в лоrике предикатов 1
ro порядка.
Пример. Некоторые студенты любят своих преподавателей. Никто не
любит невежественных людей. Следовательно, ни один преподаватель не
является невежественным.
Все предикаты заданы на области D
{люди}. Пусть Р(х): х
студент,
D(x): х
преподаватель, Q(x): х
невежественный. Цх, у)
х любит у.
Формализуем посылки:
F1: 3х(Р(х) & 'Vy(D(y)
Цх, у»).
F2: 'Vx(P(x)
'Vy(Q(y)
....,Цх, у»).
Следствие с: 'Vy(D(y)
....,Q(y».
Для доказательства лоrическоrо следования можно использовать метод
от противноrо, формальный вывод и метод резолюций.
Метод от противноrо.
Предположим, что при истинности посылок Iлl
т, 1F21
т заключение
принимает ложное значение: 'СI
F.
Из l'Vy(D(y)
....,Q(y»1
F следует, что существует такое у
а, что
ID(a)
....,Q(a)1
F. Torдa ID(a)1
T.I....,Q(a)1
F, T.e,IQ(a)1
Т.
изl3х(Р(х) & (D(a)
Цх, a»)1
т следует, что существует такое x
Ь,
что I(P(b) & (D(a)
ЦЬ, а»1
Т. Тоrда Ip(b)l
Ти ID(a)
ЦЬ, а)1
Т, а так
как ID(a)l
Т, то /ЦЬ, a)l
т.
ПосылкаF2: l'Vx(p(x)
(Q(a)
....,цх, a»)1
Тдля всехх, в том числе для
х
Ь, следовательно, 'Р(Ь)
(Q(a)
....,цЬ, a»1
Т, а так как Ip(b)1
Т,
IQ(a)1
Т, то изIQ(а)
....,L(b, a)1
Тследует 1....,L(b,a) 1= Т .
Таким образом, получаем, что истинны оба утверждения: IT
L(b, a)l
Ти
IT
....,Цb, a)l
Т, T.e.lL(b, a)l
т и 1....,L(b, a)l
т. Полученное противоречие
доказывает лоrическое следование.
Формальный вывод.
1. 3х(Р(х) & 'Vy(D(y)
Цх, у») rt
2. 'Vx(P(x)
'Vy(Q(y)
....,L(x,y») [2
3. Р(Ь) & 'Vy(D(y)
ЦЬ, у» ЭК(1)
4. Р(Ь) уд. &(3)
5. 'Vy(D(y)
ЦЬ, у» уд. &(3)
6. P(b)
'Vy(Q(y)
....,L(b,y» УК(2)
7. 'Vy(Q(y)
....,L(b,y» МР(4,6)
8. Q(z)
....,L(b. z) УК(7)
48
9. D(z)
ЦЬ, z)
10. ЦЬ, z)
-.Q(z)
11. D(z)
....,Q(z)
12. 'Vy(D(y)
....,Q(y»
УК(5)
контрапозиция (8)
силлоrизм (9, 10)
Сеn (11)
Метод резолюций.
Найдем предваренные нормальные формы (ПНФ) дЛЯ посылок.
Л: 3x(P(x)&'Vy(D(y)
L(x, у»)
3x(P(x)&'Vy(....,D(y)vL(x, у»)
3x('Vy(-.D(у)vL(х,у»&Р(х»
3x'Vy«-.D(у)vL(х, у» & Р(х»
ПНФ.
F2: 'Vх(Р(х)
'Vу(Q(у)
-.L(х, у»)
'Vx( ....,F(x)v'Vy(....,Q(y)v....,L(x, у»)
'Vx('Vy(-.Q(у)v-.L(х, у» v ....,Р(х»
'Vx'Vy(....,Q(y)v-.L(х, у) v -.Р(х»
ПНФ.
Найдем скулемовскую стандартную форму (ССФ) посылок.
Н: Элиминируем квантор 3 в формуле 3x'Vy«-.D(у)vL(х. у» & Р(х».
Положим х
а, получим ССФ посылки Н:
'Vy(....,D(y)vL(a,y»&P(a), u u
F2: 'Vx'Vy(....,Q(y)v....,L(x,y) v....,F(x» находится в скулемовскои стандартнои
форме.
Возьмем отрицание от следствия с:
....,'Vy(D(y)
-.Q(y»
3y....,(....,D(y) v -.Q(y»
3y(D(y)&Q(y». Это ПНФ.
Элиминируем квантор 3, положив у
Ь:
D(b)&Q(b)
ССФ.
Получим множество дизьюнктов:
S
{-.D(у)vL(а, у), Р(а), ....,Q(y)v-.L(x, y)v....,F(x), D(b), Q(b)}.
Построим резолютивный вывод:
1. ....,D(y)vL(a,y)
2. Р(а)
З. ....,Q(y)v....,L(x, у) v....,P(x)
4. D(b)
5. Q(b)
6. -.цх, Ь) v....,P(x)
7. -.ца, Ь)
8. -.D(b)
9. О
{Ь/у}, резольвента 5, 3
{а/х}, резольвента 2, 6
{Ь/у}, резольвента 1,7
резольвента 4, 8
49
Построение лоrической проrраммы.
Запишем множество дизъюнктов в виде клауз.
Predicates
Р(х) /* х
студент
D(x) /* х
преподаватель
Q(x) /* х
невежественный
Цх, у) /* х любит у.
Clauses
Р(п)
D(b)
:
Q(y),L(x,y),P(x)
Ца, y):
D(y)
Goal:?
not Q(b)
Дерево выполнения лоrической проrраммы приве
дено на рисунке.
Q(b)
+
:
Q(y), L(x,y), Р(х)
+ {ь/у}
:
L(x, Ь), Р(х)
+
L(a,y) :
D(y)
+ {а!х, ь/у}
:
D(b), Р(а)
+
D(b)
+
:
P(a)
+
Р(а)
+
о
Задания
11.1. Проверить лоrическое следование.
1) Области определения: множество людей и множество КНИl. Все студенты
читают учебники. Некоторые студенты не читают стихов. Следовательно, ни
один учебник не написан в стихах.
2) Область определения: люди. Ни один ToproBeQ подержанными автомоби
лями не покупает подержанные автомобили для своей семьи. Некоторые лю
ди, которые покупают подержанные автомобили для своих семей, абсолютно
нечестны. Следовательно, некоторые абсолютно нечестные люди не являются
торrовцами подержанными автомобилями.
3) Область определения: люди. Каждый, кто идет в кино, покупает билет.
Следовательно, если не существует билетов, то никто не ходит в K
HO.
4) Область rтределения: люди. Ни один лентяй не достоин славы. Некоторые
художники не лентяи. Следовательно, некоторые художники достойны славы.
5) Область определения: студенты. Некоторые первокурсники любят всех
второкурсников. Ни один первокурсник не любит никоrо из студентов пред
последнеrо курса. Следовательно, ни один второкурсник не является CTyдeH
том предпоследнеrо курса.
6) Область определения: жuвотн.ые. 1. Я люблю всех животных, которые
при надлежат мне. 2. Собаки rpызут кости. 3. Ни одно животное я не пускаю к
себе в кабинет, если оно не «служит., Korдa ero об этом просят. 4. Все животные
во дворе принадлежат мне. 5. Всем животным, которых я люблю, разрешается
входить ко мне в кабинет. 6. Единственные животные, которые «служат., если
их попросить,
собаки. Следовательно, все Животные в этом дворе rpызут кости.
50
7) Область опреде;reнuя: дни. 1. Я не называю день «несчастливым
, если
Робинсон вежлив со мной. 2. Среды всеrда бывают пасмурными днями. 3. Если
люди берут с собой зонты, день никоrда не бывает солнечным. 4. ЕдинственныЙ
день недели, коrда Робинсон невежлив со мной,
среда. 5. Всякий возьмет с собой
зонт, если идет дождь. 6. Мои «счастливые
дни неизменно оказываются
солнечными. Следовательно, дождливые дни пасмурны.
8) Область определения: люди. 1. Никто не забудет причесаться, есЛИ он
отправляется на бал. 2. Нельзя сказать, что человек выrлядит превосходно,
если он неопрятен. 3. Курильщики опиума утрачивают контроль над собоЙ.
4. Причесанный человек выrлядит превосходно. 5. Никто не наденет белых
лайковЫХ перчаток, если он не отправляется на бал. 6. Человек всеrда неопря
тен, если он утратил контроль над собой. Следовательно, курильщики опиума
никоrда не носят белых лайковых перчаток.
9) Область определения: представленные здесь картины. 1. Ни одна из
представленных здесь картин, кроме батальных, не представляет ценности.
2. Ни одна из картин, вывешенных без рам, не покрыта лаком. 3. Все баталь
ные картины написаны маслом. 4. Все распроданные картины представляют
ценность. 5. Все картины анrлийских мастеров покрыты лаком. 6. Все карти
ны, которые были вывешены в рамах, проданы. Следовательно, все представ
ленные здесь картины анrлийских мастеров написаны маслом.
10) Область определения: мои мысли. 1. Любая мысль, которую нельзя
выразить в виде силлоrизма, поистине смешна. 2. Моя мечта о сдобных булоч
ках не стоит Toro, чтобы ее записывать на бумаrе. 3. Ни одну мою несбыточ
ную мечту нельзя выразить в виде силлоrизма. 4. Мне не приходило в rолову
ни одной действительно смешной мысли, о которой бы я не сообщил своему
поверенному. 5. Я только и мечтаю, что о сдобных булочках. 6. Я никоrда не
высказывал своему поверенному ни одной мысли, если она не стоила TOro,
чтобы ее записать на бумаry. Следовательно, все мои мечты сбылись.
11) Область определения: предметы. 1. Я с отвращением отношусь ко
всему, что не может служить мостом. 2. Все, что можно воспеть в стихах, для
меня приятный подарок. 3. Радуrа не выдержит веса тачки. 4. Все, что может
служить мостом, выдержит вес тачки. 5. Я не принял бы в качестве подарка
то, что вызывает у меня отвращение. Следовательно, paдyry не стоит воспевать
в стихах.
12) Область определения: авторы литературнЪlХ nроuзведений. 1. Все авторы
литературных произведений, постиrшие природу человека, умные люди. 2. Ни
одноrо автора нельзя считать истинным поэтом, если он не способен волновать
сердца людей. 3. Шекспир написал «rамлета
. 4. Ни один автор, не постиПIШЙ
природу человека, не способен волновать сердца людей. 5. Только истинныЙ поэт
Mor написать <lrамлета
. Вывод: Шекспир был умным человеком.
51
13) Область определения: люди этОlО колледжа. 1. Все выпускники Итона
в этом колледже иrрают в крикет. 2. Никто, кроме преподавателей, не обедает
за верхним столом. 3. Ни один из тех, кто иrрает в крикет, не умеет rрести. 4.
Все мои друзья в этом колледже
выпускники Итона. 5. Все преподаватели
прекрасные rребцы. Вывод: все мои друзья обедают за нижним столом.
14) Областъопредeлeнuя:людu.1. Те, кто нарушает свои 06ещания, незаслуживают
доверия. 2. Любители выпить очень общительны. 3. Человек, ВЫПOJlliЯЮщиЙ свои
обещания, честен. 4. Ни один трезвенник не ростовщик. 5. Тому, кто очень общителен,
всеrда можно верить. Вывод: ни один ростовщик не БЬffiает нечестен.
15) Область определения: плоды на этой выставке. 1. Все плоды на этой
выставке, которые не будут удостоены Harpaдbl, являются собственностью
орrанизационноrо комитета. 2. Ни один из представленных мной персиков не
удостоен Harpaдbl. 3. Ни один из плодов, распроданных после закрытия BЫCTaB
ки, не был незрелым. 4. Ни один из спелых плодов не был выращен в теплице. 5.
Все плоды, принадлежащие орrкомитету выставки, были распроданы после ее
закрытия. Вывод: ни один из моих персиков не был выращен в теплице.
16) Область определения: поэмы. 1. Ни одна интересная поэма не останется
непризнанной людьми с тонким вкусом. 2. Ни одна современная поэма не
свободна от аффектации. 3. Все ваши поэмы написаны о мыльных пузырях.
4. Ни одна аффектированная поэма не находит признания у людей с тонким
вкусом. 5. Ни одна древняя поэма не написана о мыльных пузырях. Вывод:
все ваши поэмы не интересны.
17) Область определения: книlи в этой библиотеке. 1. Единственные книrи в
этой библиотеке, которые я не рекомендую читать, безнравственны по своему
содержанию. 2. Все книrи в твердых переплетах обладают выдающимися литера
турными достоинствами. 3. Все романы вполне нравственны по своему содержа
нию. 4. Я не рекомендую вам читать ни одну из книr в мяrкой обложке. Вывод:
все романы в этой библиотеке обладают выдающимися литературными
достоинствами.
18
Область определения: вещи. 1. Все вещи, продаваемые на улице, не имеют
особои ценности. 2. Только дрянь можно купить за rpош. 3. Яйца большой rаrарки
представляют большую ценность. 4. Лишь то, что продается на улице, и есть
настоящая дрянь. Вывод: яйцо большой rаrарки за rрош не купишь.
19) Область определения: мои дети. 1. Все мои сыновья стройны. 2. Никто
из моих детей не здоров, если он не делает утренней зарядки. 3. Все обжоры
среди моих детей страдают ожирением. 4. Ни одна из моих дочерей не делает
утренней зарядки. Вывод: все мои дети
обжоры не здоровы.
20) Область определения: люди. 1. Ни один ребенок не обладает терпением.
2. Ни один нетерпеливый человек не может сидеть спокойно. Вывод: любой
ребенок не усидит на месте.
52
21) Область определения: люди. 1. Ни одна из моих кузин не справедлива.
2. Все судьи справедливы. Вывод: среди моих кузин нет судей.
22) Область определения: живые существа. 1. Ни одно толстое создание
не беrает хорошо. 2. Некоторые rончие беrают хорошо. Вывод: roнчих трудно
назвать толстыми.
23) Области определения: множество людей и множество книl. 1. HeKOTO
рые люди пишут стихи. 2. Те, кто пишет стихи
поэты. 3. Все поэты любят
читать стихи. Вывод: некоторые люди любят читать стихи.
24) Области определения: множество людей и множество литературных
nроuзведений. 1. Некоторые студенты читают стихи. 2. Ни один студент не
читает шпарrалки. Вывод: ни одна шпарrалка не рифмована.
25) Области определения: множество людей и множество литературных
произведений. 1. Некоторые студенты пишут некоторые учебники. 2. Все
студенты пишут только письма. Вывод: некоторые учебники можно отнести
к эпистолярному жанру.
26) Область определения: литературные nроuзведения. 1. Некоторые pOMa
ны написаны в стихах. 2. Ни один учебник не написан в стихах. Вывод: ни
один учебник не является романом.
27) Область определения: студенты. 1. Некоторые студенты прилежны,
но плохо учатся. 2. Плохо учатся не очень умные студенты. Вывод: некоторые
прилежные студенты не очень умны.
28) Области определения: множество людей и множество литературных
nроuзведений. 1. Все студенты пишут кон<-пекты. 2. Ни один студент не пишет
романы. 3. Некоторые люди учатся в институте. 4. Все, кто учится в институте,
студенты. Вывод: конспекты
не романы.
29) Область определения: люди. 1. Ни один император не дантист. 2. Всех
дантистов боятся дети. Вывод: дети не боятся императоров.
30) Область определения: люди. 1. Все осмотрительные люди остереrаются
rиен. 2. Ни одному банкиру не своЙственна неосмотрительность. Вывод:
банкиры остереrаются rиен.
11.2. Составить лоrическую проrрамму и про верить лоrические следования.
1) Каждое небесное тело является либо звездой, либо кометой, либо
планетой. Венера
небесное тело, не являющееся звездой. У комет, располо
женных недалеко от солнца, есть хвосты. Венера недалеко от Солнца, но у
нее нет хвоста. Следствие: Венера
планета.
2) Каждый, кто силен и умен, добьется успеха в карьере. Джон силен и
умен. Следствие: Джон добьется успеха в карьере.
3) Ни опин дракон, который живет в зоопарке, не является счастливым. Любой
зверь, который встречает добрых людей, является счастливым. Люди, которые
53
встречаются в зоопарке
добрые. Звери, которые живут в зоопарке, встречают людей,
которые посещают зоопарк Следствие: ни один дракон не живет в зоопарке.
4) Боб счастлив, если всем ero студентам нравится лоrика. Следствие: Боб
счастлив, если у Hero нет студентов.
5) Брадобреи бреют всех тех, кто не бреется сам, и не бреют тех, кто бреется
сам. Брадобреи существуют. Должен ли брадобрей брить caMoro себя?
6) Джону нравится любой, кто не нравится самому себе. Джону не нравится
никто, кто нравится себе. Нравится ли Джон сам себе?
7) Нечто, несущее в себе черты чеrо
то хорошеrо, хорошо само по себе.
Нечто, несущее в себе черты чеrо
то плохоrо, плохо само по себе. Война несет
в себе черты мира и страдания. Мир хорош, а страдание плохо. Следствие:
некоторые вещи и хороши и плохи.
8) Каждый восхищается [ероем. Неудачник восхищается каждым.
Каждый, кто не является [ероем
неудачник. Найти пары, которые
восхищаются друr друrом.
9) Для любоrо множества Х существует множество У большей мощности.
Если Х содержится в У, то мощность Х не превышает мощности У. Каждое
множество содержится в Z. Следствие: Z не является множеством.
10) Каждый любит какую
нибудь книry. <lMaCTepa и Марrариту. любит
каждый, кто любит какую
либо книry. Следовательно, <1 Мастера и Марrари
ТУ1> любит каждый.
11) Шекспир писал только стихи. Те, кто пишет только стихи,
поэты.
Все поэты любят читать стихи. Каждый, кто любит читать какие
либо стихи,
любят читать стихи Шекспира. Следовательно, Шекспир любил почитывать
свои произведения.
12) Все склонные к rорячности люди неразумны. Ораторы выступают с
речью перед аудиторией. Во время выступления любому из ораторов трудно
оставаться спокойным. Цицерон был оратором. Разумен ли Цицерон?
13) Все драконы
не лукавые. Все шотландцы
лукавые. Следовательно,
среди шотландцев нет драконов.
14) Джон находится в этом доме. У всех, кто находится в этом доме, болят
зубы. Следовательно, у Джона болят зубы.
15) у бедных нет автомобиля. Том
беден. Все хотят быть компаньонами
только боrатых предпринимателей. у всех боrатых есть автомобиль. Следова
тельно, никто не хочет взять в компаньоны Тома.
16) Все мои друзья простудились. Джон
мой друr. Тому, кто простужен,
нельзя петь. Следовательно, Джону нельзя петь.
17) Кроссворды, напечатанные в этом журнале, очень интересные. Ни один
кроссворд, который леrко разrадывается, не интересует меня. В журнале
напечатан кроссворд о животных. CMOry ли Я ero быстро разrадать?
54
18) Все неправдоподобные истории вызывают сомнение. Любая история,
рассказанная человеком с фантазией, выrлядит неправдоподобно. Барон
Мюнхrаузен был большим фантазером. Следовательно, истории барона
вызывают сомнения.
19) Утки при ходьбе переваливаются с боку на бок. Все, что переваливается
с боку на бок, не изящно. Все, что не изящно, не участвует в конкурсах Kpaco
ты. Следовательно, утки не выставляются на конкурсе.
20) Ни один добрый поступок не является незаконным. Все, что законно,
можно делать без страха. Перевести старушку через дороry
дело доброе.
Следовательно, совсем не страшно переводить старушек через дороry.
21) Ни у одноro ископаемоrо животноrо не может быть несчастной любви.
у устрицы может быть несчастная любовь. Следовательно, устрицы не иско
паемые животные.
22) Ни одна исследованная до сих пор страна не кишит драконами. Неис
следованные страны пленяют воображение. В Бамбурrском королевстве
драконы встречаются на каждом шаrу. Следовательно, Бамбурr Mor бы нас
заинтересовать.
23) Ни одна ориrинальная работа не пишется по заказу. Стихи Льюиса
Кэрролла очень ориrинальны. Следовательно, стихи Кэрролла написаны не
по заказу.
24) Зонтики бывают очень полезны в пути. Все, что не нужно в пути,
следует оставить дома. Следовательно, зонтики надо брать с собой в дороry.
25) Все бледные люди флеrматичны. Только те, кто бледен, имеют поэтйче
скую внешность. Пушкин отличался бурным темпераментом. Имел ли он поэ
тическую внешность?
26) Ни одно успешное путешествие не остается забытым. Путешествие,
закончившееся неудачно, не заслуживает Toro, чтобы о нем писали книry. О
путешествии Афанасия Никитина написана книrа. Помним ли мы об этом
путешествии?
27) Все трезвенники любят сахар. Ни один соловей не пьет вина. Тех, кто
пьет вино, не назовешь трезвенниками. Следовательно, все соловьи любят
сахар.
28) То, что трудно, требует внимания. Если любому предмету уделять
MHoro внимания, то он становится доступным для понимания. Физика дается
с большим трудом. Стала ли физика более доступной?
29) Здесь все цветы красные. Некоторые rерани
KpacHoro цвета. Следо
вательно, среди этих цветов есть несколько rераней.
30) Никто из студентов не пишет учебники. Некоторые студенты пишут
стихи. Следовательно, ни один учебник не написан в стихах.
55
12. ТЕОРИЯ Алrоритмов
Упражнения
Построить машину Тьюринrа и нормальный алrоритм Маркова.
1) Построить алrоритм, распознающий свойство слов в алфавите A
{a, Ь}
быть палиндромом. Пример: аЬа, аа, baab
палиндромы, аЬЬ, Ьа
не
палиндромы.
2) Построить алrоритм, вычисляющиЙ предикат Р(х,у)
Т, если х > у, и
Р(х,у)
F, если х5.у, в алфавите A
{1, О, *}, [де х и у
двоичные числа с
одинаковым количеством разрядов.
3) Построить алrоритм, вычисляющий предикат Р(х,у)
Т, если х > у, и
Р(х,у)
F, если х5.у, в алфавите A
{1, О, *}, [де х и у
двоичные числа с
разным количеством разрядов.
4) Построить алroритм, вычисляющий предикат Р(х,у)
Т, если х
у, и
Р(х,у)
F, если х < у, в алфавите A
{ 1, О, *}, [де х и у
двоичные числа с
разным количеством разрядов.
5) Построить алrоритм, подсчитывающий количество вхождений буквы
а в слово WB алфавите A
{a, Ь. *,I}. Пример: исходная конфиryрация: ЬааЬаа,
конечная: baabaa*'III.
6) Построить алrоритм вычисления функции j(x)
х/2 (с остатком) в
алфавите А
{I, *,
}. Пример. Исходная конфиrурация: 1111, конечная: 11;
исходная конфиryрация: 11111, конечная: 11*1;
7) Построить алrоритм вычисления функции j(x)
3х в алфавите А
{I, *}.
8) Построить алrоритм вычисления дизъюнкции двух двоичных чисел с
одинаковым числом рарядовj(х,у)
х v у в алфавите A
{1, О, v,
}. Пример.
Исходная конфиryрация: 10011 v 11010, конечная: 10011 v 11010
11011.
9) Построить алroритм вычисления конъюнкции двух двоичных чисел с
одинаковым числом рарядовj(х,у)
х & У в алфавите A
{1, О, &,
}. Пример.
Исходная конфиryрация: 10011 v 11010, конечная: 10011 v 11010
10010.
1 О) Построить алrоритм вычисления функции сложения j(x,y) .;, х + у двух
двоичных чисел в алфавите А
{1,О,+}. Пример. Исходная конфиrурация:
10011 + 1101, конечная: 100000.
11) Построить алrоритм вычисления функции j(x)
х/2 (с остатком) для
двоичных чисел в алфавите А
{1, О, *}. Результат должен иметь вид:
<х/2>*<остаток>. Пример. Исходная конфиryрация: 1001, конечная: 100*1.
12) Построить алrоритм вычисления функции j(n,x)
nx в алфавите A
{I,
*,
}. Пример. Исходная конфиrурация: 11*111, конечная: II*IIHIIII.
13) Построить алrоритм получения остатка от деления х/у для про
извольных чисел х, у в алфавите А
{I, /,
}. Пример. Исходная конфиryрация:
11111И11, конечная: IIIIIIIIIIH; исходная конфиryрация: 11И111, конечная: IIIIIIIIHI.
56
14) Построить алroритм для вычисления функции j(x.y)
х ЕВ У (сложения
по модулю два) в алфавите А
{1, О, ЕВ,
}. Пример. Исходная конфиryрация:
10011 ЕВ 11010, конечная: 10011 ЕВ 11010
01001.
15) Построить алrоритм сортировки слова в алфавите A
{a, Ь}. Пример.
Исходная конфиrурация: ЬаааЬЬЬаЬа, конечная: аааааЬЬЬЬЬ.
16) Построить алrоритм вычисления функции модуля разностиj(х,у)
.. mod(x
у) в алфавите A
{I,
,
}. Пример. Исходная конфиryрация: IIIIIIHI,
конечная: IIIIIHIHII; исходная конфиryрация: IIHIII, конечная: IIHIIH.
17) Построить алrоритм вычисления функции вычитания j(x,y)
х
у в
двоичной системе счисления в алфавите A
{1, О,
,
}. Пример. Исходная
конфиryрация: 111
101, конечная: 111
101
010.
18) Построить алrоритм, подсчитывающий количество букв в исходном слове
в алфавите A
{a, Ь,\, *}. Пример. Исходная конфиryрация: аЬЬ, конечная: abb*\II.
19) Построить алrоритм циклическоrо сдвиrа на один символ вправо слова в
алфавите A
{a, Ь, *}. Пример. Исходная конфиrypация: аЬЬ, конечная: аЬЬ*ЬаЬ.
20) Построить алrоритм циклическоrо сдвиrа на один символ влево слова в
алФавите A
{a, Ь, *}. Пример. Исходная конфиrypация: аЬЬ, конечная: аЬЬ*ЬЬа.
21) Построить алrоритм, осуществляющий замену первоro вхождения
подслова Р на подслово Q в слове W в алфавите А
{a, Ь, *}. Пример. Исходная
конфиryрация:ЬаЬ*аЬа*аЬЬаЬаа,конечная:ЬаЬ*аЬа*аЬаЬааа.
22) Построить алrоритм упорядочения слова в алфавите А
{а, Ь, с}.
Пример. Исходная конфиryрация: ЬасЬсаЬ, конечная: ааЬЬЬсс.
23) Построить алrоритм копирования слова в алфавите А
{а, Ь, с, *}.
Пример. Исходная конфиryрация: ЬасЬсаЬ, конечная: ЬасЬсаЬ* ЬасЬсаЬ.
24) Построить алrоритм, подсчитывющийй количество вхождений подслова
Р в слове W в алфавите А
{а, Ь, * '\'
}. Исходная конфиrypация: Р* W. При мер.
Исходная конфиrypация: аЬ* аЬЬаЬаа, конечная: аЬ* abbabaa
11.
25) Построить алrоритм обращения слова в алфавите А
{а, Ь, *}. Пример.
Исходная конфиryрация: аЬЬаЬ, конечная: аЬЬаЬ*ЬаЬЬа.
26) Построить алrоритм вычисления функции j(x,y)
х
у чисел в
алфавите A
{I,
,
}. Пример. Исходная конфиryрация: IIIIIHII, конечная: II\III
IIHI; исходная конфиryрация: IIHIII, конечная: IIНIII
л (пустой символ).
27) Построить алrоритм циклическоro сдвиrа вправо двоичноrо числа W
на заданное число разрядов р в алфавите A
{1, 0,1, *}. Исходная конфиrypация:
Р* W. Пример. Исходная конфиryрация: 111*11010, конечная: 10110.
28) Построить алrоритм циклическоro сдвиrа вправо двоичноrо числа W
На заданное число разрядов Р в алфавите А
{1, О, *}. Исходная конфиryрация:
Р* W. Пример. Исходная конфиryрация: 111*11010, конечная: 10100. u
29) Построить алroритм определения максимума из двух чисел в двоичнои
системе счисления в алфавите A
{1, О, *}.
57
1.3. 1) А u В;
2) А u В;
3) А u D;
4)А;
5)0;
2.2. 1) эквивалентность;
2) не эквивалентность;
3) не эквивалентность;
4) не эквивалентность;
5) эквивалентность;
6) не эквивалентность;
7) эквивалентность;
ОТВЕТЫ
6) А u В;
7)А u (Вп С);
8) (А u В) п (CuD);
9)А;
10) (А п В) u (С (lD);
11)А;
12)АпВ;
13) 0;
14) И;
15) и.
8) не эквивалентность; 15) эквивалентность;
9) не эквивалентность; 16) эквивалентность;
10) не эквивалентность; 17) эквивалентность;
11) не эквивалентность; 18) эквивалентность;
12) эквивалентность; 19) эквивалентность;
13) не эквивалентность; 20) эквивалентность.
14) не эквивалентность;
3.1. 1) отображение; 16) отображение;
2) отображение; 17) частичная функция, отображение;
3) инъекция; 18) сюръекция;
4) биекция; 19) биекция;
5) отображение; 20) отображение;
6) биекция; 21) частичная функция, отображение;
7) биекция; 22) отображение;
8) биекция; 23) отображение;
9) частичная функция, биекция; 24) частичная функция, сюръекция;
10) отображение; 25) отображение;
11) отображение; 26) отображение;
12) отображение; 27) отображение;
13) отображение; 28) отображение;
14) отображение; 29) частичная функция, отображение;
15) чаcrnчнаяфункция,иroбражение; 30) частичная функция, отображение.
3.2. 1) отображение;
2) отображение;
3) отображение;
4) сюръекция;
5) отображение;
6) отображение;
7) отображение;
8) сюръекция;
9) отображение;
10) сюръекция;
4.1.1) Отношение не cTpororo частичноrо порядка.
2) Отношение не cTpororo частичноrо порядка.
58
11) сюръекция;
12) сюръекция;
13) биекция;
14) отображение;
15) отображение.
3) Отношение не cTpororo частичноrо порядка.
4) Отношение не cтpororo частичноrо порядка.
5) Отношение cTpororo частичноrо порядка.
6) Не является отношением порядка.
7) Отношение cTpororo частичноrо порядка.
8) Отношение не cтpororo частичноrо порядка.
9) Отношение квазипорядка.
10) Отношение CTpororo частичноrо порядка.
11) Отношение не cтpororo линейноrо порядка.
12) Отношение не cTpororo линейноrо порядка.
13) Отношение квазипорядка.
14) Отношение cTpororo частичноrо порядка.
15) Отношение cTpororo частичноrо порядка.
16) Отношение не cTpororo линейноrо порядка.
17) Отношение cTpororo частичноrо порядка.
18) Отношение квазипорядка.
19) Отношение квазипорядка.
4.2. 1) изотонно;
2) не изотонно;
3) изотонно;
4) изотонно;
5) изоморфизм;
6) изоморфизм;
7) изоморфизм;
8) дуальный изоморфизм;
9) изоморфизм;
1 О) изотонно;
11) автоморфизм;
12) изотонно;
13) дуальный изоморфизм;
14) не изотонно;
15) антитонно.
5.1. 1) модулярная, недистрибутивная, С дополнениями, с относительными
дополнениями, не булева;
2) модулярная, дистрибутивная, без дополнений, не булева;
3) модулярная, дистрибутивная, без дополнений, не булева;
4) немодулярная, недистрибутивная, без дополнений, не булева;
5) немодулярная, недистрибутивная, без дополнений, не булева;
6) немодулярная, недистрибутивная, с дополнениями, не булева;
7) немодулярная, недистрибутивная, с дополнениями, не булева;
8) модулярная, дистрибутивная, с дополнениями, булева;
9) немодулярная, недистрибутивная, с дополнениями, не булева;
10) модулярная, дистрибутивная, без дополнений, не булева;
11) немодулярная, недистрибутивная, без дополнений, не булева;
12) немодулярная, недистрибутивная, с дополнениями, не булева;
13) немодулярная, недистрибутивная, с дополнениями, не булева;
14) немодулярная, недистрибутивная, с дополнениями, не булева;
59
15) модулярная, ДlIстрибутивная, без дополнений, не булева.
5.2. 1) v
rомоморфизм;
2) изоморфизм;
3) МОНОI\lОрфИЗМ;
4) V
rомоморфизм;
5) изоморфизм:
6) не rомоморфизм;
7) v
rомоморфизм;
8) автоморфизм;
9) v
rомоморфизм;
10) v
rомоморфизм;
11) не rомоморфизм;
12) автоморфизм;
13) не rомоморфизм;
14) v
roмоморфизм;
15) не rомоморфизм.
7.2. 1) не сохраняет О, не сохраняет 1, несамодвойственна, немонотонна,
нелинейна;
2) не сохраняет О, не сохраняет 1, несамодвойственна, немонотонна,
нелинейна;
3) сохраняет О, сохраняет 1, несамодвойственна. монотонна, нелинейна;
4) не сохраняет О, сохраняет 1, несамодвойственна, немонотонна, нелинейна;
5) сохраняет О, сохраняет 1, несамодвойственна, немонотонна, нелинейна;
6) сохраняет О, сохраняет 1, самодвойственна, немонотонна, линейна;
7) не сохраняет О, сохраняет 1, несамодвойственна, немонотонна, нелинейна;
8) не сохраняет О, сохраняет 1, несамодвойственна, немонотонна,
нелинейна;
9) сохраняет О, сохраняет 1, несамодвойственна, монотонна, нелинейна;
10) сохраняет О. сохраняет 1, несамодвойственна, монотонна, нелинейна;
11) сохраняет О, сохраняет 1, самодвойственна, монотонна, линейна;
12) сохраняет О, сохраняет 1, несамодвойственна, монотонна, нелинейна;
13) не сохраняет О, сохраняет 1, несамодвойственна, немонотонна,
нелинейна;
14) сохраняет О, сохраняет 1, самодвойственна, монотонна, линейна;
15) не сохраняет О, сохраняет 1, несамодвойственна, монотонна, линейна.
7.3. 1) Система функций полна.
2) Система функций полна.
3) Система функций не полна.
4) Система функций полна.
5) Система функций полна.
6) Система функций полна.
7) Система функций полна.
8) Система функций не полна.
9) Система функций не полна.
10) Система функций не полна.
11) Система функций не полна.
12) Система функций полна.
13) Система функций полна.
14) Система функций полна.
15) Система функций полна.
8.1. 1) тавтолоrия;
2) тавтолоrия;
3) тавтолоrия;
10) тавтолоrия;
11) тавтолоrия;
12) тавтолоrия;
19) тавтолоrия;
20) тавтолоrия;
21) тавтолоrия;
60
22) тавтолоrия;
23) тавтолоrия;
24) тавтолоrия;
25) не тавтолоrия.
4) не тавтолоrия;
5) тавтолоrия;
6) тавтолоrия;
7) тавтолоrия;
8) тавтолоrия;
9) тавтолоrия;
13) тавтолоrия;
14) не тавтолоrия;
15) тавтолоrия;
16) тавтолоrия;
17) не тавтолоrия;
18) тавтолоrия;
10.3. 1) не лоrически общезначима;
2) лоrически общезначима;
3) не лоrически общезначима;
4) лоrически общезначима;
5) лоrически общезначима;
6) лоrически общезначима;
7) не лоrически общезначима;
8) не лоrически общезначима;
9) не лоrически общезначима;
10) не лоrически общезначима;
11) не лоrически общезначима;
12) не лоrически общезначима;
13) не лоrически общезначима;
14) лоrически общезначима;
15) не лоrически общезначима;
16) лоrически общезначима;
17) лоrически общезначима;
18) лоrически общезначима;
19) лоrически общезначима;
20) не лоrически общезначима;
21) лоrически общезначима;
22) не лоrически общезначима.
23) лоrически общезначима;
24) не лоrически общезначима;
25) лоrически общезначима.
61
ЛИТЕРАТУРА
1. rаврилов [. П., Сапоженко А. А. Сборник задач по дискретной математи
Ke.
М.: Наука, 1977.
2. rИIIДИКИН с. [. Алrебра лоrики в задачах.
М.: Наука, 1972.
3. rорбатов В. А. Основы дискретной математики: Учеб. пособие для
студентов вузов.
М.: Высшая школа, 1986.
4. [охман А. В., Спивак М. А., Розе н В. В. и др. Сборник задач по математиче
ской лоrике и алrебре множеств.
Саратов, 1969.
5. Жеребкiн В. €. Лоriка.: [Пiдруч. для юрид. вузiв i фак.].
Харьков: Основа.
1995.
6. Кузнецов О. П., Адельсон
Вельский [. М. Дискретная математика для
инженера.
М.: Энерrоатомиздат, 1988.
7. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математиче
ской лопше и теории алrоритмов.
М.: Наука, 1975.
8. Луцький r. М., Кривий С. Л., Печурiн М. КОснови дискретноi MaTeMa
тики: Навч. посiбник.
К: IСДО, 1995.
9. Мендельсон Э. Введение в математическую лоrику.
М.: Наука, 1976.
10. Методичнi вказiвки до практичних занять з математичноi лоriки дЛЯ CTY
дентiв спецiальностi «Математика
/Укладачi: В. Н. €владенко, С. Д. Па
ращук.
Кiровоrрад: КДПI, 1990.
11. Нефедов В. Н., Осипова В. А. Курс дискретной математики.
М.: МАИ,
1992.
12. Новиков П. С. Элементы математической лоrики.
М.: Физматrиз, 1959.
13. Оре О. Теория rрафов.
М.: Наука, 1968.
14. Робертс Ф. С. Дискретные математические модели с приложениями к co
циальным, биолоrическим и эколоrическим задачам.
М.: Наука, 1986.
15. Столл Р. Множество, лоп"ка, аксиоматические теории.
М.: Просвеще
ние, 1968.
16. Таран Т. А. Основы дискретной математики: Учебное пособие
К:
Просвiта, 1998.
17. Харари Ф. Теория rрафов.
М.: Мир, 1973.
18. Хаусдорф Ф. Теория множеств.
М.: Мир, 1973.
19. Хромой Я.В. Математична лоriка.
К: Вища школа, 1981.
20. Чень Ч., Ли Р. Математическая лоrика и автоматическое доказательство
TeopeM.
М.: Наука, 1983.
21. Черч А. Введение в математическуюлоrику.
М.: ИЛ. Т.1. 1961.
22. Яблонский С. В. Введение в дискретную математику.
М.: Наука, 1979.
62
СОДЕРЖАНИЕ
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
Введение ......... .. ................................................................................ ........................... 3
Множества .................................................................................................................. 4
Теория отношений ................................................................................................... 7
Отображения. Функции . ..................................................................................... 12
Отношение порядка ..............................................................................................15
19
Решетки .....................................................................................................................
rрафы ..........................................................................................................................22
Булева алrебра ........................................................................................................30
Алrебра высказываний .. ....................................................................................... 36
Формальные теории ..............................................................................................40
Теория предикатов первоrо порядка ............................................................... 42
Автоматическое доказательство теорем ......................................................... 48
Теория алrоритмов ................................................................................................56
Ответы ........... ............................................................................................................ 58
Литература ............................................................................................................... 62
63
Навчальне видання
Таран Тетяна Архипiвна, д
p техн. наук, проф.
Миценко Наталiя Анатолiiвна
TeMHiKoBa Олена Леонiдiвна
Збiрник задач з дискретноi математики
2
re видання, перероблене i доповнене
Росiйською мовою
в авторсысiй редакцй"
Комп'ютерна верстка i ориriнаkмакет М. е. Пizурнов
Пiдписано до друку 19.09.2005. Формат 60x90j16. rapHiтypa Petersburg.
Ум. друк. арк. 4,00. 06л.
вид. арк. 1,68.
пrо УС! 4:IHpec.
Свiдоцтво про внесення су6'Екта ВИдавничоi справи до Державноrо реЕСТРУ
ВИдавцiв, виrотiвникiв i розповсюджувачiв ВИдавничоi продукцii
ДК N2 2225 Biд 25.06.2005 р.
03067, Киiв
67. вул. Машино6удiвна, 36
тел. (044) 458
04
46, факс 458
04
29, e
mail: office@axiom.net.ua
'lr