Логика. Все лекции

§2. Кванторные операции.

Рассмотрим операции, преобразующие предикаты в высказывания.

Пусть имеется предикат P(x) определенный на множестве M . Если “а” – некоторый эле-

мент из множества M , то подстановка его вместо x в предикат P(x) превращает этот предикат в

высказывание P(a) . Такое высказывание называют единичным. Например, f (x) : “ x – четное

число” – предикат, а f (6) - истинное высказывание, f (3) – ложное высказывание.

Это же относится и к n –местным предикатам: если вместо всех предметных переменных

xi ,i =1, n подставить их значения, то получим высказывание.

Наряду с образованием из предикатов высказываний в результате таких подстановок в логике предикатов рассматриваются еще две операции, которые превращают одноместный предикат в высказывание. Эти операции называются операциями квантификации(или просто квантификацией, или связыванием кванторами, или навешиванием кванторов). При этом рассматриваются, соответственно, два типа так называемых кванторов.

1.1 Квантор всеобщности.

Определение 7. Пусть P(x) – предикат, определенный на множестве M . Под выражением "xP(x)

понимают высказывание, истинное, когда P(x) истинно для каждого элемента x из множества

M , и ложное в противном случае. Это высказывание уже не зависит от x . Соответствующее ему словесное выражение звучит так: “Для всякого x P(x) истинно ”.

Символ " называют квантором всеобщности (общности). Переменную x в предикате P(x) называют свободной (ей можно придавать различные значения изM , в высказывании же

"xP(x) x называют связанной квантором всеобщности.

1.2 Квантор существования.

Определение 9. Пусть P(x) -предикат определенный на множестве M . Под выражением $xP(x)

понимают высказывание, которое является истинным, если существует элемент x Î M , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x . Соот-

ветствующее ему словесное выражение звучит так: “Существует x , при котором P(x) истинно.”

Символ $ называют квантором существования. В высказывании $xP(x) переменная x связана

этим квантором (на нее навешен квантор).

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве M задан двухместный предикат P(x, y) . Применение кванторной операции к предикату

по переменной x ставит в соответствие двухместному предикату одноместный пре-

дикат "xP(x, y) (или одноместный предикат $xP(x, y) ), зависящий от переменной y и не завися-

щий от переменной x . К ним можно применить кванторные операции по переменной y , которые приведут уже к высказываниям следующих видов:

"y"xP(x, y),$y"xP(x, y),"y$xP(x, y), $y$xP(x, y).

3

Рассмотрим предикат P(x) , определенный на множестве M = {a1,...,an} , содержащем конеч-

ное число элементов. Если предикат P(x) является тождественно-истинным, то истинными будут высказывания P(a1), P(a2 ), ..., P(an ) . При этом истинными будут высказывания "xP(x) и конъюнкция

P(a1) Ù P(a2) Ù...Ù P(an ) .

Если же хотя бы для одного элемента ak Î M P(ak ) окажется ложным, то ложными будут

n

высказывание "xP(x) и конъюнкция Ù P(ai ) . Следовательно, справедлива равносильность i=1

n

"xP(x) º P(a1) Ù P(a2) Ù...Ù P(an ) = Ù P(ai ) . i=1

Численные кванторы.

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

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

Пусть n = 1 . Предложение “По меньшей мере один объект обладает свойством P ” имеет тот же смысл, что и предложение “Существует объект, обладающий свойством P ”, т.е.

(*)

Предложение “не более чем один объект обладает свойством P ” равнозначно предложению “Если есть объекты, обладающие свойством P , то они совпадают”, т.е.

"x"y(P(x) Ù P( y) Þ x º y). (**)

Предложение “один и только один объект обладает свойствомP ” равнозначно конъюнкции вышеуказанных предложений (*) и (**).

1.3 Отрицание предложений с кванторами.

Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу “не”. Например, отрицанием предложения “Река x падает в Черное море” является предложение “Река x не впадает в Черное море ”. Годится ли этот прием для построения отрицаний предложений с кванторами? Рассмотрим пример.

Предложения “Все птицы летают ” и “Все птицы не летают ” не являются отрицаниями друг друга, т. к. они оба ложны. Предложения “ Некоторые птицы летают ” и “ Некоторые птицы не летают ” не являются отрицанием друг друга, т. к. они оба истинны. Таким образом , предложения , полученные добавлением частицы “не” к сказуемому предложений “Все x суть P ” и “Некоторые x суть P ” не являются отрицаниями этих предложений. Универсальным способом построения отрицания данного предложения является добавление словосочетания “наверно, что” в начале предложения. Таким образом, отрицанием предложения “Все птицы летают” является предложение “Неверно, что все птицы летают”; но это предложение имеет тот же смысл, что и предложение “Некоторые птицы не летают”. Отрицанием предложения “Некоторые птицы летают” является предложение “Неверно, что некоторые птицы летают”, которое имеет тот же смысл, что и предложение “Все птицы не летают”.

Условимся отрицание предложения "x(P(x)) записывать как "x(P(x)) , а отрицание предло-

жения $x(P(x)) – как $x(P(x)) . Очевидно, что предложение "x(P(x)) имеет тот же смысл, а следова-

4

тельно, то же значение истинности, что и предложение $x(P(x)) , а предложение $x(P(x)) – тот же

смысл, что "x(P(x)) . Иначе говоря, "x(P(x)) равносильно $x(P(x)) ; $x(P(x)) равносильно "x(P(x)) .

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

предикатов высказывание и его отрицание:

1)каждый мальчик сидит с девочкой;

2)есть мальчик, который сидит один;

3)есть две девочки, которые сидят вместе;

4)мальчики и девочки сидят парами;

5)нет девочки, которая сидит одна; каждая девочка сидит с мальчиком.

5

Лекция 5. Операции над предикатами. Описание математических понятий с помощью логики предикатов.

§3. Логические операции над предикатами.

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

Пусть на некотором множестве M определены два предиката P(x) и Q(x) .

x Î M , при которых каждый из предикатов принимает значение“истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката P(x) Ù Q(x) является общая часть области

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

P(x) Þ Q(x) ºP(x) Ú Q(x) , то I PÞQ = I P È IQ .

1

МАТЕМАТИЧЕСКИХ ПРЕДЛОЖЕНИЙ, ОПРЕДЕЛЕНИЙ, ПОСТРОЕНИЯ ОТРИЦАНИЯ ПРЕДЛОЖЕНИЙ.

1. Запись математических предложений и определений в виде формул логики предикатов.

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

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

(a = lim an ) Û ("e > 0 $n0 Î N "n > n0 | an - a |< e )

n®¥

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

Пусть дано некоторое математическое утверждение А. Ему будет противоположным будет

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

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

$M Î R+"x Î E( f (x) £ M ) º"M Î R+ "x Î E( f (x) £ M ) º"M Î R+ $x Î E( f (x) £ M ) º . º "M Î R+$x Î E ( f (x) > M )

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

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

Как известно, многие теоремы математики допускают формулировку в виде условны предложений. Например, рассмотрим следующую теорему: «Если точка лежит на биссектрисе

2

угла, то она равноудалена от сторон этого угла». Условием этой теоремы является предложение «Точка лежит на биссектрисе угл»а, а заключением – предложение «Точка равноудалена от сторон угла». Видим, что и условие, и заключение теоремы представляют собой предикаты, заданные на множестве R2. Обозначая эти предикаты соответственно черезР(х) и Q(x), где хÎR2, теорему можем записать в виде формулы:

(P(x) Þ Q(x))

Всвязи с этим, говоря о строении теоремы, можно выделить в ней три части:

1)условие теоремы: предикат Р(х), заданный на множестве R2;

2)заключение теоремы: предикат Q(x), заданный на множестве R2;

3)разъяснительная часть: в ней описывается множество объектов, о которых идет речь в

теореме.

Особый интерес представляет построение утверждения, отрицающего справедливость некоторой теоремы: "x Î E(P(x) Þ Q(x)) .

Это будет утверждение: "x Î E(P(x) Þ Q(x)) º$x Î E (P(x) Þ Q(x)) º$x Î E (P(x) Ù Q(x)) . Следовательно, чтобы доказать, что теорема "x Î E(P(x) Þ Q(x)) неверна, достаточно указать

такой элемент x Î E , для которого P(x) - истина, a Q(x) - ложь, то есть привести контрпример.

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

1)«Если дифференцируемая функция y = f (x) имеет в точке х0 производную, равную нулю ( y'= 0) ,

то точка 0х – точка экстремума». Достаточно указать один пример, опровергающий утверждение теоремы. Функция y = x3 в точке х=0 имеет производную y' = 3x2 = 0 , но эта точка не является точкой экстремума. Значит, теорема не верна.

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

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

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

Так, теоремы (1)и (2), а также (3) и (4)- взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.

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

Так, теоремы (1) и (3), а также (2) и (4) являются взаимно противоположными теоремами. Например, для теоремы

“Если в четырехугольнике диагонали , равныто четырехугольник является прямоугольником ” (1) обратной является теорема

“Если четырехугольник является прямоугольником, то его диагонали равны” (2).

Для теоремы (1) противоположной является теорема

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

а для теоремы (2) противоположной является теорема

“Если четырехугольник не является прямоугольником, то его диагонали не равны ” (4).

В рассмотренном примере теоремы (1) и (4) являются одновременно ложными, а теоремы

(2)и (3) одновременно истинными. Контрпримером к теореме (1) является равнобочная трапеция. Ясно, что прямая и обратная теоремы, вообще говоря, не равносильны, т. е. одна из них

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

3

Действительно:

18 1,2 18

"x Î E(P(x) Þ Q(x)) º "x Î E(P(x) Ú Q(x)) º "x Î E(Q(x) Ú P(x)) º "x Î E(Q(x) Þ P(x)) .

Из этих равносильностей следует, что, если доказана теорема (1), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).

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

Рассмотрим теорему

случае, когда I P Ì I Q (см. рисунок).

Итак, предикат P(x) Þ Q(x) является истинным для всех x Î E том

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

Так, в теореме “Если х – число натуральное, то оно целое ” предикат Q(x): “ х – число целое ” логически следует из предиката Р():х “х – число натуральное” , а предикат “х- число натуральное” является достаточным условием для предиката “ х – целое число”.

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

"x Î E(P(x) Þ Q(x)) (1) "x Î E(Q(x) Þ P(x)) .(2)

Это, очевидно, возможно при условии, что I P = I Q .

В таком случае из теоремы (1) следует, что условия Р(х)являются достаточными для Q(x), а из теоремы (2) следует, что условие Р(х)является необходимым для Q(x).

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

Иногда вместо логической связки “необходимо и достаточно ” употребляют логическую связку “тогда и только тогда”.

Так как здесь истинны высказывания (1) и (2), то истинно высказывание

"x Î E(P(x) Þ Q(x)) Ù "x Î E(Q(x) Þ P(x)) º"x Î E(P(x) Û Q(x)) .

Примеры:

1) Теорема «Если число l делится на 12, то оно делится на3» истинна. Поэтому здесь делимость числа l на 12 является достаточным условием для делимости числаl на 3, а делимость числа l на 3 является необходимым условием для делимости числа l на 12. В то же время обратная теорема «Если число l делится на 3, то оно делится на 12» не верна. Поэтому делимость числа l на 3 не является достаточным условием делимости числаl на 12, а делимость числа l на 12 не является необходимым условием делимости числа l на 3.

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

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

3)Для каждого из условий выясните, является ли оно необходимым и является ли оно достаточным, чтобы выполнялось неравенство x2 - 2x - 8 £ 0 :

4

а) х=0, б) -1 £ x £ 3 , в) x ³ -3 , г) x > -2 , д) -1 £ x £ 10 , е) - 2 £ x £ 4 .

Неравенство перепишем в виде (x + 2)(x - 4) £ 0 , его решением являются x Î[-2;4] . а) x = 0 – достаточное условие для выполнения неравенства, т.к. 0Î[-2, 4].

б) [-1, 3]Ì [-2, 4]. Значит -1 £ x £ 3 – достаточное условие .

в) [-3, +¥)É[-2, 4], следовательно, является необходимым условием.

г) (-2, +¥)Ë[-2, 4] и [-2, 4]Ë(2, +¥), значит, не является ни необходимым, ни достаточным условием.

д) [-1, 10] Ë[-2, 4] и [-2, 4]Ë [-1, 10], значит, не является ни необходимым, ни достаточным условием.

е) [-2, 4]=[-2, 4] , следовательно, является и необходимым и достаточным условием.

5. Доказательство теорем методом от противного.

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

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

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

Действительно, предположение о том, что теорема (1) не справедлива , означает истинность

рассмотренных примеров, может быть записано как конъюнкцияC Ù C = A , где С – некоторое высказывание.

«достаточно, но не необходимо», «не необходимо и недостаточно», «необходимо и достаточно»:

а) Для того, чтобы четырехугольник был прямоугольным…, чтобы длины его диагоналей были равны;

б) Для того, чтобы x2 - 5x + 6 = 0 …, чтобы х=3;

в) Для того, чтобы сумма четного числа натуральных чисел была четным числом…, чтобы каждое слагаемое было четным;

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

д) Для того, чтобы множество было счетным…, чтобы его элементы можно было записать в виде занумерованной последовательности;

е) Для того, чтобы числовая последовательность имела предел…, чтобы она была ограниченной.

5.Сформулируйте:

а) Необходимый, но недостаточный признак параллелограмма; б) Необходимый и достаточный признак параллелограмма;

в) Достаточное, но не необходимое условие, чтобы уравнение sinx = a имело решение. г) Необходимое, но не достаточное условие, чтобы уравнение sinx = a имело решение.

5

Лекция 6. Равносильные формулы логики предикатов.

§5. Понятие формулы логики предикатов.

В логике предикатов будем пользоваться следующей символикой :

1.Символы p, q, r, …- переменные высказывания, принимающие два значения: 1- истина , 0 – ложь.

2.Предметные переменные – x, y, z, … , которые пробегают значения из некоторого множества М;

x0, y0, z0 – предметные константы, т. е. значения предметных переменных.

3.P(·), Q(·), F(·), … - одноместные предикатные переменные; Q(·,·,…,·), R(·,·, …,·) – n-местные предикатные переменные. P0(·), Q0(·,·, …,·) – символы постоянных предикатов.

4.Символы логических операций: Ù,Ú,Þ, Û

5.Символы кванторных операций: "x, $x.

6.Вспомогательные символы: скобки, запятые.

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

1.Каждое высказывание как переменное, так и постоянное, является формулой (элементарной).

2.Если F(·,·, …,·) – n-местная предикатная переменная или постоянный предикат, а x1, x2,…, xn– предметные переменные или предметные постоянные(не обязательно все различные), то F(x1, x2,…, xn) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.

3.Если А и В– формулы, причем, такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой – свободной, то слова A Ú B, A Ù B, A Þ B

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

4.Если А – формула, то A – формула, и характер предметных переменных при переходе от формулы А к формуле A не меняется.

5.Если А(х) – формула, в которую предметная переменная х входит свободно, то слова "xA(x) и $xA(x) являются формулами, причем, предметная переменная входит в них

связанно.

6.Всякое слово, отличное от тех, которые названы формулами в пунктах 1 – 5, не является формулой.

Например, если Р(х) и Q(x,y) – одноместный и двухместный предикаты, а q, r – переменные высказывания, то формулами будут, например, слова (выражения):

q, P(x), P(x) Ù Q(x0 , y),"xP(x) Þ $xQ(x, y),(Q(x, y) Ú q) Þ r .

Не является формулой, например, слово: "xQ(x, y) Þ P(x) . Здесь нарушено условие п.3, так как формулу "xQ(x, y) переменная х входит связанно, а в формулу Р(х) переменная х входит свободно.

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

1

§6. Значение формулы логики предикатов.

О логическом значении формулы логики предикатов можно говорить лишь тогда , когда задано множество M, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных.

При конкретных значениях каждого из трех видов переменных формула логики предикатов

§7. Равносильные формулы логики предикатов.

Определение 1. Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в н переменных, отнесенных к области М.

Определение 2. Две формулы логики предикатов А и В называются равносильны,миесли они равносильны на всякой области.

Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей.

Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание (или формула, не содержащая х). Тогда имеют место равносильности:

1."xA(x) º $x A(x).

2.$xA(x) º "x A(x).

3."xA(x) º $x A(x).

4.$xA(x) º "x A(x).

5."xA(x) Ù "xB(x) º "x[ A(x) Ù B(x)]

6.C Ù "xB(x) º "x[C Ù B(x)] .

7.C Ú "xB(x) º "x[C Ú B(x)]

8.C Þ "xB(x) º "x[C Þ B(x)]

9."x[B(x) Þ C] º $xB(x) Þ C.

10.$x[ A(x) Ú B(x)] º $xA(x) Ú $xB(x).

11.$x[C Ú B(x)] º C Ú $xB(x).

2