Действия над предикатами. Операции над предикатами
Понятие предиката
Определение 1
Предикат - утверждение, которое содержит переменные, принимающие значение $1$ или $0$ (истинно или ложно) в зависимости от значений переменных.
Пример 1
Например, выражение $x=x^5$ является предикатом, т.к. оно является истинным при $x=0$ или $x=1$ и ложным при всех остальных значениях $x$.
Определение 2
Множество, на котором предикат принимает только истинные значения, называется множеством истинности предиката $I_p$.
Предикат называется тождественно-истинным , если на любом наборе аргументов он принимает истинное значение:
$P (x_1, \dots, x_n)=1$
Предикат называется тождественно-ложным , если на любом наборе аргументов он принимает ложное значение:
$P (x_1, \dots, x_0)=0$
Предикат называется выполнимым , если хотя бы на одном наборе аргументов он принимает истинное значение.
Т.к. предикаты могут принимать только два значения (истинно/ложно или $0/1$), то к ним можно применять все операции алгебры логики: отрицание, конъюнкция, дизъюнкция и т.д.
Примеры предикатов
Пусть предикат $R(x, y)$: $«x = y»$ обозначает отношение равенства, где $x$ и $y$ принадлежат множеству целых чисел. В этом случае предикат R будет принимать истинное значение для всех равных $x$ и $y$.
Другой пример предиката -- РАБОТАЕТ($x, y, z$) для отношения «$x$ работает в городе y в компании $z$».
Еще один пример предиката -- НРАВИТСЯ($x, y$) для «x нравится y» для $x$ и $y$, которые принадлежат $M$ -- множеству всех людей.
Таким образом, предикатом является все то, что утверждается или отрицается о субъекте суждения.
Операции над предикатами
Рассмотрим применение операций алгебры логики к предикатам.
Определение 3
Конъюнкция двух предикатов $A(x)$ и $B(x)$ -- предикат, который принимает истинное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает истинное значение, а ложное значение -- во всех остальных случаях. Множество истинности $T$ предиката -- пересечение множеств истинности предикатов $A(x)$ и $B(x)$. Например: предикат $A(x)$: «$x$ -- чётное число», предикат $B(x)$: «$x$ делится на $5$». Таким образом, предикатом будет выражение «$x$ -- чётное число и делится на $5$» или «$x$ делится на $10$».
Определение 4
Дизъюнкция двух предикатов $A(x)$ и $B(x)$ -- предикат, который принимает ложное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает ложное значение и принимает истинное значение во всех остальных случаях. Множество истинности предиката -- объединение областей истинности предикатов $A(x)$ и $B(x)$.
Определение 5
Отрицание предиката $A(x)$ -- предикат, который принимает истинное значение при всех значениях $x$ из $T$, при которых предикат $A(x)$ принимает ложное значение и наоборот. Множество истинности предиката $A(x)$ -- дополнение $T"$ к множеству $T$ в множестве $x$.
Определение 6
Импликация предикатов $A(x)$ и $B(x)$ -- предикат, который является ложным при тех и только тех значениях $x$ из $T$, при которых $A(x)$ -- истинно, а $B(x)$ -- ложно, и принимает истинное значение во всех остальных случаях. Читается: «Если $A(x)$, то $B(x)$».
Пример 2
Пусть $A(x)$: «Натуральное число $x$ делится на $3$»;
$B(x)$: «Натуральное число $x$ делится на $4$».
Составим предикат: «Если натуральное число $x$ делится на $3$, то оно делится и на $4$».
Множество истинности предиката -- объединение множества истинности предиката $B(x)$ и дополнения к множеству истинности предиката $A(x)$.
Над предикатами помимо логических операций можно выполнять квантовые операции: применение квантора всеобщности, квантора существования и т.д.
Кванторы
Определение 7
Кванторы -- логические операторы, применение которых к предикатам превращает их в ложные или истинные высказывания.
Определение 8
Квантор -- логические операции, которые ограничивают область истинности предиката и создают высказывание.
Чаще всего используют кванторы:
квантор всеобщности (обозначается символом $\forall x$) -- выражение «для всех $x$» («для любого $x$»);
квантор существования (обозначается символом $\exists x$) -- выражение «существует $x$ такое, что... »;
квантор единственности и существования (обозначается $\exists !x$) -- выражение «существует точно одно такое $x$, что... ».
В математической логике существует понятие связывание или квантификация , которые обозначают приписывание квантора к формуле.
Примеры применения кванторов
Пусть -- предикат «$x$ кратно $7$».
С помощью квантора всеобщности можно записать следующие ложные высказывания:
любое натуральное число делится на $7$;
каждое натуральное число делится на $7$;
все натуральные числа делятся на $7$;
который будет иметь вид:
Рисунок 1.
Для записи истинных высказываний используем квантор существования :
существуют натуральные числа, которые делятся на $7$;
найдётся натуральное число, которое делится на $7$;
хотя бы одно натуральное число делится на $7$.
Запись будет иметь вид:
Рисунок 2.
Пусть на множестве $x$ простых чисел задан предикат: «Простое число является нечетным». Поставив перед предикатом слово «любое», получим ложное высказывание: «Любое простое число является нечетным» (например, $2$ является простым четным числом).
Поставим перед предикатом слово «существует» и получим истинное высказывание: «Существует простое число, которое является нечетным» (например, $x=3$).
Таким образом, предикат можно превратить в высказывание, если поставить перед предикатом квантор.
Операции над кванторами
Для построения отрицания высказываний, которые содержат кванторы, применяется правило отрицания кванторов :
Рисунок 3.
Рассмотрим предложения и выделим среди них предикаты, указав область истинности каждого из них.
Статья «Логика-predikatov.ru/logik/»
3.1. Понятие предиката
«Предикат » с английского переводится как сказуемое. Формально предикатом называется функция, аргументами которой могут быть произвольные объекты из некоторого множества, а значения функции «истина» или «ложь». Предикат можно рассматривать как расширение понятия высказывания.
Средства, предоставляемые логикой высказываний, оказываются недостаточными для анализа многих математических рассуждений. В алгебре логики не рассматриваются ни структура высказываний, ни, тем более, их содержание. В то же время и в науке, и в практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.
3.2. Логика предикатов
Логика предикатов , как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально – подлежащее, хотя оно может играть и роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения).
Субъект – это то, о чем что-то утверждается в высказывании, а предикат – это то, что утверждается о субъекте.
Логика предикатов – это расширение логики высказываний за счет использования предикатов в роли логических функций.
Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».
Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число» . При одних значениях х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.
Определение 1. Одноместным предикатом Р (х ) называется всякая функция одного переменного, в которой аргумент x пробегает значения из некоторого множества M , а функция при этом принимает одно из двух значений: истина или ложь.
Множество M , на котором задан предикат, называется областью определения предиката .
Множество , на котором предикат принимает только истинные значения , называется областью истинности предиката Р (х ).
Например, предикат P(x) - « x- простое число» определен на множестве натуральных чисел , а множество I P – это множество всех простых чисел.
Определение 2. Предикат Р (х ), определённый на множестве M , называется тождественно истинным (тождественно ложным ), если
Определение 3. Двухместным предикатом P (x, у ) называется функция двух переменных х и у , определённая на множестве М =М 1 ×М 2 и принимающая значения из множества {1,0}.
В качестве примеров двухместных предикатов можно назвать предикаты: Q (x, у ) – «х = у » предикат равенства, определённый на множестве R 2 =R ×R ; F (x, у ) – «х || у » прямая х параллельна прямой у , определённый на множестве прямых, лежащих на данной плоскости.
Говорят, что предикат Р (х ) является следствием предиката Q (х ) , если ; и предикаты Р (х ) и Q (х ) равносильны , если .
Пример 1. Среди следующих предложений выделить предикаты и для каждого из них указать область истинности:
- х + 5 = 1
- при х = 2 выполняется равенство х 2 – 1 = 0
- х 2 – 2х + 1 = 0
- существует такое число х , что х 3 – 2х + 1 = 0
- х + 2 < Зх – 4
- однозначное неотрицательное число х кратно 3
- (х + 2) – (3х – 4)
Решение
. 1) Предложение является одноместным предикатом Р
(х
), I P
= {– 4};
2) предложение не является предикатом. Это ложное высказывание;
3) предложение является одноместным предикатом Р
(х
), I P
= {1};
4) предложение не является предикатом. Это истинное высказывание;
5) предложение является одноместным предикатом Р
(х
), I P
= (3; +∞);
6) предложение является одноместным предикатом Р
(х
), I P
= {0; 3; 6; 9};
7) предложение не является предикатом;
Пример 2.
Изобразить на декартовой плоскости область истинности предиката
.
Решение . Неравенство, составляющее исходный предикат, ограничивает часть плоскости, заключенную между ветвями параболы , она изображена серой частью рисунка:
3.3. Логические операции над предикатами
Предикаты, так же, как высказывания, принимают два значения и и л (1, 0), поэтому к ним применимы все операции логики высказываний.
Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.
Пусть на некотором множестве М определены два предиката Р (х ) и Q (х ).
Определение 4. Конъюнкцией двух предикатов Р (х ) и Q (х ) называется новый предикат Р (х )&Q (х ), который принимает значение «истина» при тех и только тех значениях , при которых каждый из предикатов Р (х ) и Q (х ) принимает значение «истина» и принимает значение «ложь» во всех остальных случаях. Очевидно, что областью истинности предиката Р (х )&Q (х ) является общая часть областей истинности предикатов Р (х ) и Q (х ), т.е. пересечение .
Так, например, для предикатов Р (х ): «х – четное число» и Q (х ): « х кратно 3» конъюнкцией Р (х )&Q (х ) является предикат «х – четное число и х кратно 3», то есть предикат «х делится на 6».
Определение 5. Дизъюнкцией д вух предикатов Р (х ) и Q (х ) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях , при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Ясно, что областью истинности предиката является объединение областей истинности предикатов Р (х ) и Q (х ), то есть объединение .
Определение 6.
Отрицанием
предиката Р
(х
) называется новый предикат , который принимает значение «истина» при всех значениях , при которых предикат Р
(х
) принимает значение «ложь», и принимает значение «ложь» при тех значениях , при которых предикат Р
(х
) принимает значение «истина». Очевидно, что, .
Определение 7. Импликацией предикатов Р (х ) и Q (х ) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно Р (х ) принимает значение «истина», а Q (х ) – значение «ложь» и принимает значение «истина» во всех остальных случаях.
Ясно, что при выполнении логических операций над предикатами к ним применимы и равносильности алгебры логики. Для детального изучения темы необходим курс «Дискретной математики».
Операции над предикатами. Описание математических понятий с помощью логики предикатов.
§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 . Операция конъюнкции.
Конъюнкцией предикатов Р(х) и Q(x) , заданных на множестве Х , называется предикат Р(х) Q(x ), заданный на том же множестве и обращающийся в истинное высказывание при тех и только тех значениях х Х, при которых оба предиката принимают значения истины.
Если обозначить ТР Р(х) , Т Q - множество истинности предиката Q(х) , а множество истинности их конъюнкции TPÙQ, то, по всей видимости, TPÙQ = TP Ç TQ.
Докажем это равенство.
1. Пусть а Х и известно, что а Î TPÙQ . По определению множества истинности это означает, что предикат Р(х) Q(x ) обращается в истинное высказывание при х = а , т.е. высказывание Р(а) Q(а ) истинно. Так как данное высказывание конъюнкция, то по определению конъюнкции получаем, что каждое из высказываний Р(а) и Q(а) также истинно. Это означает, что а ТР и а ТQ . Таким образом, мы показали, что TPÙQ Ì ТР Ç ТQ .
2. Докажем обратное утверждение. Пусть а - произвольный элемент множества Х и известно, что а Î TP Ç TQ . По определению пересечения множеств это означает, что а ТР и а ТQ , откуда получаем, что Р(а) и Q(а) - истинные высказывания, поэтому конъюнкция высказываний Р(а) Q(а ) также будет истинна. А это означает, что элемент а принадлежит множеству истинности предиката Р(х) Q(x ), т.е. а Î TPÙQ .
Из 1 и 2 в силу определения равных множеств вытекает справедливость равенства TPÙQ = ТР Ç ТQ , что и требовалось доказать.
Наглядно это можно изобразить следующим образом.
3. Операция дизъюнкции.
Дизъюнкцией предикатов Р(х) и Q(x ) называется предикат Р(х) Q(x Х и обращающийся в истинное высказывание при тех и только тех значениях х Х, при которых принимает значение истины хотя бы один из предикатов Р(х ) или Q(x).
Аналогично доказывается, что TPÚQ = TP È TQ.
4 . Операция импликации.
Импликацией предикатов Р(х) и Q(x) , заданных на множестве Х , называется предикат Р(х) Q(x ), определенный на том же множестве Х и обращающийся в ложное высказывание при тех и только тех значениях х Х, при которых Р(х) принимает значение истины, а Q(x) - значение лжи.
5 .Операция эквиваленции.
Эквиваленцией предикатов Р(х) и Q(x) , заданных на множестве Х , называется предикат Р(х) Q(x ), определенный на том же множестве Х и принимающий значение истины при тех и только тех значениях х Х, при которых значения каждого из предикатов либо истинны либо ложны. Множество истинности в таком случае выглядит так:
TPÛQ
= .
Пример . На множестве М={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} заданы предикаты: А(х) - «число х не делится на 5 », В(х) - «х - число четное», С(х) - «х - число простое», D(x) - «число х кратно 3 ». Найти множество истинности следующих предикатов:
a) А(х) В(х); b) A(x) ; c) C(x)A(x); d) B(x)D(x) и изобразить их при помощи диаграмм Эйлера-Венна.
Решение: a) Найдем множество истинности предикатов.
А(х): T = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19};
В(х): Т = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}.
Множество истинности конъюнкции А(х) В(х) есть истинности T и Т .
В алгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности. Ни структура высказываний, ни, тем более, их содержание не затрагиваются. В то же время и в науке, и в практике используются заключения. существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.
Например, в рассуждении «Всякий ромб – параллелограмм; 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-местный предикат.