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

Определение 1: Отрицанием - местного предиката
, определенного на множестве
, называется новый- местный предикат, определенный на том же множестве. Обозначается:
. Читается: «неверно, что
». Предикат
принимает значение «истина» только для тех аргументов, для которых значение предиката
есть «ложь» и наоборот. Другими словами предикат
удовлетворяется теми и только теми аргументами, которые не удовлетворяют данному предикату
.

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

Определение 2: Конъюнкцией - местного предиката
, определенного на множестве
, и
- местного предиката
, определенного на множестве
, называется новый
- местный предикат, определенный на множестве
, обозначаемый. Читается: «
и
». Этот предикат принимает значение «истина» только для тех значений аргументов, для которых предикаты
и
одновременно принимают значение «истина».

Если, например,
- двуместный предикат, определённый на множестве
, а
- одноместный предикат, определённый на множестве, то конъюнкция этих предикатов
есть трёхместный предикат, определённый на множестве
. Этот новый предикат принимает значение «истина» для таких троек элементов
,
,
,
, для которых
и
.

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

Пусть
и
– два- местных предиката, зависящих от одних и тех же переменных. Тогда:

а) множество истинности конъюнкции равно пересечению множеств истинности ее членов;

б) множество истинности дизъюнкции равно объединению множеств истинности ее членов.

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

Всякое уравнение (неравенство), содержащее переменные, является предикатом, определённым на том же множестве, на котором задано уравнение (неравенство). Множество решений уравнения (неравенства) есть ничто иное, как множество истинности предиката. Это означает, что при подстановке корней уравнения (или решений неравенства) вместо неизвестных будут получены истинные высказывания. Если же в уравнение (неравенство) вместо переменных подставлять числа, не являющиеся решениями, то будут получены ложные высказывания. Всякая система уравнений (неравенств) может быть рассмотрена, как конъюнкция предикатов. Решить систему – значит найти область истинности конъюнкции предикатов. Совокупность уравнений (неравенств) есть ничто иное, как дизъюнкция предикатов. Равносильность уравнений (неравенств) означает равносильность соответствующих предикатов.

Если
, то говорят, что аргумент
удовлетворяет данному предикату. Например, число 3 удовлетворяет предикату
, а число 1 ему не удовлетворяет.

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

Определение 3: Пусть
- одноместный предикат, определенный на непустом множестве

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

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

Например, для предикатов «
» и «
», определенных на множестве действительных чисел, соответствующие универсальные высказывания будут иметь вид:
– «каждое действительное число равно самому себе» (истинное) и
– «каждое действительное число больше 2» (ложное).

Теорема 1: Если
- одноместный предикат, определенный на конечном множестве, состоящем из
элементов,,…,, то соответствующее ему универсальное высказывание эквивалентно конъюнкции
высказываний:

Доказательство. В самом деле, согласно определению квантора общности, высказывание

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

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

Определение 4: Пусть
- одноместный предикат, определенный на множестве
. Операция, превращающая предикат
в высказывание
(читается: «существует, удовлетворяющее предикату
»), называетсяквантором существования (или экзистенциональным высказыванием). Высказывание
будет истинным тогда и только тогда, когда предикат
выполнимый. Это высказывание будет ложным, если предикат
тождественно ложный.

Символ называется квантором существования по переменной. Его можно прочитать: «существуеттакой, что
», или «найдётся такой, что
». Символпроисходит от английского слова «Exist» (существует).

Теорема 2: Если
– одноместный предикат, определенный на конечном множестве из
элементов,,…,, то соответствующее ему экзистенциональное высказывание эквивалентно дизъюнкции
высказываний:

Доказательство: По определению: высказывание
будет ложно тогда и только тогда, когда ложны все
высказываний, которые получаются из данного предиката при замене переменнойаргументами,,…,соответственно. Последнее замечание возможно в том и только в том случае, когда ложна дизъюнкция этих
высказываний. Т.е. члены эквивалентности одновременно истинны или ложны, следовательно, эта эквивалентность истинна.

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

Следует запомнить, что для любого предиката
, определенного на множестве
выражения
и
– это высказывания, а не предикаты. Присутствие переменнойздесь чисто внешнее, связанное со способом обозначений. Поэтому переменная, входящая в выражения
и
, называетсясвязанной переменной, в отличие от переменной, входящей в предикат
, где переменная называетсясвободной. Если применить операцию «навешивания» кванторов двуместному предикату
по какой-нибудь переменной, то в результате двуместный предикат превратится в одноместный предикат с одной свободной переменной. Аналогичные рассуждения можно провести для второй переменной. Переменная, по которой был применён квантор, называетсясвязной переменной. Если применить кванторную операцию к - местному предикату по какой-нибудь переменной, то он превратится в
- местный предикат.

Если в любом предикате все переменные связаны, то этот предикат является высказыванием. Например, рассмотрим предикат
, определённый на некотором числовом множестве. Составим высказывание
. Это ложное высказывание, которое утверждает, что найдётся такое число, которое больше всякого числа(- единственное число для всех). Поменяв местами кванторы, получим новое высказывание:
. Это высказывание утверждает, что для любого числаможно подобрать такое число, что выполняется неравенство
(для каждогосуществует своё число). Это высказывание истинно. Видно, что при перестановке кванторов местами меняется смысл высказывания. Таким образом,перестановка разноимённых кванторов местами является недопустимой операцией. Одноимённые кванторы местами менять можно. Причем, одноимённые кванторы можно объединять в один, например: . Недопустимым является также применение нескольких кванторов по одной и той же переменной, например:
.

Определение 5: Универсальным высказыванием , соответствующим - местному предикату
, определенному на множестве

последовательным применениемкванторов общности по переменным
в любом порядке.

Обозначается такое высказывание и читается кратко так: «для всех
выполняется
».

Определение 6: Экзистенциональным высказыванием, соответствующим - местному предикату
, определенному на множестве
, называется высказывание, полученное из
последовательным применениемкванторов существования по переменным
в любом порядке.

Полученное экзистенциональное высказывание обозначают и читают так: «существует такой набор
, что выполняется
».

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

Теорема 3: (Условие тождественной истинности квантифицированного предиката).

‑местный предикат, полученный из ‑ местного предиката
, определенного на множестве
, применением квантора общности по какой–либо переменной является тождественно истинным тогда и только тогда, когда данный предикат
– тождественно истинный.

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

, определенному на множестве
. Последнее замечание возможно тогда и только тогда, когда предикат
– тождественно истинный, но т.к. аргументы
выбирались произвольно, то это равносильно тождественной истинности данного- местного предиката
. Теорема доказана.

Теорема 4: (Условие тождественной ложности квантифицированного предиката).

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

Доказательство: Пусть имеем
- местный предикат
, определенный на множестве
. Он будет тождественно ложен тогда и только тогда, когда его значение для произвольно взятых аргументов
есть «ложь». Это значит, что ложно экзистенциональное высказывание
, соответствующее одноместному предикату
, определенному на множестве
. Последнее возможно в том и только в том случае, когда предикат
тождественно ложен, а т.к. аргументы
выбирались произвольно, то и данный- местный предикат
тождественно ложен. Что и требовалось доказать.

До сих пор мы противопоставляли предикаты высказываниям. Однако удобнее считать высказывания 0 ‑ местными предикатами. Тогда любые два истинные и любые два ложных высказывания следует считать равносильными между собой.

Статья «Логика-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. Среди следующих предложений выделить предикаты и для каждого из них указать область истин­ности:

1. х + 5 = 1
2. при х = 2 выполняется равенство х 2 – 1 = 0
3. х 2 – 2х + 1 = 0
4. существует такое число х , что х 3 – 2х + 1 = 0
5. х + 2 < Зх – 4
6. однозначное неотрицательное число х кратно 3
7. (х + 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, 4, получаем высказывания, причем в первом случае оно будет истинным, а во втором –– ложным. Таким образом, каждому натуральному числу соответствует значение «И» и «Л» в зависимости от того, является оно простым или нет.

Следовательно, выражение «х –– простое число» определяет функцию одной переменной (одноместную), заданную на множестве натуральных чисел со значениями в множестве {И, Л}.

Аналогично, подставляя в выражение «х Подобным образом выражение «х и у –– родители z» определяет функцию трех переменных (трехместную) на множестве людей со значениями в множестве {И, Л}. Выражение х1 + х2 + … + хn = 0 определяет функцию n переменных (n–местную), заданную на множестве действительных чисел со значениями в множестве {И, Л}:

Такие функции называются предикатами.

Определение 1. n–местным предикатом на множестве М называется n–местная функция, аргументы которой принимают значения из множества М, а область значений есть множество {И, Л}.

Короче, n–местным предикатом на множестве М называется функция типа Мп→{И, Л}.

Для обозначения предикатов используют либо большие латинские буквы, либо символы: А(х, у), В(х), Р(х1, х2,…, хn) и т.д. (к предикантным символам А, В, Р добавляют в скобках символы переменных, от которых зависят данные предикаты). При этом, например, выражение А(10, 8) служит для обозначения (постоянного) высказывания, которое получается, если переменным х, и у предиката А(х, у) придать соответственно значения 10 и 8. Некоторые предикаты записывают с помощью тех или иных знаков, имеющих в теории определенный смысл, например: х = у, х > у, х + у = z и т.д.

При n = 1 n–местный предикат называют унарным, при n = 2 –– бинарным, а при n = 3 –– тернарным.

Определение 2. Пусть Р(х1, х2,…, хn) –– n–местный предикат, определенный на множестве М. Множеством истинности этого предиката называется совокупность таких упорядоченных n–ок (х1, …, хn), для которых Р(х1, х2,…, хn) принимает значение И.

Определение 3. Два предиката Р(х1, …, хn) и Q(х1, …, хn), определенные на одном и том же множестве М, называются равносильными на множестве М, если они принимают одинаковые значения И или Л при любых значениях х1, …, хn из множества М.

Таким образом, два предиката Р(х1, …, хn) и Q(х1, …, хn) на множестве М называются равносильными на множестве М, если множества истинности этих предикатов совпадают.

Определение 4. Предикат Р(х1, …, хn), определенный на множестве М, называется тождественно–истинным (тождественно–ложным) на М, если при подстановке вместо х1, …, хn любых элементов из множества М он принимает значение И (Л), т.е. множество истинности этого предиката Мn (пустое).

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

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

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

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

Подобным образом вводятся предикаты Р(х) ? Q(х), Р(х) Û Q(х).

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

Пусть Р(х, у) и Q(х, у) –– два двухместных предиката, определенных на множестве М. Тогда Р(х, у) Ù Q(y, z) –– трехместный предикат на множестве М, он принимает значение И для тех и только тех упорядоченных троек (х, у, z) множества М, для которых Р(х, у) и Q(y, z) одновременно принимают значения И.

Отметим еще, что Р(х, у) Ù Q(х, у) –– двухместный, а Р(х, у) Ù Q(z, v) –– четырехместный предикаты, определенные на множестве М.

Если Р(х) и Q(х) –– два одноместных предиката, то не следует смешивать предикаты Р(х) Ù Q(х) и Р(х) Ù Q(у). Первый из них –– одноместный, а второй –– двухместный предикаты.

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

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

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

Пусть Р(х) –– предикат «х –– простое число», определенный на множестве натуральных чисел. Тогда высказывание (х –– простое число) ложно на множестве натуральных чисел. Это же высказывание (х –– простое число) истинно на множестве простых чисел.

Определение 6. Пусть Р(х) –– одноместный предикат, определенный на множестве М. Символом $ обозначим высказывание, которое истинно, когда в множестве М существует такой элемент х0, что Р(х0) = И, и ложно в противоположном случае, т. е. $ –– истинное высказывание, если множество истинности предиката Р(х) непустое; в противном случае $ –– ложное высказывание.

Выражение $ читается «существует х такое, что Р(х)», а часть $х в выражении $ называют квантором существования. Например, высказывание $х (х –– простое число) на множестве натуральных чисел истинно, высказывание $ на множестве действительных чисел ложно.

Символ $ –– перевернутая первая буква слова exist (англ.), existieren (нем.), exister (фр.).

Замечание 1. Применение квантора превращает одноместные предикаты в высказывания (не зависящие от х). Совершенно аналогично применяются кванторы к любому предикату с большим числом переменных. В результате применения квантора к n –– местному предикату (при n > 0) получается (n – 1) –– местный предикат.

Замечание 2. К одному и тому же предикату можно применять кванторы несколько раз. Например, применив к предикату Р(х, у) квантор существования по х, мы получим одноместный предикат $, к которому опять можем применить квантор существования или квантор общности по переменной у. В результате получим высказывание

$у($ или у($.

Скобки обычно опускают, получая при этом выражения

$у$ или у$.

Замечание 3. Одинаковые кванторы можно переставлять, получая при этом эквивалентные высказывания, т.е. истинные эквиваленции.

Пример: В высказывании «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">

Рассматриваемые вопросы
1.
Понятие предиката. Область определения предиката.
2.
Одноместный предикат. Многоместный предикат.
3.
Логические операции над предикатами.

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

Выразительные возможности языка логики высказываний очень
ограничены. С ее помощью невозможно проанализировать
внутреннюю структуру даже очень простых рассуждений.
Пример: есть два умозаключения.
Любой человек смертен, Сократ - человек, следовательно, Сократ
смертен.
Крокодилы не летают, Луна - головка швейцарского сыра,
следовательно, сборная России выиграет чемпионат мира по футболу.
X Y Z.
Расширение
логики
высказываний
называется логикой предикатов

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

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

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

В высказывании все четко: это - конкретное утверждение о
конкретных объектах - истинное или ложное.
Предикат - предложение, похожее на высказывание, но все же им не
являющееся: о нем нельзя судить, истинно оно или ложно.

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

Логика предикатов, как и традиционная формальная логика,
расчленяет
элементарное
высказывание
на
субъект
(подлежащее, хотя оно может играть и роль дополнения) и
предикат (сказуемое, хотя оно может играть и роль
определения).
Субъект – это то, о чем что-то утверждается в высказывании
Предикат – это то, что утверждается о субъекте
Например, в высказывании “7 - простое число”, “7” – субъект,
“простое число” – предикат.
Это высказывание утверждает, что “7” обладает свойством
“быть простым числом”.

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

ПРИМЕР “7 - простое число”
Если в рассмотренном примере заменить конкретное число 7
переменной х из множества натуральных чисел, то получим
высказывательную форму:
“х – простое число”
При одних значения х (например, х=13, х=17) эта форма дает
истинные высказывания, а при других значениях х (например,
х=10, х=18) эта форма дает ложные высказывания.
Эта высказывательная форма определяет функцию одной
переменной х, определенной на множестве N, и принимающую
значения из множества {1;0}.
Здесь предикат становится функцией субъекта и выражает
свойство субъекта.

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

В естественной речи часто встречаются сложные высказывания,
истинность которых может изменяться при изменении объектов,
о которых идет речь, хотя форма самого высказывания остается
прежней.
Например:
«У кошки четыре ноги» - истинно,
«У слона четыре ноги» - истинно,
«У человека четыре ноги» - ложно.
Все эти высказывания имеют одну форму:
«У субъекта х четыре ноги».

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

Таким образом, раздел математической логики, изучающий логические
законы, общие для любой области объектов исследования
(содержащей хоть один объект) с заданными на этих объектах
предикатами (т. е. свойствами и отношениями) называется ЛОГИКОЙ
ПРЕДИКАТОВ
Объект – некоторая часть окружающего нас мира, которая может быть
рассмотрена как единое целое
Субъект – (в логике) подлежащее суждения, то есть предмет, о
котором что-либо говорится или мыслится
Переменное высказывание, истинностное значение которого зависит
от параметра, и называется предикатом.
Предикат от лат. Praedicatum – сказанное. Таким образом, предикат
есть функция, определенная на некотором множестве параметров и
со значениями в {0, 1}.

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

Определение 1. Одноместным предикатом Р(х) называется такая функция
одной переменной, в которой аргумент х пробегает значения из некоторого
множества М, а функция при этом принимает одно из двух значений: истина
или ложь.
Само множество М называется предметным множеством, а аргументы
x1,...,xn M - предметными переменными.
Множество М, на котором задан предикат, называется областью определения
предиката.
Множество, на котором предикат принимает только истинные значения,
называется областью истинности предиката Р(х).
Определение 2. N-местным предикатом называется такая функция n
переменных Q(x1, x2, …,xn), определенная на множестве М=М1 М2 … Мn
и принимающая на этом множестве одно из двух значений: истина или ложь.
Можно считать, что высказывание это нульместный предикат, то есть
предикат, в котором нет переменных для замены.

10. Понятие предиката. Примеры

Пример 1
Пусть предметное множество М есть класс млекопитающих.
Рассмотрим одноместный предикат Р(х):
«У х четыре ноги».
Тогда Р(слон) = 1,
Р(кошка) = 1,
Р(человек) =0.
Пример 2
Пусть М - множество натуральных чисел.
Рассмотрим двухместный предикат G(x,y): х<у.
Тогда, например, G(l,3) = l,
G(8,5) = 0.

11. Классификация предикатов

Предикат называется:
А) Тождественно истинным, если значение его для любых
аргументов есть «истина»
Предикат “x+y=y+x” является тождественно истинным.
Б) Тождественно ложным, если значение его для любых
аргументов есть «ложь»
Предикат “x+1=x” – тождественно ложным.
В) Выполнимым, если существует, по крайней мере, одна nсистема его аргументов, для которой значение предиката есть
«истина».
Предикат “x+y=5” – выполнимым.

12. Равносильность предикатов

Два n-местных предиката Р(х1, х2, ..., хn) и Q(x1, x2, ..., хn),
заданных над одними и теми же множествами М1, М2, …, Мn,
называются равносильными, если набор предметов (элементов)
а1 М1, а2 М2, .., an Мn превращает первый предикат в
истинное высказывание Р(а1, а2, …, аn) в том и только в том
случае, когда этот набор предметов превращает второй предикат
в истинное высказывание Q(а1, а2, …, аn).
Предикаты Р(х1, х2, ..., хn) и Q(х1, х2, ..., хn) равносильны тогда
и только тогда, когда их множества истинности совпадают
Р+ = Q+.
Переход от одного равносильного предиката к другому
называется равносильным преобразованием первого

13. Пример

Пусть требуется решить
уравнение (найти множество
истинности предиката):
4х-2=-3х-9
Преобразуем его равносильным образом:
4х-2=-3х-9 4х+3х=-9 + 2 x = -1.
Ответ:{-1} - множество всех решений данного уравнения
(множество истинности данного предиката).

14. Следование предикатов

Предикат Q(х1, х2, ..., хn), заданный над множествами М1, М2,
…, Мn, называется следствием предиката Р(х1, х2, ..., хn),
заданного над теми же множествами, если он превращается в
истинное высказывание на всех тех наборах значений
предметных переменных из соответствующих множеств, на
которых в истинное высказывание превращается предикат Р(х1,
х2, ..., хn).
Предикат Q является следствием предиката Р тогда и только
тогда, когда Р + Q +.
Обозначается P Q

15. Пример

Одноместный предикат, определенный на
множестве
натуральных чисел, «n делится на 3» является следствием
одноместного предиката, определенного на том же множестве,
«n делится на 6».
Из двух предикатов первый будет следствием второго, если
считать, что оба предиката заданы на множестве Z целых чисел.

16. Упражнение 1.

Среди следующих предложений выделите предикаты:
1) Луна есть спутник Венеры
2) Планеты х и y принадлежат Солнечной системе
3) 5 5 70 6 10 150
2
4) x 3x 2 0
4
x
3x 8
5)
6) Любое простое число не имеет делителей, отличных от себя и 1
7) Натуральное число n не меньше 1
8) Треугольник АВС равен треугольнику А1В1С1
9) x 2 2 x 1 0
1
10) 1 tg 2 x
cos 2 x
11) ln x sin x
Ответ: 2); 4); 7)-11)

17.

Упражнение 2.
Среди следующих предложений выделить предикаты и для каждого из
них указать область истинности.
1) x+5=1
2) При х=2 выполняется равенство х2-1=0
3) х2-2x+1=0
4) Существует такое число х, что х2-2x+1=0
5) x+2<3x-4
6) Однозначное число x кратно 3
7) (x+2)-(3x-4)
1)
2)
3)
4)
5)
6)
7)
Одноместный предикат P(x), Ip=-4
Ложное высказывание. Не предикат
Одноместный предикат P(x), Ip=1
Истинное высказывание. Не предикат
Одноместный предикат P(x), Ip=(3;+)
Одноместный предикат P(x), Ip=(0;3;6;9)
Не предикат

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

Отрицанием предиката P(x) называется новый предикат,
множество истинности которого является дополнением
множества истинности предиката Р(х), то есть:
I p CI p
Пример. Предикат P(x) - «x<3»
Отрицание предиката – «x>3»

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

Конъюнкцией предикатов P(x) и Q(x) называется новый

значениях, при которых каждый из предикатов P(x) и Q(x)

Множество истинности есть пересечение множеств истинности
I P Q I p I q
Пример. Предикаты P(x) - «x>-3» и Q(x) – «x<3»
Конъюнкция предикатов – «(x>-3) Λ (x<3)»

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

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

I P Q I p I q
Пример. Предикаты P(x) - «x≠0» и Q(x) – «y ≠0»
Дизъюнкция предикатов – «(x ≠0) v (y ≠0)»

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

Импликацией предикатов P(x) и Q(x) называется предикат,
который имеет значение ложь на тех и только на тех наборах
аргументов х, на которых P(x) имеет значение 1, а Q(x) –
значение 0.
Множество истинности есть объединение множеств истинности
I P Q CI p I q
Пример. Предикаты P(x) - «Натуральное число х делится на 3».
Q(x) – «Натуральное число х делится на 4»
Импликация предикатов – «Если натуральное число х
делится на 3, то оно делится и на 4»

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

Эквиваленцией P(x) и Q(x) называется предикат, который имеет
значение истина на тех и только на тех наборах аргументов х, на
которых значения истинности P(x) и Q(x) совпадают.
Множество истинности есть объединение множеств истинности
I P Q (CI p CI q) (I p I q)

23.

Упражнение 3.
Пусть даны предикаты P(x): «х – четное число» и Q(x): «х кратно 3»,
определенные на множестве N. Найти области истинности
предикатов:
1) P(x) Λ Q(x)
2) P(x) v Q(x)
3) ¬P(x)
4) P(x) -> Q(x)
Ip = {2,4,6,8,10,12,…2n,…}, Iq= { 3,6,9,12,...3n,…}
1)
2)
3)
4)
{6,12,…6n,…}
{2,3,4,6,…2n,3n,…}
{1,3,5,…2n-1,…}
{1,3,5,…2n-1,…} v {3,6,9,…3n,…}

24.

Упражнение 4.
Если значения x,y принадлежат отрезку , то в списке
выражений следующего вида:
1) х=2 или y=7
2) x-y=7
3) x+y<2
4) x 2 5 0
5) 3 6) x>12
Число истинных и ложных предикатов соответственно равно:
А) 2,4
Б) 1,4
В) 3,3
Г) 1,5
Д) 2,3
ОТВЕТ Г) 1,5

25.

Упражнение 5.
Запишите предикат (условие, которое может быть и сложным),
полностью описывающий область, нестрого заключенную между
окружностью с центром в начале координат и радиусом 2 и
квадратом, в который вписана эта окружность.
Уравнение окружности имеет вид: x 2 y 2 4
Уравнения квадрата: x 2
y 2
Искомая область образуется пересечением внешней области
окружности, и внутренней области квадрата
Таким образом, ответ: (x 2 y 2 4) & (x 2) & (y 2)

26.

Самостоятельно
Для более подробного изучения материала
самостоятельно читаем:
УЧЕБНИК: «Математическая логика и теория
алгоритмов»,
автор Игошин В.И.
Страницы 146-156