В алгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности. Ни структура высказываний, ни, тем более, их содержание не затрагиваются. В то же время и в науке, и в практике используются заключения. существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.
Например, в рассуждении «Всякий ромб – параллелограмм; AВCD – ромб; следовательно, AВCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.
В связи с этим возникает необходимость в расширении логики высказываний, в построении такой логической системы, средствами которой можно было бы исследовать и структуру тех высказываний, которые в рамках логики высказываний рассматриваются как элементарные.
Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части.
Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально – подлежащее, хотя оно и может играть роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения).
Субъект – это то, о чем что-то утверждается в высказывании; предикат – это то, что утверждается о субъекте.
Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом»
Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например. х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.
Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1,0}. Здесь предикат становится функцией субъекта и выpaжает свойство субъекта.
Определение. Одноместным предикатом Р(х) нaзывается произвольная функция переменного х, определенная на множестве М и принимающая значения из множества {1,0}.
Множество М, на котором определен предикат Р(х), называется областью определения предиката.
Множество всех элементов, при которых предикат принимает значение «истина», называется множеством истинности предиката Р(х) , то есть множество истинности предиката Р(х) – это множество.
Так. предикат Р(х) – «х – простое число»
определен на множестве N, а множество
для
нeгo есть множество всех простых чисел.
Предикат Q(x) – «»
определен на множествеR,
а eгo множество истинности
.
Предикат F(x) «Диагoнали
параллелогpамма х перпендикулярны»
определен на множестве всех параллелограммов,
а eгo множеством истинности является
множество всех ромбов.
Приведенные при меры одноместных предикатов выражают свойства предметов.
Определение. Предикат Р(х), определенный на множестве М, называется тождественно истинным (тождественно ложным), если .
Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью котopoгo выражаются отношения между предметами.
Примером бинарного отношения (отношения между двумя предметами) является отношение «меньше». Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой «x<у », где, то есть является функцией двух переменных Р(х,у), определенной на множествес множеством значений {1,0}.
Определение. Двухместным предикатом Р(х, у) называется функция двух переменных х и y, определенная на множествеИ принимающая значения из множества {1,0}.
Аналогично определяется n-местный предикат.
Операции над предикатами. Описание математических понятий с помощью логики предикатов.
§3. Логические операции над предикатами.
Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.
Пусть на некотором множестве определены два предиката и .
Определение 7. Конъюнкцией двух предикатов https://pandia.ru/text/80/323/images/image003_26.gif" width="36" height="21 src=">называется новый (сложный) предикат , который принимает значение “истина” при тех и только тех значениях https://pandia.ru/text/80/323/images/image004_23.gif" width="83" height="21 src="> является общая часть области истинности предикатов и , т. е. пересечение .
Пример 8. Для предикатов https://pandia.ru/text/80/323/images/image007_16.gif" width="13" height="15 src="> – четное число” и : “ кратно 3” конъюнкцией является предикат “ – четное число и кратно трем”, т. е. предикат “ делится на 6”.
Определение 8. Дизъюнкцией двух предикатов https://pandia.ru/text/80/323/images/image003_26.gif" width="36" height="21 src="> называется новый предикат , который принимает значение “ложь” при тех и только тех значениях DIV_ADBLOCK29">
Ясно, что областью истинности предиката https://pandia.ru/text/80/323/images/image009_18.gif" width="55" height="25 src=">.
Определение 9. Отрицанием предиката P(x) называется новый предикат или, который принимает значение “истина” при всех значениях https://pandia.ru/text/80/323/images/image002_38.gif" width="35" height="21"> принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат принимает значение “истина”.
Очевидно, что , т. е..gif" width="35" height="21 src=">.gif" width="88" height="21">.gif" width="35" height="21"> принимает значение “истина”, а – значение “ложь”, и принимает значение “истина” во всех остальных случаях.
Поскольку при каждом фиксированном справедлива равносильность 
, то 
.
Определение 11. Эквиваленцией предикатов https://pandia.ru/text/80/323/images/image003_26.gif" width="36" height="21 src=">называется новый предикат , который обращается в “истину” при всех тех и только тех https://pandia.ru/text/80/323/images/image002_38.gif" width="35 height=21" height="21"> и обращаются оба в истинные или оба в ложные высказывания.
Для его множества истинности имеем:
§4. П РИМЕНЕНИЕ ЯЗЫКА ЛОГИКИ ПРЕДИКАТОВ ДЛЯ ЗАПИСИ МАТЕМАТИЧЕСКИХ ПРЕДЛОЖЕНИЙ, ОПРЕДЕЛЕНИЙ, ПОСТРОЕНИЯ ОТРИЦАНИЯ ПРЕДЛОЖЕНИЙ.
1. Запись математических предложений и определений в виде формул логики предикатов.
Язык логики предикатов удобен для записи математических предложений и определений. Он дает возможность выражать логические связи между понятиями, записывать определения, теоремы, доказательства. Приведем несколько примеров таких записей.
Пример 1. Определение предела числовой последовательности.
https://pandia.ru/text/80/323/images/image019_9.gif" width="211" height="21 src=">, запишем:
https://pandia.ru/text/80/323/images/image021_9.gif" width="13" height="19">” функции ƒ(х), определенной в области E, в точке x0:
https://pandia.ru/text/80/323/images/image023_7.gif" width="285" height="27">.
Пример 3. Определение непрерывности функции в точке.
Функция https://pandia.ru/text/80/323/images/image025_6.gif" width="48 height=24" height="24">, если , где .
Пример 4. Определение возрастающей функции.
Функция , определенная на множестве E, возрастает на этом множестве, если
https://pandia.ru/text/80/323/images/image029_5.gif" width="72" height="23 src=">.gif" width="16" height="21">. Логика предикатов позволяет путем равносильных преобразований формулы придать ей хорошо обозримый вид.
Определение неограниченной функции мы получим, беря отрицание этой формулы и проводя равносильные преобразования:
Последняя формула дает не негативное, а положительное определение неограниченной функции.
Из приведенного определения видно, что для построения противоположного утверждения к утверждению, заданному формулой логики предикатов, содержащей все кванторы впереди, необходимо заменить все кванторы на противоположные и взять отрицание от предиката, стоящего под знаком кванторов.
Как известно, многие теоремы математики допускают формулировку в виде условных предложений. Например, рассмотрим следующую теорему: «Если точка лежит на биссектрисе угла, то она равноудалена от сторон этого угла» . Условием этой теоремы является предложение «Точка лежит на биссектрисе угла» , а заключением – предложение «Точка равноудалена от сторон угла» . Видим, что и условие, и заключение теоремы представляют собой предикаты, заданные на множестве R2. Обозначая эти предикаты соответственно через Р(х) и Q (x ), где х ÎR2, теорему можем записать в виде формулы:
В связи с этим, говоря о строении теоремы, можно выделить в ней три части:
1) условие теоремы: предикат Р(х), заданный на множестве R2;
2) заключение теоремы: предикат Q (x ), заданный на множестве R2;
3) разъяснительная часть: в ней описывается множество объектов, о которых идет речь в теореме.
Особый интерес представляет построение утверждения, отрицающего справедливость некоторой теоремы: https://pandia.ru/text/80/323/images/image035_5.gif" width="411 height=32" height="32">.
Следовательно, чтобы доказать, что теорема https://pandia.ru/text/80/323/images/image036_4.gif" width="37" height="17">, для которого - истина, a - ложь, то есть привести контрпример.
Используя данный прием докажем несправедливость утверждений:
1) «Если дифференцируемая функция имеет в точке х0 производную, равную нулю https://pandia.ru/text/80/323/images/image041_3.gif" width="41" height="24"> в точке х=0 имеет производную 0 " style="border-collapse:collapse;border:none">
Определение 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) всегда равносильны.
Действительно:
Из этих равносильностей следует, что, если доказана теорема (1), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).
4. Необходимые и достаточные условия.
Рассмотрим теорему
(1)
Как отмечалось, множество истинности предиката есть множество ..gif" width="55" height="25"> (см. рисунок).
Итак, предикат https://pandia.ru/text/80/323/images/image052_4.gif" width="40" height="19"> том и в только в том случае, когда множество истинности предиката Р(х) содержится в множестве истинности предиката Q(x). При этом говорят, что предикат Q(x) логически следует из предиката Р(х), и предикат Q(x) называют необходимым условием для предиката Р(х), а предикат Р(х) – достаточным условием для Q(x).
Так, в теореме “Если х – число натуральное, то оно целое ” предикат Q(x): “ х – число целое ” логически следует из предиката Р(х): “х – число натуральное” , а предикат “х - число натуральное” является достаточным условием для предиката “ х – целое число”.
Часто встречается ситуация, при которой истинны взаимно обратные теоремы
Это, очевидно, возможно при условии, что .
В таком случае из теоремы (1) следует, что условия Р(х)являются достаточными для Q(x), а из теоремы (2) следует, что условие Р(х)является необходимым для Q(x).
Таким образом, если истинны теоремы (1) и (2), то условие Р(х) является и необходимым, и достаточным для Q(x). Аналогично в этом случае условие Q(х) является необходимым и достаточным для Р(x).
Иногда вместо логической связки “необходимо и достаточно ” употребляют логическую связку “тогда и только тогда”.
Так как здесь истинны высказывания (1) и (2), то истинно высказывание
Примеры:
1) Теорема «Если число l делится на 12, то оно делится на 3» истинна. Поэтому здесь делимость числа l на 12 является достаточным условием для делимости числа l на 3, а делимость числа l на 3 является необходимым условием для делимости числа l на 12. В то же время обратная теорема «Если число l делится на 3, то оно делится на 12» не верна. Поэтому делимость числа l на 3 не является достаточным условием делимости числа l на 12, а делимость числа l на 12 не является необходимым условием делимости числа l на 3..
Неравенство перепишем в виде 
, его решением являются .
а) – достаточное условие для выполнения неравенства, т. к. 0Î[-2, 4].
б) [-1, 3]Ì [-2, 4]. Значит – достаточное условие.
в) [-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) не справедлива, означает истинность ее отрицания, т. е. формулы 
. Можно показать, что противоречивое утверждение, которое получается из допущенного предположения, как мы видели из ранее рассмотренных примеров, может быть записано как конъюнкция https://pandia.ru/text/80/323/images/image039_3.gif" width="57" height="20 src="> имеет в точке х0 вторую производную, равную нулю, то точка х0 – точка перегиба графика функции».
б) «Если числовая последовательность ограничена, то она имеет предел».
в) «Если функция непрерывна в точке х0, то она имеет производную в этой точке».
д) Для того, чтобы множество было счетным…, чтобы его элементы можно было записать в виде занумерованной последовательности;
е) Для того, чтобы числовая последовательность имела предел…, чтобы она была ограниченной.
5.Сформулируйте:
а) Необходимый, но недостаточный признак параллелограмма;
б) Необходимый и достаточный признак параллелограмма;
в) Достаточное, но не необходимое условие, чтобы уравнение sinx = a имело решение.
г) Необходимое, но не достаточное условие, чтобы уравнение sinx = a имело решение.
Так как для любого набора значений переменных из области определения предиката он превращается в высказывание, то на множестве предикатов определены те же логические операции, что и для высказываний. При этом от содержания предикатов отвлекаются. Предикаты рассматриваются только с точки зрения их значения. Другими словами, равносильные предикаты не различаются.
Определение
1: Отрицанием
-
местного предиката
,
определенного на множестве
,
называется новый
-
местный предикат, определенный на том
же множестве. Обозначается:
.
Читается: «неверно, что
».
Предикат
принимает значение «истина» только для
тех аргументов, для которых значение
предиката
есть «ложь» и наоборот. Другими словами
предикат
удовлетворяется теми и только теми
аргументами, которые не удовлетворяют
данному предикату
.
Двуместный предикат
принимает
значение «истина» для тех и только тех
значений переменных
из области определения предиката, для
которых предикат
принимает значение «ложь», т. е..
Определение
2: Конъюнкцией
-
местного предиката
,
определенного на множестве
,
и
-
местного предиката
,
определенного на множестве
,
называется новый
-
местный предикат, определенный на
множестве
,
обозначаемый.
Читается: «
и
».
Этот предикат принимает значение
«истина» только для тех значений
аргументов,
для которых предикаты
и
одновременно принимают значение
«истина».
Если, например,
- двуместный предикат, определённый на
множестве
,
а
- одноместный предикат, определённый
на множестве
,
то конъюнкция этих предикатов
есть трёхместный предикат, определённый
на множестве
.
Этот новый предикат принимает значение
«истина» для таких троек элементов
,
,
,
,
для которых
и
.
Аналогично
определяются дизъюнкция, импликация и
эквивалентность предикатов. Значения
предикатов при заданных значениях
свободных переменных определяются в
соответствии с конкретными логическими
операциями. Операции
можно применять также к предикатам, у
которых имеются общие переменные. В
таком случае число переменных полученного
составного предиката будет равняться
числу различных переменных у его членов.
В частности, если операции
применяются к двум
-
местным предикатам, зависящим от одних
и тех же переменных, то в результате
применения логических операций получается
-
местный предикат, зависящий от тех же
переменных.
Пусть
и
– два
-
местных предиката, зависящих от одних
и тех же переменных. Тогда:
а) множество истинности конъюнкции равно пересечению множеств истинности ее членов;
б) множество истинности дизъюнкции равно объединению множеств истинности ее членов.
Не трудно показать,
что конъюнкция двух предикатов
тождественно истинна тогда и только
тогда, когда оба данных предиката
тождественно истинны. Дизъюнкция двух
предикатов выполнима тогда и только
тогда, когда, по крайней мере, один из
них выполним. Дизъюнкция двух предикатов
тождественно ложна тогда и только тогда,
когда оба данных предиката тождественно
ложны. Импликация двух
-
местных предикатов зависящих от одних
и тех же аргументов, тождественно истинна
тогда и только тогда, когда ее заключение
является следствием посылки. Эквивалентность
двух
-
местных предикатов, зависящих от одних
и тех же переменных тождественно истинна
тогда и только тогда, когда оба предиката
равносильны.
Всякое уравнение (неравенство), содержащее переменные, является предикатом, определённым на том же множестве, на котором задано уравнение (неравенство). Множество решений уравнения (неравенства) есть ничто иное, как множество истинности предиката. Это означает, что при подстановке корней уравнения (или решений неравенства) вместо неизвестных будут получены истинные высказывания. Если же в уравнение (неравенство) вместо переменных подставлять числа, не являющиеся решениями, то будут получены ложные высказывания. Всякая система уравнений (неравенств) может быть рассмотрена, как конъюнкция предикатов. Решить систему – значит найти область истинности конъюнкции предикатов. Совокупность уравнений (неравенств) есть ничто иное, как дизъюнкция предикатов. Равносильность уравнений (неравенств) означает равносильность соответствующих предикатов.
Если
,
то говорят, что аргумент
удовлетворяет данному предикату.
Например, число 3 удовлетворяет предикату
,
а число 1 ему не удовлетворяет.
В математической логике кроме логических операций над предикатами, существуют операции квантификации , которые делают логику предикатов значительно богаче по содержанию в сравнении с логикой высказываний. При этом, как и в случае простейших операций, предикаты рассматриваются только сточки зрения их значений, т.е. равносильные предикаты не различаются. Основными кванторными операциями являются: квантор общности и квантор существования, которые являются двойственными друг для друга.
Определение
3:
Пусть
- одноместный предикат, определенный
на непустом множестве
в высказывание:
(читается: «для любого
выполняется
»),
называетсяквантором
общности
(или
универсальным высказыванием). Высказывание
истинно тогда и только тогда, когда
данный предикат
тождественно истинный (т. е. область
истинности предиката
совпадает с множеством
).
Символ
называется квантором общности по
переменой
,
его читают: «для всех
»
или «для каждого
».
Говорят, что высказывание
есть результат применения квантора
общности к предикату
.
Символ
происходит от английского слова «All»
(в переводе: «все»).
Например, для
предикатов «
»
и «
»,
определенных на множестве действительных
чисел, соответствующие универсальные
высказывания будут иметь вид:
– «каждое действительное число равно
самому себе» (истинное) и
– «каждое действительное число больше
2» (ложное).
Теорема 1:
Если
- одноместный предикат, определенный
на конечном множестве, состоящем из
элементов
,
,…,
,
то соответствующее ему универсальное
высказывание эквивалентно конъюнкции
высказываний:
Доказательство.
В самом
деле, согласно определению квантора
общности, высказывание
тождественно истинный, т.е. когда истинны
все
высказываний,
получаемые из данного предиката при
замене переменного
аргументами
,
,…,
соответственно. Последнее замечание
возможно в том и только том случае, когда
истинна конъюнкция этих
высказываний. Т.е. члены эквивалентности
одновременно истинны или ложны, а,
следовательно, эквивалентность доказана.
Теорема показывает, что для предикатов, определенных на конечном множестве, операция применения квантора общности может быть выражена через конъюнкцию. Для предикатов, определенных на бесконечном множестве, это сделать невозможно, в этом случае операция применения квантора общности является абсолютно новой.
Определение
4:
Пусть
- одноместный предикат, определенный
на множестве
.
Операция, превращающая предикат
в высказывание
(читается: «существует
,
удовлетворяющее предикату
»),
называетсяквантором
существования
(или
экзистенциональным высказыванием).
Высказывание
будет истинным тогда и только тогда,
когда предикат
выполнимый. Это высказывание будет
ложным, если предикат
тождественно ложный.
Символ
называется квантором существования по
переменной
.
Его можно прочитать: «существует
такой, что
»,
или «найдётся такой
,
что
».
Символ
происходит от английского слова «Exist»
(существует).
Теорема 2:
Если
– одноместный предикат, определенный
на конечном множестве из
элементов
,
,…,
,
то соответствующее ему экзистенциональное
высказывание эквивалентно дизъюнкции
высказываний:
Доказательство:
По
определению: высказывание
будет ложно тогда и только тогда, когда
ложны все
высказываний,
которые получаются из данного предиката
при замене переменной
аргументами
,
,…,
соответственно. Последнее замечание
возможно в том и только в том случае,
когда ложна дизъюнкция этих
высказываний. Т.е. члены эквивалентности
одновременно истинны или ложны,
следовательно, эта эквивалентность
истинна.
Эта теорема утверждает, что для предикатов, определенных на конечных множествах, операция применения квантора существования может быть выражена через дизъюнкцию. Для предикатов, определенных на бесконечных множествах, это сделать невозможно. Операция применения квантора существования тогда является абсолютно новой.
Следует запомнить,
что для любого предиката
,
определенного на множестве
выражения
и
– это высказывания, а не предикаты.
Присутствие переменной
здесь чисто внешнее, связанное со
способом обозначений. Поэтому переменная
,
входящая в выражения
и
,
называетсясвязанной
переменной,
в отличие от переменной, входящей в
предикат
,
где переменная называетсясвободной.
Если
применить операцию «навешивания»
кванторов двуместному предикату
по какой-нибудь переменной, то в результате
двуместный предикат превратится в
одноместный предикат с одной свободной
переменной. Аналогичные рассуждения
можно провести для второй переменной.
Переменная, по которой был применён
квантор, называетсясвязной
переменной.
Если применить кванторную операцию к
-
местному предикату по какой-нибудь
переменной, то он превратится в
-
местный предикат.
Если в любом
предикате все переменные связаны, то
этот предикат является высказыванием.
Например, рассмотрим предикат
,
определённый на некотором числовом
множестве. Составим высказывание
.
Это ложное высказывание, которое
утверждает, что найдётся такое число
,
которое больше всякого числа
(
- единственное число для всех
).
Поменяв местами кванторы, получим новое
высказывание:
.
Это высказывание утверждает, что для
любого числа
можно подобрать такое число
,
что выполняется неравенство
(для каждого
существует своё число
).
Это высказывание истинно. Видно, что
при перестановке кванторов местами
меняется смысл высказывания. Таким
образом,перестановка
разноимённых кванторов местами является
недопустимой операцией.
Одноимённые
кванторы местами менять можно. Причем,
одноимённые кванторы можно объединять
в один, например:
.
Недопустимым является также применение
нескольких кванторов по одной и той же
переменной, например:
.
Определение
5: Универсальным высказыванием
,
соответствующим
-
местному предикату
,
определенному на множестве
последовательным применением
кванторов общности по переменным
в любом порядке.
Обозначается такое
высказывание
и читается кратко так: «для всех
выполняется
».
Определение
6: Экзистенциональным высказыванием,
соответствующим
-
местному предикату
,
определенному на множестве
,
называется высказывание, полученное
из
последовательным применением
кванторов существования по переменным
в любом порядке.
Полученное
экзистенциональное высказывание
обозначают
и читают так: «существует такой набор
,
что выполняется
».
Например, для
двуместного предиката «
»
соответствующие высказывания имеют
вид:
– «для любых двух действительных чисел:
первое больше второго» (ложное), и
– «существуют два действительных числа,
из которых первое больше второго»
(истинное).
Теорема 3: (Условие тождественной истинности квантифицированного предиката).
‑местный предикат,
полученный из
‑
местного предиката
,
определенного на множестве
,
применением квантора общности по
какой–либо переменной является
тождественно истинным тогда и только
тогда, когда данный предикат
– тождественно истинный.
Доказательство:
Действительно,
пусть дан
- местный предикат
,
определенный на множестве
.
По определению, этот предикат будет
тождественно истинным тогда и только
тогда, когда его значение для произвольно
взятых значений аргументов есть «истина».
Это значит, что истинным является
универсальное высказывание
,
определенному на множестве
.
Последнее замечание возможно тогда и
только тогда, когда предикат
– тождественно истинный, но т.к. аргументы
выбирались произвольно, то это равносильно
тождественной истинности данного
-
местного предиката
.
Теорема доказана.
Теорема 4: (Условие тождественной ложности квантифицированного предиката).
-местный
предикат, полученный из
-
местного предиката
,
определенного на множестве
,
применением квантора существования по
какой-либо переменной, тождественно
ложен тогда и только тогда, когда данный
предикат тождественно ложен.
Доказательство:
Пусть
имеем
- местный предикат
,
определенный на множестве
.
Он будет тождественно ложен тогда и
только тогда, когда его значение для
произвольно взятых аргументов
есть «ложь». Это значит, что ложно
экзистенциональное высказывание
,
соответствующее одноместному предикату
,
определенному на множестве
.
Последнее возможно в том и только в том
случае, когда предикат
тождественно ложен, а т.к. аргументы
выбирались произвольно, то и данный
-
местный предикат
тождественно ложен. Что и требовалось
доказать.
До сих пор мы противопоставляли предикаты высказываниям. Однако удобнее считать высказывания 0 ‑ местными предикатами. Тогда любые два истинные и любые два ложных высказывания следует считать равносильными между собой.
Пример: В высказывании «7 - простое число», «7» -субъект, «простое число» - предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом». Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х - простое число». При одних значениях х, (например, х = 13, х =17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.
Примеры: Р(х) - «х - простое число» определен на множестве N, а множество истинности для него есть множество всех простых чисел. Предикат Q{x} - « sin х = 0 » определен на множестве R, а его множество истинности -Q. Предикат F(x) - «Диагонали параллелограмма перпендикулярны» определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.
Конъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х) Q{x), который принимает значение «истина» при тех и только тех значениях х М, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.
Дизъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х)V Q(x), который принимает значение «ложь» при тех и только тех значениях х М, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях.
Отрицанием предиката Р(х) называется новый предикат, который принимает значение «истина» при всех значениях х М, при которых предикат Р(х) принимает значение «ложь», и принимает значение «ложь» при тех значениях х М, при которых предикат Р(х) принимает значение «истина». 2)v(y>1))((x" title="Задание 2 Изобразить на декартовой плоскости области истинности предикатов: х+у=1; х+3у=3; ((x>2)v(y>1))((x" class="link_thumb"> 16 Задание 2 Изобразить на декартовой плоскости области истинности предикатов: х+у=1; х+3у=3; ((x>2)v(y>1))((x 2)v(y>1))((x"> 2)v(y>1))((x"> 2)v(y>1))((x" title="Задание 2 Изобразить на декартовой плоскости области истинности предикатов: х+у=1; х+3у=3; ((x>2)v(y>1))((x"> title="Задание 2 Изобразить на декартовой плоскости области истинности предикатов: х+у=1; х+3у=3; ((x>2)v(y>1))((x">
Отношение порядка. Упорядоченные множества
Определение. Отношение R на множестве Х называется отношением порядка, если оно транзитивно и асимметрично или антисимметрично.
Определение. Отношение R на множестве Х называется отношением строгого порядка, если оно транзитивно и асимметрично.
Примеры отношений строгого порядка: «больше» на множестве натуральных чисел, «выше» на множестве людей и др.
Определение. Отношение R на множестве Х называется отношением нестрогого порядка, если оно транзитивно и антисимметрично.
Примеры отношений нестрогого порядка: «не больше» на множестве действительных чисел, «быть делителем» на множестве натуральных чисел и др.
Определение. Множество Х называют упорядоченным, если на нем задано отношение порядка.
Пример . На множестве Х = {1; 2; 3; 4; 5} заданы два отношения: «х £ у » и «х – делитель у ».
Оба эти отношения обладают свойствами рефлексивности, антисимметричности и транзитивности (постройте графы и проверьте свойства самостоятельно), т.е. являются отношением нестрогого порядка. Но первое отношение обладает свойством связности, а второе – нет.
Определение. Отношение порядка R на множестве Х называется отношением линейного порядка, если оно обладает свойством связности.
В начальной школе изучаются многие отношения порядка. Уже в первом классе водятся отношение «меньше», «больше» на множестве натуральных чисел, «короче», «длиннее» на множестве отрезков и др.
Контрольные вопросы
1. Дайте определение бинарного отношения на множестве Х .
2. Как записать утверждение о том, что элементы х и у находятся в отношении R ?
3. Перечислите способы задания отношений.
4. Сформулируйте свойства, которыми могут обладать отношения. Как данные свойства отражаются на графе?
5. Какими свойствами должно обладать отношение, чтобы оно являлось отношением эквивалентности?
6. Как отношение эквивалентности связано с разбиением множества на классы?
7. Какими свойствами должно обладать отношение, чтобы оно являлось отношением порядка?
Глава 5. Предикаты и теоремы
В математике часто встречаются предложения, содержащие одну или несколько переменных, например: «х + 2 = 7», «город стоит на Волге». Эти предложения не являются высказываниями, т.к. о них нельзя сказать, истинны они или ложны. Однако при подстановке конкретных значений переменной х они обращаются в истинные или ложные высказывания. Так, в первом примере при х = 5 получаем истинное высказывание, а при х = 3 – ложное высказывание.
Определение . Предложение с переменными, которое при конкретных значениях переменных обращается в высказывание, называется высказывательной формой или предикатом.
По числу входящих в предикат переменных различают одноместные, двухместные и т.д. предикаты и обозначают А (х ), В (х;у )…
Пример : А (х ): «х делится на 2» – одноместный предикат, В (х ; у ): «прямая х перпендикулярна прямой у » – двухместный предикат.
Следует иметь в виду, что в предикате переменные могут содержаться неявно: «число делится на 2», «студент получил отличную оценку на экзамене по математике».
Задание предиката, как правило, предполагает и задание множества, из которого выбираются значения переменных, входящих в предикат.
Определение . Множеством (областью) определения предиката называется множество Х , состоящее из всех значений переменных, при подстановке которых в предикат последний обращается в высказывание.
Так, предикат «х > 2» можно рассматривать на множестве натуральных чисел или действительных чисел.
Каждый предикат А (х ), х Î Х определяет множество Т Ì Х , состоящее из элементов, при подстановке которых в предикат А (х ) вместо х получается истинное высказывание.
Определение . Множество, состоящее из всех тех значений, при подстановке которых в предикат получается истинное высказывание, называется множеством истинности предиката (обозначается Т ).
Пример . Рассмотрим предикат А (х ): «х < 5», заданный на множестве натуральных чисел. Т = {1; 2; 3; 4}.
Предикаты, как и высказывания, бывают элементарными и составными. Составные предикаты образуются из элементарных при помощи логических связок.
Пусть Т А А (х ), Т В – область истинности предиката В (х ).
Определение . Конъюнкцией предикатов А (х ) и В (х ) называется предикат А (х ) Ù В (х х Î Х , для которых оба предиката истинны.
Покажем, что Т А Ù В = Т А ÇТ В .
Доказательство . 1) Пусть а Î Т А Ù В Þ А (а ) Ù В (а ) – истинное высказывание. По определению конъюнкции имеем: А (а ) – истинно, В (а ) – истинно Þ а Î Т А Ù а Î Т В Þ а Î Т А Ç Т В Þ Т А Ù В Ì Т А Ç Т В.
2) Пусть b Î Т А Ç Т В Þ b Î Т А Ù b Î Т В Þ А (b ) – истинно, В (b ) – истинно Þ по определению конъюнкции А (b ) Ù В (b ) – истинное высказывание Þ b Î Т А Ù В Þ Т А Ç Т В Ì Т А Ù В .
Т.к. Т А Ù В Ì Т А Ç Т В и Т А Ç Т В Ì Т А Ù В , то по свойству равенства множеств Т А Ù В = Т А ÇТ В , что и требовалось доказать.
Заметим, что полученное правило справедливо и для предикатов, содержащих более одной переменной.
Пример . Рассмотрим предикаты А (х ): «х < 10», В (х ): «х А (х ) Ù В (х ): «х < 10 и делится на 3».
Т А = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10}, Т В = {3; 6; 9; 12; 15; …}, тогда Т А Ù В = {3; 6; 9}.
Определение . Дизъюнкцией предикатов А (х ) и В (х ) называется предикат А (х ) Ú В (х ), который истинен для тех и только тех значениях х Î Х , для которых истинен хотя бы один из предикатов.
Можно доказать (самостоятельно), что Т А Ú В = Т А ÈТ В .
Пример . Рассмотрим предикаты А (х ): «х делится на 2 », В (х ): «х делится на 3», заданные на множестве натуральных чисел. Найдем область истинности предиката А (х ) Ú В (х ): «х делится на 2 или на 3».
Т А = {2; 4; 6; 8; 10;…}, Т В = {3; 6; 9; 12; 15; …}, Т А Ú В = {2; 3; 4; 6; 8; 9; …}.
Определение . Отрицанием предиката А (х ) называется предикат . Он истинен для тех и только тех значениях х Î Х , для которых предикат А (х ) ложен и наоборот.
Заметим, что = .
Определение . Импликацией предикатов А (х ) и В (х ) называется предикат А (х ) Þ В (х ) (читают: «Если А (х ), то В (х )»). Он обращается в ложное высказывание при тех значениях х Î Х , для которых предикат А (х ) истинен, а предикат В (х ) ложен.
Из определения имеем, что предикат А (х ) Þ В (х ) ложен на множестве Т А Ç , а следовательно истинен на дополнении к этому множеству. Воспользовавшись законами операций над множествами, имеем: .
Контрольные вопросы
1. Что называется высказывательной формой или предикатом?
2. Какие различают предикаты по числу входящих в них переменных? Приведите примеры.
3. Какое множество называют областью определения предиката?
4. Какое множество называют множеством истинности предиката?
5. Что называют конъюнкцией предикатов? Докажите равенство, связывающее область истинности конъюнкции предикатов с областями истинности этих предикатов.
6. Дайте определения дизъюнкции, отрицания, импликации предикатов. Запишите равенства, связывающие области истинности конъюнкции предикатов с областями истинности этих предикатов.
