WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

ВВЕДЕНИЕ

Предлагаемое учебное пособие представляет собой первую часть

курса лекций по дискретной математике. Кроме этой части предполагается издание двух частей теоретического материала. Вторая часть будет

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

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

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

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

ВВОДНАЯ ГЛАВА

МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ (ММИ)

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

1) развитием компьютерной техники и компьютерных наук, которые базируются, а по существу являются продолжением дискретной математики;

2) запросами различных прикладных наук – теории управления, экономики, оптимизации и многих, многих других;

3) логикой внутреннего развития этих наук: появлением новых разделов, глубоких интересных проблем, развитием мощных методов их решения.




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

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

Буквой N в дальнейшем мы будем обозначать множество натуральных чисел:

N 1,2,3,..., n,....

N 0 – расширенное множество натуральных чисел, то есть N0 0,1,2,3,..., n,....

Пусть P n обозначает некоторое свойство натуральных чисел.

Теорема 1 (стандартный ММИ) Пусть свойство P верно при n 1 и пусть из истинности P при n k следует его истинность при n k 1. Тогда свойство P верно для любого n N.

Пример Доказать, что nn 1 2... n. (1) Доказательство Метод математической индукции будем оформлять по следующей схеме.

1. Базис индукции: проверим равенство при n 1. Левая часть (ЛЧ)=1, правая часть (ПЧ)= 1. Равенство при n 1, то есть базис индукции, выполняется.

2. Индуктивное предположение: допустим, равенство (1) верно при n k, то есть допустим, что kk 1 2... k. (2) 3. Индуктивный переход: докажем равенство (1) при n k 1, то k 1k есть докажем, что 1 2... k k 1. В самом деле, kk k 1. Здесь мы применили индуктивk k kk 1 k k 1k ное предположение. Далее, k1 k1 2 2 что и требовалось доказать.

На основании ММИ равенство (1) верно при любом n.

Символом n! обозначается произведение n! 1 2 n, где n N.

Например, 5! 1 2 3 4 5 120. По определению полагают 0! 1.

Пример Доказать, что для любого n N n 1 ! 1. (3) 1 1! 2 2!... n n!

Доказательство 1. Базис индукции: проверим утверждение (3) при n 1.

ЛЧ= 1 1! 1, ПЧ= 1 1 ! 1 2! 1 1. Базис индукции доказан.

2. Индуктивное утверждение: допустим, (3) верно при n l, то есть допустим:

3. Индуктивный переход: докажем (3) при n l 1, используя (4), то есть докажем, что 1. Базис индукции: проверим (5) при n 1. ЛЧ=4+15-1=18 делится на 9.

2. Индуктивное предположение: допустим, (5) выполняется при 3. Индуктивный переход: докажем (5) при n m 1, используя (6), то есть докажем, что 4 m 1 15(m 1) 1 делится на 9.

Первая скобка делится на 9 по индуктивному предположению. Осталось доказать, что второй слагаемый делится на 9, то есть надо доказать, что 4 m 5 делится на 3. Это утверждение мы будем доказывать методом математической индукции, то есть нам придется применять "индукцию в индукции". При m=1 4+5=9 делится на 3. Допустим, 4 k делится на 3. Докажем, что 4 k 1 5 делится на 3, но 4 k 4 4 k 5 4 k 5 3 4 k. Первый слагаемый делится на три по индуктивному предположению, а второе – очевидно. Таким образом, мы доказали, что 4 m 5 делится на 3, а вместе с этим, что 4 n 15n 1 делится на 9.





Теперь сформулируем несколько утверждений, эквивалентных ММИ.

Пусть множество A N обладает следующими свойствами.

Пусть свойство Р(n) выполняется при n=1 и из того, что оно верно для любого k n, следует, что Р верно при n. Тогда Р верно при любом натуральном n.

И последнее. Индуктивный процесс не обязан начинаться с 1. В качестве базиса индукции может выступать любое целое число a.

Пусть свойство P(n) выполняется при n=a и из истинности его для любого k a следует истинность для k+1. Тогда P(n) истинно для любого целого n a.

§2. Доказательство неравенств ММИ. Неравенство Коши При n=1 неравенство очевидно: 21. Допустим, 2 k k. Докажем, 2 k k по индуктивному предположению и 2k 1 – очевидное неравенство.

При n=5 получаем верное неравенство 3225. Допустим, неравенство верно при n k 5, то есть 2 k k 2. Докажем, что 2 k 1 k 1.

Это неравенство равносильно 2 k 2 k k 2 2k 1. Если мы докажем, что 2 k 2k 1 k 5, то будет доказано и исходное неравенство. Неравенство 2 k 5 доказываем индукцией (индукция в индукk 1 k ции). При k 5 имеем верное неравенство 32 11. Допустим, неравенство верно при k m, то есть 2 m 2m 1. Докажем при k m 1, то есть докажем, что 2 m 1 2 m 1 1 2m 3 или 2 m 2 m 2m 1 2.

Очевидно, что это неравенство верно в силу индуктивного предположения.

Для любых чисел a1,..., an, b1,..., bn Перепишем это неравенство, частично раскрыв скобки:

Легко заметить, что для того, чтобы доказать это неравенство, достаточно доказать Перенеся все слагаемые в одну сторону, и сгруппировав их, получаем очевидное неравенство:

А это и доказывает неравенство Коши-Буняковского.

1. Число a1 a2... an n называется средним арифметическим чисел a1, a2,..., an.

ним геометрическим чисел a1, a2,..., an.

Шаг первый: сначала индукцией докажем это неравенство для натуральных чисел вида n 2 m. При m=1 надо доказать, что a1 a 2. Это неравенство эквивалентно a1 2 a1a2 a2 0, то чальное верно, так как они равносильны. Допустим, неравенство верно при m=k, то есть Докажем неравенство (1) для m=k+1, то есть докажем, что В самом деле, Итак, мы доказали неравенство Коши, когда количество чисел в средних есть степень двойки. А как быть с остальными? Для них мы докажем неравенство Коши, используя еще одну модификацию индукции – "индукцию вниз". Допустим, что неравенство Коши верно для n=k, то есть допустим, что и докажем это неравенство для n=k-1. Для этого в неравенстве Коши После элементарных алгебраических преобразований получили:

Сократим неравенство на второй множитель правой части:

Неравенство Коши доказано полностью.

ГЛАВА I

АЛГЕБРА ВЫСКАЗЫВАНИЙ

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

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

Под высказыванием мы понимаем предложение русского языка, о котором можно сказать, истинно оно или ложно. Чуть позже станет ясно, почему здесь говорится не об определении, а о понятии высказывания. А в дальнейшем у нас появится возможность дать точное определение высказывания. Высказывания мы будем обозначать заглавными буквами латинского алфавита, возможно с индексами: A, B, X, Y, C1, A4, …. Если высказывание А истинно, мы будем писать А=1; если высказывание А ложно, мы будем писать А=0.

1. А="два умножить на два равно семи"= 2. В="два плюс два равно 4"= 3. С="снег белый"= 4. Д="если сегодня среда, то завтра будет четверг"= 5. Х="если два плюс два равно пяти, то три плюс два равно десяти"=?

6. Y="если после четверга следует пятница, то после пятницы следует воскресенье"=?

7. Z="если 1+1=3, то после четверга следует суббота"=?

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

Существуют, очевидно, предложения русского языка, которые заведомо не являются высказываниями. Например: "Ты пойдешь в кино?", "Отойди от доски!" и т.п.

Но есть предположения, которые по своей структуре очень схожи с высказываниями, но таковыми не являются. Это в дальнейшем и приведет нас к необходимости дать строгое определение высказывания. Рассмотрим следующий пример. Возьмем два листа бумаги, пронумеруем их – номер 1 и номер 2. На первом листе напишем высказывание "На втором листе написана ложь", на втором листе напишем высказывание "На первом листе написана истина". На первый взгляд обычное высказывание, ничем не отличающееся от многих подобных, но...! Задайтесь вопросом, истинно оно или ложно, и Вы увидите, что любое из этих предположений приводит к противоречию, то есть о нем нельзя сказать, истинно оно или ложно. Такие ситуации в математике и семантике называются логическими парадоксами.

Таким образом, предложение, по форме похожее на высказывание, таким не является.

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

1. Из высказывания А можно получить высказывание "неверно, что А". Например, пусть A="2·2=5", тогда получаем высказывание "неверно, что А".

Высказывание "неверно, что А" называется отрицанием А и обозначается A (или ~ A, или A ). Задается действие отрицания с помощью таблицы истинности:

2. Из высказываний А, В можно образовать высказывание "А и В".

Например, "2·2=4 и 5+3=9" Высказывание "А и В" называется конъюнкцией высказываний А и В. Конъюнкция имеет много обозначений: A B, A & B, A B, AB.

Конъюнкция задается с помощью таблицы истинности:

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

3. Из высказываний А, В можно образовать высказывание "А или В". Например, "2·2=4 или 5+3=9".

Высказывание "А или В" называется дизъюнкцией высказываний А и В и обозначается A B.

Дизъюнкция задается с помощью таблицы истинности:

Дизъюнкцию иногда называют логическим сложением, но здесь аналогия "портится" четвертой строчкой.

4. Из высказываний А, В можно образовать следующее высказывание: "А тогда и только тогда, когда В". Например, треугольник является равносторонним тогда и только тогда, когда все его углы равны между собой. Синонимами служат фразы: "А в том и только в том случае, когда В", "А необходимо и достаточно для того, чтобы выполнялось В", "А равносильно В", "А эквивалентно B".

Высказывание "А равносильно В" называется эквивалентностью высказываний А и В и обозначается A B, A ~ B, A B.

Эквивалентность задается таблицей истинности:

5. И, в заключение, определим, пожалуй, самую интересную и самую главную логическую операцию. Из высказываний А и В можно образовать высказывание "если А, то В". Например, если две прямые параллельны третьей, то они параллельны между собой. Синонимами служат следующие фразы: "из А следует В", "В является следствием А", "А влечет В", "А достаточное условие для В", "В необходимое условие для А" и т.п.

Высказывание "если А, то В" называется импликацией высказываний А и В и обозначается A B, A B. В этой ситуации высказывание А называется посылкой, а В – заключением. Задается импликация таблицей истинности:

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

1) если посылка ложна, то импликация всегда истинна, независимо от заключения, то есть 0 B 1 ;

2) если заключение истинно, то импликация также истинна, независимо от посылки, то есть A 1 1.

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

Составим таблицу истинности:

1) Все ли значения истинности А, В, С мы перебрали?

2) Почему эти наборы истинности мы расположили именно в таком порядке, а не в каком-то другом?

3) Что такое таблица истинности?

На все эти вопросы мы ответим в следующем параграфе, но было бы неплохо подумать самостоятельно.

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

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

Обозначаться логические переменные будут заглавными латинскими буквами с индексами или без них: A, B, X, Y, A2, C3,....

Определение 2 (индуктивное определение высказывания) 1. Каждая логическая переменная является высказыванием. Такие высказывания мы будем называть простейшими.

Подумайте, какова роль третьего пункта определения.

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

Первое "высказывание" таковым не является, так как здесь не хватает скобок, а если мы внимательно прочитаем п. 2 определения, то заметим, что каждая операция,,, требует пары скобок – открывающей и закрывающей. Из этого выражения можно сделать два высказывания: A B C и A B C, которые существенно отличаются друг от друга, как мы увидим чуть позже. Второе выражение высказыванием является. Третье выражение высказываем является. Казалось бы, это не так – нет скобок для импликации, но здесь в качестве "скобок" служит отрицание. Четвертое выражение высказыванием не является, оно станет таковым, если поставить внешние скобки:

A B. Наконец, пятое выражение высказыванием является. Этими примерами хотелось бы подчеркнуть два обстоятельства:

1) роль скобок – они играют большую роль при правильном построении высказываний и указывают порядок выполнения этих операций (так же, как в арифметике и алгебре);

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

Если высказывание сконструировано из однотипных операций, то они выполняются в порядке их следования. К примеру, B C являются высказываниями.

A BC D ABC

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

A BC A B CA B A

A BC AB CA B A

A B C A B CA B A

A B C A B CA B A

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

Если высказывание F построено из логических переменных A1, A2,..., An, то мы будем обозначать это так: F F A1, A2,..., An.

Первая основная задача, которая здесь возникает, это вычислить значения истинности F, когда переменным A1, A2,..., An придаются конкретные значения. В этом случае мы пишем: значение F равно F 1, 2,..., n, где i принимают значения 0 или 1. Пример был приведен в §1, поэтому сейчас мы поставим вопрос другой – на каком количестве наборов вообще надо считать значения F A1, A2,..., An.

Другими словами – сколько существует наборов длины n из 0 и 1.

Наборов длины n из 0 и 1 существует 2 n.

Обозначим это количество буквой I n и докажем ММИ, что I n 2 n.

Пусть n=1. Наборов длины 1 из 0 и 1 существует 2: (0) и (1), поэтому I1 21. Базис индукции заложен.

Индуктивный переход. Докажем, что I k 2 k 1. В самом деле, рассмотрим какой-нибудь набор из 0 и 1 длины k, скажем 1, 2,..., k.

Тогда из него можно получить ровно два набора длины k+1, а именно 1, 2,..., k,0 и 1, 2,..., k,1. Значит, наборов длины k+1 в два раза больше, чем наборов длины k, то есть I k 1 2 I k 2 2 k 2 k 1. Теорема доказана.

Существует общепринятый порядок выписывания наборов длины n из 0 и 1. Начинается этот список с нулевого набора – (0,0,..,0,0). Каждый следующий набор получается из предыдущего прибавлением 1 в двоичной арифметике. Заканчивается список единичным набором – (1,1,..,1,1). Тем, кто забыл или не знает двоичной арифметики, сообщаем необходимые и самые простые равенства: 0+0=0, 0+1=1+0=1, 1+1=10.

Составим списки наборов из 0 и 1 длины 3 и длины 4:

Составьте список наборов длины пять.

Таблица истинности для высказывания F A1, A2,..., An имеет вид:

По сути дела, пример таблицы истинности был приведен в §1.

Здесь же мы лишь дали необходимые обозначения и теоретические обоснования. В дальнейшем нам неоднократно придется строить таблицы истинности.

имеет место равенство:

Обозначим F A1, A2,..., An G A1, A2,..., An.

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

A B A B AB

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

Основные логические тождества:

1) A A A – идемпотентность дизъюнкции;

2) A A A – идемпотентность конъюнкции;

3) A B B A – коммутативность дизъюнкции;

4) A B B A – коммутативность конъюнкции;

7) A B C A B A C – дистрибутивность конъюнкции относительно дизъюнкции;

относительно конъюнкции.

A BC AB AC

Необходимо обратить внимание на следующие два тождества. В дальнейшем они будут играть большую роль.

9) A B A B – первый закон Моргана.

A B AB AB

A B AB AB

A A – закон двойного отрицания.

11) A A 0 – закон противоречия.

12) A A 1 – закон исключенного третьего.

13)

A B A BB A

A B AB AB

Тождества, содержащие константы:

17) A 0 A.

18) A 1 1.

19) A 0 0.

20) A 1 A.

21) A 1 1.

22) 1 A A.

23) 0 A 1.

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

27) A AB A.

§4. Дизъюнктивные нормальные формы (ДНФ) В этом параграфе мы докажем, что все высказывания с помощью логических тождеств можно привести к некоторому единообразному стандартному виду, в котором они наиболее эффективно поддаются исследованию.

Достаточно построить таблицу истинности для Aa :

Непосредственно видно, что Aa 1 на тех и только тех наборах, Утверждение доказано.

Конъюнкция логических переменных или их отрицаний называется элементарной конъюнкцией.

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

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

Общий вид ДНФ: K1 K 2... K m, где каждая K i, в свою очередь, является элементарной конъюнкцией.

Второе высказывание не является ДНФ, так как в ДНФ перемножаются лишь переменные или их отрицания. Пятое высказывание не является ДНФ, так как в ДНФ отрицание может располагаться лишь над переменными. Остальные высказывания являются дизъюнктивными нормальными формами.

Любое высказывание равносильно дизъюнктивной нормальной форме (говорят еще так: “Любое высказывание приводимо к ДНФ”).

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

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

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

Очевидно, что это высказывание есть ДНФ.

Допустим, утверждение о приведении к ДНФ доказано для всех высказываний с числом логических операций n k. И докажем теперь его для высказывания F, которое содержит n k 1 логических операций. Опять же, следуя определению высказывания и тому обстоятельству, что в F нет импликаций и эквивалентностей, F представимо в одном из трех видов:

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

Во всех случаях F1 и F2 по индуктивному предположению приводятся к ДНФ, поэтому можно считать, что F1 K1 K 2 K l, F P1 P2 Pm, где K i и Pj – элементарные конъюнкции.

есть F является дизъюнкцией элементарных конъюнкций, то есть ДНФ.

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

Осталось доказать приводимость к ДНФ в третьем случае, то есть Для упрощения выкладок будем считать, что l=2 и каждая элементарная конъюнкция есть произведение двух логических переменных или их отрицаний, то есть F A a B b C c D d.

При доказательстве того, что F приводимо к ДНФ, нам придется воспользоваться следующим простым равенством, которое мы рекомендуем доказать самостоятельно:

Итак, начинаем приводить F к ДНФ:

AC BC AD

случае F приводимо к ДНФ.

Таким образом, теорема доказана.

F AB C C AB A B C C AB

A B C C AB A B C C AB

C AB ABC С A B

AC BC CC A AB B AB

ABC ABCС A B

AC BC AB ABC С ABC CA B AB 1 AB ABC

С B A A A C C AB BC C B A B B C – ДНФ.

Отметим, что доказательство теоремы носит конструктивный характер. В нем указана последовательность действий (алгоритм), которые необходимо производить с высказыванием, чтобы привести его к ДНФ:

избавляемся в F от импликаций и эквивалентностей;

2) используя законы Моргана и закон двойного отрицания, добиваемся того, чтобы отрицания находились лишь над логическими переменными;

3) используя дистрибутивные законы, "раскрываем" скобки и приводим высказывание к ДНФ;

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

F ABC A BC BA BA

ABC AB AC AB AB

ABC ABC AB AB

ABC AB AC AB AB A B CA BA C AB AB

AB AB C A CB A C AB AB

ABC BAA BAC C AA CBA AB AB

ABC AB ABC AC ABC AB AB

Вводя понятие элементарной дизъюнкции, конъюнктивной нормальной формы, можно построить аналогичную теорию для КНФ. Читателю, склонному к самостоятельным изысканиям, предлагаем развить эту теорию самостоятельно.

§5. Построение высказываний по таблице истинности.

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

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

Пусть A, B, C. Рассмотрим элементарные конъюнкции:

A, AB, ABC, BC, B AC, ABC. Лишь третья, пятая, шестая элементарные конъюнкции являются полными относительно X.

Пусть F A1a A2... An – полная элементарная конъюнкция отa носительно множества X A1, A2,..., An. Тогда F содержит в таблице истинности лишь одну единицу, причем на наборе a1, a2,..., an. И наоборот, если в таблице истинности высказывания F имеется лишь одна единица на наборе a1, a2,..., an, то F является полной элементарной Вспомним соотношение: Aa 1 в том и только в том случае, когда a. Итак, пусть A1a A2... An 1, отсюда следует, что для любого i 1,..., n Aia 1, а это значит, что Ai ai. Итак, мы доказали, что полi ная элементарная конъюнкция равна 1 лишь на одном наборе a1, a2,..., an.

Докажем в другую сторону. Пусть F A1, A2,..., An 1 лишь при одном наборе значений Ai ai, i 1,..., n, но по доказанному выше этим же свойством обладает полная элементарная конъюнкция A1 A2... An, значит F A1, A2,..., An Утверждение доказано.

Пусть F A1, A2,..., An – высказывание. Обозначим через I F множество всех наборов a1, a2,..., an, на которых F a1, a2,..., an 1. I F называется множеством истинности высказывания F. Можно записать: I F a1, a2,..., an F a1, a2,..., an 1.

Составим таблицу истинности для F :

Отметим, что множество I F полностью определяет таблицу истинности для высказывания F, так как на остальных наборах, не входящих в I F, F 0.

Чтобы доказать равенство двух множеств, надо доказать, что они состоят из одних и тех же наборов. Возьмем набор a1, a2,..., an I F, значит F a1, a2,..., an 1, следовательно, M a1, a2,..., an N a1, a2,..., an 1.

По определению дизъюнкции M a1, a2,..., an 1 или N a1, a 2,..., a n 1, то есть a1, a 2,..., a n I M или a1, a2,..., an I N, а это и означает, a1, a2,..., an I N, то есть M a1, a2,..., an 1 или N a1, a2,..., an 1, а это и значит, что F a1, a2,..., an 1, следовательно, a1, a2,..., an IF.

Теорема доказана.

Дизъюнктивная нормальная форма называется совершенной (СДНФ), если все составляющие ее элементарные конъюнкции являются полными.

Вторая и четвертая ДНФ являются СДНФ, а первая и третья – нет.

Пусть F A1, A2,..., An – высказывание, не являющееся тождественно ложным, то есть I F 0,тогда Каждое такое высказывание является полной элементарной конъюнкцией, у которой в таблице истинности находится одна 1 на наборе a1, a2,..., an, то есть a1, a2,..., an, следовательно, Эта теорема и отвечает на вопрос, как по таблице истинности строится высказывание.

A B C A B C A B C A B C.

Полученную СДНФ можно упростить, приведя ее к более простой ДНФ:

F A BC ABC ABC ABC AC B B BC A A AC BC.

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

1. Если по цепи С идет ток, то мы будем писать С=1; если же по С ток не идет, то С=0.

2. Если цепь С состоит из двух последовательно подключенных переключателей А и В, то по С идет ток в том и только в том случае, когда включены А и В, то есть С=1 тогда и только тогда, когда А=1 и В=1:

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

3. Аналогично параллельное соединение переключателей моделируется дизъюнкцией:

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

Не давая строгого определения, что такое параллельно-последовательный двухполюсник, приведем пример такого объекта:

Опишем данный двухполюсник формулой алгебры высказываний:

F A BC AC C A AB B ABC AB A C

A B C B B A B AC BC.

Упростив высказывание F, мы построим схему, соответствующую этому более простому высказыванию. Построенная схема будет функционировать так же, как и исходная, но будет устроена, как мы увидим, более просто:

F AB C AC C A CAB AB A C

A B BC B A AC BC

ABC AB ABC A BB A AC BC

BC A A AB AB B AB AC BC

BC AB B AC BC BC AB BAC

B C A AC B C A A A C B C A C B.

Таким образом, исходная схема равносильна схеме:

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

Дан двухполюсник.

Обозначим предложенную сеть символом S(A, B, C).

1. Положим, A=0, B=0, C=0. Непосредственно видно, что нет пути из М в N, проходящего по ребрам A, B, C, поэтому S(0,0,0)=0.

2. Положим, A=0, B=0, C=1. Проверка показывает, что нет пути из М в N по ребрам A, B, C, поэтому S(0,0,1)=0.

3. A=0, B=1, C=0. Есть путь из М в N. Условно его можно обозначить так: B C A C B C. Поэтому S(0,1,0)=1.

Поэтому S(0,1,1)=1.

5. A=1, B=0, C=0. Нет пути из М в N, то есть S (1, 0, 0)=0.

6. A=1, B=0, C=1. S(1, 0, 1)=0.

7. A=1, B=1, C=0. S (1, 1, 0)=0.

8. A=1, B=1, C=1. S (1, 1, 1)=0.

Сети S соответствует таблица истинности:

сильна следующей:

И, в заключение, рассмотрим пример на голосование. Имеется комиссия, состоящая из четырех человек a, b, c, d (а – председатель комиссии). Предложение считается принятым, если за него проголосовало большинство, но председатель обладает следующим преимуществом – правом "вето": если он проголосовал "против", то предложение не принимается, если проголосовал "за", то достаточно, чтобы еще кто-то один поддержал это предложение. Сконструировать схему, в которой сигнал бы зажигался, если предложение принято, и не зажигался в противном случае. Обозначим эту схему через F(a, b, c, d) и построим для нее таблицу истинности:

Значит, abcd abc abc abc abcd abc ab Строим схему голосования:

ГЛАВА II

ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ

§1. Основные определения, терминология Под множеством А мы понимаем совокупность объектов произвольной природы, объединенных общим свойством Р(х).

Обозначение Читается: "А есть множество х, таких, что Р(х)".

Легко заметить, что множество состоит из двух чисел: 1 и 2.

C есть множество всех натуральных чисел. Это множество, как мы уже знаем, обозначается буквой N.

Если х входит в А, то мы говорим, что х есть элемент множества А и обозначаем это так:

В противном случае мы говорим, что х не является элементом множества А и пишем:

Последнее обозначение подчеркивает тот факт, что высказывание " x A " является отрицанием высказывания " x A ".

Множество А называется подмножеством В, если для любого х Обозначение: A B.

Другими словами, символ " A B " есть сокращение для высказывания x A x B.

Для любых множеств А, В, С верно следующее:

Для доказательства а) надо убедиться в истинности высказывания x A, но оно очевидным образом истинно, так как представxA ляет собой импликацию, в которой посылка и заключение совпадают.

Для доказательства б) надо убедится в истинности высказывания Обозначим: " x A " через U, " x B " через V, " x C " через Z. Тогда надо убедиться в истинности высказывания

F U V V Z U

Упростим это высказывание:

FUV V Z U Z

UV UZ VZ U Z

UV UZ VZ U Z

U VU ZV Z U Z

U VU UZ VZ V Z U Z U VZ V Z U Z

UV U UZ Z VZ

UV UZ VZ U Z

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

Множества А и В называются равными, если они состоят из одних и тех же элементов (A=В). Другими словами, обозначение А=В служит сокращением для высказывания x A x B.

Если множество А конечно и состоит из элементов а1,а2,...,аn, то пишем: А={а1, а2,...,аn}.

Иногда подобное обозначение распространяется и на некоторые бесконечные множества. Так, Можно ли подобным образом записать множество Q рациональных чисел? А множество R вещественных чисел?

Вернемся к определению равенства множеств.

{x|x2-3x+2=0} = {1,2}.

Доказательство этого факта основано на том, что эквивалентность Таким образом, для того, чтобы доказать равенство множеств А и В, надо доказать два включения: A B и B A, что часто используется для доказательства теоретико-множественных равенств.

Доказать самостоятельно.

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

Обозначение:.

Отметим, что понятия элемента и множества довольно условны.

Один и тот же объект в одной ситуации может выступать как элемент, а в другой – как множество.

Например, N, Z, Q, R – числовые множества, но в множестве А={N, Z, Q, R} каждое из них является элементом четырехэлементного множества А. В этом отношении достаточно привлекательным является множество x. Отметим, что Xи X одновременно. В связи с этим возникает следующая Существует ли объект X, такой, что X X?

§2. Операции объединения и пересечения Объединением двух множеств А и В называется множество Другими словами, x A B x A x B (теоретико-множественной операции "объединение" соответствует логическая операция "или").

Пусть А={1,2,3,4}, B={2,4,6,8}, тогда A B = {1,2,3,4,6,8}.

Пусть А, В, С – произвольные множества. Тогда:

а) A A A – идемпотентность объединения;

б) A B B A – коммутативность объединения;

в) A B C A B C – ассоциативность объединения;

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

Следовательно, A B C A B C.

вание x тождественно ложно. Следовательно, A A.

тогда и только тогда, когда ложны оба эти высказывания. Следовательно, x A иx B, а значит A B Пусть А, В – произвольные множества, тогда:

есть B A.

Теперь пусть B A. Чтобы доказать равенство A A B, надо доказать два включения: A A B и A B A.

Первое включение – есть пункт а).

Докажем второе включение. Возьмем Следовательно, A B A. Теорема доказана.

Пусть А, В, С – произвольные множества, тогда:

а) A A A – идемпотентность пересечения;

б) A B B A – коммутативность пересечения;

в) A B C A B C – ассоциативность пересечения;

Следовательно, A B B A.

в) Возьмем венно ложное высказывание.

Пусть А, В – произвольные множества. Тогда:

б) Пусть A B A. Возьмем пусть A B. Включение A B A уже доказано.

Докажем включение в другую сторону.

Пусть А, В, С – произвольные множества, тогда:

относительно объединения;

ния относительно пересечения.

б) Предлагается доказать самостоятельно.

Разностью множеств называется множество Пусть А={1,3,4,7,8,9,10}, B={2,3,4,5,6,7}, тогда A\B={1,8,9,10}, B\A={2,5,6}.

Пусть А, В, С – произвольные множества, тогда:

а) Возьмем x A \ A x A x A – тождественно ложное высказывание. Оно равносильно другому тождественно ложному высказыванию x, поэтому A \ A.

Множество U назовем "универсальным", если оно содержит все элементы и все множества являются его подмножествами. Понятие абсолютно универсального множества, то есть множества, для которого истинно высказывание "для любого х x U ", несмотря на кажущуюся его простоту, мгновенно приводит к так называемым теоретикомножественным парадоксам. Поэтому понятие "универсального множества" у нас будет зависеть от круга задач, которые мы рассматриваем.

Довольно часто под универсальным множеством понимают множество R – множество вещественных чисел или множество С – комплексных чисел. Возможны и другие примеры. Всегда в контексте необходимо оговорить, что мы понимаем под универсальным множеством U.

Если U – множество вещественных чисел и А – множество рациональных чисел, то A – множество иррациональных чисел.

Доказать самостоятельно Теорема 6 (законы Моргана для дополнений) Необходимо внимательно следить за тем, какая черточка означает отрицание, а какая – теоретико-множественное дополнение.

Следовательно, A B A B.

Симметрической разностью множеств А и В называется множество A B A \ B B\ A.

Пусть А={1,3,4,7,8,9,10}, B={2,3,4,5,6,7}, тогда A B ={1,2,5,6,8,9,10}.

Пусть А, В, С – произвольные множества, тогда:

б) A B B A – коммутативность симметрической разности;

в) A B C A B C – ассоциативность симметрической разности;

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

в) Предлагается доказать самостоятельно.

Пункты д) и е) предлагается доказать самостоятельно.

множеств пусто тогда и только тогда, когда оба эти множества пусты.

есть, A=B.

Соотношения между множествами наглядно поясняют так называемые круги Эйлера (или диаграммы Венна):

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

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

Упорядоченной парой называется множество (a; b)={{a};{a, b}}.

Если (a; b)=(x; y), то a=x, b=y.

Из (a; b)=(x; y) следует {{a};{a; b}}={{x};{x; y}}.

Равенство двух двухэлементных множеств возможно лишь при равенстве составляющих их элементов. Здесь возможны два случая:

1) {a}={x}, {a; b}={x; y} или 2) {a}={x, y}, {a; b}={x}.

В первом случае из равенства {a}={x} следует а=х, а из второго равенства a; b x; y и того, что а=х, следует у=в, что и требовалось доказать.

Во втором случае из равенства {a}={x, y} следует а=х=у, а из равенства {a; b}={x} следует х=а=в. В частности, а=х и в=у.

Теорема доказана.

Индуктивно определим упорядоченный набор длины n.

1) (a; b)={{a};{a; b}};

2) (a1,a2,...,an,an+1)=((a1,a2,...,an),an+1).

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

Индукция по n.

При n=2 это есть теорема 2. Допустим, утверждение верно при n=k, то есть допустим, что из равенства a1 ; a2 ;...; ak b1 ; b2 ;...; bk следует Докажем теорему при n=k+1.

Декартовым произведением множеств А и В называется множество Пусть A={1;2}, B={a, b, c}, тогда A B {(1;a);(1;b);(1;c);(2;a);(2;b);(2;c)};

а B A {(a;1);(b;1);(c;1);(a;2);(b;2);(c;2)}. Очевидно, что, вообще говоря, B A B A.

множеств;

б) An A A... A - (n cомножителей) – n-aя декартова степень множества А;

Установим связь между декартовыми произведениями и ранее введенными теоретико-множественными операциями.

Пусть А, В, С – произвольные множества, тогда Поскольку в цепочке преобразований не везде стоят эквивалентности, а в одном месте стоит всего импликация, мы доказали включение A B\C сторону.

Если множество А состоит из m элементов, а В – из n элементов, тогда А В состоит из m n элементов.

Доказываем индукцией по числу n-элементов множества В.

A B имеет m=m 1 элементов.

Допустим, теорема верна при n=k. И пусть теперь В состоит из к+ элемента, то есть Первое множество A B состоит из m k элементов по индуктивному предположению, второе множество A bk 1 состоит из m элементов, как отмечалось в базисе индукции. Кроме того, А В состоит из mk+m=m(k+1) элементов, что и требовалось доказать.

а) Множество P A1 A2... An называется n-местным предикатом (отношением) между элементами множеств А1,А2,...,Аn;

б) Если a1, a2,..., an P, то мы говорим, что отношение Р истинно на наборе (a1,a2,...an) и обозначаем Р(a1,a2,...an)=1 или просто Р(a1,a2,...an), если же a1, a2,..., an P, то мы говорим, что P ложно на наборе (a1,a2,...an) и пишем Р(a1,a2,...an)=0 или P (a1,a2,...an).

а) При n=1 P A1 называется одноместным предикатом или свойством, определенным на множестве A1 ;

б) при n=2 Р называется двухместным предикатом или бинарным предикатом или просто отношением;

в) если P A 2, то Р называется отношением между элементами множества А.

1) Пусть A1 Z. Свойство P x Z определяется условием:

Р(х)=1 х – четное число, тогда Р={...;-4;-2;0;2;4;...}.

4) A1 – множество треугольников на плоскости, P x 1 x– равносторонний треугольник.

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

Пусть А1 состоит из n элементов. Сколько разных свойств можно определить на А1?

1) Пусть P Z Z определяется условием: P x, y 1 x y делится на 3;

2) P2 Z Z определяется условием: P x, y 1 x y делится на 3;

P7 x; y В дальнейшем мы будем изучать, как правило, 1- и 2-местные предикаты.

На множестве всех бинарных предикатов можно определить две полезные операции.

IA называется диагональным отношением или отношением равенства или просто равенством на множестве А.

PQ A C x A, z C P Q называется суперпозицией предикатов Р и Q.

A={1,2,3},B={a, b, c},C={x, y, z};

P={(1;a);(1;c);(2;b);(2;c);(3;a)} A B;

Q={(a; x);(a; y);(b; y);(b; z);(c; x);(c; z)} B C;

P Q ={(1;x);(1;y);(1;z);(2;x);(2;y);(2;z);(3;x);(3;y)}=(A C)\{(3;z)}.

A={a, b, c, d}; P={(a; a);(a; b);(a; d);(c; a);(c; b);(d; a)}, тогда P ={(a; a);(b; a);(d; a);(a; c);(b; c);(a; d)}.

б) P P 1 = {(a; a);(a; c);(a; d);(c; a);(c; c);(c; d);(d; a);(d; c); (d;

d)};

в) P 1 P = {(a; a);(a; b);(a; d);(b; a);(b; b);(b; d);(d; a);(d; b); (d;

d)}.

Аналогично доказывается пункт б).

ассоциативность суперпозиции.

Отношение P A A называется отношением эквивалентности, если выполняются три аксиомы:

а) для любого x A P x, x 1 – рефлексивность;

транзитивность.

A Z, P Z Z определяется условием: P x, y 1 x y делится на 3. Проверка выполняется для всех трех аксиом.

а) x x 0 делится на 3, следовательно, P x, x 1.

б) Пусть P x, y 1, то есть x y делится на 3, значит, и в) Пусть P x, y 1, P y, z 1, следовательно, x y делится на 3 и есть P x, z 1.

x y делится на 3. Данное отношение не является отноQ( x, y) шением эквивалентности, так как нарушается уже первая аксиома – рефлексивность, так как не для любого x Z x x делится на 3. Достаточно взять x 2. Проверьте самостоятельно, выполняются ли остальные две аксиомы.

а) Так как для любого x R x x 0 Q, значит, P x, x 1.

P y, x 1. Симметричность выполняется.

следовательно, x y y z x z Q, поэтому P x, z 1. Транзитивность выполняется.

Пусть A – множество мужчин, P A A определяется условием x – брат y. Если договориться, что мужчина сам себе являP x, y ется братом, то P является отношением эквивалентности, так как симметричность и транзитивность выполняется очевидным образом.

Если договорится для отношения эквивалентности P вместо P x, y 1 писать x ~ y, то аксиомы этого отношения перепишутся более простым и обычным образом:

Докажите, что эти условия равносильны следующим отношениям:

Пусть задана система множеств Ai i I, тогда:

Очевидно, что объединение и пересечение конечного числа множеств, например, n, является частным случаем этих определений, когда индексное множество I 1,2,..., n.

Система множеств Ai, i называется разбиением множества A, если Другими словами, различные множества из системы Ai не пересекаются.

Пусть P A 2 – отношение эквивалентности на A. Классом эквивалентности, порожденным элементом a A, называется множество Если P – отношение эквивалентности на A, то множество классов эквивалентности образуют разбиение A.

x a b, то есть x a и x b. По транзитивности a b. Теперь Итак, мы доказали, что любое отношение эквивалентности на множестве A порождает естественным образом разбиение A на классы эквивалентности. Оказывается, имеет место и обратное утверждение.

Пусть система множеств Ai, i I образует разбиение множества A. Отношение P x, y 1 существует такое i, что x, y Ai является отношением эквивалентности на A. Причем элементы разбиения являются классом эквивалентности.

Проверим выполнение всех трех аксиом – рефлексивности, симметричности, транзитивности.

Рефлексивность. Пусть a A, тогда a Ai для некоторого i I.

Транзитивность. Пусть P a,b 1 и P b,c 1, значит, существуют такие i и j, что a, b Ai и b, c A j, но тогда b Ai A j, то есть есть P a,c 1.

Теорема доказана.

Отношение P A 2 называется отношением порядка на множестве A, если выполнены следующие условия:

а) для любого x A P x, x 1 (рефлексивность);

(транзитивность);

в) для любых x, y A, если P x, y 1 и P y, x 1, то x y (антисимметричность).

Если P – отношение частичного порядка, то вместо P x, y принято писать x y. Тогда условия а), б), в) примут вид:

Если на множестве A задано отношение частичного порядка, то оно называется частично упорядоченным множеством и обозначается 1. На множестве N, Z, Q, R задан естественный порядок, который вы изучали еще в школе. Мы его так и будем называть – естественный порядок – и обозначать, как обычно,.

2. Пусть A – произвольное множество и P A x | x A – множество всех подмножеств множества A. На P A определено отношение порядка следующим условием: X Y тогда и только тогда, когда X Y. Очевидным образом выполняются следующие условия:

То есть отношение включения подмножеств есть отношение частичного порядка. Этот пример имеет принципиальное отличие от естественных порядков, рассмотренных в первом примере. В первом примере любые два числа сравнимы по величине, то есть имеет место: для любых x, y x y y x.

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

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

4. На одном и том же множестве можно задать разные отношения порядка. Например, на множестве N кроме естественного порядка можно задать следующее отношение:

m n в том и только в том случае, когда n делится на m, то есть существует x N, такое, что n m x. Докажем, что введенное отношение на N есть отношение частичного порядка.

б) Пусть m l и l n, тогда l m x и n l y, где x, y N, следовательно, n m x, y, то есть n делится на m и m n ;

в) Пусть m n и n m, тогда n m x и m n y. Отсюда следует, что n n x y, поэтому x y 1, а произведение двух натуральных чисел равно 1 только в том случае, когда x y 1, отсюда n m 1, то есть n m. Итак все три свойства – рефлексивность, транзитивность, антисимметричность – частичного порядка выполняются. Значит, отношение делимости на N является отношением частичного порядка.

Это отношение отличается от естественного порядка. Например, 3 5, но неверно, что 3 5, так как 5 не делится на 3.

5. Конечные упорядоченные множества удобно изображать с помощью схем. Проиллюстрируем это двумя примерами.

Пусть A 2,3,4,6,8,9,10. Если на А рассмотреть естественный порядок, то получим схему:

Мы проводим стрелку от a к b, если a b. Стрелку же от 2 к 4 мы не проводим потому, что существование ее гарантируется стрелками от 2 к 3, от 3 к 4 и транзитивностью.

Теперь на том же множестве А рассмотрим отношение делимости, тогда получим схему:

Получим совершенно различные схемы на одном и том же множестве А.

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

Множество A; называется строго частично упорядоченным, если выполняются условия:

а) для любого x A неверно, что x x (антирефлексивность);

б) для любых x, y, z A влечет xy и yz влечет xz (транзитивность);

в) для любых x, y A не могут одновременно выполняться соотношения xy и yx.

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

Если x y есть отношение частичного порядка, то отношение y x y является отношением строгого порядка на А.

а) Высказывание x x x x ложно, так как ложно второе утверждение конъюнкции x x, значит, ложно xx.

б) Пусть xy и yz, это значит, истинно высказывание Из первого и третьего членов этой коньюнкции следует x z. Осталось доказать, что x z. Допустим, x=z, тогда получаем x y y x, то есть x=y, но по условию x y. Это противоречие и доказывает, что xz.

в) Допустим, что выполняется конъюнкция x y y x, то есть x y x y y x y x, но первый и третий член коньюнкции влекут x=y. Противоречие. Значит соотношения xy и yx не могут выполняться одновременно.

Теорема доказана.

Верно и обратное утверждение.

Любой строгий частичный порядок порождает естественным образом просто частичный порядок.

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

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

а) x y x x – эта дизъюнкция истинна, так как истинен ее второй член х=х, поэтому x x.

Первый, второй и третий члены этой дизъюнкции ложны. Первый по свойству в) определения строгого порядка, второй и третий по свойству а). Остается равенство х=у.

Теорема доказана.

§8. Линейно упорядоченные множества.

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

Частично упорядоченное множество A; называется линейно упорядоченным, если выполняется условие:

Для строгого порядка это условие принимает вид:

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

Пусть A; и B; – линейно упорядоченные множества. Определим на A B бинарное отношение следующим образом:

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

множество A B; также линейно упорядочено.

Проверим выполнение всех четырех условий линейной упорядоченности.

а) Рефлексивность. Очевидно, что a, b a, b, так как выполняется второе условие дизъюнкции в определении лексикографического порядка: a a b b.

б) Транзитивность. Пусть a1, b1 a2, b2 и a2, b2 a3, b3. Если довательно, b1 b3 и a1, b1 a3, b3, что и завершает доказательство транзитивности.

в) Антисимметричность. Пусть a1, b1 a2, b2 и a2, b2 a1, b1.

a2 a1, то есть a1 a2. Из второго "слагаемого" дизъюнкции в определении лексикографического порядка теперь получаем b1 b2 и b2 b1.

Следовательно, a1, b1 a2, b2.

г) Сравнимость любых двух элементов множества A B. Пусть a1, b1, a2, b2 A B. Так как A – линейно упорядоченное множество, то для элементов a1, a2 A выполнено одно из трех условий:

a2. В этом случае для элементов b1, b2 B возможно одно из двух:

Таким образом, сравнимость, а вместе с ней и вся теорема, доказана.

Таким образом, если A; – линейно упорядоченное множество, то на множестве А2 естественным образом также возникает линейный порядок – лексикографический. По индукции лексикографический порядок определяется на множестве Аn и по индукции же доказывается, что этот порядок – линейный.

Проиллюстрируем вышеизложенные конструкции примером.

Пусть А 1,2,3. Расположим в лексикографическом порядке возрастания элементы множества A3 :

§9. Экстремальные элементы в частично упорядоченных а) Пусть A; – частично упорядоченное множество. Элемент a A называется максимальным элементом множества A, если не существует b A, такого, что b a. Иногда это определение можно встретить в такой формулировке: для любого b A б) Элемент a A называется минимальным элементом множества A, если не существует элемента b A, такого, что b a или для любого b A Максимальные и минимальные элементы в частично упорядоченных множествах могут существовать, а могут и не существовать, их может быть несколько, как показывают нижеприведенные примеры.

R; – множество вещественных чисел с естественным порядком.

В этом множестве нет ни максимального, ни минимального элементов.

В множестве 0,1 есть максимальный элемент a 1 и минимальный элемент b 0. В множестве 0,1 есть максимальный, но нет минимального элемента, а в множестве 0,1 есть минимальный, но нет максимального элемента.

2,3,4,6,7,12,16,18 ;, где – отношение делимости. Для наглядA ности построим диаграмму этого множества:

Здесь 2, 3, 7 являются минимальными элементами, а 7, 12, 16, 18 – максимальными.

Придумать множество, которое имеет бесконечно много максимальных элементов.

Придумать множество, которое имеет бесконечно много максимальных и бесконечно много минимальных элементов.

Пусть A; – частично упорядоченное множество.

а) Элемент a A называется наибольшим элементом А, если для любого b A a b.

б) Элемент a A называется наименьшим элементом А, если для любого b A a b.

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

Если в частично упорядоченном множестве A; есть наибольший элемент, то он единственный.

A a x, в частности, a b. Аналогично b a. Следовательно, Замечание. Аналогичное верно для наименьших элементов.

Если A; – линейно упорядоченное множество и a – максимальный элемент, то а является наибольшим, а значит, единственным максимальным элементом.

Так как а – максимальный элемент, то не существует b A, такого, что b a. С другой стороны, так как A; линейно упорядочено, то выполняется альтернатива b a b a, поэтому a b, где b – произвольный элемент А.

Теорема доказана.

Пусть A; – частично упорядоченное множество и B A.

а) Элемент a A называется верхней границей множества В, если для любого x B a x. Обозначение верхней границы: a B.

б) Наименьшая из всех верхних границ множества В, если она существует, называется точной верхней границей и обозначается:

a sup B.

в) Элемент a A называется нижней границей множества В, если для любого x B a x. Обозначение нижней границы: a B.

г) Наибольшая из всех нижних границ множества В, если она существует, называется точной нижней границей и обозначается: a inf B.

Рассмотрим R; и 0;1 R. Числа 2, 1, 3, 1000 являются верхними границами множества 0;1, 1 sup 0;1. Числа 0, 1, 5 являются нижними границами множества 0;1, 0 inf 0;1.

Отношение F A B называется функциональным, если выполняется условие однозначности: для любых a;b1 и a;b2, если a;b1, Функциональные отношения называются отображениями, функциями, соответствиями. Для отображения F A B используют запись F : A B. О некоторых других обозначениях отображения будет сказано ниже.

1. Найти все функциональные отношения порядка.

2. Найти все функциональные отношения строгого порядка.

3. Найти все функциональные отношения строгого линейного порядка.

4. Найти все функциональные отношения эквивалентности.

Отметим, что, несмотря на кажущуюся сложность, все эти задачи решаются весьма просто. Например, в первой и четвертой задачах ответом является отношение равенства на A: I A A A, которое определяется условием: a, b I A тогда и только тогда, когда a b.

Пусть F : A B, тогда множество А называется областью отправления F, а B – областью прибытия отображения F. Если пара a; b F, то мы пишем F a b. В этом равенстве элемент b B называется образом элемента a, а элемент a A называется прообразом элемента b.

а) Множество x A существует y B, такой, что F x y называется областью определения F и обозначается D F ;

зывается областью значений F и обозначается V F.

ется образом множества X при отображении F;

б) если Y B, то F 1 Y x D F F x Y называется прообразом множества Y при отображении F.

b F X F Y. Аналогично рассматривается случай a Y. Итак мы доказали, что F X Y F X F Y.

Теперь пусть b F X F Y. Возьмем для определенности b F X, значит, существует a X, такой, что F a b. Из того, что (Словами: прообраз объединения равен объединению прообразов).

Докажем включение в другую сторону.

чит, F X F Y Теорема доказана.

Построим пример, который показывает, что обратное включение, а значит, и равенство, здесь не выполняется. Возьмем Пусть F : A B и G : B C. Суперпозицией отображений G и F называется отображение G F : A C, которое определяется следующими условиями:

Суперпозиция отображений называется еще композицией, или функциональным произведением отображений G и F, или сложной функцией G F x.

(ассоциативность суперпозиции).

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

1) Отображение F называется взаимооднозначным (или однооднозначным), если для любых a1 и a2 из А a1 a2 F a1 F a2.

Другими словами, разные элементы из области определения имеют разные образы.

Такие отображения называются еще вложениями.

2) Отображение F : A B называется отображением "на", если для любого b B существует a A, такой, что F a b, то есть для любого b B имеется в А его прообраз.

Обозначение F : A на B ;

3) Отображение F : A B, которое является одновременно и взаимооднозначным и "на", называется биекцией и обозначается Пусть F x sin x, тогда F x : R R не является взаимнооднозначным и не является отображением "на". Если же записать для F x sin x следующее: F x : R 1;1, то это отображение становится уже отображением "на", не являясь взаимооднозначным. Если же здесь записать F x : 2 ; 2 1;1, то это отображение является биекцией.

R не является взаимооднозначным и не является "на".

R является взаимооднозначным, но не является "на".

имнооднозначным.

Приведенные примеры отображений F : A Bx показывают, что в этой записи большую роль играет не только структура операции F, но также множества А и В.

Весьма большую роль играет понятие "сужения" отображения.

делено условиями:

1) Пусть F : A B – биекция. Обратным отображением F 1 к отображению F называется отображение, которое определяется условиями:

2) Отображение I A : A A определяется следующими условиями:

I A называется единичным или тождественным отображением на Для введенных в определение 14 понятий выполняются свойства, которые мы сформулируем и докажем в теореме.

Пусть F : A B – биекция, тогда:

1) F 1 тоже биекция;

отображения, образ у любого аргумента х при F определен однозначно (свойство однозначности отображений). Поэтому y1 y 2. Докажем, что 1) Докажем, что G F есть отображение "на". Возьмем элемент c C. Так как G есть отображение "на", то существует b B, такой, что G b c. В свою очередь, так как F есть отображение "на", то существует a A, такой, что F a b, поэтому G F a G F a G b c, то есть G F есть отображение "на". Докажем, что G F является G взаимооднозначно, то G b1 G b2, поэтому G F a1 G F a2, то есть G F взаимооднозначно, а поэтому является биекцией.

2) G F отображает множество А на множество С, значит, ние G F является взаимооднозначным, поэтому из равенства G F x1 следует равенство x x1. Мы доказали, что для Теорема доказана.

И, в заключение параграфа, определим на множестве отображений теоретико-множественные операции.

ся согласованными, если для любого x D F1 D F2 F1 x F2 x.

б) Пусть дано семейство отображений Fi : Ai B i I. Семейство Fi i I называется согласованным, если отображения Fi попарно согласованы, то есть для любых i, j I и для любого x D Fi D F j Отметим, что если области определения D Fi попарно не пересекаются, то семейство отображений Fi i I согласовано.

Тогда отображение F1 F2 определяется условиями:

Отображение F1 F2 определяется условиями:

Согласованность гарантирует корректность определений F1 F2 и F1 F2.

ний, тогда есть отображение, определяемое условиями:

индекс из I.

Опять же, согласованность гарантирует корректность этих определений.

Отметим, что F1 и F2 согласованы, так как ; 1 1;0, F семейство отображений F1, F2, F3 согласовано.

F1 F2 F3 всюду определено.

Строим график:

ЛИТЕРАТУРА

1. Гильберт Д., Бернойс П. Основания математики. – М.: Наука, 1979.

2. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986.

3. Мальцев А.И. Алгебраические системы. – М.: Наука, 1970.

4. Мендельсон Н. Введение в математическую логику. – М.: Мир, 1974.

5. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ВВОДНАЯ ГЛАВА

МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ (ММИ)

§1. ФОРМУЛИРОВКИ ММИ. ДОКАЗАТЕЛЬСТВО РАВЕНСТВ................. §2. ДОКАЗАТЕЛЬСТВО НЕРАВЕНСТВ ММИ. НЕРАВЕНСТВО КОШИ.....

ГЛАВА I

АЛГЕБРА ВЫСКАЗЫВАНИЙ

§1. ОСНОВНЫЕ ПОНЯТИЯ. ЛОГИЧЕСКИЕ ОПЕРАЦИИ

§2. ОПРЕДЕЛЕНИЕ ВЫСКАЗЫВАНИЯ. ТАБЛИЦА ИСТИННОСТИ

ДЛЯ ВЫСКАЗЫВАНИЙ

§3. РАВНОСИЛЬНЫЕ ВЫСКАЗЫВАНИЯ. ОСНОВНЫЕ

ЛОГИЧЕСКИЕ ТОЖДЕСТВА

§4. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ)

§5. ПОСТРОЕНИЕ ВЫСКАЗЫВАНИЙ ПО ТАБЛИЦЕ ИСТИННОСТИ.

СОВЕРШЕННЫЕ ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (СДНФ).........

§6. ПРИЛОЖЕНИЕ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ К ИССЛЕДОВАНИЮ

ЭЛЕКТРИЧЕСКИХ ДВУХПОЛЮСНИКОВ

ГЛАВА II

ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ

§1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ, ТЕРМИНОЛОГИЯ

§2. ОПЕРАЦИИ ОБЪЕДИНЕНИЯ И ПЕРЕСЕЧЕНИЯ

§3. РАЗНОСТЬ МНОЖЕСТВ, ДОПОЛНЕНИЕ, СИММЕТРИЧЕСКАЯ РАЗНОСТЬ

§4. ДЕКАРТОВЫ ПРОИЗВЕДЕНИЯ

§5. ПРЕДИКАТЫ

§6. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ

§7. ОТНОШЕНИЕ ПОРЯДКА

§8. ЛИНЕЙНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВА.

ЛЕКСИКОГРАФИЧЕСКИЙ ПОРЯДОК

§9. ЭКСТРЕМАЛЬНЫЕ ЭЛЕМЕНТЫ В ЧАСТИЧНО УПОРЯДОЧЕННЫХ

МНОЖЕСТВАХ И ПОДМНОЖЕСТВАХ

§10. ОТОБРАЖЕНИЯ

ЛИТЕРАТУРА



 







 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

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