Предикаты. Основные понятия 16 описание двухместных предикатов характеризующих структуру системы

Рассмотрим предложение

Это предложение не является высказыванием, так как о нем нельзя сказать, истинно оно или ложно. Оно называется предикатом или условием (на х и у). Приведем другие примеры предложений с переменными:

Есть простое число;

Есть четное число;

Меньше у,

Есть общий делитель у, z.

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

2 есть простое число;

3 есть четное число;

5 меньше 7;

3 есть общий делитель 6 и 12.

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

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

По числу входящих свободных переменных различают предикаты одноместные, двухместные, трехместные и т. д. Предикаты (2) и (3) - одноместные, предикаты (1) и (4) - двухместные, предикат (5) - трехместный. Высказывания будем считать нульместными предикатами.

Заменяя в одноместном предикате (2) переменную натуральными числами, будем получать высказывания:

0 есть простое число;

1 есть простое число;

2 есть простое число;

3 есть простое число и т. д.

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

Одноместный предикат можно рассматривать как условие на объекты данного вида; двухместный - как условие на пары объектов данного вида и т. д.

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

Обозначать предикаты будем большими буквами латинского алфавита (возможно, с нижними индексами) с указанием в скобках всех свободных переменных, входящих в этот предикат. Например, - обозначение двухместного предиката, - трехместного и - обозначение -местного предиката.

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

Высказывание, которое получается при подстановке в предикат набора допустимых значений вместо его переменных, будем обозначать Если это высказывание истинное (ложное), говорят, что набор значений удовлетворяет (не удовлетворяет) предикату

В алгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности.

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

Например, в рассуждении “Всякий ромб – параллелограм; АВСD – ромб; следовательно, АВСD - параллелограм ” посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

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

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

Субъект – это то, о чем что-то утверждается в высказывании;

предикат – это то, что утверждается о субъекте.

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

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

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1;0}. Здесь предикат становится функцией субъекта и выражает свойство субъекта.

Областью значений предиката является двухэлементное множество B={true, false}. При этом сами переменные x 1 ,...,x n называются предметными переменными, т.е. их значения не являются логическими (не принадлежат множеству B).

Понятие ``предикат"" обобщает понятие ``высказывание"". Неформально говоря, предикат – это высказывание, в которое можно подставлять аргументы. Если аргумент один – то предикат выражает свойство аргумента, если больше – то отношение между аргументами.

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

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

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

В классическом исчислении предикатов употребляются следующие знаки: 1) т. н. предметные переменные - буквы х, у, z ,..., которые содержательно рассматриваются как неопределённые имена объектов исследования теории; 2) предикатные переменные - знаковые комплексы вида P m , Q n , R l ,... (m, n, l - натуральные числа), причём, например, Q n означает произвольное n-местное отношение между объектами; 3) знаки для логических связок: конъюнкции &, дизъюнкции , импликации É, отрицания ù, означающие соответственно «... и...», «... или...», «если..., то...», «неверно, что...»; 4) знаки для кванторов " (квантор всеобщности), $ (квантор существования), означающие соответственно «для всех...» и «существует... такое, что...»; 5) запятая, скобки (для уточнения строения формул).

Определение 2Квантор (от лат. quantum - сколько), логическая операция, дающая количественную характеристику области предметов, к которой относится выражение, получаемое в результате её применения.

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

С помощью кванторов можно записать четыре основных формы суждений традиционной логики: «все А суть В » записывается в виде " x [A (x )É ÉB (x )], «ни одно A не есть B » - в виде " x [A (x )É B (x )], «некоторые А суть B » - в виде $ x [A (x )&B (x )], «некоторые А не суть В » - в виде $ x [A (x )& B (x )] (здесь А (х ) означает, что х обладает свойством A) .

Часть формулы, на которую распространяется действие каких-либо Квантора, называется областью действия этого Квантора (её можно указать с помощью скобок). Применение Квантора уменьшает число свободных переменных в логическом выражении и превращает (если Квантор не «фиктивный», т. е. относится к переменной, действительно входящей в формулу) трёхместный предикат в двухместный, двухместный - в одноместный, одноместный - в высказывание.

Определение 3. Одноместным предикатом Р(x) называется произвольная функция переменной x, определенная на множестве M и принимающая значение из множества {1; 0}.

Определение 4. Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество или иначе: или так: Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности I P для него есть множество всех простых чисел.

Предикат Q(x) – “sin(x)=0” определен на множестве R, а его множеством истинности является

Предикат F(x) – “диагонали параллелограма x взаимно перпендикулярны” определен на множестве всех параллелограмов, а его множеством истинности является множество всех ромбов.

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

Определение 5. Предикат Р(х), определенный на множестве М, называется тождественно истинным , если его множество истинности совпадает с областью определения, т. е. I p =M.

Определение 6. Предикат Р(х), определенный на множестве М, называется тождественно ложным , если его множество истинности является пустым множеством, т. е. I p =0.

Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношениямежду предметами.

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

Определение 7. Двухместным предикатом Р(x,y) называется функция двух переменных x и y, определенная на множестве М=М 1 хМ 2 и принимающая значения из множества {1;0}.

В числе примеров двухместных предикатов можно назвать такие предикаты: Q(x, y) – “x=y” - предикат равенства, определенный на множестве RхR=R 2 ; F(x,y) – “х параллелен y”, “прямая х параллельна прямой y”, определенный на множестве прямых, лежащих на данной плоскости.

Совершенно аналогично вводится понятие трехместного предиката. Приведем пример трехместного предиката (функции трех переменных): S(x,y,z) – “x+y=z”. Подстановка в него х=3 превращает его в двухместный предикат: S(y,z) – “3+y=z”, а подстановка х=3, z=2 – в одноместный предикат S(y) – “3+y=2”.Подстановка же S(2,3,5) превращает его в истинное высказывание, а S(1,7,4)– в ложное.

Аналогично определяется и n-местный предикат (функция n переменных). Пример п- местного предиката:

R(x 1 , x 2 ,…,x n): a 1 x 1 +…+a n x n =0,

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

При n=0 будем иметь нульместный предикат – это логическая (пропозициональная) переменная, принимающая значения из множества {1;0}.

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

Основой для «функциональной» точки зрения на предикат служат в естественных и в искусственных (точных) языках выражения вида повествовательных предложений, содержащие неопределённые термины - неопределённые имена предметов: переменные (параметры) в записи утверждений в математическом языке, например х + 2 = 4; слова «нечто», «некто», «кто-либо» и пр., играющие в естественном языке роль переменных в выражениях типа: «Некто человек», «Кто-то любит кого-то», «Если кто-либо человек, то он смертен» и т.п. Записав эти выражения некоторым единым способом, например заменяя неопределённые термины пробелами, аналогично тому, как это делается в опросных бланках, «-+ 2 = 4», «-человек», «- любит -», «Если - человек, то - смертен», или же принимая запись с помощью переменных в качестве основной, «x + 2 = 4», «x человек», «х любит у », «Если х человек, то х смертен», легко заметить нечто общее между ними. Во-первых, наличие неопределённых терминов делает эти и подобные им выражения, вообще говоря, неопределёнными как в смысле того, что в них утверждается, так и в смысле их истинностного значения; во-вторых, всякое подходящее указание на область значений неопределённых терминов и одновременная квантификация или замена неопределённых терминов их значениями преобразует соответствующие выражения в осмысленные высказывания. В современной логике выражения, имеющие вид повествовательных предложений и содержащие неопределённые термины, получили общее название пропозициональных функций, или, сохраняя традиционный термин, предикатов. Как и числовые функции, предикаты. являются соответствиями. Неопределённые термины играют в них обычную роль аргументов функции, но, в отличие от числовых функций, значениями предикатов. служат высказывания. В общем случае, отвлекаясь от какого-либо определённого языка и сохраняя только функциональную форму записи, предикат от n переменных (от n неопределенных терминов) выражают формулой P (x 1 ,..., x n ), где n ³ 0. При n = 0 предикат совпадает с высказыванием, при n = 1 предикат будет свойством в узком смысле (1-местным предикатом), при n = 2 - свойством «пары» (2-местным предикатом, или бинарным отношением), при n = 3 - свойством «тройки» (3-местным предикатом, или тернарным отношением) и т.д.

Примеры предикатов:

1. Возьмём высказывания: `` Сократ - человек "", `` Платон - человек "". Оба эти высказывания выражают свойство ``быть человеком"". Таким образом, мы можем рассматривать предикат `` быть человеком "" и говорить, что он выполняется для С0ократа и Платона.

2. Возьмём высказывание: `` расстояние от Иркутска до Москвы 5 тысяч километров "". Вместо него мы можем записать предикат `` расстояние "" (означающий, что первый и второй аргумент этого предиката находятся на расстоянии, равном третьему аргументу) для аргументов `` Иркутск "", `` Москва "" и `` 5 тысяч километров "".

3. Высказывание "у каждого человека есть отец" можно записать:

"x $ y (человек(x) Éотец(y,x))

3. Выражение "Джон владеет красной машиной" записывается, например, так:

$ x (владеет(Джон, x) Éмашина(x) &красный(x))

4. Выражение «все простые числа больше чем x» можно записать

" y (P (y ) É Q (x, y )). , где

· P (x ) выражает условие ``x является простым числом"",

· Q (x, y ) выражает условие ``x меньше чем y"".

5. Выражение "у всех людей общий отец".

$ y "x (человек(x) É отец(y,x))

Если попытаться с помощью логики высказываний доказать корректное умозаключение «Каждый человек любит самого себя (Л). Я- человек (В). Следовательно, я люблю самого себя (С)», то общезначимого вывода (А & В) н С не получится. С посылками (А & В) совместимо не только заключение С, но и его отрицание. Значит, высказывание С не является необходимым следствием (А & В). Причина этого не в ущербности логики высказываний, а в ее ограниченности. Согласно одному из ее допущений внутренняя структура простых высказываний не учитывается. Поэтому неудивительно, что расширение возможностей формализации было связано прежде всего с отказом от указанного допущения. Это привело к созданию важного обобщения ЛВ, названного логикой предикатов.

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

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

• универсум;
• имя собственное;
• предметная константа;
• предметная переменная;
• предикат, терм;
• предметная функция;
• квантор.

Кроме того, использование Л П требует принятия особых допущений.

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

Универсум U логики предикатов - класс объектов с заданными свойствами и отношениями.

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

Чтобы обсуждать вещи универсума, необходимо для каждой из них заручиться именем собственным (обозначает эту и только эту вещь).

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

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

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

В логике предикатов не важно, каким именем обозначается та или иная вещь, существенно, какая вещь обозначается. Поэтому если два и более различных имени обозначают одну и ту же вещь, то независимо от различия своих интенсионалов (смыслов) они считаются экстенсионально взаимозаменяемыми. Например, «автор “Евгения Онегина”» и «А. С. Пушкин» - экстенсионально взаимозаменяемые имена, так как обозначают одного и того же человека. В противном случае значение истинности высказывания будет зависеть от малейшего изменения смысла контекста, в котором оно употребляется.

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

Как и в логике высказываний, в логике предикатов сохраняется допущение бивалентности.

Допущение бивалентности - каждое простое высказывание ЛП

либо истинно, либо ложно.

Из-за необходимости учитывать внутреннюю структуру высказываний атомарные формулы Л П значительно отличаются по своей структуре от атомарных формул ЛВ. Напомним, что в ЛВ таковыми считаются знаки (прописные буквы латинского алфавита), обозначающие простое высказывание.

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

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

Различие между предметными константами и переменными поясняет следующий пример. Допустим, необходимо формализовать утверждение, что некоторая вещь из универсума U обладает свойством Р. Это возможно осуществить двумя способами: либо как Ра, если а - известное имя собственное вещи, либо как Рх, если имя собственное вещи неизвестно. Выражение Ра читается: «Данная вещь а из универсума U обладает свойством Р». Выражение Рх читается так: «Произвольная вещь*из универсума U обладает свойством Р». Фундаментальное различие между обоими случаями состоит в том, что выражения типа Ра, РЬ... можно оценивать как истинные или ложные, а выражения Рх, Ру... так оценивать нельзя.

Пусть U= «пищевые продукты», Р= «сладкий», а =* «сахар», b = «соль». Тогда выражение Ра = «Сахар сладкий» истинно, а выражение РЬ =* «Соль сладкая» ложно. Сказать же, что Рх - «Произвольный пищевой продукт сладкий» истинно или ложно, бессмысленно, потому что неизвестно, о каком же именно пищевом продукте идет речь. Знак * обозначает любую съедобную вещь или, как говорят, «пробегает» по всем вещам рассматриваемого универсума. Значит, чтобы выражение ЛП, содержащее вхождения предметных переменных, можно было интерпретировать как истинное или ложное высказывание, их необходимо заменить соответствующими им предметными константами.

Допустим, необходимо формализовать утверждение, что некоторая вещь находится в определенном отношении к другой вещи. Здесь также различаются указанные выше два случая. Выражение вида Rxy означает «Произвольные вещи лги у из универсума х принято называть одноместными (одноаргументными) предикатами. Их отличительная особенность состоит в том, что они обозначают свойства вещей. Выражения вида Р 2 ху называют двухместными (двухаргументными ) предикатами. Их особенность заключается в том, что они обозначают бинарные отношения. В общем, выражения вида Р п принято называть п-местными предикатами , обозначающими л-местные отношения, п > 0. В случае Р° предикатная буква - знак простого высказывания Л В, которое по допущению бивалентности либо истинно, либо ложно. Так как атомарные формулы ЛВ сводимы к виду Р°, то они все представляют собой атомарные формулы ЛП.

Верхними индексами для обозначения местности предиката можно и не пользоваться, так как число мест предиката легко определяется по числу предметных переменных, которыми он управляет. Например, Р 8 означает, что после предикатной буквы Р должно стоять три предметных переменных - Pxyz. В дальнейшем используется именно данный вариант символизации.

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

Двухместная функция сложения /(а, Ь), определенная на множестве натуральных чисел, устанавливает соответствие между парой определенных натуральных чисел а и Ь и новым числом с из этого же множества как результатом их суммы: а + Ь - с. Например,/(1,2) = 3,/(/(1,2), /(1, 2)) = 3 + 3 = 6. Другие примеры и-иредметных функций: g(b) = = мать b, g(g(b)) = мать матери b = бабушка b, g(g(g(b))) = мать бабушки b = прабабушка Ь. Функция f n при п = 0 обозначает предметную константу.

Предметные константы и предметные переменные принято объединять общим именем - простой терм (от англ. term). Понятие терма обобщает понятие субъекта в традиционной логике. К числу сложных термов относятся «-местные функциональные знаки, п > 0, сопровождаемые «-предметными константами или переменными в качестве простых термов.

Объединение термов с предикатной буквой порождает атомарную формулу ЛП. Основное правило в этом процессе следующее: п-мест- ной предикатной букве должно соответствовать п термов. Таким образом, выражение Л 3 не будет атомарной формулой ЛП, так как предикатный символ не сопровождается тремя термами, а выражение вида РаДгтаковой признать можно. Если?,... t n - произвольные термы, Р" - произвольный «-местный предикат, то атомарная формула ЛП имеет следующий канонический вид: Р а - 1п п>0. Только атомарным формулам ЛП и построенным из них сложным формулам можно приписывать то или иное значение истинности.

Некоторые формулы ЛП с вхождениями предметных переменных могут быть квантифицированы. Кванторы в Л П играют такую же роль, как и знаки количества - «все», «ни один», «некоторые» - в традиционной логике. Они определяют количественные границы свойств и отношений, обозначаемых предикатами.

Пусть универсум состоит из трех вещей, каждая из которых имеет свое собственное имя, U = {а , Ь, с). Если необходимо сказать, что все элементы данного универсума обладают свойством Р, это можно сделать двумя способами. Во-первых, построив конъюнкцию - (Ра & РЬ & Рс), которая истинна, если и только если истинны все ее конъюнкты. Во-вторых, использовав специальное сокращение, называемое квантором общности и ставящееся перед той формулой (Рх - в данном случае), количественную характеристику которой оно определяет: (х)Рх. Формула Рх, перед которой поставлен квантор общности (х)Рх, читается так: «Каждый х обладает свойством Р», «Для всех х имеет место свойство Р». Формула -i(х)Рх читается следующим образом: «Неверно, что каждый х обладает свойством Р». Формула (х)-лРх означает: «Ни один х не обладает свойством Р».

Если необходимо сказать, что некоторые вещи рассматриваемого универсума обладают свойством Р, то это можно сделать также двумя способами. Во-первых, построив дизъюнкцию (Ра v Pbv Рс), которая истинна, если и только если истинен по крайней мере один ее дизъюнкт. Во-вторых, использовав специальное сокращение, называемое квантором существования и ставящееся перед тем выражением, количественную характеристику которого оно определяет: (Ех)Рх. Формула Рх, перед которой поставлен квантор существования (Ех)Рх , читается «Существует такой х , который обладает свойством Р», «По крайней мере для одногох имеет место Р». Формула -i(Ех)Рх читается «Неверно, что существует такой.г, который обладает свойством Р». Формула (Ex)-iPx означает «Некоторые х не обладают свойством Р».

При задании частичного порядка, если пара элементов (a ,b ) принадлежит U , то говорят, что a предшествует b . Если никакой из этих двух элементов другому не предшествует, но говорят, что они не сравнимы.

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

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

Итальянский экономист Вильфредо Парето (1848-1923) предложил использовать в таких задачах конструкцию, которая в его честь называется границей Парето (Pareto frontier). Мы ее сейчас опишем.

Подмножество PF множества A называется его границей Парето для частичного порядка U , если любые два элемента PF не сравнимы, а любому другому элементу из A предшествует какой-либо элемент из PF .

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

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

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

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