Какому отношению и функции соответствует следующий предикат. Предикаты и кванторы. Примеры применения кванторов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

на тему: "Предикаты: определения и примеры"

Введение

Заключение

Введение

В чемсостоит необходимость введения предикатов в математику?

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

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

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

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

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

Цель данного реферата заключается в том, чтобы совершить обзор

литературных источников по проблеме предикатов в дискретной математике.

Для достижения поставленной цели необходимо решить следующие задачи:

·найти нужную информацию о предикатах по данной теме;

·тщательно проанализировать и выбрать нужные данные;

·оформить реферат согласно требованиям.

Объектом исследования является архив материалов по математическим предикатам.

Предметом исследования являются предикаты в дискретной математике.

Реферат состоит из введения, основной части, заключения и списка использованной литературы.

Предикаты: определения и примеры

Введем основное понятие темы.

Определение 1. Пусть М - непустое множество. Тогда n-местным предикатом, заданным на М, называется выражение, содержащее n переменных и обращающееся в высказывание при замене этих переменных элементами множества М .

Поясним конкретными примерами. Пусть М есть множество натуральных чисел N . Тогда, например, такие выражения: "x - простое число", "x - четное число", "x больше 10" являются одноместными предикатами. При подстановке вместо x произвольных натуральных чисел получаются высказывания: "2 - простое число", "6 - простое число", "3 - четное число", "5 больше 10" и т.д.

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

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

Так, предикат P (x ) - "х - простое число" определён на множестве N , а множество для него есть множество всех простых чисел.

Вот такие выражения: " x больше y", " x делит y нацело", " x плюс y равно 10, или x+y=10 " являются двухместными предикатами. Примеры трехместных предикатов, заданных на множестве натуральных чисел: " число z лежит между x и y", " x плюс y равно z", " |x-y| = z " .

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

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

Например, выражение " существует число x такое, что y = 2 x " на множестве натуральных чисел определяет одноместный предикат.,

По смыслу этого выражения, в нем можно заменять только переменную y. Например: если применить замену y на 6, то получим истинное высказывание: " существует число x такое, что 6 = 2x", а если заменим y на 7, то получим ложное (на множестве N) высказывание: " существует число x такое, что 7 =2x".

Предикат с заменяемыми переменными x1,…,xn обычно обозначается заглавной латинской буквой, после которой в скобках указываются эти переменные. Например, P (x1,x2), Q (x2,x3), R (x1). Среди переменных в скобках могут быть и фиктивные .

Определение 2. Предикат (n -местный, или n -арный <#"20" src="doc_zip3.jpg" /> (или " Истина " и " Ложь "), определённая на n -й декартовой степени <#"21" src="doc_zip4.jpg" />,

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно - ложным и пишут:

если на любом наборе аргументов он принимает значение 0.

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

Например, обозначим предикатом EQ (x, y) отношение равенства (" x = y "), где x и y принадлежат множеству вещественных чисел <#"justify">Определение 3. Предикат W (x1,…,xn) называется конъюнкцией предикатов U (x1,…,xn) и V (x1,…,xn), заданных на множестве М , если для любых а1,…, аn из М высказывание W (а1,…, аn) есть конъюнкция высказываний U (а1,…, аn) и V (а1,…, аn) .

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

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

Пусть дано выражение: " существует число х, такое, что x + y=10". На множестве натуральных чисел это предложение определяет одноместный предикат P (y), так, например, Р (2) и Р (9) - истинные высказывания, а Р (11) - ложное. Если обозначить предикат " x + y = 10 " через S (x,y) (а это предикат двухместный), то P (y) можно записать так: " существует х такой, что S (x,y)". В этом случае говорят, что предикат P (y) получен из предиката S (x,y) навешиванием квантора существования на x и пишут P (y) = (?x) S (x,y)

Рассмотрим другой пример. Выражение " для всех х справедливо, что y = - х2 " определяет на множестве целых чисел одноместный предикат Q (y). Если предикат " y = - х2 " обозначить через T (x,y), то Q (y) можно записать так: "для всех x справедливо T (x,y)". В таком случае говорят, что предикат Q (y) получен из предиката T (x,y) навешиванием квантора общности на х и пишут Q (y) = (?x) T (x,y).

Пользуясь этими примерами, дадим определение в общем виде.

Определение 4. Пусть P (x1,…,xn) - предикат, заданный на множестве M , y - переменная. Тогда выражение: " для всякого y выполняется P (x1,…,xn)" - предикат, полученный из P навешиванием квантора общности на переменную y, а выражение " существует y такой, что выполняется P (x1,…,xn)" - предикат, полученный из P навешиванием квантора существования на переменную y .

Заметим, что в определении не требуется, чтобы y была одна из переменных x1,…,xn, хотя в содержательных примерах, квантор навешивается на одну из переменных x1,…,xn. Указанное требование не накладывается, чтобы избежать усложнения определения формулы логики предикатов. Если y - одна из переменных x1,…,xn, то после навешивания квантора на y новый предикат является (n-1) - местным, если y{ x1,…,xn}, то местность нового предиката равна n .

Если предикат W (x1,…,xn) получен из предикатов U (x1,…,xn) и V (x1,…,xn) с помощью связок, то истинность высказывания W (a1,…,an) определяется таблицами истинности этих связок . Пусть W (x1,…,xn) = (?y) U (x1,…,xn,y). Тогда высказывание W (a1,…,an) истинно тогда и только тогда, когда для любого b M истинно высказывание U (a1,…,an,b). Если же W (x1,…,xn) = (?y) U (x1,…,xn,y), то высказывание W (a1,…,an) истинно в том и только в том случае, когда найдется b M, для которого высказывание U (a1,…,an) истинно .

Вообще понятие предиката - весьма широкое понятие . Это видно уже из приведенных выше римеров. Тем не менее, еще раз подчеркнем, показав, что n - местная функция может рассматриваться как (n+1) - местный предикат. Действительно, функции y = f (x1,…,xn), заданной на множестве М, можно поставить в соответствие выражение " y равно f (x1,…,xn)". Это выражение есть некоторый предикат P (x1,…,xn,y). При этом, если элемент b есть значение функции в точке (a1,…,an), то высказывание P (a1,…,an,b) истинно, и обратно. (Подобное "превращение" функции в предикат мы уже привели в качестве примера выше для сложения натуральных чисел.)

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

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

Пусть предикат P (x1,…,xn) задан на множестве M. Рассмотрим прямую степень этого множества Mn = Mx Mx…xM и подмножество Dp множества Mn, определяемое равенством:

Dp = { (a1,…,an) Mn высказывание P (a1,…,an) истинно}.

Отношение Dp можно назвать областью истинности предиката P. Во многих случаях предикат P можно отождествить с отношением Dp.

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

Во-вторых, предикат P (x1,…,xn), заданный на M, можно отождествить с функцией fp: Mn {0,1}, определяемой равенством:

Говорят, что предикат Р (х ) является следствием предиката Q (х ) : , если; и предикаты Р (х ) и Q (х ) равносильны:

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

Пример 1. Среди следующих предложений выделить предикаты и для каждого из них указать область истинности, если M = R для одноместных предикатов и M = R×R для двухместных предикатов :

. х + 5 = 1

При х = 2 выполняется равенство х 2 - 1 = 0

. х 2 - 2х + 1 = 0

Существует такое число х , что х 3 - 2

. х + 2 < Зх - 4

Однозначное неотрицательное число х кратно 3

. (х + 2) - (3х - 4)

. х 2 + у 2 > 0

Решение .

1) Р (х ), I P = { - 4};

2)Предложение не является предикатом. Это ложное высказывание;

3)Предложение является одноместным предикатом Р (х ), I P ={1};

4)Предложение не является предикатом. Это истинное высказывание;

5) Предложение является одноместным предикатом Р (х ), I P = (3; +?);

) Предложение является одноместным предикатом Р (х ), I P = {0; 3; 6; 9};

) Предложение не является предикатом;

) Предложение является двухместным предикатом Q (х,y ), I Q = R×R \ { (0,0) }.

Пример 2. Изобразить на декартовой плоскости область истинности предиката .

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

Рисунок 1. График параболы х = у 2

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

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

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

предикат декартова плоскость математика

Заключение

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

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

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

Список используемых источников

1.Эвнин А.Ю. Дискретная математика. Конспект лекций. 1998.

2.Ерусалимский А.Я. Дискретная математика. Теория. Задачи. Приложения. 2000.

3.Электронный источник. URL: http://forum. vopr.net

Электронный источник. http://lib. mexmat.ru/books/109887

Электронный источник. http://lib. mexmat.ru/books/81214

Репетиторство

Нужна помощь по изучению какой-либы темы?

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

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

1. Всякий друг лица А есть друг лица В. С не есть друг В, следовательно, С не есть друг А.
2. Простое число два – четное. Следовательно, существуют простые четные числа.

Корректность этих умозаключений основана на внутренней структуре самих предложений и на смысле слов «всякий» и «существует».

Рассмотрим предложения, зависящие от параметров, например: «х – четное число», «х меньше y », «x +y =z », «u и v – братья». Если в первых трех предложениях заменить x ,y и z некоторыми числами, а в последнем подставить имена членов некоторой семьи, то полученные высказывания могут быть истинными или ложными. Например, для х =5, y =2, z =7, u – Петр, v – Иван получим: «5 – четное число», «5 меньше 2», «5+2=7», «Петр и Иван – братья».

Предложения такого типа называются предикатами. Точнее, предикатом P(x 1 ,…,x n) называется функция, переменные которой принимают значения из некоторого множества М, а сама она принимает два значения: истинное (И) и ложное (Л), т.е. P(x 1 ,…,x n):М {И,Л}.

Предикат от n аргументов называют n-местным предикатом и обозначают полностью P (n) (x 1 ,…,x n) , если нужно подчеркнуть число аргументов. Высказывания считают нуль-местными предикатами.

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

Например:

1. Пусть P (1) (x) означает предикат «х делится на 2», а Q (1) (х) – предикат «х делится на 3». Тогда выражение P (1) (x) &Q (1) (х) означает предикат «х делится на 2 и х делится на 3», т.е. определяет предикат делимости на 6.

2. Пусть S (2) (х,у) означает предикат «х=у ». Он принимает значение И тогда и только тогда, когда х=у . В этом случае выражение ┐S (2) (х,х) ÞS (2) (х,у) определяет предикат, принимающий значение И при любых х и у.

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

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

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

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

1. $ х (P (1) (x) &Q (1) (х)) – истинное высказывание;
2. " х (P (1) (x) &Q (1) (х)) – ложное высказывание;
3. " х,у (┐S (2) (х,х) ÞS (2) (х,у)) – истинное высказывание.

Введем теперь строгие определения для исчисления предикатов.

(Чистое) исчисление предикатов (первого порядка) - это формальная теория К, в которой оп­ределены следующие компоненты.

1. Алфавит:

связки основные ┐,

дополнительные &,

служебные символы (,) Î (, ’ , ’ ,)

кванторы всеобщности

существования

предметные константы

переменные

предметные предикаты P, Q, . . .

функторы f, q,. . .

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

2. Формулы имеют следующий синтаксис:

Формула = (атом

| ┐ (формула | ( формула

(фор­мула ) | (переменная формула

| перемен­ная формула

Атом = предикат ( список термов )

Список термов = терм | терм ,

Список термов терм = константа |

Переменная | функтор ( спи­сок термов )

При этом должны быть выполнены следующие контекстные условия: в терме f (t 1 ,. . .,t n) функтор f должен быть n - местным. В атоме (или атомарной формуле) P(t 1 ,. . .,t n) предикат Р должен быть n - местным.

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

Например, рассмотрим формулу x (Р(х) y Q(x,y)) и ее подформулы. В подформулу y Q(x,y) пере­менная х входит свободно, а оба вхождения переменной у связаны (квантором существования). Таким образом, эта подформула не замкнута. С другой стороны, то же самое вхождение пере­менной х в подформулу Q(x,y) является связанным вхождением в формуле x (Р(х) y Q(x,y)) . В этой формуле все вхождения всех переменных связаны, а потому формула замкнута.

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

Формулы вида А и ┐А, где А - атом, называются литеральными формулами (или литералами). В формулах x А и x А подформула А называется областью действия квантора по х.

Обычно связки и кванторы упорядочивают по приоритету следующим образом: ┐, ,$, &, , . Лишние скобки при этом опускают. Терм t называется свободным для переменной х в формуле А, если никакое свободное вхождение переменной х в формулу А не лежит в области действия никакого квантора по переменной у, входящей в терм t. В частности, терм t свободен для любой переменной в формуле А , если ника­кая переменная терма не является связанной переменной формулы А.

Например:

а) терм у свободен для переменной х в формуле Р(x) , но тот же терм у не свободен для пере­менной х в формуле y P{x).

б) терм f(x, z) свободен для переменной х в формуле y P(x,y) Q(x), но тот же терм f(x, z) не свободен для переменной х в формуле

z y P(x,y) Q(x).

Переход от предиката Р(х) к " х Р(х) или $ х Р(х) называется связыванием переменной х , или навешиванием квантора на переменную х , или квантификацией переменной х.

Выражение " х Р(х) и $ х Р(х) не зависят от х и при фиксированных Р и предметного множества М имеет вполне определенные значения, представляя вполне конкретные высказывания относительно всех х в предметной области М.

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

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

Рассмотрим решение некоторых примеров.

Пример 4.4. Пусть N (х) – предикат «х – натуральное число». Рассмотреть варианты навешивания кванторов, интерпретировать и определить их истинность.

Решение. " х N(х) –«все числа натуральные». Это высказывание истинно на любом множестве натуральных чисел и ложно, если М содержит хоть одно ненатуральное число (например, целое отрицательное).

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

Решение . Используя взаимно однозначное соответствие между отношениями предикатами, можно проиллюстрировать решение схемами (рис. 4.1.).

Рис. 4.1. Иллюстрация влияния кванторов

Интерпретация:

" х $ y Р(х,у) – «для любого х существует у , которого он любит».

$ у " х Р(х,у) – «существует такой у , которого любят все х ».

" х "уР(х,у ) - «все х любят всех у ».

$ х $ у Р(х,у) – « найдется х , который любит кого-то из у » или «найдется человек, который кого-то любит».

$ х " у Р(х,у) – «существует х , который любит всех у ».

" у $ х Р(х,у) – «для любого из у найдется х , который его любит».

Аксиомы (логические): любая система аксиом исчисления высказываний, плюс

P 1: x A(x) A(t),

P 2: A(t) x A(x),

где терм t свободен для переменной х в формуле А.

Правила вывода:

где формула А содержит свободные вхождения переменной х, а формула В их не содержит.

Исчисление предикатов, которое не содержит предметных констант, функторов, предикатов и собственных аксиом, называется чистым. Исчисление предикатов, которое содержит предметные константы и/или функторы и/или предикаты и связывающие их собственные аксиомы, называется прикладным.

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

Соответствие между предикатами, отношениями и функциями

n – местный предикат можно рассматривать как функцию Р (х 1 ,…х n) от n переменных х i Î М i , где М i - предметные области, а РÎВ={0,1}={И,Л}. Таким образом, предикат Р (х 1 ,…х n) является функцией типа Р: М 1 ´М 2 ´… ´М n ®В , или, если предметная область едина для всех переменных, то имеем Р: М n ®В .

Из рассмотренного очевидно, что для любых М и n существует однозначное соответствие между n-местными отношениями R ÍМ n и предикатами Р (х 1 ,…х n) , М n ®В :

Каждому n – местному отношению R соответствует предикат Р (х 1 ,…х n) такой, что Р (а 1 ,…а n)=1, если и только если (а 1 ,…а n)ÎR;

Всякий предикат Р (х 1 ,…х n) определяет отношение R такое, что (а 1 ,…а n)ÎR , если и только если Р (а 1 ,…а n)=1.

При этом R задает область истинности предиката P.

Рассмотрим теперь функцию f (х 1 ,…, х n), f : М n ®M . Тогда можно видеть, что всякой функции f: М n ®M соответствует предикат Р (х 1 ,…х n +1), Р: М n +1 ®В , такой что Р(а 1 ,…а n +1)=1 , если и только если f (а 1 ,…а n)=а n +1 .

Понятие предиката шире понятия функции (см. рис. 4.1.), поэтому обратное соответствие (от (n+1 )-местного предиката к n–местной функции) возможно не всегда, а только для таких предикатов, для которых выполняется условие, связанное с однозначностью функции:

Р(а 1 ,…а n +1)=0 ® ("а¢ n +1 ÎМ|а¢ n +1 ¹а n +1 Р(а 1 ,…а¢ n +1)=0. (4.3.)

Аналогичное соответствие имеется между подмножеством отношений {R¢}Ì{R} и множеством функций {f} . Для этого класса отношений выполняется условие

(а 1 ,…а n +1)ÎR¢ ® ("а¢ n +1 ÎМ|а¢ n +1 ¹а n +1 (а 1 ,…а¢ n +1)ÎR¢). (4.4.)

Пример 4.6. Каким отношениям и функциям соответствуют предикаты, определенные на множестве натуральных чисел?

1. Предикат суммы S: N 3 ®В:

S(х 1 ,х 2 ,х 3)=1 тогда и только тогда, когда х 1 +х 2 =х 3 .

2. Предикат порядка Q:N 2 ®В:

Q (х 1 ,х 2)=1 тогда и только тогда, когда х 1 £х 2 .

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

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

Например, в рассуждении “Всякий ромб – параллелограм; АВС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))

п-местный предикат - это функция Р(х 1 х 2 , х п) от п переменных, принимающих значения из некоторых заданных предметных областей, так что,a функция P принимает два логических значения – «истинно» или «ложно».

Таким образом, предикат Р(х 1, х 2, ..., х п) является функцией типа , где множества, называются предметными областями предиката; х 1, х 2, ..., х п -предметными переменными предиката; В = {1,0}.

Соответствия между предикатами, отношениями и функциями:

1. Для любых М и п существует взаимно однозначное соответствие между n -местными отношениями u n-местными предикатами Р(х 1, х 2, ..., х п), :

Каждому n -местному отношению R соответствует предикат Р(х 1, х 2, ..., х п), такой, что Р(a 1, a 2, ...,a п) = 1, если и только если (a 1, a 2, ..., a п) Î R;

Всякий предикат Р(х 1, х 2, ..., х п) определяет отношение R такое, что (a 1, a 2, ..., a п) Î R, если и только если Р(a 1, a 2, ...,a п) = 1.

При этом R задает область истинности предиката Р.

2. Всякой функции f (х 1, х 2, ..., х п) , соответствует предикат Р(х 1, х 2, ..., х п, х п+1)=1такой, что Р(a 1, a 2, ..., a п, a п+1)=1, если и только если f (a 1, a 2, ..., a п)=a n +1 .

Обратное соответствие (от (n+1 )-местного предиката (рис. 2.17) к n -местной функции) возможно не всегда, а только для таких предикатов Р ’ для которых выполняется условие (связанное с требованием однозначности функции): Р(a 1, a 2, ...,a п, a п+1) = 1, то для любого

a ’ п +1 ≠a п +1 Р(a 1, a 2, ...,a п, a ’ п +1) = 0 {1}

Аналогичное соответствие (взаимно однозначное) имеется между подмножеством отношений {R"}{R} и множеством функций {f }.

Для этого класса отношений выполняется аналогичное условие: если (a 1, a 2, ..., a п, a п+1) Î R ’ то для любого a ’ п+1 ≠a п+1 , (a 1, a 2, ..., a п, a п+1)R ’

Выражение Р(a 1, a 2, ...,a п) будем понимать как высказывание «Р(a 1, a 2, ...,a п)=1», а выражение Р(х 1, х 2, ..., х п) - как переменное высказывание, истинность которого определяется подстановкой элементов множества М вместо переменных (х 1, х 2, ..., х п).

Для обозначения двухместных предикатов помимо префиксной записи Р(х 1, х 2) используется нередко инфиксная запись х 1 Рх 2

Каким отношениям и функциям соответствуют следующие предикаты, определенные на множестве натуральных чисел:

1. Предикат тождества E:N 2 →В: Е(а ], а 2) = 1 тогда и только тогда, когда а ]= а 2

Двухместному предикату тождества Е – «x ]= x 2 » взаимно однозначно соответствуют:

а) двухместное отношение R 1 , - «быть равным», , тогда и только тогда, когда Е (a 1 , а 2) = 1;

б) одноместная функция (операция) тождества f 1 (x 1 )=х 2 , а именно:.

2. Предикат делимости D: N 2 →В: D (а ], а 2) = 1 тогда и только тогда, когда а ] делится на а 2:

Двухместному предикату делимости D – «х 1 делится на х 2 » взаимно однозначно соответствует двухместное отношение R 2 – «делиться», тогда и только тогда, когда D (a 1 , а 2) = 1. Однако функции f 1 (x 1 )=х2 для предиката делимости D (x 1 , x 2) не существует, так как не выполнено условие (1), например D(6, 2) = 1 и D(6, 3) = 1, однако 2≠3.

3. Предикат суммы S:N 3 →В: S(а 1, а 2, а 3) = 1 тогда и только тогда, когда а 1 +a 2 = a 3 .

Трехместному предикату суммы S – «x 1 +x 2 =x 3 » взаимно однозначно соответствуют:

а) трехместное отношение: тогда и только тогда, когда S(а 1, а 2, а 3) = 1;

б) двухместная функция (операция арифметики) - сложение f(х 1 , х 2) = х 3 , а именно: х 1 + х 2 = х 3 .