Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

UML_4822 дм практикум

.pdf
Скачиваний:
302
Добавлен:
01.06.2015
Размер:
3 Мб
Скачать
☆

I - частноутвердительное высказывание «Некоторые S суть Р»:x(S(x) P(x)), что означает: «Существует такой объект х, обладающий свойством S, который также обладает свойством Р»;

O - частноотрицательное высказывание «Некоторые S не суть Р»:x S x P x , что означает: «Существует такой объект х, который обла-

дает свойством S и не обладает свойством Р».

На основе правил преобразования высказываний и зависимостей между кванторами получены зависимости:

x S x P x

 

x

 

 

 

 

 

 

 

 

x S x

 

;

 

 

 

 

 

 

P x

 

 

S x

P x

 

 

 

(4.27)

x S x

 

 

 

 

 

x S x P x ;

 

 

P x

 

 

(4.28)

 

 

x S x

 

x S x P x ;

 

 

 

P x

 

 

(4.29)

 

 

x S x P x x S x

 

.

 

 

 

P x

 

 

(4.30)

Как видно из приведенных равносильностей, высказывания А и О, а также Е и I являются отрицаниями друг от друга (если одно из них истинно, то другое ложно и обратно) и называются противоположными. Из коммутативности операции конъюнкции следует, что суждения Е и I до-

пускают перестановку предикатов S(x) и P(x), то есть

x S x P x x P x S x ;x S x P x x P x S x .

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

Обычно категорические высказывания сокращенно обозначают совокупностью трех букв SaP, SeP, SiP, SoP, где a, e, i, o указывают на тип высказывания (А, Е, I, О); S и Р - термины, означающие свойства (в таком порядке, в каком они входят в высказывание). Например, непосредственное заключение x(S(x) P(x)) x(S(x) P(x)) в принятых обозначениях запишется как SаP SiP.

Простой анализ показывает, что SiP является логическим следствием SaP, а SoP - логическим следствием SeP. Высказывания SaP и SeP могут одновременно быть ложными, но не истинными и поэтому называются противоречивыми. Высказывания SiP и SoP могут быть одновременно истинными, но не ложными и поэтому называются антипротиворечивыми.

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

141

S

P

S

P

SaP

 

Следствие

S

P

SiP

*

 

S

P

S P

S P

Противоречивые

SeP

Противоположные

Следствие

 

S P

* SoP

Антипротиворечивые

S P

Рис. 24. Логический квадрат

На рис. 24 также приведены диаграммы Венна для каждого из четырех типов высказываний. Они непосредственно вытекают из правых частей выражений (4.27)-(4.30) и теоретико-множественной интерпретации логических операций над предикатами, причем заштрихованные области соответствуют пустым множествам, а отмеченные звездочкой (*) - непустым множествам.

Поскольку каждый из четырех типов высказываний может быть как посылкой, так и следствием, то всего можно образовать 4 4=16 модусов непосредственных заключений с одинаковым положением терминов S и Р в посылках и следствиях. Изменив порядок следования терминов в следствиях (SP на PS), получим еще 16 модусов. Итак, имеется всего 32 существенно различных модусов непосредственных заключений. Анализ (например, с помощью диаграмм Венна) показывает, что только 10 из них являются тавтологиями, то есть правильными модусами. Кроме четырех модусов, в которых посылки и следствия являются одинаковыми высказываниями, и двух модусов, допускающих перестановку терминов (SeP PeS, SiP PiS), правильными являются модусы: SaP SiP, SeP SoP, SaP PiS, SeP PoS.

142

4.8. Простейшие правила вывода

Распространим понятие вывода, введенное в разделе 2, на ЛП следующим образом:

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

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

Пример 253. Построить вывод x (C(x) R(x)), C(a)|-R(a).

Решение.

1.

x (C(x) R(x));

1.

посылка;

2.

C(a) R(a);

2. ? (1);

3.

C(a);

3.

посылка;

4.

R(a);

4.

ПЗ (2,3).

Комментарий.

Чтобы последовательность формул 1-4 была требуемым выводом, необходимо ввести правило вывода, позволяющее из формулы 1 получить

формулу 2, то есть

x P x

, где а - предметная переменная, название эле-

P a

мента из области определения предиката Р(х) (в нашем случае роль предиката Р(х) играет C(x) R(x)). Это правило вывода обосновывается тем, что

|- x Р(x) Р(а).

(4.31)

Действительно, если Р(а) истинно, то импликация (4.31)

истинна.

Если же Р(а) ложно, то ложно и высказывание x Р(x), а следовательно, (4.31) снова истинно.

Это правило, позволяющее вывести единичное высказывание (касающееся одного предмета а) из общего, назовем правилом вывода единичного и обозначим ВЕ.

Теперь вывод заключения R(a) из посылок x (C(x) R(x)) и C(a) за-

пишется следующим образом:

 

 

1.

x (C(x) R(x));

1.

посылка;

2.

C(a) R(a);

2.

ВЕ (1);

3.

C(a);

3.

посылка;

4.

R(a);

4.

ПЗ (2,3).

143

Q x

Пример 289. Построить вывод для формулы x (C(x) R(x)), C(y)|-R(y), являющегося отображением рассуждения «Все целые числа - рациональные; у - целое число; следовательно, у - рациональное число».

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

1.

x (C(x) R(x));

1. посылка;

2.

C(у) R(у);

2.

? (1);

3.

C(у);

3. посылка;

4.

R(у);

4.

? (2,3).

Для получения формулы 2 из 1 необходимо правило вывода

 

x P x

,

 

 

 

 

P y

 

позволяющее вывести логическую функцию из общего высказывания.

Это правило обосновывается

общезначимостью формулы x

Р(x) Р(у), которая легко доказывается. Правило вывода x P x назовем

P y

правилом вывода логической функции и обозначим ВЛ.

Для получения формулы 4 из формул 2 и 3, очевидно, нужно расши-

рить ПЗ на логические функции

P x Q x , P x .

Это правило обосновывается общезначимостью формулы [P(x) Q(x)]P(x) Q(x), получаемой из тождественно истинной формулы ЛВ (p q)p q заменой р на Р(х), q на Q(x).

Впредь ПЗ будем обозначать правило заключения применительно к высказываниям или логическим функциям (высказывательным формам).

Теперь можно записать

вывод

заключения R(y) из посылок

x(C(x) R(x)) и C(y) следующим образом:

1.

x (C(x) R(x));

1.

посылка;

2.

C(у) R(у);

2.

ВЛ (1);

3.

C(у);

3.

посылка;

4.

R(у);

4.

ПЗ (2,3).

4.9. Применение логики предикатов в математике

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

предела числовой последовательности.

Решение. Число а является пределом последовательности (an) тогда и только тогда, когда для любого положительного числа существует такой

144

номер n0, что для всех натуральных чисел, больших или равных n0, справедливо неравенство |an–а| < .

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

a lim an 0 n0 N n N (n n0 | an a | ) . n

Как известно, многие теоремы допускают формулировку в виде условных предложений: «Если любой элемент х из множества М обладает свойством Р(х), то он обладает свойством Q(x)», то есть x (P(x) Q(x)).

Например, если {x} – множество всех треугольников на плоскости, Р(х) – свойство х быть прямоугольным, Q(x) – свойство х иметь гипотенузу, квадрат длины которой равен сумме квадратов длин катетов, то формула x (P(x) Q(x)) дает запись формулировки теоремы Пифагора.

Пример 291. Рассмотрим геометрическое предложение, обычно принимаемое в качестве аксиомы: «Для любых двух точек существует прямая, инцидентная им (проходящая через них)».

Введем следующие предикаты:

Т(х) – «х – точка»;

Р(х) – «х – прямая»;

I(x, y) – «х инцидентна у».

С помощью этих предикатов приведенное предложение запишется так: x y T (x) T ( y) r P(z) I (r, y) .

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

Решение. Пусть М = {x} – множество всех числовых рядов, Р(х) –

свойство х быть сходящимся рядом, Q(x) lim an 0, где an – общий член

n

ряда х. Тогда формула x (P(x) Q(x)) представляет собой формулировку указанной теоремы.

Построение противоположных утверждений

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

Пример 293. Определение предела числовой последовательности дано в примере 290. Противоположным ему утверждением будет:

a lim an 0 n0 N n N (n n0 | an a | ) n

0 n0 N n N (n n0 ) & (| an a | ) .

145

Очевидно, если теорема x М (P(x) Q(x)) несправедлива, то будет истинным утверждение

x М (P(x) Q(x)) x М (P(x) & Q(x)) .

Чтобы доказать несправедливость теоремы достаточно указать хотя бы один элемент из М, при котором условие теоремы Р(х) истинно, а значение Q(x) ложно, то есть привести контрпример.

Пример 294. Докажите, что неверна теорема «Если функция f(x) ограничена на сегменте [a, b], то она и интегрируема на этом сегменте».

Решение. Пусть М – множество всех функций, определенных на сегменте [a, b], Р(х) – свойство f быть ограниченной на [a, b], Q(x) – свойство f быть интегрируемой на [a, b]. Чтобы доказать несправедливость теоремыf М (P( f ) Q( f )) нужно доказать справедливость утверждения

f М (P( f ) & Q( f )). Нужным контрпримером здесь может быть функция

Дирихле, рассматриваемая на [a, b]. Она, как известно, ограничена на любом сегменте, но не интегрируема на этом сегменте.

Прямая, обратная и противоположная теоремы

Рассмотрим четыре теоремы:

x E (P(x) Q(x));

(4.32)

x E (Q(x) P(x));

(4.33)

 

 

 

 

 

 

x E (P(x) Q(x)) ;

(4.34)

 

 

 

 

x E (Q(x) P(x));

(4.35)

Определение. Пара теорем, у которых условие одной является заключением второй, а условие второй является заключением первой, называются взаимно обратными друг другу. Так, теоремы (4.32) и (4.33), а также (4.34) и (4.35) – взаимно обратные теоремы. При этом если одну из них называют прямой теоремой, то вторую – обратной.

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

Так, теоремы (4.32) и (4.34), а также (4.33) и (4.35) являются взаимно противоположными.

Пример 295. Для теоремы: «Если четырехугольник является прямоугольником, то в четырехугольнике диагонали равны» сформулируйте теоремы (4.33)–(4.35).

Решение. Пусть Е = {х} – множество всех четырехугольников на плоскости, Р(х) – свойство х иметь равные диагонали. В сформулированной теореме Р(х) является условием, а Q(х) – заключением. Поэтому теорема (4.33) обратная данной формулируется примерно так: «Если в четырехугольнике диагонали равны, то четырехугольник является прямо-

146

угольником». Теорема (4.34) противоположная прямой, формулируется так: «Если четырехугольник не является прямоугольником, то в нем диагонали не равны». И, наконец, теорема (4.35), противоположная обратной, формулируется так: «Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником».

Нетрудно видеть, что первая и последняя теоремы истинны, а вторая и третья теоремы ложны (приведите контрпример!). Ясно, что прямая и обратная теоремы не равносильны (одна из них может быть истинной, вторая – ложна). Однако легко показать, что теоремы (4.32) и (4.35), а также теоремы (4.33) и (4.34) всегда равносильны.

Необходимые и достаточные условия

Представим теорему формальной записью: x E (P(x) Q(x)).

Множество истинности предиката P(x) Q(x) есть множество

СI P IQ .

Но

тогда

множество

ложности

этого

предиката

будет

С(СI P IQ IP СIQ . Последнее множество будет пустым лишь в случае,

когда

I P IQ .

Отсюда следует, что предикат P(x) Q(x) является ис-

тинным для всех x E тогда и только тогда, когда множество истинности

предиката Р(х) содержится в множестве истинности предиката Q(x), то есть предикат Q(x) является следствием предиката Р(х). При этом предикат Q(x) называют необходимым условием для предиката Р(х), а предикат Р(х) – достаточным условием для Q(x).

Пример 296. Рассмотрим утверждение «Если число х делится на 6, то число х делится на 3». Здесь предикат Р(х): «число х делится на 6», предикат Q(x) – «число х делится на 3». Предикат Q(x) логически следует из предиката Р(х): P(x) Q(x) . Предикат Р(х) (делимость числа х на 6) яв-

ляется достаточным условием для предиката Q(x) (делимость числа х на 3). Предикат Q(x) (делимость числа х на 3) является необходимым условием для предиката Р(х) (делимость числа х на 6).

Часто встречаются ситуации, при которых истинны взаимно обратные теоремы:

x E (P(x) Q(x));

(4.36)

x E (Q(x) P(x)).

(4.37)

Это очевидно возможно при условии, что I P IQ , то есть когда пре-

дикаты Р(х) и Q(x) равносильны (Р(х) Q(x)). В таком случае из теоремы (4.36) следует, что условие Р(х) является достаточным условием для Q(x), а из теоремы (4.37) следует, что условие Р(х) является необходимым для Q(x). Таким образом, в этом случае условие Р(х) является необходимым и достаточным условием для Q(x). Аналогично, условие Q(x) является необходимым и достаточным для Р(х).

147

x1 x2

Пример 297. Рассмотрим теоремы: «В описанном четырехугольнике суммы длин противоположных сторон равны между собой» и «Если в четырехугольнике суммы длин противоположных сторон равны между собой, то этот четырехугольник можно вписать в окружность». Эти теоремы взаимообратные. Следовательно, каждое из условий: «В четырехугольнике суммы длин противоположных сторон равны» и «В четырехугольнике можно вписать окружность» является необходимым и достаточным.

Задача 298. Запишите на языке логики предикатов определения:

1)линейно упорядоченного множества (упорядоченное множество называется линейным, если для любых элементов этого множества х и у либо х = у, либо х < y, либо x > y).

Ответ. x M y M ((x y) (x y) (x y)).

2)ограниченной функции (функция f(x) называется ограниченной на множестве М, если существует такое неотрицательное число L, что для всех x M справедливо неравенство | f (x) | L ).

Ответ. L R x M | f (x) | L .

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

Ответ. x M ( x M) & ( f ( x) f (x)) .

4) периодической функции (функция f называется периодической, если существует такое число Т 0 , что при любом х из области определения f элементы х –Т и х +Т также принадлежат этой области, и при этом выполнено равенство f (x T ) f (x) ).

Ответ. T R \ {0} x M (x T M) & ( f (x T ) f (x)) .

5) возрастающей функции на множестве М (функция f называется возрастающей на множестве M , если для любых чисел х1 и х2, принадлежащих множеству М, из неравенства следует неравенство

f (x1) f (x2 ) ).

Ответ: x1 M x2 M((x1 x2 ) ( f (x1) f (x2 ))).

Задача 299. Пользуясь полученными в задаче 298 формулами, ответьте на следующие вопросы. Что значит:

1)Упорядоченное множество не является линейным?

Ответ. x M y M ((x y) & (x y) & (x y)).

2)Функция не является ограниченной?

| f (x) | L .Ответ. L R x M

3) Функция не является четной?

Ответ. x M ( x M) & ( f ( x) f (x)) .

4) Функция не является периодической?

148

Ответ. T R \ {0} x M (x T M) & ( f (x T ) f (x)) .

5) Функция не является периодической на множестве М?

Ответ. x1 M x2 M((x1 x2 ) ( f (x1) f (x2 ))).

Задача 300. Доказать несправедливость утверждений:

1)«Если функция непрерывна в точке х0, то она и дифференцируема

вэтой точке».

Ответ. f (x) | x |, x0 0.

2)«Если предел n-го члена числового ряда равен нулю, то ряд схо-

дится».

Ответ. Гармонический ряд.

3)«Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником».

Ответ. Равнобочная трапеция.

4)«Если функция интегрируема на a, b , то она непрерывна на нем».

Ответ. Функция y=sgn(x) на [-1, 1].

5) «Если функция интегрируема на a, b , то она монотонна».

Ответ Функция x=y2 на сегменте [1, 1].

6) «Если числовая последовательность имеет предел, то она монотонна».

Ответ. Числовая последовательность с общим членом an ( 1)n 1n .

7) «Если формула логики предикатов выполнима, то она общезначи-

ма».

Ответ. Формула x P(x) , очевидно, является выполнимой, но не

общезначимой.

Задача 301. Для каждого из следующих условий выясните, является ли оно необходимым и является ли оно достаточным для того, чтобы вы-

полнялось неравенство x2 2x 8 0:

 

1)

x 0 ;

3) x 2 ;

5) x 1 и x 10 ;

2)

x 3;

4) x 1 и x 3 ;

6) 2 x 10 .

Ответ. 1)

Условие x 0 является достаточным, но не является не-

обходимым;

x 3 является необходимым, но не является достаточ-

2)

Условие

ным;

 

 

 

3)

Условие x 2 является необходимым, но не является достаточ-

ным;

 

 

 

4)

Условие ( x 1 и x 3 ) является достаточным, но не является не-

обходимым;

5) Условие ( x 1 и x 10 ) не является ни необходимым, ни доста-

точным.

6) Условие ( 2 x 10 ) является необходимым, но не достаточным.

149

Библиографический список

1.Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: Физматлит, 2005.

2.Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ – Петербург, 2004.

3.Эвнин А.Ю. Задачник по дискретной математике. – М.: Книжный дом «ЛИБРОКОМ», 2011.

4.Москитова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях. Учебное пособие. – М.: Логос, 2003.

5.Самойленко А.П., Усенко О.А. Математическая логика и теория алгоритмов в примерах и задачах. Учебное пособие / Под ред. Л.Ф. Беловой. – Таганрог: Изд.-во ТГПИ, 2004.

6.Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БХВ – Петербург, 2006.

7.Шапорев С.Д. Математическая логика. Курс лекций и практических занятий. – СПб.: БХВ – Петербург, 2005.

8.Андерсон Д. Дискретная математика и комбинаторика. Пер. с англ. – М.: Издательский дом «Вильямс», 2004.

9.Редькин Н.П. Дискретная математика. Курс лекций для студентовмехаников: Учебное пособие. 2-е стер. – СПб.: Изд-во «Лань», 2005.

10.Спирина М.С., Спирин П.А. Дискретная математика. – М.: Изд. Центр «Академия», 2004.

11.Плотников А.А. Дискретная математика: Учебное пособие. 2-е изд. – М.: Новое знание, 2006.

12.Палий И.А. Дискретная математика. Курс лекций. – М.: ЭКСМО,

2008.

13.Иванов Б.Н. Дискретная математика. Алгоритмы и программы. Учебное пособие. – М.: Лаборатория Базовых Знаний, 2002.

14.Новиков Ф.А. Дискретная математика для программистов. Учебник для вузов. – СПб.: Питер, 2007.

15.Судоплатов С.В., Овчинников Е.В. Дискретная математика. Учебник. – 2-е изд., перераб. – М.: ИНФРА, Новосибирск: Изд-во НГТУ,

2007.

16.Хаггарт Т., Шлинф Дж. Дискретная математика для программистов; пер. с англ. – М.: БИНОМ. Лаборатория Знаний, 2010.

17.Соболева Т.С., Чечкин А.В. Дискретная математика: учебник для студ. вузов. – М.: Издательский центр «Академия», 2006.

18.Галушкин Ю.И., Марьямов О.И. Конспект лекций по дискретной математике. – М.: Айрис-пресс, 2007.

150

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]