рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ - раздел Математика, Министерство Образования И Науки Украины Восточноукраинский Национал...

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

имени ВЛАДИМИРА ДАЛЯ

 

 

Фесенко Т.Н.

Чалая Е.Ю.

 

КУРС ЛЕКЦИЙ

 

 

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

«Информатика», «Системный анализ», «Компьютерные системы и сети»)  

Глава 1.

Множества

Основные понятия и определения теории множеств.

 

Понятие множества является одним из фундаментальных понятий математики. Рассматривая любую математическую задачу, мы постоянно сталкиваемся с некоторыми множествами. Это могут быть числовые множества, множества каких-то геометрических объектов, символов, букв и т. д. Понятию «множество» невозможно дать строгое определение. Для того чтобы определить какое-либо понятие, необходимо указать, частным случаем какого более широкого понятия оно является. Для понятия множества это выполнить невозможно, потому что оно само по себе является наиболее широким понятием и ни в каких других не содержится. Иногда множество определяют как совокупность элементов одной природы. Но слова «совокупность», «семейство», «класс» являются словами-синонимами, поэтому их нельзя использовать для строгого определения понятия множества. Но этим определением можно пользоваться, как интуитивным. Действительно, когда мы говорим о множестве, то объединяем некоторые предметы по некоторому признаку в одно целое. Основатель теории множеств Георг Кантор подчеркнул это следующим словами: «Множество есть многое, мыслимое нами как единое».

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

Множества принято обозначать заглавными буквами: . Элементы множеств – строчными буквами: . В теории множеств рассматривается символ принадлежности элемента некоторому множеству. Если некоторый элемент принадлежит множеству , то записывают: . Если не принадлежит множеству , то пишут: .

Определение 1: Если множество содержит конечное число элементов, то его называют конечным, а если в нём бесконечное число элементов, то – бесконечным.

Возможны различные способы задания множеств. Можно, например, задать множество, предъявляя список элементов, входящих во множество. Множество студентов данной группы можно задать списком в журнале академической группы. Но этот способ применим только к конечным множествам, да и то далеко не ко всем. Если множество нельзя задать при помощи списка (бесконечное множество), то его задают путём указания некоторого характеристического свойства, которым обладают все элементы данного множества и только они. Например, если говорится о множестве натуральных чисел , тогда ясно, что число , а числа или . Перечисляя элементы множества, их записывают в фигурных скобках, например: , .

Отметим, что если множество задано своим характеристическим свойством, то не всегда известно, существует хотя бы один элемент с таким свойством. Поэтому приходится рассматривать множество, не имеющее ни одного элемента. Это множество называют пустым и обозначают: . Пустое множество единственно. Приведём пример пустого множества. Множество , состоящее из всех четырёхугольников, все углы которых прямые, и диагонали имеют различную длину, пусто, так как диагонали прямоугольников равны. Пустым также будет множество всех треугольников, длины сторон которых равны 1, 2 и 8 сантиметров.

В математике важную роль играют множества, составленные из геометрических фигур, алгебраических выражений, функций и т.д. Даже школьная математика имеет дело с множествами на каждом шагу. Особенно часто встречаются множества, составленные из чисел: а) множество натуральных чисел ; б) множество всех целых чисел ; в) множество всех рациональных чисел ; г) множество действительных чисел ; д) множество комплексных чисел .

Определение 2: Множества и называются равными, если они состоят из одних и тех же элементов.

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

Определение 3: Пусть и – два множества. Множествоназывается подмножеством множества , если каждый элемент множества является элементом множества . В этом случае пишут: . Читают: включается во множество , или является частью множества .

Замечание: Символ включения применяется для множеств, а символ принадлежности применяется для элементов.

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

– множество всех четырёхугольников;

– множество всех трапеций;

– множество параллелограммов;

– множество всех прямоугольников;

– множество всех квадратов;

Видно, что .

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

Очевидно, что всякое множество является частью самого себя: . Кроме того, пустое множество является подмножеством любого множества: . Эти два подмножества называются несобственными подмножествами. У любого произвольного множества всегда есть два несобственных подмножества (пустое и само множество). Если у данного множества есть другие подмножества, отличные от несобственных, то они называются собственными подмножествами.

Определение 4: Если и , то называется собственным подмножеством множества .

Замечание: Можно отметить, что . Действительно, – это множество, не содержащее ни одного элемента, а – это множество, содержащее один элемент - . Таким образом, эти два множества не равны.

Определение 5: Иногда при рассмотрении некоторых множеств оказывается, что все они являются подмножествами одного и того же фиксированного множества. Обычно его обозначают: и называют универсальным множеством. Таким образом, универсальное множество – это множество всех подмножеств в данной конкретной задаче.

Отношение включения обладает следующими свойствами:

1) (рефлексивность включения);

2) если и , то (транзитивность включения);

3) если и , то (антисимметричность включения).

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

 

 

Операции над множествами. Булевы алгебры.

 

Основными операциями над множествами являются: объединение, пересечение множеств, а также разность и дополнение множества до универсального. Для наглядности изображения множеств и их комбинаций удобно пользоваться диаграммами Эйлера-Венна, на которых множества выглядят как геометрические фигуры (круги, прямоугольники, эллипсы).

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

Обозначают: (иногда: ).

По определению: . Объединение можно ещё назвать слиянием одного или нескольких множеств. Из рисунка видно, что произвольный элемент принадлежит объединению двух множеств (общая закрашенная часть), если он принадлежит одному из кругов или . Следовательно: и . Эта операция очень часто встречается в различных разделах математики. Например, объединением множеств остроугольных, тупоугольных и прямоугольных треугольников даёт множество всех треугольников. Объединением чётных и нечётных целых чисел является всё множество целых чисел.

Определение 2:Пересечением (произведением) множеств и называется множество, состоящее из всех тех элементов, которые принадлежат как множеству , так и множеству . Обозначают: (или ).

По определению: . Пересечение можно также называть общей частью двух множеств. На рисунке общая часть показана штриховкой. Любая точка принадлежит заштрихованной части только тогда, когда она одновременно принадлежит и кругу , и кругу . Отсюда следует: , и . Рассмотрим некоторые примеры. Пересечением множества целых чисел, делящихся на 2, и множества чисел, делящихся на 3, является множество целых чисел, делящихся на 6. Множество правильных треугольников является пересечением множества всех треугольников с множеством правильных многоугольников.

Название операции пересечения происходит от того факта, что при пересечении множеств точек двух геометрических фигур получают множество точек пересечения этих фигур в обычном смысле слова. Например, прямая линия пересекает круг по хорде . Множество точек этого отрезка является пересечением множества точек прямой с множеством точек круга. Однако операция пересечения применима для любых множеств.

Если у множеств и нет общих элементов, то говорят, что данные множества не пересекаются, т. е. = Ш. Например, пересечением множества чётных натуральных чисел с множеством нечётных чисел является пустое множество.

Замечание: Анализируя определения 1 и 2, можно отметить, что операции объединения соответствует логический союз «или», а операции пересечения – союз «и».

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

Обозначают: . Читают: множество без .

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

В случае если , то разность называется дополнением множества до множества , обозначают: .

Теорема 1: Для любых множеств и следующие утверждения являются равносильными:

1) ;

2) ;

3) .

Доказательство: Докажем сначала, что .

Если , то - очевидно. Докажем второе следствие. По определению операции пересечения множеств имеем: . Нужно получить обратное включение. Если удовлетворяется равенство , тогда , откуда . Если , то . Значит, по свойству антисимметричности отношения включения: . Покажем, что . По определению , но по условию , значит .

Аналогично можно показать, что выполняются и обратные утверждения.

Теорема 2: (свойства операций над множествами): Для любых множеств А, В, С имеют место следующие равенства:

1) ; (идемпотентность);

2) ; (коммутативность);

3) ; (ассоциативность);

4) ; (дистрибутивность);

5) ; .

Доказательство: Доказательства подобных утверждений можно проводить с помощью диаграмм Эйлера-Венна, или с помощью рассуждений. Докажем для примера одно из утверждений (5):

.

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

Пусть , тогда по определению разности: и . Это значит (по определению операции объединения), что и (и ). Последняя ситуация возможна в тех случаях, когда (и ) и (и ). Значит, по определению операции разности: и . Следовательно, . Это показывает, что произвольно выбранный элемент из правой части равенства, принадлежит левой части. Обратное включение – аналогично. Равенство доказано.

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

Определение 4: Пусть - некоторое подмножество универсального множества: . Тогда ту часть универсального множества, которая не содержится во множестве , называют дополнением множества до универсального множества. Обозначают: .

Если , то справедливы следующие очевидные утверждения:

;

;

;

;

;

;

.

Теорема 3: Для любых множеств и имеют место следующие утверждения:

1) ;

2) ;

3) ;

4) (законы де Моргана).

Доказательство: Докажем некоторые утверждения.

1) Покажем, что если произвольный элемент принадлежит левой части, то он принадлежит и правой части равенства и наоборот.

Пусть , это возможно тогда и только тогда, когда . Из последнего по определению разности множеств имеем: и . Значит, по определению дополнения имеем: и . Последнее равносильно тому, что . Следовательно, по определению операции пересечения. Таким образом, выполнено равенство: . Оно означает, что дополнение к дополнению множества , есть само множество .

3) Докажем один из законов де Моргана.

Пусть . Это возможно тогда и только тогда, когда . Используя свойства операций над множествами (теорема 2), преобразуем разность: . Последнее означает, что . Что и требовалось доказать.

Замечание: В теории множеств очень распространённым является соотношение двойственности. Оно заключается в следующем. Если в каждом из перечисленных свойств операций над множествами поменять между собой символы и , и , и , то в результате снова получится одно из этих свойств. Отсюда вытекает, что каждой теореме, которая может быть выведена из перечисленных свойств, соответствует другая, двойственная ей теория.

Теорема 4: Пусть - конечное множество, содержащее элементов: . Тогда множество всех подмножеств множества содержит элементов.

Доказательство: Для доказательства можно использовать свойства биномиальных коэффициентов. Формула бинома Ньютона имеет следующий вид: . Применим её для нашего случая: . Здесь - это число подмножеств, не содержащих элементов (т.е. пустое множество); - это число одноэлементных подмножеств; - число всех двухэлементных подмножеств и т. д., - это само множество . Значения биномиальных коэффициентов могут быть взяты из соответствующих строк треугольника Паскаля. Таким образом, будет посчитано количество всех подмножеств данного множества.

Замечание: Для произвольного множества множество всех его подмножеств часто обозначают .

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

В математике встречаются и другие объекты, кроме множеств, для которых определены операции «сложения», «умножения» и «дополнения», удовлетворяющие свойствам операций над множествами (коммутативность, ассоциативность и др.). Такие системы впервые изучал в 1847 г. английский математик Дж. Буль, поэтому такие системы называют булевыми алгебрами.

Примером булевой алгебры может служить множество всех делителей числа 30. Рассмотрим это множество: и зададим на нём операции сложения и умножения его элементов. Под «сложением» двух делителей будем подразумевать образование их наименьшего общего кратного, а под «умножением» – образование наибольшего общего делителя.

Например, ,. Соотношение означает, что – делитель числа . Роль элемента играет число 1, а роль элемента число 30. Дополнением делителя до универсального множества будем считать элемент . Например, . Дополнение, а также результаты любой операции (объединение, пересечение), должны принадлежать множеству . Это означает замкнутость данного множества относительно основных операций.

Далее можно проверить выполнение всех свойств, перечисленных выше:

1) ; ;

2) ; ;

3) ; ;

4) ; ;

5) ; .

Определение 5: Таким образом, булева алгебра – это непустое множество с тремя операциями , и удовлетворяющими аксиомам (1)-(5).

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

Позже будет установлена связь между булевыми алгебрами и алгеброй логики.

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

,

,

.

Из определения следует, что отображение сохраняет операцию вычитания:

.

Кроме того, изоморфизм переводит нуль и единицу алгебры в нуль, и единицу алгебры :

; .

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

 

 

Прямое произведение множеств. Бинарные отношения.

Пусть и - произвольные элементы. Из элементов и можно образовать двухэлементное множество . Порядок указания элементов в этом множестве может быть… Определение 1: Прямым или декартовым произведением множеств и называется… .

Представление бинарных отношений графами.

Граф представляет собой конечный набор точек плоскости (вершины графа). Часть вершин может быть соединена отрезками со стрелками или без них (дуги и…      

Бинарные отношения эквивалентности

И порядка. Фактор-множество.

В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинарное отношение .… Определение 1: Бинарное отношение называется рефлексивным, если для всякого…

Определение 11: Пусть , - разбиение множества . Определим отношение следующим образом: Элементы поставлены в отношение только в том случае, когда они принадлежат одному классу эквивалентности. Отношение называется бинарным отношением, определённым разбиением .

Теорема 2: Пусть , - разбиение множества , - бинарное отношение, определённое разбиением . Тогда - является отношением эквивалентности и фактор-множество совпадает с разбиением .

Доказательство: По определению: . Тогда условие:

1) - выражает рефлексивность отношения .

2) - выражает симметричность отношения .

3) - транзитивность .

Следовательно, - есть отношение эквивалентности. Тогда, согласно теореме 1, фактор-множество совпадает с разбиением. Теорема доказана.

Определение 12: Пусть , - бинарное отношение, определённое на множестве . Отношение на множестве называется отношением порядка, если оно антисимметрично и транзитивно.

Определение 13: Порядок на множестве называется строгим, если бинарное отношение антирефлексивно. Порядок называется нестрогим, если рефлексивно.

Замечание: Бинарное отношение, обладающее свойствами рефлексивности, транзитивности и антисимметричности, также называют отношением частичного порядка. Множество с заданной на нем частичной упорядоченностью называется частично упорядоченным множеством.

Примеры:

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

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

3) Рассмотрим множество , пусть - множество всех подмножеств множества . Проверим свойства отношения включения. Пусть .

а) - рефлексивность;

б) если и , то - антисимметричность;

в) если и , то - транзитивность.

Значит, отношение включения – это отношение нестрогого порядка.

4) На множестве зададим отношение следующим образом:

(читают: ниже , если - делитель ).

Проверяя свойства этого отношения, легко можно убедиться, что оно является отношением нестрогого порядка.

Определение 14: Отношение порядка на множестве называется линейным (или отношением бинарного порядка), если бинарное отношение связно, т. е. для любых элементов : если , то .

Отношение частичного порядка не является линейным.

Примеры:

1) Отношение < на множестве - строгий линейный порядок.

2) Отношение ≤ на множестве натуральных чисел - это нестрогий линейный порядок.

3) Отношение на множестве - это нестрогий частичный порядок.

Определение 15: Пусть во множестве задана частичная упорядоченность (бинарное отношение ≤). Элементы и этого множества называются сравнимыми, если и .

Не всякие два элемента из множества могут быть сравнимыми, по этой причине мы говорим о «частичной» упорядоченности. Так, например, тривиальная частичная упорядоченность множества задается диагональю , в этом случае только если , разные элементы из множества в этом случае будут несравнимыми.

Определение 16: Пусть - отношение порядка на множестве . Если - отношение частичного порядка и элементы такие, что и , , тогда элементы и называются несравнимыми элементами при заданном порядке .

Определение 17: Частично упорядоченное множество называется линейно упорядоченным или цепью, если любые два элемента этого множества сравнимы, т.е. для любых либо , либо .

Примеры:

1) Множество натуральных, целых, рациональных и действительных чисел в их естественной упорядоченности будут линейно упорядочен­ными множествами.

2) Множество всех подмножеств некоторого данного множества соотношением теоретико-множественного включения будет частично упорядоченным, но не линейно упорядоченным множеством.

Доказано, что всякое частичная упорядоченность может быть продолжена до линейной упорядоченности этого множества, т.е. может быть включена в линейную упорядоченность (в смысле включения бинарных отношений).

 

 

Отображения (функции).

Алгебраические операции.

 

Пусть - некоторые непустые множества, - бинарное отношение, определённое на этих множествах: .

Определение 1: Бинарное отношение называется функциональным отношением или функцией, если для каждого элемента найдётся единственный элемент , такой что . В этом случае пишут: . Множество называют областью определения функции, а множество - множеством значений.

,

.

Функция на множествах и называется также отображением из множества во множество . Обозначают:

- для множеств,

- для элементов.

Определение 2: Два отображения и называются равными, если выполнено условие: .

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

Рассмотрим некоторые свойства отображений.

Определение 3: Пусть . Отображение называется инъективным (или инъекцией), если при этом отображении различные элементы из множества имеют различные образы во множестве :

.

Определение 4: Пусть . Отображение называется сюрьективным (или сюрьекцией), если множество значений совпадает с :

- сюръекция ,

т. е. каждый образ имеет единственный прообраз.

Определение 5: Отображение из множества во множество называется биективным (или биекцией), если оно сюрьективно и инъективно.

Примеры:

1) отображение , такое, что не является биекцией (инъективность и сюрьективность не выполняются). Различные элементы из области определения (например, числа 3 и -3) имеют один и тот же образ. Каждый образ (например, 9) имеет не один, а два прообраза (3 и -3).

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

3) , такое, что является сюрьекцией, но не является инъекцией, следовательно, не биекция.

Замечание: Биективное отображение ещё называют взаимно однозначным отображением.

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

Рассмотрим понятие и свойства обратных отображений (обратных функций).

Определение 6: Пусть , пара тогда и только тогда, когда и . Пара называется обратной (или инверсной) паре . Очевидно, что пара .

Множество всех инверсных пар обозначим: . Имеем: . Из того, что - это функция, ещё не следует, что тоже является функциональным отображением.

Пример: , . Рассмотрим бинарное отношение:

. Из рисунка видно, что - это сюрьективное отображение (функция). Но если построить , то такое образование функцией не будет.

Если , то , а также область определения и множество значений меняются ролями.

Теорема 1: Пусть , тогда - является отображением тогда и только тогда, когда - биекция.

Следствие: Если - биекция, то обратное отображение тоже является биекцией, причём .

Определение 7: Пусть . Всякое отображение называется - арной (- местной) алгебраической операцией.

Отображение для элементов выглядит следующим образом: , причём образ отображения определяется однозначно.

Замечание: Если , то операция – унарная. Если , то – бинарная операция; если - тернарная. Если , то операция будет называться 0 - арная.

Определение 8:0 – арной алгебраической операцией во множестве называется выделение (фиксирование) какого-либо элемента с заранее заданными свойствами.

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

Примеры:

1) , такое, что это унарная алгебраическая операция, которая каждому действительному числу ставит в соответствие противоположное ему число.

2) , такое, что не является алгебраической операцией, т. к. не для всякого действительного числа существует образ (для 0). Но если удалить 0 из множества действительных чисел и рассматривать отображение , где , тогда оно будет унарной алгебраической операцией нахождения обратного элемента.

3) , такое, что это бинарная операция сложения натуральных чисел. Операция сложения будет алгебраической для любых числовых множеств. То же можно сказать и об операции умножения.

4) , такое, что на множестве натуральных чисел не является алгебраической. Результат применения операции (образ) должен принадлежать множеству . Но если взять, например, , полученное число натуральным не является. Значит, операция деления на множестве - не алгебраическая.

5) Рассмотрим - арную операцию: , при которой для элементов характерно отображение . Это операция нахождения наименьшего общего делителя натуральных чисел для числа .

6) На множестве зададим операцию умножения чисел и рассмотрим элемент . Этот элемент относительно операции умножения обладает свойством: . Фиксирование элемента - это 0 – арная алгебраическая операция.

7) Фиксирование элемента , обладающего свойством: - есть 0 – арная алгебраическая операция во множестве целых чисел относительно операции сложения.

Существует тесная связь между отношениями эквивалентности на множестве и отображением множества на произвольное множество .

Определение 10: Пусть . Используя отображение , введём бинарное отношение на множестве следующим образом:

.

Введенное отношение называется отношением равнообразности при отображении .

Теорема 2: Пусть , - отношение равнообразности при отображении , тогда отношение является отношением эквивалентности на множестве .

Доказательство: Необходимо показать, что отношение - рефлексивно, симметрично и транзитивно.

1) Согласно определению отношения равнообразности, . Отсюда следует, что отношение рефлексивно, т. к. образы одного элемента равны между собой.

2) Пусть элементы находятся в отношении . Тогда справедливо следующее рассуждение: , значит, отношение симметрично.

3) Пусть находятся в отношении , т. е. и . Тогда, по определению отношения равнообразности имеем: и . Отсюда, в силу транзитивности отношения равенства получим: . Следовательно, по определению: , что означает транзитивность отношения . Значит, есть отношение эквивалентности на множестве . Что и требовалось доказать.

Рассмотрим теперь связь между отношением частичного порядка и отображением.

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

Определение 11: Если из условия , где следует, что , и наоборот, то отображение называется изоморфным отображением (или изоморфизмом) между множествами и . Сами множества и называются изоморфными частично упорядоченными множествами.

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

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

Теорема 3: Всякое частично упорядоченное множество изоморфно вкладывается во множество всех подмножеств некоторого множества , частично упорядоченное по включению.

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

Если , то из условия будет следовать, что . Это означает, что . Рассмотрим обратные рассуждения. Если , то , значит . Таким образом, соответствие является изоморфным вложением. Теорема доказана.

 

 

Частично упорядоченные множества.

Булевы алгебры.

Определение 1: Пусть - отношение порядка на множестве . Элемент называется наименьшим (наибольшим) элементом множества , если выполнено условие: (для наименьшего элемента); (для наибольшего элемента).

Определение 7: Дистрибутивная решетка с отличными друг от друга 0 и 1, в которой всякий элемент имеет дополнение, называется булевой алгеброй.

Определение 8: Линейно упорядоченное множество, удовлетворяющее условию минимальности (а значит и двум другим условиям, эквивалентным с ним),… Примером вполне упорядоченного множества служит множество натуральных чисел с… Во вполне упорядоченном множестве для всякого элемента существует элемент, непосредственно следующий за . Элемент…

Мощность множества. Сравнение мощностей.

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

Определение 2: Множества, обладающие одинаковой мощностью, называются равномощными (эквивалентными).

Возвращаясь, к примеру, можно отметить, что множество точек любого интервала и прямой – равномощны. Это означает, что на прямой и в интервале… При сравнении мощностей бесконечных множеств удобно пользоваться следующими… Теорема 1 (о мощности промежуточного множества): Пусть , причем , тогда .

Определение 3: Множество, эквивалентное множеству чисел натурального ряда, называется счетным.

Теорема 4: Для того чтобы множество было счетным, необходимо и достаточно, чтобы его элементы можно было «перенумеровать», т.е. представить в форме… . (1) Доказательство: Если множество представлено в форме (1), то достаточно каждому элементу поставить в соответствие его…

Арифметика кардинальных чисел. Ординалы.

Трансфинитная индукция.

Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное… Аналогично определяются операции над мощностями (кардинальными числами) как… Определение 1: Если мощность некоторого множества равна , мощность множества равна , причём и не пересекаются, то…

Определение 3: Если два линейно упорядоченных множества изоморфны, то их называют подобными множествами.

Каждому такому классу поставим в соответствие символ, и будем называть его порядковым типом любого множества данного класса. Порядковый тип линейно упорядоченного множества обозначают . Если множества и… Все множества, имеющие один и тот же порядковый тип , имеют одинаковую мощность, которую обозначают . Таким образом,…

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

Число 0 и все натуральные числа есть конечные порядковые числа.

Определение 6: Порядковые числа называют ординалами.

Если и - два любых ординала, то каждое из следующих соотношений: , , исключает остальные, и одно из них обязательно выполняется.

Покажем, как можно представлять себе некоторые счётные ординалы. На рисунке показано, как можно луч взаимно однозначно отобразить на отрезок так, чтобы при этом сохраняется порядок указания точек. Точкам на луче будут взаимно однозначно соответствовать точки на отрезке . Рассмотрим точку 1 на отрезке . Эту точку уже невозможно занумеровать натуральным числом, для её нумерации нужен новый символ, например .Так принято обозначать трансфинитное число, идущее сразу за всеми натуральными числами. Слово «трансфинитное» происходит от латинских слов: trans-через, finite-конечный.

Перенесем теперь полученные точки на отрезок бесконечного луча. Множество полученных точек также является вполне упорядоченным.

Множество теперь сдвинет полученное множество точек на 1 влево, при этом точки отобразится следующим образом: , ,..., , и т.д.

Получим множество на отрезке луча . Эти точки будем нумеровать трансфинитными числами , ,..., ,..., - так занумеруем точку 2 на луче. Подобным образом получим на луче точки , ,..., . Продолжая таким же образом, получим множество, состоящее из точек занумерованных трансфинитными числами вида , где и - натуральные числа. В итоге у нас снова получилось вполне упорядоченное множество точек на всем луче . На каждом отрезке этого луча есть бесконечно много точек нашего множества. Отобразим снова луч на промежуток . Мы получим множество точек, приближающихся к точке 1, чтобы теперь занумеровать и эту точку понадобится новое трансфинитное число, которое обозначим . А дальше можно построить точки: , ,..., ,..., и даже и т.д.

Таким образом, даже счётные ординалы могут быть устроены достаточно сложно. Из теоремы Цериело следует, что существуют ординалы любой мощности.

Рассмотрим некоторые практические приложения вышеизложенного материала.

Известно, какую важную роль играет в математике метод полной математической индукции. Этот метод можно использовать для доказательства различных математических предложений (равенств, неравенств и т. д.). Метод математической индукции можно применять, если предложение рассматривается во множестве натуральных чисел. Он основан на следующей теореме.

Теорема 1 (принцип математической индукции): Пусть предложение, определённое на множестве натуральных чисел. Если предложение будет таким, что высказывание - истинно, и из истинности высказывания следует истинность высказывания для любого , то предложение выполняется для любого натурального числа .

Доказательство: Допустим, что существуют такие натуральные числа , что ложно. Пусть - наименьшее из этих чисел. Тогда из истинности следует, что . Значит . Из определения следует, что - истинно. Полученное противоречие доказывает теорему.

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

1) База индукции: Проверка истинности высказывания . Если выполняется, то переходим к следующему пункту.

2) Индуктивное допущение: Делается предположение об истинности высказывания для произвольного числа .

3) Индуктивное доказательство: Исходя из условий задачи, нужно показать, что из истинности высказывания следует истинность высказывания .

Если все три пункта пройдены, то делают заключение о том, что предложение принимает истинное значение для всех натуральных чисел .

Замечание: Иногда база индукции начинается не с 1, а с некоторого натурального числа .

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

Теорема 2 (о трансфинитной индукции): Пусть предложение, определённое на множестве порядковых чисел, т. е. - порядковое число. Если высказывание истинно, и из истинности вытекает истинность , где , тогда истинно для всех порядковых чисел .

Доказательство теоремы 2 аналогично доказательству теоремы 1.

Множество натуральных чисел - первый числовой класс.

Определение 7: Вторым числовым классом назовем множество всех порядковых чисел, являющихся наименьшим числом второго класса и наименьшим трансфинитным числом. Можно доказать, что если - число второго класса, то также число второго класса; если - счетное множество чисел второго класса и - наименьшее число, большее всех чисел из множества , то и - число второго класса.

Отсюда следует, что множество порядковых типов второго числового класса несчетно (иначе, первое, следующее число за вторым числовым классом, должно было бы принадлежать этому классу).

Заметим, что порядковые числа принадлежат второму числовому классу, т.е. каждое из них есть вполне упорядоченное счетное множество. Наименьшее порядковое число, следующее за всеми числами второго числового класса, обозначается , а мощность множества второго числового класса обозначается (читается: «алеф одна»).

Определение 8: Мощность вполне упорядоченного множества называется алефом.

Множество алефов есть вполне упорядоченное множество.

Заметим, что арифметика ординалов отличается от арифметики кардинальных чисел. В частности, если и ординалы, то и , и . (например, и, но ) и значит, .

 

Заключение.

«Наивная» теория множеств Г. Кантора, набросок которой мы сделали в этой главе, внутренне противоречива. Приведем пример логического противоречия в теории множеств.

Как правило, множества не являются своими собственными элементами. Но природа элементов множества произвольна, поэтому можно рассмотреть и такие множества, которые содержат себя в качестве одного из своих элементов. Назовем такие множества неправильными, а остальные множества – правильными.

Образуем теперь множество , элементами которого являются все правильные множества. Попробуем выяснить, каким является само множество - правильным или неправильным. Если оно правильное, то оно входит в себя как один из элементов (мы ведь собрали во множестве все правильные множества). Но тогда, по определению, оно является неправильным. Если же множество неправильное, то по определению оно должно быть своим собственным элементом, а среди элементов множества неправильных множеств нет!

Получилось неразрешимое логическое противоречие. Множества, которые кажутся вполне определенным, оказываются неопределенными.

Подобное логическое противоречие обнаружил сам Г. Кантор (см. парадокс Кантора в следующей главе).

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

 

 

Задачи для самостоятельной работы.

2) Обозначим через множество всех дробей со знаменателем : , ,..., . Найти и . 3) Известно, что из 100 студентов в секциях спортклуба занималось: 28 человек - в гимнастической секции; 30 - в…

Глава 2.

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

 

Введение.

 

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

1. Я видел портрет Ползунова. Ползунов – изобретатель паровой машины, следовательно, я видел портрет изобретателя паровой машины.

2. Я видел портрет кого-то; кто-то изобрел колесо; следовательно, я видел портрет изобретателя колеса.

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

Кроме того, богатство языка, наличие синонимов, имеющих разные смысловые оттенки в разных контекстах, не позволяют использовать разговорный язык в строгом логическом анализе. Возьмем, например, фразы «великий русский поэт А. С. Пушкин» и «автор «Евгения Онегина»», определяют ли эти фразы одно и то же? Если это синонимы, то в любом предложении можно заменить одну из этих фраз другой, не меняя смысла предложения.

Возьмем предложение: «Великий русский поэт А.С. Пушкин является автором «Евгения Онегина»» и заменим в этом предложении одну из двух фраз другой, получим предложение: «Великий русский поэт А.С. Пушкин является А.С. Пушкиным». Таким образом, из предложения, имеющего смысл, мы получим предложение, лишенное смысла.

Математическая логика возникла в середине XIX века, но получила мощный толчок для развития в конце XIX века открытием парадоксов теории множеств. Напомним некоторые из парадоксов.

1. Парадокс Рассела (1902): Как правило, множества не содержат самих себя в качестве своего элемента. Например, множество простых чисел не является простым числом. Но так как никаких ограничений на множества не накладывается, то можно представить себе и множества, которые содержат себя в качестве своих элементов. Назовем такие множества неправильными. Таким образом, множество является правильным, если оно не содержит себя в качестве своего элемента.

Пусть – множество всех правильных множеств. Теперь поставим вопрос: будет ли множество правильным или неправильным? Предположим, что – правильное, но все правильные множества являются элементами множества , т. е. тогда содержит себя в качестве одного из элементов, значит множество – неправильное. Предположим, что это так, тогда является элементом , но множество , по определению, содержит лишь правильные множества, и значит, должно быть правильным. Получено логическое противоречие.

2. Парадокс Кантора (1899): С одной стороны множество всех множеств должно иметь наибольшую мощность, с другой стороны, мощность множества всех его подмножеств должна быть ещё большей.

3. Парадокс Бурелли-Форти (1897): Этот парадокс аналогичен парадоксу Кантора, но возникает в теории порядковых (ординальных чисел). Для любого ординального числа существует ординальное число, следующее за ним. Однако ординальное число, определяемое множеством всех ординальных чисел, является наибольшим порядковым числом.

Кроме парадоксов теории множеств существует ещё семантические парадоксы. Рассмотрим наиболее известные из них.

4. Парадокс лжеца: Некто говорит «Я лгу». Если он при этом лжёт, то сказанное им ложь, т.е. он сказал правду. Если же он не лжёт, то сказанное им есть истина, и, следовательно, он лжёт. Т.е. он и лжёт и не лжёт одновременно. С парадоксом лжеца имеет сходство известный ещё в древности «парадокс критянина». Критский философ Эпименид сказал: «Все критяне – лжецы». Если он сказал правду, то, поскольку сам Эпименид критянин, сказанное им есть ложь. Если сказанное им ложь, то существуют критянин, который не лжёт.

5. Парадокс Берри (1906): Существует конечное число слогов в русском языке. Следовательно, имеется лишь конечное число таких фраз русского языка, которые содержат не более пятидесяти слогов. Поэтому с помощью таких фраз можно охарактеризовать только конечное число натуральных чисел. Пусть есть «наименьшее из натуральных чисел, которое не характеризуется никакой фразой русского языка, содержащей не более пятидесяти слогов». Взятая в кавычки фраза характеризует число и содержит менее пятидесяти слогов.

Анализ парадоксов привёл к различным планам их устранения.

Логические парадоксы содержат допущение, что для любого свойства существует соответствующее множество всех элементов , обладающих свойством . Если отвергнуть это допущение, то логические парадоксы становятся невозможными. Так, например, парадокс Рассела зависит от существования множества всех множеств, которые не является элементами самих себя. Поэтому парадокс Рассела доказывает, что такого множества не существует. Парадоксы Кантора и Бурелли-Форти показывают, что не существует универсального «множества всех множеств» и не существует множества всех ординальных чисел. В 1908 г. Цермело построил аксиоматическую теорию множеств. В рамках этой теории логические парадоксы невозможны, а семантические парадоксы даже невозможно сформулировать.

Более глубокое исследование парадоксов было предпринято конструктивистами (Брауэр) и интуиционистами (Гейтинг). С их точки зрения, объект, обладающий некоторыми свойствами, существует только тогда, когда указан метод построения, отыскания такого объекта.

Однако какой бы подход не был избран к проблеме парадоксов, необходимо исследовать язык логики и математики, чтобы разобраться, какие допустимы символы, как из них составлять формулы, утверждения и доказательства, что может и что не может быть доказано, если исходить из различных аксиом и правил вывода. В этом состоянии одна из задач математической логики.

 

 

Основные понятия и определения алгебры

Высказываний.

 

В данном параграфе будет рассмотрена наиболее простая (элементарная) часть логики.

Определение 1:Высказыванием будем называть простое повествовательное предложение, которое что-либо утверждает и может быть либо истинным, либо ложным. Например, предложение: «Луганск стоит на берегу реки Лугань» – истинное высказывание, а «» – ложное.

Определение 2: Высказывание, для которого никакая его часть не является высказыванием, называется простым или элементарным высказыванием, или атомом.

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

Определение 3: Под значением высказывания понимают его истинностное значение (т. е. ложь или истина).

Рассмотрим логические операции над высказываниями. К основным логическим операциям относятся следующие:

Отрицание – обозначается ,читается:«не » или «неверно, что ».

3) Конъюнкция (логическое умножение), обозначаемое (читается «и »). 4) Импликация – обозначается или (читается «из следует», «если , то », «влечёт… 5) Эквивалентность – обозначается или (читается «равносильно », «тогда и только тогда, когда », «для необходимо и…

Формулы алгебры логики. Тавтологии.

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

Доказательство.

Достаточность: Пусть формула в условии теоремы есть тавтология, тогда для любого набора значений пропозиционных переменных, например, , ,..., её…    

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

Основные понятия и определения.

 

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

В логике часто встречаются выражения, грамматически имеющие форму высказываний, но содержащие предметные переменные некоторых множеств. Например, предложение «– простое число» содержит свободную переменную , принимающую значения из множества натуральных чисел. Это множество является допустимым множеством переменной , а элементы множества являются допустимыми значениями переменной . Если заменить любым натуральным числом, то данное предложение превращается в высказывание. Например, «16 – простое число» - это ложное высказывание, а «19 – простое число» - истинное высказывание. В дальнейшем всякое предложение, содержащее свободную переменную, будем называть предикатом.

Определение 1: - местным предикатом, определенным на некотором множестве , называется выражение, содержащее предметные переменные данного множества, и обращающиеся в высказывание при замене переменных любыми элементами данного множества.

Замечание: Если , то предикат называется одноместным, при имеем двуместный предикат и т. д.

Каждое алгебраическое уравнение и неравенство представляет собой предикат. Например, «» - двуместный предикат, определённый на множестве всех пар действительных чисел. Подставив вместо переменных любую пару действительных чисел, получим высказывание (- ложное высказывание, - истинное). Одноместный предикат выражает условие или свойство объекта (например, ), а двуместный предикат – отношение между объектами (например, ). Высказывание принято считать нульместным предикатом.

Для предикатов введём следующие обозначения: - одноместный предикат, - двуместный, - трёхместный. В общем случае будем рассматривать - - местный предикат.

Любое уравнение (или система уравнений) с неизвестными, допустимая область значений которых есть множество действительных чисел, будет – местным предикатом, определенным на множестве действительных чисел. При замене переменных решением уравнения (или системы), получим истинное высказывание; при замене переменных числами, не являющимися решениями, получим ложное высказывание.

Определение 2: Пусть - - местный предикат, определённый на некотором множестве . Если значения такие, что , то говорят, что набор значений удовлетворяют предикату .

Определение 3: Множество всех значений таких, что предикат при этих значениях принимает значение «истина», называется областью истинности предиката.

В этом случае область истинности предиката совпадает с множеством . Определение 5: Предикат , определённый на множестве , называется тождественно… В данном случае область истинности предиката – есть пустое множество.

Операции над предикатами.

 

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

Определение 1: Отрицанием - местного предиката , определенного на множестве , называется новый - местный предикат, определенный на том же множестве. Обозначается: . Читается: «неверно, что ». Предикат принимает значение «истина» только для тех аргументов, для которых значение предиката есть «ложь» и наоборот. Другими словами предикат удовлетворяется теми и только теми аргументами, которые не удовлетворяют данному предикату.

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

Определение 2: Конъюнкцией - местного предиката , определенного на множестве , и - местного предиката , определенного на множестве , называется новый - местный предикат, определенный на множестве , обозначаемый . Читается: «и ». Этот предикат принимает значение «истина» только для тех значений аргументов , для которых предикаты и одновременно принимают значение «истина».

Если, например, - двуместный предикат, определённый на множестве , а - одноместный предикат, определённый на множестве , то конъюнкция этих предикатов есть трёхместный предикат, определённый на множестве . Этот новый предикат принимает значение «истина» для таких троек элементов , , , , для которых и .

Аналогично определяются дизъюнкция, импликация и эквивалентность предикатов. Значения предикатов при заданных значениях свободных переменных определяются в соответствии с конкретными логическими операциями. Операции можно применять также к предикатам, у которых имеются общие переменные. В таком случае число переменных полученного составного предиката будет равняться числу различных переменных у его членов. В частности, если операции применяются к двум - местным предикатам, зависящим от одних и тех же переменных, то в результате применения логических операций получается - местный предикат, зависящий от тех же переменных.

Пусть и – два - местных предиката, зависящих от одних и тех же переменных. Тогда:

а) множество истинности конъюнкции равно пересечению множеств истинности ее членов;

б) множество истинности дизъюнкции равно объединению множеств истинности ее членов.

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

Всякое уравнение (неравенство), содержащее переменные, является предикатом, определённым на том же множестве, на котором задано уравнение (неравенство). Множество решений уравнения (неравенства) есть ничто иное, как множество истинности предиката. Это означает, что при подстановке корней уравнения (или решений неравенства) вместо неизвестных будут получены истинные высказывания. Если же в уравнение (неравенство) вместо переменных подставлять числа, не являющиеся решениями, то будут получены ложные высказывания. Всякая система уравнений (неравенств) может быть рассмотрена, как конъюнкция предикатов. Решить систему – значит найти область истинности конъюнкции предикатов. Совокупность уравнений (неравенств) есть ничто иное, как дизъюнкция предикатов. Равносильность уравнений (неравенств) означает равносильность соответствующих предикатов.

Если , то говорят, что аргумент удовлетворяет данному предикату. Например, число 3 удовлетворяет предикату , а число 1 ему не удовлетворяет.

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

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

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

Например, для предикатов «» и «», определенных на множестве действительных чисел, соответствующие универсальные высказывания будут иметь вид: – «каждое действительное число равно самому себе» (истинное) и – «каждое действительное число больше 2» (ложное).

Теорема 1: Если - одноместный предикат, определенный на конечном множестве, состоящем из элементов ,,…,, то соответствующее ему универсальное высказывание эквивалентно конъюнкции высказываний :

.

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

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

Определение4: Пусть - одноместный предикат, определенный на множестве . Операция, превращающая предикат в высказывание (читается: «существует , удовлетворяющее предикату »), называется квантором существования (или экзистенциональным высказыванием). Высказывание будет истинным тогда и только тогда, когда предикат выполнимый. Это высказывание будет ложным, если предикат тождественно ложный.

Символ называется квантором существования по переменной . Его можно прочитать: «существует такой, что », или «найдётся такой , что ». Символ происходит от английского слова «Exist» (существует).

Теорема 2: Если – одноместный предикат, определенный на конечном множестве из элементов ,,…,, то соответствующее ему экзистенциональное высказывание эквивалентно дизъюнкции высказываний :

.

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

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

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

Если в любом предикате все переменные связаны, то этот предикат является высказыванием. Например, рассмотрим предикат , определённый на некотором числовом множестве. Составим высказывание . Это ложное высказывание, которое утверждает, что найдётся такое число , которое больше всякого числа (- единственное число для всех ). Поменяв местами кванторы, получим новое высказывание: . Это высказывание утверждает, что для любого числа можно подобрать такое число , что выполняется неравенство (для каждого существует своё число ). Это высказывание истинно. Видно, что при перестановке кванторов местами меняется смысл высказывания. Таким образом, перестановка разноимённых кванторов местами является недопустимой операцией. Одноимённые кванторы местами менять можно. Причем, одноимённые кванторы можно объединять в один, например: . Недопустимым является также применение нескольких кванторов по одной и той же переменной, например: .

Определение 5: Универсальным высказыванием, соответствующим - местному предикату , определенному на множестве , называется высказывание, полученное из последовательным применением кванторов общности по переменным в любом порядке.

Обозначается такое высказывание и читается кратко так: «для всех выполняется ».

Определение 6: Экзистенциональным высказыванием, соответствующим - местному предикату , определенному на множестве , называется высказывание, полученное из последовательным применением кванторов существования по переменным в любом порядке.

Полученное экзистенциональное высказывание обозначают и читают так: «существует такой набор , что выполняется ».

Например, для двуместного предиката «» соответствующие высказывания имеют вид: – «для любых двух действительных чисел: первое больше второго» (ложное), и – «существуют два действительных числа, из которых первое больше второго» (истинное).

Теорема 3: (Условие тождественной истинности квантифицированного предиката).

‑ местный предикат, полученный из ‑ местного предиката , определенного на множестве , применением квантора общности по какой–либо переменной является тождественно истинным тогда и только тогда, когда данный предикат – тождественно истинный.

Доказательство: Действительно, пусть дан - местный предикат , определенный на множестве . По определению, этот предикат будет тождественно истинным тогда и только тогда, когда его значение для произвольно взятых значений аргументов есть «истина». Это значит, что истинным является универсальное высказывание , соответствующее одноместному предикату , определенному на множестве . Последнее замечание возможно тогда и только тогда, когда предикат – тождественно истинный, но т.к. аргументы выбирались произвольно, то это равносильно тождественной истинности данного - местного предиката . Теорема доказана.

Теорема 4: (Условие тождественной ложности квантифицированного предиката).

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

Доказательство: Пусть имеем - местный предикат , определенный на множестве . Он будет тождественно ложен тогда и только тогда, когда его значение для произвольно взятых аргументов есть «ложь». Это значит, что ложно экзистенциональное высказывание , соответствующее одноместному предикату , определенному на множестве . Последнее возможно в том и только в том случае, когда предикат тождественно ложен, а т.к. аргументы выбирались произвольно, то и данный - местный предикат тождественно ложен. Что и требовалось доказать.

До сих пор мы противопоставляли предикаты высказываниям. Однако удобнее считать высказывания 0 ‑ местными предикатами. Тогда любые два истинные и любые два ложных высказывания следует считать равносильными между собой.

 

 

Формулы и тавтологии логики предикатов.

При введении определения формул логики предикатов будем использовать следующие обозначения (алфавит): 1) – индивидные переменные, 2) – предикатные буквы.

Формальный язык логики высказываний.

Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или… Определение 1: Формальная (аксиоматическая) теория считается определенной,… 1) Задано счетное множество символов – алфавит теории. Конечные последовательности символов алфавита называются…

Определение 4: Формула называется следствием формул множества тогда и только тогда, когда существует такая последовательность формул , что . И для каждого формула является либо аксиомой, либо формулой из множества , либо непосредственным следствием некоторых предыдущих формул по одному из правил вывода. Такая последовательность называется выводом из множества . Формулы из множества называются гипотезами, или посылками вывода.

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

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

2) а) Каждая пропозиционная буква есть формула.

б) Если и – формулы, то и – тоже формулы.

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

3) Каковы бы ни были формулы теории , следующие формулы есть аксиомы в теории :

(А1) ;

(А2) ;

(А3) .

4) Единственным правилом вывода служит правило modus ponens: «есть непосредственное следствие и ». Это правило будем сокращенно обозначать: Далее будем придерживаться соглашений о сокращении числа скобок.

Отметим, что бесконечное множество аксиом теории задано с помощью всего лишь трех схем аксиом ,,, каждая из которых порождает бесконечное множество аксиом.

Мы строим систему таким образом, чтобы класс всех теорем этой теории совпадал с классом всех тавтологий исчисления высказываний.

Введем в рассмотрение остальные логические операции (связки) с помощью следующих определений:

означает ;

означает ;

означает .

Другими словами, мы выбираем новые названия для некоторых выражений языка теории .

Замечание: Слово «вывод» (или «доказательство») употребляется в двух различных смыслах. Во-первых, оно употребляется как название конечных последовательностей формул теории . Во-вторых, оно означает последовательность предложений разговорного языка (дополненного техническими терминами), о которой предполагается, что она служит достаточно обоснованной аргументацией в пользу утверждения о теории . Мы изучаем язык теории с помощью метаязыка. Этот метаязык можно было бы формализовать, но тогда рассуждения о нём нужно было бы проводить в новом метаязыке и т. д.

Далее будут рассмотрены теоремы формальной теории и «метатеоремы» о свойствах этой формальной теории.

Теорема 1: Для любой формулы в теории формула выводима.

Доказательство: Построим вывод формулы в теории .

1. (схема аксиом (А2)).

2. (схема аксиом (А1)).

3. (из 1 и 2 по правилу вывода ).

4. (схема аксиом (А1)).

5. (из 3 и 4 по правилу вывода ).

Подобным образом доказываются другие теоремы этой теории.

Теорема 2 (метатеорема): Всякая теорема теории есть тавтология.

Доказательство прямого утверждения очень простое. Для примера можно убедиться в том, что каждая аксиома теории есть тавтология. Кроме того, если и – тавтологии, то и является тавтологией. Таким образом, правило modus ponens, примененное к тавтологиям, приводит к тавтологиям. Следовательно, всякая теорема теории есть тавтология.

Можно показать, что верна и обратная теорема, а именно, что каждая тавтология является теоремой теории .

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

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

Отметим, что существуют и другие аксиоматизации теории .

Из непротиворечивости следует существование формулы, не являющейся теоремой теории (например, отрицание любой теоремы).

 

 

Основные понятия о формализации логики

Предикатов. Свойства теорий первого порядка.

Для записи формул логики предикатов используется следующий алфавит: скобки, запятые, символы исчисления высказываний (отрицание , импликация ),… Определение 1: Формулы исчисления предикатов определяются следующим образом: … 1) всякая элементарная формула – есть формула.

Задачи для самостоятельной работы.

1) , 2) , 3) ,

Глава 3.

Булевы функции

(Функции алгебры логики)

 

Основные понятия и определения.

 

С точки зрения алгебры высказываний логические операции полностью характеризуются истинностными таблицами. При этом можно забыть о том, что мы рассматриваем какие-то операции над высказываниями, и иметь дело лишь с самими таблицами. Таблицу можно рассматривать, как способ задания некоторой функции. Таким образом, мы приходим к понятию функции алгебры логики, которое и будем исследовать в дальнейшем. Однако полезно не забывать об указанных интерпретациях логических связок.

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

Будем исходить из счетного алфавита переменных .

Определение 1: Пусть это множество всех функций , переменные которых определены на множестве и таких, что , если . Функции из множества будем называть функциями алгебры логики (или булевыми функциями).

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

Замечание: В общем случае логические переменные могут принимать одно из значений. Такая логика называется - значной логикой. Перечень всех символов составляет алфавит, а сами символы - буквы алфавита.

Определение 2: Функция полностью определена, если задана таблица, содержащая всевозможные варианты значений переменных (наборы) и соответствующие им значения функции.

Из определения следует, что функция полностью определена, если задана таблица:

 

................ ..................

 

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

Определение 3: Будем говорить, что функция существенно зависит от переменной , если найдутся два набора, отличающиеся только - й переменной: и такие, что . Переменная называется существенной для функции . Все переменные, от которых функция не зависит существенно, называются фиктивными.

Определение 4: Число всех переменных, от которых функция зависит существенно, называется порядком функции.

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

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

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

 

0 0
0 1
        1 0
        1 1

 

Функции и называются константами. Функция называется функцией, тождественно равной , а называется отрицанием переменной . Функция называется конъюнкцией (или логическим произведением) и , а дизъюнкцией (или логической суммой) и . Функция – это импликация переменных и . Выражение представляет собой эквивалентность от тех же переменных. Функция - это сложение по модулю 2. Наконец, называется функцией Шеффера (или штрихом Шеффера) от переменных и .

Замечание: Далее вместо символа будем употреблять символ умножения или, как в обычной алгебре, знак этой операции будем опускать. Символы и в дальнейшем будут употребляться для обозначения сложения по , при этом, исходя из определения: .

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

 

 

Определение формулы и суперпозиции.

Пусть имеется счетное множество переменных , где . Рассмотрим конечную или счетную систему функций алгебры логики над этим множеством: . (*) Введем понятие формулы над этой системой функций.

Определение замкнутого класса.

Принцип двойственности.

Пусть – некоторое подмножество множества булевых функций: . Определение 1: Множество называется замыканием множества , если оно содержит… Например, если , тогда, очевидно, .

Многочлены Жегалкина.

Линейные функции. Монотонные функции.

Рассмотрим систему функций: , , , . (***) Суперпозицию функций системы (***) можно преобразовать, пользуясь правилами элементарной алгебры и специальными…

Теорема Поста.

В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для… — класс булевых функций, сохраняющих 0; — класс функций, сохраняющих 1;

Задачи для самостоятельной работы.

2) Сколько имеется различных функций алгебры логики от переменных? 3) Сколько имеется различных функций от переменных, сохраняющих 0 (т.е. равных… 4) Доказать равносильности алгебры логики:

КОМБИНАТОРИКА.

 

Введение.

 

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

Задача считается комбинаторной, если она формулируется следующим образом: дано некоторое конечное множество, состоящее из элементов, из этого множества нужно выбрать подмножество из элементов, , спрашивается, сколькими способами это можно сделать? Комбинаторика работает только с конечными множествами.

Комбинаторика, как самостоятельная дисциплина, возникла в XVI веке, хотя самые первые комбинаторные задачи решались еще в Древнем Китае, а позднее – в Римской империи. Первые задачи комбинаторики касались азартных игр – сколькими способами можно получить данное число очков, бросая две или три кости, или сколькими способами можно вытянуть двух королей из карточной колоды и т.д. Подобные вопросы и явились движущей силой развития комбинаторики и теории вероятностей. Яркий свет в комбинаторике оставили Паскаль, Я. Бернулли, Лейбниц, Эйлер и другие математики.

В ХХ веке комбинаторику стали рассматривать как часть теории множеств, которая изучает различные вопросы, связанные с конечными множествами. Такой подход является естественным с точки зрения классификации основных понятий и задач комбинаторики. Иногда по смыслу задачи становится очевидным, что существует лишь конечное число интересующих нас объектов. Они, как правило, являются определенными комбинациями других объектов, например, букв, чисел, слов и т.д. Отсюда и название самой дисциплины – комбинаторика (от латинского слова combinatio – соединение).

Из сказанного становится понятным, что комбинаторика имеет дело лишь с натуральными числами. Поэтому, может показаться, что она более «элементарна», чем другие разделы математики. Такое впечатление обманчиво.

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

 

 

Правила комбинаторики.

Начнем с основных принципов комбинаторики, т.е. с правил. Существует два общих правила комбинаторики: правило сложения и правило… Правило сложения.

Комбинаторика без повторений.

 

Для построения соответствующих математических моделей комбинаторных задач будем использовать математический аппарат теории множеств. Может случиться, что в данном множестве порядок следования элементов не важен, а важен только состав множества. Но есть задачи, в которых прядок элементов является существенным.

Определение 1:Порядок во множестве из элементов – это нумерация его элементов натуральными числами, т.е. отображение множества на множество .

Определение 2: Множество с заданным на нем порядком называется упорядоченным множеством.

Например, из двух букв и можно построить упорядоченное множество двумя различными способами: и . Три буквы , и можно расположить в виде последовательности шестью способами:

Определение 8: Конечные упорядоченные множества называются размещениями.

. (2) Доказательство. Пусть имеется произвольное множество , состоящее из элементов.… Выбор элементов осуществляется поэтапно. Первый элемент расстановки можно выбрать различными способами. Тогда из…

Определение 10: Конечные неупорядоченные множества называются сочетаниями.

Сочетаний из элементов по элементов должно быть меньше, чем соответствующих размещений. Это следует из того, что не надо засчитывать расстановки… Теорема 4: Число сочетаний находится по следующей формуле: . (4)

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

Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых… , (1) . (2)

Комбинаторика с повторениями.

Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по… Рассмотрим для примера задачу: определить, сколькими способами можно… Таким образом, при решении задач важно точно понимать смысл слов «различные варианты». Нужно выяснить, важен ли…

Определение 2: Группы, составленные из объектов, которые принадлежат одному из типов элементов, называют сочетаниями с повторениями.

Сочетания с повторениями, как было показано в примере, могут быть сведены к перестановкам с повторениями, поэтому имеем формулу: . Доказательство. Пронумеруем элементы исходного множества числами от 1 до . Пусть в одно из сочетаний с повторениями…

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

1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?   2. Собрание из 25 человек выбирает президиум из 3 человек. Первый – председатель, второй – заместитель, третий –…

Список литературы.

 

1) Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971.

2) Клини С. Математическая логика. – М.: Мир, 1973.

3) Гиндикин С. Г. Алгебра логики в задачах. – М.: Наука, 1972.

4) Курош А. Г. Лекции по общей алгебре. – М.: Наука, 1970.

5) И.А. Лавров, Л. Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов, М., Наука, 1975.

6) Р. Л. Гудстейн. Математическая логика (пер. с англ.), М., Ин. литература, 1961.

7) П. С. Новиков. Конструктивная математическая логика с точки зрения классической, М., Наука, 1977.


 

Учебное издание

 

курс лекций

по дискретной математике

(для студентов, специальности “Прикладная математика”,

«Информатика», «Системный анализ»,

«Компьютерные системы и сети»)

 

 

Составители:

Татьяна Николаевна ФЕСЕНКО

Елена Юрьевна ЧАЛАЯ

 

Авторский оригинал-макет

 

Издательство Восточноукраинского национального
университета имени Владимира Даля

 

Адрес издательства :91034, г. Луганск, кв. Молодежный, 20а

Телефон:8 (0642) 41-34-12, факс. 8 (0642) 41-31-60

E-mail: uni@snu.edu.ua http: www.snu.edu.ua

 

– Конец работы –

Используемые теги: курс, лекций, дискретной, математике0.078

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Курс офтальмологии КУРС ЛЕКЦИЙ ТЕМАТИЧЕСКИЙ ПЛАН ЛЕКЦИЙ 1. Введение. Офтальмология и ее место среди других медицинских дисциплин. История офтальмологии. Анатомо-физиологические особенности органа зрения. 2. Зрительные функции и методы их исследования
Курс офтальмологии... КОРОЕВ О А...

Курс лекций к экспериментальной программе: Теория и методика начального курса математики
Педагогический колледж... Курс лекций к экспериментальной программе Quot Теория и методика...

Краткий курс механики в качестве программы и методических указаний по изучению курса Физика Краткий курс механики: Программа и методические указания по изучению курса Физика / С
Федеральное агентство железнодорожного транспорта... Омский государственный университет путей сообщения...

КОНСПЕКТ ЛЕКЦИЙ по курсу Архитектурное материаловедение Конспект лекций по курсу Архитектурное материаловедение
ФГОУ ВПО ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ... ИНСТИТУТ Архитектуры и искусств... КАФЕДРА ИНЖЕНЕРНО строительных ДИСЦИПЛИН...

КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Барабаш В В...

Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... ИНСТИТУТ ЭКОНОМИКИ УПРАВЛЕНИЯ И ИНФОРМАЦИОННЫХ СИСТЕМ В СТРОИТЕЛЬСТВЕ... ИЭУИС...

МАСТЕРСКАЯ ПРАКТИЧЕСКОГО ПСИХОЛОГА КУРС ЛЕКЦИЙ Введение в общую психодиагностику. Курс лекций
ИНСТИТУТ ИНФОРМАТИЗАЦИИ СОЦИАЛЬНЫХ СИСТЕМ... МАСТЕРСКАЯ ПРАКТИЧЕСКОГО ПСИХОЛОГА...

Курс лекций: Элементы дискретной математики
Рис... Если A Igrave В то разность А В называется дополнением множества А до... U А Egrave В Говорят при этом что множество U разбито на два множества на А и Аналогичному разбиению можно подвергнуть множество А или множество или то и...

КУРС ЛЕКЦИЙ по дисциплине Железобетонные конструкции Курс лекций. Для специальностей «Архитектура» и «Промышленное и гражданское строительство»
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ... ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ...

Курс лекций Экономика недвижимости Введение в курс. 3 Глава 1. Недвижимое имущество и его виды
Курс лекций Экономика недвижимости Кафедра Финансовый менеджмент Преподаватель Шаренков С Б...

0.04
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам