Перечислите операции которые можно осуществлять над предикатами

Обновлено: 19.04.2024

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

Начнем с простого частного случая — одноместных предикатов, у которых области допустимых значений переменных совпадают. Образуем из двух предикатов новый предикат . Это предикат от двух свободных переменных х и у, и истинностное значение его на любом наборе допустимых значений переменных определяется как истинностное значение высказывания Аналогично определяются предикаты

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

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

Рассмотрим еще несколько примеров:

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

Логическое следствие. Равносильные предикаты.

ОПРЕДЕЛЕНИЕ. Предикат называется тождественно истинным, если для любого набора допустимых значений входящих в него свободных переменных его истинностным значением является И.

Примером тождественно истинного предиката может служить трехместный предикат, заданный неравенством где х, у, z — рациональные переменные.

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

ОПРЕДЕЛЕНИЕ. Предикат называется логическим следствием предиката если предикат является тождественно истинным.

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

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

Доказательство этого утверждения предоставляется читателю.

ОПРЕДЕЛЕНИЕ. Предикат называется логическим следствием предикатов если предикат

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

ОПРЕДЕЛЕНИЕ. Предикаты называются равносильными (логически эквивалентными), если предикат является тождественно истинным.

Запись означает, что предикаты равносильны.

Легко видеть, что предикаты равносильны тогда и только тогда, когда

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

ОПРЕДЕЛЕНИЕ. Предикат называется тождественно ложным, если его истинностным значением является Л для любого набора допустимых значений входящих в него свободных переменных.

Например, тождественно ложным является предикат где целочисленная переменная.

ОПРЕДЕЛЕНИЕ. Предикат называется выполнимым у если существует хотя бы один набор допустимых значений входящих в него свободных переменных, на котором его истинностным значением является И.

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

Любой предикат либо тождественно истинен, либо выполним, либо тождественно ложен.

При изучении высказываний мы отмечали, что утверждение с переменными не является высказыванием. Можно, например, рассмотреть предложение %%P(x) : x^2 + 1 > 2%% с переменной %%x \in \mathbb R%%. Это предлождение не является высказыванием, так как нельзя сказать истинно оно или ложно. Однако, если заменить переменную %%x%% на какое-либо значение, например, %%x = 1%%, получаем высказывание %%2 > 2%%, которое является ложным. Заменив переменную %%x%% на значение %%x = 2%%, получим истинное высказывание %%5 > 2%%. Итак есть выражение %%P(x)%% не являющиееся высказыванием, но превращающееся в него при замене переменной %%x%% на ее произвольное значение из соответствующего множества.

Определение

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

Примеры

Следующие предложения являются одноместными предикатами:

%%P(x): x^ 2 + 1 > 2%%, где %%D%% — множество действительных чисел.
%%Q(x):%% Длина отрезка равна %%1%%, где %%D%% — множество всех отрезков прямой.

Следующие предложения не являются одноместными предикатами:

%%n%%-местный предикат

%%n%%-местым предикатом с областью определения %%D = D_1 \times D_2 \times \ldots \times D_n%% называется предикат %%P(x_1, x_2, \ldots, x_n)%% от %%n%% переменных, который превращается в высказывание при замене переменных %%x_1, x_2, \ldots, x_n%% на их значения из множеств %%D_1, D_2, \ldots, D_n%% соответственно.

Тогда предложение прямая %%x%% параллельна прямой %%y%% является двуместным предикатом %%P(x, y)%%, где %%X, Y%% — множество всех прямых.

Область определения предиката

Рассмотрим %%n%%-местный предикат %%P(x_1, x_2, \ldots, x_n)%%. В этом случае переменные берутся из множеств %%D_1, D_2, \ldots, D_n%% соответственно. Можно рассмотреть множество %%D = D_1 \times D_2 \times \ldots \times D_n%% — декартово произведение множеств %%D_1, D_2, \ldots, D_n%%, элементами которого являются всевозможные упорядоченные %%n%%-ки %%(d_1, d_2, \ldots, d_n)%% элементов исходных множеств.

Множество %%D%% называется областью определения предиката.

Область истинности

Областью истинности предиката %%P(x_1, x_2, \ldots, x_n)%% называется множество всех %%n%%-ок %%(d_1, d_2, \ldots, d_n) \in D%% таких, что при замене %%x_1%% на %%d_1%%, %%x_2%% на %%d_2%%, . %%x_n%% на %%d_n%% получается истинное высказывание.

Пример

На множестве %%D = \< 1, 2, 3, 4, 5, 6, 7, 8, 9\>%% рассмотрим одноместный предикат %%P(x): x%% — простое число. Найти область истинности предиката %%P(x)%%.

Обозначим область истинности буквой %%A%%. Тогда %%A%% состоит из таких элементов, при которых выполняется предикат %%P(x)%%. Поэтому %%A = \%%.

Операции над предикатами

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

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

Отрицанием предиката %%P(x)%% называется новый предикат, обозначаемый %%\overline%% и являющийся ложным для тех и только тех %%x%%, для которых предикат %%P(x)%% истинный.

Конъюнкцией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) \land Q(x)%% и являющийся истинным для тех и только тех %%x%%, для которых предикаты %%P(x)%% и %%Q(x)%% истинны.

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

Импликацией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) \rightarrow Q(x)%% и являющийся ложным для тех и только тех %%x%%, для которых предикаты %%P(x)%% истинный, а %%Q(x)%% ложный.

Эквиваленцией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) \leftrightarrow Q(x)%% и являющийся истинным для тех и только тех %%x%%, для которых предикаты %%P(x)%% и %%Q(x)%% имеют одинаковые значения.

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

Предикаты %%P(x)%% и %%Q(x)%% эквивалентные , если для любого значения переменной %%x%% их значения истинности совпадают. Обозначают $$P(x) \equiv Q(x).$$

Законы алгебры предикатов

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

В случае тождественно истинных и тождественно ложных предикатов имеем следующие определения.

Предикат %%P(x_1, x_2, \ldots, x_n)%% называется тождественно истинным если при любой замене переменных %%x_1, x_2, \ldots, x_n%% на их значения предикат превращается в истинное высказывание.

Предикат %%P(x_1, x_2, \ldots, x_n)%% называется тождественно ложным если при любой замене переменных %%x_1, x_2, \ldots, x_n%% на их значения предикат превращается в ложное высказывание.

Высказывание является частным случаем предиката, когда в предикате нет переменных. То есть высказывание является предикатом %%0%% порядка (от %%0%% переменных).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение. Предложения, содержащие переменные, истинность или ложность которого зависит от значения переменного, входящего в него, называется предикатом. Другими словами, это функция, заданная на определенном множестве. Обозначение Р(х), Р(х,у), …, Р(х1,х2, …,хn).

Основные множества для предикатов

Считается, что с каждым предикатом задано множество, из которого выбирают значение переменных. Такое множество называют областью определения предиката. Обозначение D(P).

Пример. Р(х)=«х+3 . Какое бы число не поставить вместо х, будем получать либо ложное либо истинное высказывание.

Подмножеством области определения предиката, на котором он принимает значение истинность, называется множеством истинности данного предиката. Обозначение М(Р). М(Р) D(P).

Пример для Р(х)=«х+3

Операции над предикатами

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

Пример. =\ =то есть убрать из D(P) все числа, делящиеся на 9.

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

Пример. = =

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

= =

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

Пример. =\ =

Эквиваленцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х) ↔ Q(x), определённый на множестве D(Р) и истинный при тех значениях переменных х, при которых либо оба предиката истины, либо оба предиката ложны.

= ,

Кванторы. Операции навешивания квантора

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

Задания для самостоятельной работы

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

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

однозначное число х кратно 3;

На множестве M = определены предикаты: P(x) - "число Х делится на 6" и Q(x) - "число Х 30". Найдите область истинности предикатов , , , ,

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

а) Некоторые машины умнее людей.

б) Любой играет в теннис лучше Фрэда.

в) Для каждого действует существует равное и противоположно направленное противодействие.

г) Каждый игрок в гольф, в конце концов, будет обыгран более сильным игроком

Над предикатами можно проделывать те же самые логические операции, что и над высказываниями. Рассмотрим основные три операции в их связи с операциями над множествами.

Определение. Отрицанием n – местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, называется новый n-местный предикат, определенный на тех же множествах, обозначаемый Р(х₁, х₂, …, х_n), который превращается в истинное высказывание при всех тех значениях предметных переменных, при которых исходный предикат превращается в ложное высказывание.

Теорема. Для n-местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, множество истинности его отрицания Р(х₁, х₂, …, х_n) совпадает с его дополнением множества истинности данного предиката:

Определение. Конъюнкцией n – местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, и т-местного предиката Q(у₁, у₂, …, у_т), определенного на множествах N₁, N₂, …, N_m, называется новый (n + m)-местный предикат, определенный на множествах М₁, М₂, …, М_n, N₁, N₂, …, N_m, обозначаемый Р(х₁, х₂, …, х_n) Q(у₁, у₂, …, у_т), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания.

Для n-местных предикатов Р(х₁, х₂, …, х_n) и Q(х₁, х₂, …, х_n), определенных на множествах М₁, М₂, …, М_n, множество истинности конъюнкции Р(х₁, х₂, …, х_n) Q(х₁, х₂, …, х_n) совпадает с пересечением множеств истинности исходных предикатов:

Определение. Дизъюнкцией n – местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, и т-местного предиката Q(у₁, у₂, …, у_т), определенного на множествах N₁, N₂, …, N_m, называется новый (n + m)-местный предикат, определенный на множествах М₁, М₂, …, М_n, N₁, N₂, …, N_m, обозначаемый Р(х₁, х₂, …, х_n) Q(у₁, у₂, …, у_т), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один исходный предикат.

Теорема. Для n-местных предикатов Р(х₁, х₂, …, х_n) и Q(х₁, х₂, …, х_n), определенных на множествах М₁, М₂, …, М_n, множество истинности дизъюнкции Р(х₁, х₂, …, х_n) Q(х₁, х₂, …, х_n) совпадает с объединением множеств истинности исходных предикатов:

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

Читайте также: