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

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

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

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

Кванторные операции над предикатами. 11

Квантор общности ∀. 11

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

Применение кванторов к естественному языку. 15

Операции над кванторами. 15

Контрольные вопросы. 16

Введение

У имени существительного «предикат» есть несколько значений.

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

Предикаты

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

Определение 1: Предложение, содержащее переменные, которые при замене их на возможные значения становятся высказываниями, называются предикатом или высказывательной формой.

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

Определение: Предикат, зависящий от одной переменной, называют одноместным. Предикат, зависящий от n переменных, называют n- местным предикатом.

Таким образом, бывают двухместные, трехместные и т.д. предикаты.

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

Предложение А(x): «|x|=x» является предикатом одной переменной (одноместным).

Предложение «Река х впадает в озеро Байкал» является одноместным предикатом, определенным над множеством всех названий рек. Подставив вместо предметной переменной х название «Баргузин», получим высказывание «Река Баргузин впадает в озеро Байкал». Это высказывание истинно. Подставив вместо предметной переменной х название «Днепр», получим ложное высказывание «Река Днепр впадает в озеро Байкал».

Предложение (выражение) «х 2 +y 2 ≤9» является двухместным предикатом, заданным над множествами R, R. Множества, на которых задан двухместный предикат, совпадают (говорят, что это «двухместный предикат задан на множестве R2»). Пара действительных чисел 2, 2 превращает данный предикат в истинное высказывание: «2 2 +2 2 ≤9», а пара чисел 2, 3 — в ложное:

Домашнее задание: Самостоятельно докажите, почему предикат в примере 6 тождественно истинный?

Двухместный предикат «х 2 +y 2 2 +y 2 =9», заданного на множестве R2, есть множество всех таких пар действительных чисел, которые являются координатами точек плоскости, образующими окружность с центром в начале координат и радиусом 3.

Определение: Предикаты А(х) и В(х) с одной и той же областью определения называются равносильными, если они имеют одинаковые множества истинности. Их обозначают: А(х) ⟺ В(х)

Предикаты А(х): «|x-1|=x-1» и В(х): «х-1=√(х − 1) 2 » заданные на множестве действительных х, имеют одинаковые множества истинности х≥1, поэтому А(х) ⟺ В(х).

Пусть А(х) и В(х) – предикаты с некоторой частью области определения переменной х.

Определение: Предикат В(х) называют следствием предиката А(х), если множество истинности предиката А(х) является частью множества истинности предиката В(х).

Например, из равенства х=0 следует, что sinx=0, но не наоборот. Пояснение: Здесь даны два предиката: А(х): «х=0» и В(х): «sinx=0», определенные на множестве действительных чисел. Множеством истинности предиката А(х):

«х=0» является единственное значение х=0 среди всех действительных чисел, но множество истинности предиката В(х): «sinx=0», имеющего ту же область определения, содержит бесконечно много значений х, задаваемых формулой х=πk (k=0; ±1; ±2…), среди которых есть и х=0. Это означает, что предикат В(х) есть следствие предиката А(х).

Определение: Предикаты А(х) и В(х) одной и той же областью определения равносильны тогда и только тогда, когда В(х) есть следствие предиката А(х), и А(х) есть следствие предиката В(х).

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

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

Источник

MT1102: Линейная алгебра (введение в математику)

При изучении высказываний мы отмечали, что утверждение с переменными не является высказыванием. Можно, например, рассмотреть предложение %%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%%. Одноместный предикат будем называть унарным или предикатом от одной переменной.

Примеры

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

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

%%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%% называется областью определения предиката.

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

Пример

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

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

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

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

Пусть %%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_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. ОБЛАСТЬ ОПРЕДЕЛЕНИЯ И ОБЛАСТЬ ИСТИННОСТИ ПРЕДИКАТА Примеры: 1) Р(х) – «х –четное число» UP = N IP= 2) Q(x) – «2х – 3 = 0» UQ = R, IQ = <1,5>3) P(x, y) – «х кратно у» UP = N2 IP =

2. ОБЛАСТЬ ОПРЕДЕЛЕНИЯ И ОБЛАСТЬ ИСТИННОСТИ ПРЕДИКАТА

2. ОБЛАСТЬ ОПРЕДЕЛЕНИЯ И ОБЛАСТЬ ИСТИННОСТИ ПРЕДИКАТА Напр.: 1) «(х – у)(х + у) = х2 – у2» – тождественно истинный двуместный предикат 2) «х2 – 2х = 0» – выполнимый одноместный предикат 3) «х + 1 = х» – тождественно ложный одноместный предикат

2. ОБЛАСТЬ ОПРЕДЕЛЕНИЯ И ОБЛАСТЬ ИСТИННОСТИ ПРЕДИКАТА Опр. Два предиката называются эквивалентными (равносильными), если они определены на одном и том же множестве и их множества истинности совпадают.

ПРИМЕР Идентифицируйте следующие предложения. Для предикатов найдите их область определения и область истинности. Укажите вид предиката. «х2 + 1» «y 0» «х – 5 = 4х + 1» «n – кратно 5» «х2 – 2х + 3 ≥ 0» «с2 = а2 + в2 »

II. КОНЪЮНКЦИЯ ПРЕДИКАТОВ Опр. Конъюнкцией 2-х предикатов P(x) и Q(x) называется предикат P(x) /\ Q(x), который становится истинным высказыванием лишь при тех значениях х, при которых оба предиката становятся истинными высказываниями. (!!) Очевидно, что множество истинности предиката P(x) /\ Q(x) – есть пересечение множеств истинности исходных предикатов.

III. ДИЗЪЮНКЦИЯ ПРЕДИКАТОВ Опр. Дизъюнкцией 2-х предикатов P(x) и Q(x) называется предикат P(x) \/ Q(x), который становится истинным высказыванием при тех значениях х, при которых хотя бы один из предикатов становится истинными высказываниями. (!!) Очевидно, что множество истинности предиката P(x) \/ Q(x) – есть объединение множеств истинности исходных предикатов.

V. ЭКВИВАЛЕНЦИЯ ПРЕДИКАТОВ Опр. Эквиваленцией 2-х предикатов P(x) и Q(x) называется предикат P(x) ↔ Q(x), который становится истинным высказыванием при тех значениях х, при которых предикаты Р(х) и Q(x) становятся высказыванием с одинаковыми значениями истинности.

ПРИМЕР На множестве А = <3; 4; 5; …; 17>заданы предикаты: Р(х) – «х кратно 3», Q(x) – «х – составное число», S(x) – «х – нечетное число». Найдите множества истинности следующих предикатов: 1) Q (x) 2) P(x) /\ Q(x) 3) P(x) \/ S(x); 4) S(x) → Q(x); 5) P(x) ↔ Q(x).

I. КВАНТОР ВСЕОБЩНОСТИ Обозначается: x P(x) Читается: для всех, для любого, для каждого x выполняется условие P(x) все х из U обладают свойством Р(х) Например: 1) P(x) – «Река x имеет исток» x P(x) – «Любая река имеет исток» 2) Р(х) – «х – простое число» x P(x) – «Все натуральные числа простые»

I. КВАНТОР ВСЕОБЩНОСТИ Опр. Переход от одноместного предиката Р(х) к высказыванию xP(x) называется операцией связывания предметной переменной х квантором общности. При этом переменная х называется связанной. (!!) Очевидно, что такое высказывание является истинным тогда и только тогда, когда Р(х) – тождественно истинный предикат.

I. КВАНТОР ВСЕОБЩНОСТИ Рассмотрим теперь двуместный предикат Р(х; у) – «х делится на у», определенный на множестве 2 Ясно, что х Р(х; у) – одноместный предикат от предметной переменной у: «Все натуральные числа делятся на у» При у = 3 – ложное высказывание При у = 1 – истинное высказывание Т.о., это одноместный выполнимый предикат Очевидно, что предикат у Р(х; у) является тождественно ложным предикатом, а х у Р(х; у) – есть ложное высказывание.

II. КВАНТОР СУЩЕСТВОВАНИЯ Обозначается: x P(x) Читается: существует, найдется некоторое, какое-то x, для которого выполняется P(x) Например: 1) P(x) – «Дверь x закрыта» x P(x) – «Существует дверь, которая закрыта» 2) Р(х) – «х – простое число» x P(x) – «Существует простое натуральное число»

II. КВАНТОР СУЩЕСТВОВАНИЯ Опр. Переход от одноместного предиката Р(х) к высказыванию xР(х) называется операцией связывания предметной переменной х квантором существования. (!!) Высказывание xР(х) является ложным тогда и только тогда, когда Р(х) – тождественно ложный предикат.

II. КВАНТОР СУЩЕСТВОВАНИЯ (!!) В п-местном предикате Р(х1; х2; …; хп) некоторые предметные переменные могут быть связаны квантором общности, а некоторые – квантором существования. Местность такого предиката определяется числом свободных переменных. Напр.: х у P(x; y; z) – одноместный предикат от переменной z.

3. ПРЕДИКАТНАЯ ФОРМУЛА 4) Если Ф1 и Ф2 – формулы, имеющие одинаковый характер вхождения предметных переменных, то Ф1  Ф2, Ф1  Ф2, Ф1 → Ф2, Ф1 ↔ Ф2 – формулы алгебры предикатов. В этих формулах те переменные, которые в исходных формулах были свободны, являются свободными, а те, которые были связанными, остаются связанными.

5. ПРЕДИКАТНАЯ ФОРМУЛА (!!)1 Очевидно, что все формулы алгебры высказываний являются формулами алгебры предикатов. (!!)2 Иерархия логических операций остается та же, что и в алгебре высказываний, однако, следует иметь в виду, что кванторы связывают сильнее, чем другие логические связки.

5. ПРЕДИКАТНАЯ ФОРМУЛА Опр. Две формулы алгебры предикатов называются равносильными на области U, если они принимают одни и те же истинностные значения, какие бы значения ни придавались входящим в них переменным из области U. (!!) Все равносильности, известные в алгебре высказываний, распространяются на алгебру предикатов. Кроме них в алгебре предикатов существуют равносильности c кванторами.

6. РАВНОСИЛЬНОСТИ С КВАНТОРАМИ 1. Если предикат определен на конечном множестве М = <а1,…, ап>, то а) x P(x) ≡ Р(а1)  Р(а2)  …  Р(ап) б) x P(x) ≡ Р(а1)  Р(а2)  …  Р(ап) Т.о., кванторы – другая форма записи конъюнкции и дизъюнкции. (!!) Кванторная форма записи конъюнкции и дизъюнкции пригодна и в случае, когда область определения предиката – бесконечное множество.

6. РАВНОСИЛЬНОСТИ С КВАНТОРАМИ 2. Знак отрицания можно внести под знак квантора, изменив квантор на двойственный, т.е.: а) x P(x) ≡ x P(x); б) х P(x) ≡ x P(x). (!!) Это правило справедливо для многокванторных предикатов.

6. РАВНОСИЛЬНОСТИ С КВАНТОРАМИ 3. Квантор общности обладает распределительным свойством относительно конъюнкции, т.е.: x (P(x)  Q(x)) ≡ x P(x)  x Q(x); 4. Квантор существования обладает распределительным свойством относительно дизъюнкции, т.е.: х (P(x)  Q(x)) ≡ x P(x)  x Q(x).

6. РАВНОСИЛЬНОСТИ С КВАНТОРАМИ 5. Одноимённые кванторы можно менять местами, т.е.: x у P(x; у) ≡ у x P(x; у); x у P(x; у) ≡ у x P(x; у). (!!) Разноименные кванторы менять местами нельзя.

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

Курс повышения квалификации

Методика обучения математике в основной и средней школе в условиях реализации ФГОС ОО

Курс профессиональной переподготовки

Математика: теория и методика преподавания в образовательной организации

Ищем педагогов в команду «Инфоурок»

Номер материала: ДБ-983290

Не нашли то что искали?

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Госдума приняла закон об использовании онлайн-ресурсов в школах

Время чтения: 2 минуты

Международный конгресс-выставка «Молодые профессионалы» пройдет с 12 по 14 декабря в Москве

Время чтения: 1 минута

В России утвердили новый порядок формирования федерального перечня учебников

Время чтения: 1 минута

В МГПУ сформулировали новые принципы повышения квалификации

Время чтения: 4 минуты

Путин поручил не считать выплаты за классное руководство в средней зарплате

Время чтения: 1 минута

Учителям предлагают 1,5 миллиона рублей за переезд в Златоуст

Время чтения: 1 минута

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Источник

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

Предикат- представляет собой функцию субъекта и выражения свойств о субъекте.

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

Например, в рассуждении «Всякий ромб – параллелограмм; ABCD – ромб; следовательно, ABCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учёта их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект(буквально – подлежащее, хотя оно может играть и роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения).

Субъект – это то, о чем что-то утверждается в высказывании, а предикат – это то, что утверждается о субъекте. Логи­ка предикатов – это расширение логики высказываний за счет использова­ния предикатов в роли логических функций.

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

Определение 1. Одноместным предикатом Р(х) на­зывается всякая функция одного переменного, в кото­рой аргумент xпробегает значения из некоторого мно­жества M, а функция при этом принимает одно из двух значений: истина или ложь.

Множество M, на котором задан предикат, называ­ется областью определения предиката.

Множество _{Так, предикат P(x) – «х – простое число» определён на множестве N, а множество Определение 2. Предикат Р(х), определённый на множестве M, называется тождественно истин­ным (тождественно ложным), если Говорят, что предикат Р(х) является следствием предиката Q(х) 1/Temp/msohtmlclip1/01/clip_image004.gif» />, если 1/Temp/msohtmlclip1/01/clip_image005.gif» />; и предика­ты Р(х) и Q(х)равносильны 1/Temp/msohtmlclip1/01/clip_image006.gif» />, если Определение 4. Конъюнкцией двух предикатов Р(х) и Q(х) называется новый предикат Р(х)&Q(х), который принимает значение «истина» при тех и только тех значениях 1/Temp/msohtmlclip1/01/clip_image008.gif» />, при которых каждый из предикатов Р(х) и Q(х) принимает значение «истина» и принимает значение «ложь» во всех остальных случаях. Очевидно, что областью истинности предиката Р(х)&Q(х) является общая часть областей истинности предикатов Р(х) и Q(х), т.е. пересечение Определение 5. Дизъюнкцией двух предикатов Р(х) и Q(х) называется новый предикат 1/Temp/msohtmlclip1/01/clip_image010.gif» />, который принимает значение «ложь» при тех и только тех значе­ниях 1/Temp/msohtmlclip1/01/clip_image008.gif» />, при которых каждый из предикатов при­нимает значение «ложь» и принимает значение «исти­на» во всех остальных случаях. Ясно, что областью истинности предиката 1/Temp/msohtmlclip1/01/clip_image011.gif» /> является объединение областей истинности предикатов Р(х) и Q(х), то есть объединение Определение 6. Отрицанием предиката Р(х) назы­вается новый предикат 1/Temp/msohtmlclip1/01/clip_image013.gif» />, который принимает значе­ние «истина» при всех значениях 1/Temp/msohtmlclip1/01/clip_image014.gif» />, при которых предикат Р(х) принимает значение «ложь», и принима­ет значение «ложь» при тех значениях 1/Temp/msohtmlclip1/01/clip_image008.gif» />, при кото­рых предикат Р(х) принимает значение «истина». Очевидно, что, Определение 7. Импликацией предикатов Р(х) и Q(х) называется новый предикат 1/Temp/msohtmlclip1/01/clip_image016.gif» />, который является ложным при тех и только тех значениях Источник}