ЭЛЕМЕНТЫ
ДИСКРЕТНОЙ
МАТЕМАТИКИ
НАЧАЛЬНЫЕ ПОНЯТИЯ И МОДЕЛИ
МНОЖЕСТВА
ПОНЯТИЕ МНОЖЕСТВА
Множеством называется всякая совокупность объектов.
При этом, как правило, можно указать общее свойство, которым обладают или которым характеризуются элементы, входящие во множество. Например, множество писателей, книги которых имеются в продаже в некотором магазине. Элементами данного множества являются люди, характеризующиеся общим свойством: авторы книг, продаваемых в данном магазине.
Множествами можно также считать следующие совокупности:
1) всех рек, впадающих в Черное море;
2) видов птиц, гнездящихся на данной территории;
3) сортов картофеля, районированных в некотором регионе;
4) студентов первого курса факультета прикладной математики.
Математика имеет дело со специальными множествами такими, как множество точек на плоскости, множество простых чисел, множество решений некоторого уравнения, множество монотонно возрастающих числовых функций.
Для обозначения множеств в математике принято использовать прописные символы. Объекты, входящие во множества или элементы множеств, обозначаются с помощью строчных символов.
Пусть элемент a входит в некоторое множество A. Данный факт будем записывать с помощью выражения: a 
A. Здесь - специальный символ принадлежности элемента множеству, а запись a A понимается как " a является элементом множества A " или "элемент a принадлежит множеству A ".
Если объект a не содержится во множестве A, то запись этого факта имеет вид: a 
A.
Среди множеств особое место занимает множество, не содержащее ни одного элемента, которое называется пустым множеством и обозначается специальным символом 
.
Самое большое множество, состоящее из всех возможных элементов, называется Универсумом и обозначается как U. Всякое конкретное множество является частью или подмножеством этого множества.
ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ
Для представления или задания множеств используется несколько разных способов.
1. Непосредственное задание
Множества задаются перечислением всех входящих в них элементов, которые заключаются в фигурные скобки.
Например, множество областных и краевых центров юга России можно задать как { АСТРАХАНЬ, ВОЛГОГРАД, КРАСНОДАР, РОСТОВ, СТАВРОПОЛЬ }.
Данный способ может использоваться и для задания множеств, содержащих бесконечное число элементов. В этом случае записывается несколько элементов таких множеств, после чего ставится многоточие, предполагающее, что понятно каким образом можно выписать и другие элементы данного множества.
Например, множество всех целых неотрицательных чисел можно задать как: N = { 0, 1, 2,... }. Множество всех четных натуральных чисел может быть записано { 0, 2, 4,... }, где многоточие понимается как слова " и так далее ".
2. Задание множества указанием характеристического
свойства
В таком способе задания множеств используются записи в фигурных скобках.
Пространство между открывающей и закрывающей скобками делится на две части с помощью вертикальной черты.
Слева от разделителя записывается общий вид элементов множества, а справа - свойство, которым обладают элементы данного множества и не обладают никакие другие элементы. Свойство элементов множества, указанное в задании множества, называется характеристическим свойством.
Например. Множество всех пар людей, знакомых между собой, может быть задано так: {(x, y) | x знает y } - это множество пар людей, первый из которых знает второго.
Множество { 2 n | n N } - это множество всех четных натуральных чисел.
3. Задание множества указанием его имени
Например. Множество A, список № 5 или 5-й класс А средней школы № 1.
Данный способ удобен, когда множество рассматривается целиком как совокупность объектов, обладающих общим свойством.
4. Задание множеств с помощью диаграмм Венна
Диаграммы Венна представляют собой наглядный способ одновременного задания нескольких произвольных множеств. При этом всякое множество представляется областью на плоскости, ограниченной замкнутой линией. Обычно такие области ограничиваются линиями, подобными окружностям.
В изображении нескольких множеств на диаграммах Венна представляется их возможное взаимное сорасположение. Общие части замкнутых областей для множеств задают общие части соответствующих множеств. В частности, эти части могут быть пустыми.
Например, диаграммы Венна для произвольных двух и трех множеств имеют вид:
 |
A A C
B B
Множество B называется подмножеством множества A, если каждый элемент множества B является элементом множества A.
Если B является подмножеством A, то в этом случае говорят о включении B в A и используют символическое обозначение B 
A, где - символ включения множеств. Пусть B A и дополнительно известно, что A не содержится в B. В этом случае говорят, что множество B строго включено во множество A. Для обозначения строгого включения множеств используют специальный символ 
.
Заметим, что для любого множества A справедливо включение: 
A.
Множества называются равными, если они состоят из одних и тех же элементов. Очевидно, что множества A и B являются равными тогда и только тогда, когда A B и B A.
ОПЕРАЦИИ НАД МНОЖЕСТВАМИ
Пусть A и B - некоторые множества. Над этими множествами могут выполняться следующие основные операции.
Объединение множеств
Объединением множеств A и B называется множество C, определяемое соотношением: { x | x 
A или x B }, т.е. в объединение двух множеств входят те и только те элементы, которые содержатся хотя бы в одном из объединяемых множеств. Для обозначения операции пересечения используется специальный символ 
, а объединение множеств A и B записывается как A B.
Диаграмма Венна для объединения множеств имеет вид:
 |
A A B
A B
2. Пересечение множеств
Пересечением множеств A и B называется множество { x | x A и x B }, т.е. в пересечение двух множеств A и B входят только такие элементы, которые содержатся в обоих множествах. Для обозначения операции пересечения используется специальный символÇ, а пересечение множеств A и B записывается как A Ç B.
Соответствующая диаграмма Венна имеет вид:
 |
A B
A Ç B
Разность множеств
Разностью множеств A и B называется множество:
{ x | x A и x B }, т.е. в разность множеств A и B входят только те элементы A, которые не содержатся в B. Для обозначения операции разности множеств используется специальный символ\, а разность множеств A и B записывается как A \ B.
Диаграмма Венна для разности множеств A и B имеет вид:
 |
A B
A \ B
В определенных случаях приходится рассматривать все возможные элементы или объекты, которые не содержатся в некотором множестве A. Для такой ситуации разность между Универсумом U и данным множеством A называется дополнением множества A. Дополнение A обозначается как 
.
4. Произведение множеств
Произведением множеств A и B называется множество {(x, y) | x A и y B }, т.е. A 
B состоит из всевозможных пар элементов, в которых первая компонента является элементом A, а вторая - элементом B. Для обозначения операции произведения множеств используется специальный символ´, а произведение A и B обозначается как A ´ B.
Операцию произведения множеств можно продемонстрировать на примере произведения двух подмножеств множества вещественных чисел, представляемых отрезками на числовой оси.
 |
B
A
Здесь множества A и B представлены отрезками числовых осей. Тогда произведение этих множеств - это множество точек плоскости, образующее прямоугольник, проекции которого на оси совпадают с отрезками, представляющими A и B.
Заметим, что если R - это множество всех вещественных чисел, то R R или R2 представляет собой множество всех пар вещественных чисел. Это множество принято отождествлять с двумерной координатной плоскостью.
Аналогично, R3 обозначает множество троек вещественных чисел. Это множество отождествляется с множеством точек в трехмерном пространстве.
Степень множества
Если A - множество, то 2A обозначает множество всех подмножеств множества A и называется степенью этого множества.
Упражнение.
1. Используя операции над множествами, выразить через множества A, B и C множества 1 - 7 на следующей диаграмме Венна.
A 1 2 3 B
45 6
C 7
2. Проверьте справедливость тождеств (A´B) Ç (C´D) = (AÇC) (BÇD) и (A´B)È(C´D) = (AÈC) ´ (BÈD).
МОЩНОСТЬ МНОЖЕСТВ
Характеристика множеств, представляющая количество содержащихся в них элементов, называется мощностью множеств.
Если некоторое множество A содержит конечное число элементов, то его мощность | A | равна числу элементов этого множества. Для бесконечных множеств понятие количества элементов требует уточнения.
В общем случае понятие мощности произвольных множеств определяется через их равномощность.
ОПРЕДЕЛЕНИЕ
Множества A и B называются равномощными, если их элементы можно поставить во взаимно однозначное соответствие.
То есть можно определить такое множество пар (a, b), первая компонента которых принадлежит A, а вторая компонента принадлежит B. При этом для каждого a A существует одна пара, первая компонента которой равна a. Аналогично, для каждого элемента b B существует одна пара, вторая компонента которой равна b.
ОПРЕДЕЛЕНИЕ
Мощностью множества A называется семейство всех множеств, равномощных A.
Поскольку всякое множество равномощно самому себе, то мощность всякого множества является непустым семейством. Поэтому мощность является реальной характеристикой всякого множества. Мощность произвольного множества A обозначается символически как | A |.
Множество A - конечно, если оно пустое или равномощно некоторому началу { 1, 2,..., k } множества натуральных чисел N. Для непустого конечного множества A, состоящего из k элементов, принято использовать число k в качестве обозначения мощности этого множества.
Мощность пустого множества считается равной нулю.
Множество A называется счетно-бесконечным, если оно равномощно множеству натуральных чисел N. Мощность счетно-бесконечного множества обозначается как 
0.
Множество A называется счетным, если оно конечное или счетно-бесконечное. Содержательно счетность множества означает, что его элементы можно последовательно пересчитать подобно тому, как могут быть пересчитаны все элементы множества натуральных чисел. Для этого достаточно организовать пересчет N, при котором для каждого натурального числа указывается соответствующий ему элемент счетного множества A.
Замечание. Счетные множества объектов - это основной вид множеств объектов, изучаемых в дискретной математике.
Упражнение. Показать, что если A равномощно B, а B равномощно C, то A равномощно C.
Рассмотрим некоторые свойства счетных множеств.
ТЕОРЕМА 1.1
Объединение любых двух счетных множеств является счетным множеством.
Доказательство
Пусть A и B - счетные множества. Возможны следующие случаи.
1. Если A и B - конечные множества, то A È B состоит из конечного числа разных элементов, т.е. является счетным.
2. Если A - конечное, а B - счетно-бесконечное, и A ={ a 1,..., a k }, B = { b 1,..., b i,...}, где элементы A и B перечислены в порядке соответствия элементов A и B элементам множества { 1,..., k } и множеству натуральных чисел соответственно.
Удалим из A элементы, содержащиеся в B. В результате получим новое множество { a j 1,..., a jl }, которое может оказаться пустым.
Тогда множество { a j 1,..., a jl, b 1,..., b i,...}, в котором элементы перечислены в порядке соответствия возрастающим элементам множества натуральных чисел, является множеством, равномощным N.
3. Множества A и B - счетно-бесконечные. Тогда их можно представить в виде:
A = { a 1,..., a i,...}, B = { b 1,..., b i,...}.
Рассмотрим процесс последовательного выписывания в один список первых, вторых, третьих и последующих элементов этих множеств: a 1 и b 1, a 2 и b 2, a 3 и b 3 и т.д.
При этом в список не включаются такие из выбираемых элементов, которые уже встречались ранее.
Этот процесс позволяет записать все элементы множества A È B в виде счетной бесконечной последовательности c 1,..., c j,....
Такая последовательность содержит все элементы A È B по одному разу, в сопоставлении их с натуральными числами, так что элемент c i соответствует числу i.
Следовательно, A È B - является счетным множеством.
Доказательство окончено.
Упражнение. Доказать, что пересечение любых двух счетных множеств является счетным.
Нетрудно убедиться в том, что объединение и пересечение всякого конечного числа счетных множеств также является счетным множеством. В некоторых случаях приходится иметь дело с объединением или пересечением счетно-бесконечного семейства счетных множеств, т.е. рассматриваются множества, представляемые в виде: A = 
.
Здесь запись обозначает бесконечное объединение множеств A 1 
... Ai... При этом Ai = { a i 1,..., a ij,...}.
Здесь a ij - j -й по порядку пересчета элементмножества Ai.
Как следует из приводимой далее теоремы, такие множества также оказываются счетными.
ТЕОРЕМА 1.2
Счетно-бесконечное объединение счетных множеств является счетным множеством.
Доказательство
Проведем доказательство для простейшего случая, когда все множества Ai - счетно-бесконечные и непересекающиеся. Остальные случаи могут быть предложены в качестве упражнения.
Выпишем элементы множества в виде таблицы:
a 1 1 a1 2 a 1 3 ... a 1 j ...
a 2 1 a 2 2 a 2 3 ... a 2 j ...
a 3 1 a 3 2 a 3 3 ... a 3 j ...
. . . ...
. . . ... . ...
a i 1 a i 2 a i 3 ... a i j...
. . . ... . . ..
Последовательно пройдем по всем элементам таблицы в порядке, указанном стрелками, выписав все элементы множества . Элементы таблицы последовательно проходят по диагоналям таблицы, начиная с левого верхнего угла, а на диагоналях - в направлении сверху вниз.
Такой пересчет элементов ставит их в однозначное соответствие элементам множества натуральных чисел.
Доказательство окончено.
Определим натуральное число n, равное порядковому номеру элемента a ij в выписанном множестве .
Отметим следующие свойства пересчета элементов:
1) число элементов i -й по порядку диагонали равно i;
2) при движении по диагонали сверху вниз первый индекс элементов возрастает, а второй убывает;
3) сумма индексов элементов i -й диагонали постоянна и равна i + 1.
Воспользуемся данными свойствами. Тогда справедливы следующие выводы:
а) элемент a ij находится на (i + j -1)– й, начиная от левого верхнего угла диагонали, поэтому число элементов диагоналей, предшествующих диагонали, содержащей a ij, равно:
1 + 2 +... + i + j - 2 = (i + j - 1) (i + j - 2) / 2;
b) элемент a ij является j- м по порядку элементом на диагонали с номером i + j - 1.
Поэтому порядковый номер a ij в выписанном множестве равен: ((i + j - 1) (i + j - 2) / 2) + j.
Упражнение
1. Доказать справедливость последней теоремы для случаев, когда множества Ai могут быть конечными или пересекающимися.
2. Доказать, что пересечение счетно-бесконечного семейства счетных множеств является счетным.
ТЕОРЕМА 1.3
Для любого множества A множества A и 2 A не являются равномощными.
Доказательство
Предположим противное. Пусть для некоторого множества A существует взаимно однозначное соответствие элементов этого множества и множества 2 A .
Обозначим как Bx - множество, соответствующее элементу x Î A.
Рассмотрим множество D = { x | x 
Bx }. То есть это все такие элементы из A, которым соответствуют подмножества A, не содержащие эти элементы. Если для некоторого элемента- y A справедливо равенство By = Æ, то y D. Следовательно, D ¹ Æ.
Возьмем y A такое что D = By.
Возможен лишь один из следующих случаев:
а) y By;
b) y By.
В первом случае имеем: если y By, то y D, т.е. y By.
Во втором случае: если y By, то y D. Поэтому y By, т.е. в обоих случаях получаем противоречие.
Поэтому предположение о существовании взаимно однозначного соответствия между элементами A и 2 A является неверным.
Доказательство окончено.
ОТОБРАЖЕНИЯ И ФУНКЦИИ
Понятие отображения является фундаментальным для современной математики, поскольку всякий ее раздел связан с исследованием специальных множеств объектов вместе с системой операций над элементами множеств. Отображения являются важным случаем таких операций.
ОСНОВНЫЕ ПОНЯТИЯ
Пусть A и B непустые множества. Отображением множества A во множество B называется всякое соотнесение каждому элементу множества A единственного элемента множества B.
При этом множество A называется областью определения, а B - множеством значений отображения.
Для обозначения отображений будем использовать малые символы латинского алфавита.
Если f - отображение множества A во множество B, то для представления этого факта применяется специальное обозначение f: A 
B.
Пусть отображение f: A B ставит в соответствие элементу a A элемент b B. В этом случае будем говорить, что f переводит a в b, и использовать запись f (a) = b.
Если f: A B, то запись f (A) обозначает множество элементов, в которые f переводит элементы A.
Отображение f: A B называется отображением множества A на множество B (или сюръекцией), если f (A) = B. В противном случае отображение называется отображением множества A во множество B.
Отображение f называется инъективным, если оно переводит разные элементы A в разные элементы B.
Замечание. Содержательно отображение f является сюръективным, если в каждый элемент B отображается хотя бы один элемент множества A. Отображение f - инъективно, если в каждый элемент множества B отображается не более одного элемента из A.
Наглядным способом представления произвольных отображений являются диаграммы, имеющие вид (рис. 1.1):
A B
a f 3
b 1
c 2
d
Рис. 1.1
Здесь элементы множеств A и B изображаются точками замкнутых областей на плоскости, а отображение f, сопоставляющее элементам A элементы B, - ориентированными дугами, соединяющими элементы A с соответствующими им элементами B.
Рассмотрим пример диаграммы (рис. 1.2), на которой изображено неинъективное и несюръективное отображение.
A B
a f
b x
c y
d z
Рис. 1. 2
Отображение f неинъективно, поскольку f (a) = f (c). Кроме того, f - это несюръективное отображение, так как элементу y не соответствует ни один элемент A.
Пусть f: A B. Обозначим как f -1 соответствие элементам множества B совокупностей элементов A, определяемое по следующему правилу: если b B, то f -1 ставит в соответствие b те элементы множества A, которые отображением f переводятся в элемент b.
Обозначим совокупность таких элементов как f -1(b). Для приведенной ранее диаграммы соответствие f -1 имеет следующий вид:
f -1(x) = { a, c, d }, f -1(y) = 
, f -1(z) = { b }.
Если f -1 сопоставляет каждый элемент B с одноэлементным множеством, то это соответствие порождает отображение, переводящее каждый элемент B в единственный элемент множества, соответствующего этому элементу. Такое отображение называется отображением (или функцией), обратным к f, и обозначается тем же символом, что и определяющее его соответствие элементов B и подмножеств A. Очевидно, что в приведенном примере отображение f не имеет обратного к нему отображения.
ТЕОРЕМА 1.4
Отображение f имеет обратное отображение тогда и только тогда, когда f является инъективным и сюръективным.
Доказательство
Необходимость. Пусть отображение f: A B имеет обратное отображение. По определению обратной функции это означает, что в каждый элемент множества B отображение f переводит хотя бы один элемент A. Поэтому f (A) = B, т.е. f - это сюръективное отображение.
Поскольку f -1 - отображение, то отображение f переводит в каждый элемент b B ровно один элемент a A. Следовательно, f - это инъективное отображение.
Достаточность. Пусть отображение f - инъективное и сюръективное. Тогда в каждый элемент b B отображение f переводит единственный элемент a A, т.е. f -1 является отображением.
Теорема доказана.
ПРОИЗВЕДЕНИЕ ОТОБРАЖЕНИЙ
Пусть f: A B и g: B C. Тогда отображение h: A C, для которого h (a) = c тогда и только тогда, когда из того что
f (a) = b следует, что g (b) = c, называется произведением или композицией этих отображений. Произведение отображений f и g записывается в виде h = 
.
Содержательно отображение h получается последовательным применением отображений f и g. Наглядное представление произведения отображений приведено на рис. 1.3.
A B C
h
a f b g c
Рис. 1.3
Упражнение. Доказать, что произведение отображений обладает свойством ассоциативности, т.е. для любых отображений f, g, h, для которых определено произведение 
, справедливо равенство: 
.
Обобщением операции композиции отображений является операция суперпозиции. Такая операция применяется тогда, когда области определений представляют собой произведения систем множеств или части таких произведений. Суперпозиция отображений связана с подстановкой вместо отдельных компонент наборов элементов из области определения заданной функции других функций, области значений которых содержатся во множествах значений заменяемых компонент.
Пусть f: A B и A = A 1 ´... ´ A n. Для работы с компонентами элементов области определения такой функции используют представление f в виде f (x 1,..., x n). В этой записи символы переменных x 1,..., x n обозначают компоненты элементов множества A.
Пусть i - этонекоторое число из множества { 1,..., k }, и задана еще одна функция: g: D 1´... ´ D k A i, представляемая в виде g (v 1,..., v k). Обозначим как { w 1,..., w m} - множество из всех переменных f, за исключением x i и всех переменных g.
Тогда суперпозицией f и g, в которой функция g (v 1,..., v k) подставляется в f вместо x i, называется такое отображение h (w 1,..., w m), когда для каждого набора (a 1,..., a m) значений переменных w 1,..., w m выполнено соотношение
h (a 1,..., a m)= f (b 1,... b i - 1, d, b i + 1,…, b n).
В последнем соотношении b 1,... b i - 1, b i + 1,…, b n - это значения переменных x 1,... xi - 1, xi + 1,…, x n в наборе (a 1,..., a m), а d = g (s 1,..., s k), где s 1,..., s k - значения v 1,..., v k, выбираемые из того же набора.
Для обозначения суперпозиции функций f и g применяется специальная запись f (x 1,... xi - 1, g (v 1,..., v k), xi + 1,…, x n).
Если к некоторой функции f операция суперпозиции применяется несколько раз по различным переменным, то получаемое в результате отображение называется суперпозицией f и отображений, подставляемых вместо переменных f.
Если все переменные отображения f (x 1,..., x n) заменяются на g 1 (v 1,1,..., v 1, k 1),..., g n (v n ,1,..., v n , k n) соответственно, то такая суперпозиция представляется записью:
f (g 1 (v 1,1,..., v 1, k 1),.,..., g n (v n ,1,..., v n , k n).
ЛОГИКА ДОКАЗУЕМОСТИ И ИСТИННОСТИ
ВЫСКАЗЫВАНИЯ
ОПРЕДЕЛЕНИЕ
Высказыванием называется всякое предложение, о котором можно сказать, что оно является истинным или ложным.
Истинностные значения высказываний “ истина “ и “ ложь “ сокращенно будем записывать с помощью символов “ t “ и “ f “.
Например, предложение “ Новороссийск - приморский город “ образует высказывание, которое является истинным и принимает истинностное значение “ t “.
Утверждение “ Солнце восходит на западе “ образует ложное высказывание, истинностное значение его равно “ f “.
Некоторые предложения не принимают никакого конкретного истинностного значения и не являются высказываниями. Например, предложение “ В январе дни короче, чем в июне “ не может быть истинным или ложным, так как для северного полушария оно истинно, а для южного - ложно. Приведенное предложение можно рассматривать как неточное или неправильное, которое можно уточнить так, чтобы получить высказывание. Например, “ В январе в северном полушарии дни короче, чем в июне “ - это истинное высказывание, а “ В январе в Аргентине дни короче, чем в июне “ - ложное высказывание.
Содержательно высказывание указывает на наличие свойства предмета или предметов, о котором говорится в соответствующем предложении. В первом примере говорится о свойстве объекта (города Новороссийск) располагаться в определенном месте (являться приморским городом). Об аналогичном свойстве идет речь и в другом высказывании: “ Одесса - приморский город “. В обоих случаях высказывания являются конкретизациями одной и той же конструкции, различаются только именем объекта - населенного пункта. На основе этой и других подобных конструкции можно строить многочисленные примеры высказываний.
ПАРАДОКСЫ
Парадоксы это утверждения, которые интуитивно представляются осмысленными и указывают на конкретные свойства предметов, но не являются ни истинными, ни ложными. Широко известен пример такого предложения, называемый парадоксом лжеца.
Рассмотрим высказывание некоторого человека, который говорит о себе: " Я лжец ". Для простоты будем считать, что всякий человек может быть либо лжецом, т.е. всегда лгать, либо не быть лжецом и всегда говорить правду. Поэтому мы будем понимать смысл произнесенной фразы как признание в том, что этот человек всегда лжет.
Проанализируем приведенное предложение с точки зрения его истинности. Интуиция или здравый смысл обычно не дает оснований сомневаться в наличии смысла у этого предложения. Поэтому оно должно быть либо истинно, либо ложно.
Предположим, что предложение является истинным, и построим следующую цепочку рассуждений:
1) поскольку сказанное человеком истинно, то данный человек всегда лжет;
2) так как человек всегда лжет, то он лжет и в данном случае;
3) поскольку человек лжет, то предложение "Я лжец" - ложно.
Следовательно, предложение "Я лжец" не является истинным.
Рассмотрим второй возможный случай. Предположим, что данное предложение является ложным. Тогда построим следующую цепочку рассуждений:
1) поскольку данное предложение ложно, то человек не является лжецом;
2) так как человек не лжец, то сказанное в предложении является истинным;
3) следовательно, приведенное предложение должно быть истинным, а значит, предложение " Я лжец " не является ложным.
Окончательно получаем, что интуитивно понятное и допускаемое в качестве высказывания предложение не имеет никакого истинностного значения, или не имеет смысла.
В повседневной жизни предложения, подобные парадоксу лжеца, могут возникать и применяться в разных ситуациях. Это обычно не мешает людям общаться и понимать друг друга. Однако существование в разговорной речи противоречивых утверждений требует изучения или хотя бы учета возможности логической некорректности при решении задач, в конкретных областях знаний и деятельности. Последнее замечание связано с тем, что традиционные схемы рассуждений и решения задач основаны на использовании понятия истинности исходных данных утверждений, получаемых в процессе рассуждений, и делаемых в процессе вывода заключений.
При этом, если используемые при решении задач знания или факты представляют собой парадоксы, то рассуждения, проводимые на их основе не могут считаться истинными так как некорректен истинностный смысл полученных заключений или выводов.
В частности, для парадокса лжеца попытка доказательства истинности соответствующего предложения приводит к установлению его ложности. Верно и обратное, на основе ложности предложения с помощью приведенных ранее рассуждений устанавливается его истинность.
Противоречие, аналогичное парадоксу лжеца, может содержаться и в совокупностях связанных и интуитивно осмысленных предложений.
Например, рассмотрим факты, сообщенные в качестве начальной информации двумя лицами А и В:
А: " То, что говорит В - ложно ";
В: " То, что сказал А - истинно ".
Подобно тому, как это было проделано для парадокса лжеца, можно убедиться, что предположение о некотором истинностном смысле любого из предложений приводит к установлению, что это предложение должно иметь противоположный истинностный смысл.
Естественный способ, позволяющий избежать использования внутренне противоречивой информации, состоит в применении ограниченных языковых средств, позволяющих формировать высказывания.
Например, в приведенных примерах речь фактически идет об утверждениях, содержащих не столько информацию об окружающем мире, сколько говорящих об истинности утверждений об этом мире (в частности, о своем истинностном значении).
К логическим парадоксам близки так называемые семантические или смысловые парадоксы, представляемые предложениями, которые интуитивно имеют смысл, но в действительности таковыми не являются.
В качестве примера рассмотрим парадокс брадобрея или парадокс парикмахера, который содержится в следующем предложении:
" В городе живет брадобрей, который бреет всех мужчин города, которые не бреются сами ".
Свойство брадобрея, указанное в предложении вполне понятно пока мы не попытаемся получить ответ на вопрос о том, кто бреет самого брадобрея. Анализ данной задачи показывает, что брадобрей с одной стороны, не может брить самого себя, а с другой стороны, обязан брить самого себя.
В заключение рассмотрим пример парадокса, связанного с неточным определением множества, данным в предыдущем разделе. Для этого введем такое понятие, как множество всех множеств.
С точки зрения использованного ранее интуитивного понятия множества, множество всех множеств - это совокупность, элементами которой являются любые множества. Поэтому интуитивно эта совокупность множеств также является множеством множеств. Общее свойство элементов множества всех множеств - быть множеством.
Поэтому множество всех множеств должно являться элементом самого себя. Последнее заключение противоречиво, поскольку множество всех множеств не может быть элементом самого себя хотя бы потому, что в нем кроме него самого содержатся и другие элементы, являющиеся множествами. Следовательно, для множества всех множеств не выполняется фундаментальное свойство понятия равенства, которое состоит в равенстве всякого объекта самому себе.
Последний пример свидетельствует о некорректности интуитивного понятия множества и указывает на необходимость аккуратного применения этого понятия при проведении рассуждений, чтобы избежать противоречивых конструкций и выводов из-за использования некорректных объектов.
Тем не менее, во всех рассмотрениях настоящего курса, да и многих областей математики, интуитивное понятие множества является достаточным, поскольку используемые в этих областях примеры множеств не являются внутренне противоречивыми.
ПРЕДИКАТЫ
Ранее приводились примеры высказываний, являющихся уточнениями некоторого общего утверждения, не являющегося высказыванием. Такие общие утверждения носят название высказывательных форм и используются как обобщение понятия высказывания, в котором представлено несколько отдельных высказывания или групп отдельных высказываний.
ОПРЕДЕЛЕНИЕ
Высказывательной формой или предикатом называется всякое предложение, содержащее наименования неопределенных объектов или неизвестных, которое превращается в высказывание после подстановки в него конкретных объектов вместо имен неопределенных объектов.
Для обозначения неопределенных или произвольных объектов удобно использовать символы переменных. Для каждой такой переменной уточняется множество, элементы которого могут подставляться в высказывательную форму вместо переменной.
Например, к высказывательным формам относится предложение “ x учится в школе с номером y “. Здесь x обозначает элементы множества всех людей, а y - элемент множества всех натуральных чисел.
Подобным образом высказывательные формы образуют предложения: “ x дружит с y “ и “ x имеет рост y и вес z “, “ x живет в городе y “.
Для удобства будем использовать сокращенную запись высказывательных форм: сначала записывается имя свойства неопределенных объектов, входящих в форму, а затем, в скобках, в определенном порядке перечисляются имена входящих в нее переменных.
Для приведенных примеров высказывательных форм сокращенные записи имеют вид:
Учится (x, y), дружит (x, y), рост-вес (x,y, z), живет (x, y).
Рассмотрим пример высказывательной формы, которая может быть определена для высказывания:
“ Занятия физкультурой дают силу студенту Иванову “.
Эта форма может быть записана в виде: Дает (x, y, z). Здесь x - обозначение объекта, дающего что-то, т.е. выполняющего действие, y - объект или предмет, который дают, а z - объект, получающий y от z.
Примерами применения этой формы являются:
Дает (логика, знания, студент I курса);
Дает (сигарета, здоровье, человек).
Здесь первый из приведенных примеров принимает истинностное значение “ t “, а второй - “ f “.
Пусть P - это символическое обозначение высказывательной формы (свойства), связывающей компоненты n - элементных наборов объектов, обозначаемых символами переменных x1,..., xn, которые могут принимать значения из множеств A 1,..., An. Тогда предикату P можно поставить в соответствие функцию, отображающую всякий набор из A 1 ´... ´ Aп в одно из двух истинностных значений. Множество A 1 ´... ´ Aп является областью определения соответствующего отображения.
Кроме того множество наборов значений переменных предиката, при подстановке которых вместо неопределенных объектов формы P получается истинное высказывание, образует отношение на множестве всех таких наборов.
Свойство P называется предикатом, а число входящих в него переменных - арностью или размерностью этого предиката.
В частности, высказывания представляют собой нульарные предикаты, поскольку они являются утверждениями, не содержащими переменных.
В приведенных примерах предикат Дает имеет арность 3, а предикат Дружит - арность 2. Предикаты арности 1 и 2 называются также соответственно унарными и бинарными предикатами.
Общеупотребительные арифметические сравнения могут рассматриваться как бинарные предикаты, которые соответственно можно представлять в виде:
Больше (x
