Главная Биология-репетитор Обычные логические операции над предикатами. Предикаты. Операции над предикатами. Композиция машины Тьюринга

Обычные логические операции над предикатами. Предикаты. Операции над предикатами. Композиция машины Тьюринга

Понятие предиката

Определение 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 (х ) – значение «ложь» и принимает значение «истина» во всех остальных случаях.

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

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

Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.

Пусть на некотором множестве М определены два предиката Р(х) и Q(х).

Определение 1. Конъюнкцией двух предикатов Р(х) и Q(х) называется новый предикат Р(х)& Q(х), который принимает значение «истина» при тех и только тех значениях , при которых каждый из предикатов принимает значение «истина» и принимает значение «ложь» во всех остальных случаях.

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

Так, например, для предикатов Р(х): «х – четное число» и Q(х): «х кратно 3» конъюнкцией P(x)&Q(x) является предикат «x– четное число» и «х кратно 3», то есть предикат «x делится на 6».

Определение 2. Дизъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х) ∨Q(x), который принимает значение «ложь» при тех и только тех значениях, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях.

Ясно, что область истинности предиката Р(х) ∨Q(х) является объединение областей истинности предикатов Р(х) и Q(x), то есть объединение.

Определение 3. Отрицанием предиката Р(х) называется новый предикат Р(х), который принимает значение «истина» при всех значениях . при которых предикат Р(х) принимает значение «ложь», и принимает значение «ложь» при тех значениях, при которых предикат Р(х) принимает значение «истина».

Из этого определения следует, что .

Определение 4. Импликацией предикатов Р(х) и Q(x) называется новый предикат Р(х) → Q(x), который является ложным при тех и только тех значениях , при которых одновременно Р(х) принимает значение «истина», а Q(x) – значение «ложь» и принимает значение «истина» во всех остальных случаях.

Так как при каждом фиксированном справедлива равносильность, то

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

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

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

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

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

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

,,,

Например, рассмотрим предикат Р(х,у): «х:у», определенный на множестве N. Применение кванторных операций к предикату Р(х, у) приводит к восьми возможным высказываниям:

1. – «Для всякого у и для всякого х у является делителем х».

2. – «Существует у, которое является делителем всякого х».

3. , – «Для всякого у существует х такое, что х делится на у».

4. – «Существует у и существует х такие, что у является делителем х».

5. – «Для всякого х и для всякого у у является делителем х».

6. «Для всякого х существует такое у, что х делится на y».

7. «Существует х и существует у такие, что у является делителем х».

8. – «Существует х такое, что для всякoгo у х делится наy».

Легко видеть, что высказывания 1, 5 и 8 ложны, а высказывания 2, 3, 4, 6 и 7 истинны.

Из рассмотренных примеров видно, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания, а значит, и eгo логическое значение (например, высказывания 3 и 8).

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

Если же хотя бы для одного элемента окажется ложным, то ложными будут высказываниеи конъюнкция, следовательно, справедлива равносильность.

Нетрудно показать, что справедлива и равносильность

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

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

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

Определение 1.

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат , который принимает значение “истина” при тех и только тех значениях , при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

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

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Определение 2.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат , который принимает значение “ложь” при тех и только тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

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

Определение 3.

Отрицанием предиката P(x) называется новый предикат или , который принимает значение “истина” при всех значениях , при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат P(x) принимает значение “истина”.

Очевидно, что , т.е. множество истинности предиката является дополнением к множеству I P .

Определение 4.

Импликацией предикатов P(x) и Q(x) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

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

Определение 5.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат , который обращается в “истину” при всех тех и только тех , при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем:

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

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

Пусть имеется предикат Р(х) определенный на множестве М. Если “а” – некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называют единичным . Например, r(x): “х – четное число” – предикат, а r (6)- истинное высказывание, r (3) – ложное высказывание.

Это же относится и к n – местным предикатам: если вместо всех предметных переменных х i , i= подставить их значения, то получим высказывание.

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

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

Пусть Р(х) – предикат , определенный на множестве М. Под выражением понимают высказывание , истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: “Для всякого х Р(х) истинно ”.

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

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

Пусть P(x) -предикат определенный на множестве М. Под выражением понимают высказывание , которое является истинным, если существует элемент , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).

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

Рассмотрим предикат P(x) определенный на множестве M={a 1 ,…,a n }, содержащем конечное число элементов. Если предикат P(x) является тождественно - истинным, то истинными будут высказывания P(a 1),P(a 2),…,P(a n). При этом истинными будут высказывания и конъюнкция .

Если же хотя бы для одного элемента P(a k)окажется ложным, то ложными будут высказывание и конъюнкция . Следовательно, справедлива равносильность .

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

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

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

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

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

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

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

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

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

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

Определение 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 имело решение.