Методические рекомендации по изучению дисциплины (стр. 2 )

Принцип индукции, а следовательно, и метод полной математической индукции может применяться и в другой (эквивалентной, рассмотренной выше) форме: утверждение Р(п), зависящее от натурального параметра п, считается доказанным, если это утверждение верно для п = 0 и, для любого натурального числа k>0, из того, что оно истинно при всех , следует, что оно истинно и при п = к + 1.

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

Q(0); Q(1); …; Q(t); …,

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

Индуктивное определение – это определение понятия Р(п), которое зависит от натурального параметра п, осуществляющееся по следующей схеме: понятие Р(0) определяется непосредственно, далее на основе предположения о том, что для любого натурального числа к>0, из того, что понятие Р(к) определено для всех к £ п, формулируется правило, позволяющее определить понятие Р(к + 1).

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

Пример Пусть g(x) и h(x; y; z) – всюду определенные числовые функции. С использованием этих функций определим новую числовую функцию f(x; y) по следующим правилам. Для данного фиксированного х Î N, полагаем:

Шаг 0 f(x; 0) = g(x).

Предполагаем, что функция f(x; к) определена для всех к £ п.

Шаг п + 1 Положим f(x; п + 1) = h(x; п; f(x; п)).

Таким образом функция f(x; у) определяется индуктивно, по схеме:

(1)

в которой роль параметра индукции играет второй аргумент у, при любом фиксированном х. Согласно этой схеме, для того чтобы вычислить значение f(x0; 3), последовательно вычисляем:

(2)

Система равенств (2) показывает, что для вычисления значения f(x0; 3) необходимо предварительно вычислить f(x0; 0); f(x0; 1); f(x0; 2).

Пример Пусть , – числовые функции ( зависит от у фиктивно). Найдем функцию f(x; у), которая получается по схеме (1) из функций g(x) и h(x; y; z). Схема (1) в этом конкретном случае примет вид:

(3)

так как, согласно второй строке схемы (1), при вычислении f(x; у +1) значение f(x; у) подставляется в функцию h(x; y; z) вместо переменной z. Чтобы сделать мотивированное предположение о аналитическом представлении функции f(x; у), вычислим (подобно тому, как это было сделано в (2)) несколько значений функции f(x, y) при фиксированном х:

(4)

Система равенств (4) позволяет сделать предположение о том, что схема (3) задает функцию:

. (5)

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

а) Базис индукции (у = 0) имеет место, согласно первой строке системы равенств (4).

б) Индукционное предположение (y £ k). Предположим, что для всех y, не превосходящих k.

в) Индукционный шаг (у=к+1). Докажем, что .

Действительно, согласно второй строке схемы (3) имеем:

. Таким образом , что и требовалось доказать.

Упражнение Выявить индуктивные схемы, аналогичные схеме (2), которые лежат в основе определения числовых функций:

а) ;

б) ;

в) .

Упражнение По данным числовым функциям g(x) и h(x; y; z), используя схему (1), определить функцию f(x, y)

а) ;

б) ;

в) ;

г) .

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

а) непосредственным образом задаются некоторые исходные объекты (объекты шага 0);

б) указываются некоторые конкретные правила (правила образования), позволяющие из ранее определенных объектов (объектов шагов 0; 1; …; t) получать новые объекты (объекты шага t+1);

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

Каждое из правил образования представляет собой операцию, применение которой на шаге (t+1) к конечной упорядоченной последовательности объектов, полученных на предыдущих шагах 0;1;…;t дает новый объект, определяемой совокупности. При этом предполагается, что каждый объект шага (t+1) получается из объектов шагов 0;1;…; t применением к ним не более чем одного правила образования. Отсюда следует, что всякий объект шага t будем объектом шага t/ для каждого t/ >t.

Предположим, что посредством индуктивного определения задается класс объектов Т. Если множество исходных объектов обозначить через Т0, а через Тt (t >0) множество объектов построенных на шаге t (т. е. объектов шага t), то .

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

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

Шаг 0 Множества объявляются множествами класса Т (т. е. данные множества берутся в качестве исходных объектов, ).

Предполагая, что каждое из множеств М1 и М2 получено на одном из шагов с номерами (т. е. ), переходим к следующему шагу.

Шаг (t + 1) Множества, полученные из множеств М1 и М2 не более, чем однократным применением к ним одной из операций , т. е. множества:

(); (); (); М1; М2

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

В частности, множества:

(); (); А4; ();

получаются на первом шаге, а множества

; ; ; А6

получаются на шаге с номером два.

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

Отметим, что одно и то же множество, впервые появившись на шаге с номером t будет появляться и на всех последующих шагах t+1; t+2; … . Тем не менее, в соответствии с определением сложности объекта из класса Т,

; ; .

Свойства теоретико-множественных операций. Диаграммы Эйлера-Венна

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

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

Теорема Имеют место следующие равенства:

- коммутативность операций ;

- ассоциативность операций ;

дистрибутивность опера-ций и относительно друг друга;

-

- идемпотентность операций ;

- законы де Моргана;

- законы поглащения;

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

Доказательство: Равенства 1 – 15 доказываются применением метода включений. Продемонстрируем использование этого метода на доказательстве равенства 9. Для доказательства равенства нужно доказать два включения:

а) ;

б) ;

а) Пусть и и и и ;

б) Пусть и и и и . ÿ

Рисунок 1.4.1

Упражнение Доказать равенства 1) – 8); 10) – 15), приведенные в теореме.

Упражнение Доказать равенства, используя метод включений:

а) ;

б) .

Результаты применения теоретико-множественных операций к множествам А и В можно наглядно проинтерпретировать на, так называемых, диаграммах Эйлера – Венна. Для этого множества А и В изображаются на плоскости в виде геометрических фигур. Чаще всего для этой цели выбираются эллипсы или окружности. В качестве элементов множеств рассматриваются точки плоскости, попавшие внутрь фигуры или на ее границу. Тогда, если множества изображены так, как это сделано на рисунке 1.4.1 а), то изображения для ; ; будут иметь вид, данный на рисунке 1.4.1 б), в), г).

Для наглядности соответствующие части диаграмм заштриховываются (или затушевываются).

Пример Построим диаграммы Эйлера – Венна для множеств:

а) ;

б) .

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

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

Рисунок 1.4.2

б) Приведем конечный результат (смотри рисунок 1.4.3).

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

Пример Обоснуем, используя диаграммы Эйлера – Венна, равенство .

Диаграмма, соответствующая левой части этого множества изображена на рисунке 1.4.4 а). Диаграмма, соответствующая правой части – на рисунке 1.4.4 б).

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

Упражнение Построить диаграммы Эйлера – Венна, соответствующие данным множествам:

а) ;

б) .

Рисунок 1.4.4

Упражнение Обосновать используя диаграммы Эйлера – Венна следующие равенства:

а) ;

б) .

Алгебра высказываний

Высказывания и логические операции над ними

Под простым высказыванием понимается простое повествовательное предложение, относительно которого можно с полной определенностью утверждать, что оно является или истинным или ложным, но не может быть одновременно и тем и другим. Примерами простых высказываний могут служить следующие предложения: «Число 8 является четным.»; «Город Павлодар расположен на берегу реки Лена.»; «Число π больше 3.»; «Река Иртыш впадает в Каспийское море.»; «Лондон – столица Англии.», при этом первое, третье и пятое из них являются истинными, а второе и четвертое – ложными. Предложения: «Пойдешь ли ты в театр?»; «Сегодня хорошая погода.»; «Я лгу.»; «Геометрическое место точек, равноудаленных от данной точки, называется окружностью.» не являются простыми высказываниями. Первое из них – вопросительное предложение. Утверждение о том, что оно истинно (ложно) лишено всякого смысла. Второе предложение носит субъективный характер: одни могут утверждать, что это высказывание истинно, другие – ложно. Третье предложение не является высказыванием, в силу своей внутренней противоречивости (если утверждать, что оно истинно, то согласно его смысла оно должно быть ложным и, наоборот, из предложения о его ложности вытекает, что оно должно быть истинным). И, наконец, последнее предложение не является высказыванием, как и любое другое определение.

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

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

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

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

К примеру, из высказываний: «При температуре 00С лед не тает.» и «При температуре 00С вода не замерзает.» можно построить такие новые высказывания:

1 «При температуре 00С вода не замерзает и при температуре 00С лед не тает.»;

2 «При температуре 00С лед не тает тогда и только тогда, когда при температуре 00С вода не замерзает.»;

3 «Если при температуре 00С вода не замерзает, то при температуре 00С лед не тает.»;

4 «Неверно, что при температуре 00С вода не замерзает.»;

5 «При температуре 00С вода не замерзает или при температуре 00С лед не тает.».

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

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

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

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

С этих позиций на простые высказывания можно будет смотреть как на переменные, а на сложные высказывания, как на некоторые функции от этих переменных, область значений которых также содержится в множестве {и; л}. При таком подходе свойство высказываний представлять «истину» или «ложь» не будет зависеть от их сложности. В соответствии с этим, понятие «простое высказывание» примет относительный характер (т. е. в качестве исходных можно будет взять любые высказывания и получать из них «более сложные»).

В число исходных высказываний обычно включаются также логические константы: л и и.

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

А; В; С; …; Х; У; …; А1; А2; …; Х1; Х2; Х3; … .

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

&	Ú	→	↔	┐
«и»	«или»	«если …, то …»	«… тогда и только тогда …»	«не …»
конъюнкция	дизъюнкция	импликация	эквиваленция	отрицание

Таблица 2.1.1

Операции Ú и & называются также логической суммой и логическим произведением соответственно.

Определение 2.1.1 Пусть А и В – произвольные высказывания, тогда:

а) конъюнкцией высказываний А и В называется высказывание (А & В), которое является истинным тогда и только тогда, когда высказывания А и В одновременно являются истинными;

б) дизъюнкцией высказываний А и В называется высказывание (А Ú В), которое является истинным тогда и только тогда, когда хотя бы одно из высказываний А или В является истинным;

в) импликацией высказываний А и В называется высказывание (А → В), которое является ложным тогда и только тогда, когда высказывание А является истинным, а высказывание В – ложным. Высказывание А называется посылкой, а высказывание В заключением импликации (А → В);

г) эквиваленцией высказываний А и В называется высказывание (А ↔ В), которое является истинным тогда и только тогда, когда высказывания А и В принимают одинаковые истинностные значения, т. е. одновременно являются ложными или одновременно – истинными.

д) Отрицанием высказывания А называется высказывание ┐А, которое является истинным тогда и только тогда, когда высказывание А является ложным.

Логические операции &, Ú, →, « применяются к двум высказываниям. В соответствии с этим, они называются двухместными или бинарными. Логическая операция ┐применятся к одному высказыванию и, в связи с этим называется одноместной или унарной.