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

/

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

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

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

РЕФЕРАТ

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

2014

Оглавление

• Введение
• Предикаты: определения и примеры
• Заключение
• Список используемых источников

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предикат с заменяемыми переменными x₁,…,x_n обычно обозначается заглавной латинской буквой, после которой в скобках указываются эти переменные. Например, P (x₁,x₂₎, Q (x₂,x₃₎, R (x₁₎. Среди переменных в скобках могут быть и фиктивные [2].

Определение 2. Предикат (n-местный, или n-арный) - это функция с областью значений (или ' Истина ' и ' Ложь '), определённая на n-й декартовой степени множества M. Таким образом, каждую n-ку элементов M предикат характеризует либо как 'истинную', либо как 'ложную' [5].

Предикат можно связать с математическим отношением: если n-ка принадлежит отношению, то предикат будет возвращать на ней 1 [3].

Предикат - один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам [3].

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

P ,

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

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

P ,

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

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

Например, обозначим предикатом EQ (x, y) отношение равенства (' x = y '), где x и y принадлежат множеству вещественных чисел. В этом случае предикат EQ будет принимать истинное значение для всех чисел, равных x и y.

Более житейским примером может служить предикат ' ПРОЖИВАЕТ (x, y, z)' для отношения ' x проживает в городе y на улице z ' или предикат ' ЛЮБИТ (x, y)' для выражения ' x любит y', где множество M - это множество всех людей.

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

Определение 3. Предикат W (x₁,…,x_n) называется конъюнкцией предикатов U (x₁,…,x_n) и V (x₁,…,x_n), заданных на множестве М, если для любых а₁,…, а_n из М высказывание W (а₁,…, а_n) есть конъюнкция высказываний U (а₁,…, а_n) и V (а₁,…, а_n) [2].

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

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

Пусть дано выражение: ' существует число х, такое, что 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 (x₁,…,x_n) - предикат, заданный на множестве M, y - переменная. Тогда выражение: ' для всякого y выполняется P (x₁,…,x_n)' - предикат, полученный из P навешиванием квантора общности на переменную y, а выражение ' существует y такой, что выполняется P (x₁,…,x_n)' - предикат, полученный из P навешиванием квантора существования на переменную y [1].

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

Если предикат W (x₁,…,x_n) получен из предикатов U (x₁,…,x_n) и V (x₁,…,x_n) с помощью связок, то истинность высказывания W (a₁,…,a_n) определяется таблицами истинности этих связок [3]. Пусть W (x₁,…,x_n) = (?y) U (x₁,…,x_n,y). Тогда высказывание W (a₁,…,a_n) истинно тогда и только тогда, когда для любого b M истинно высказывание U (a₁,…,a_n,b). Если же W (x₁,…,x_n) = (?y) U (x₁,…,x_n,y), то высказывание W (a₁,…,a_n) истинно в том и только в том случае, когда найдется b M, для которого высказывание U (a₁,…,a_n) истинно [4].

Вообще понятие предиката - весьма широкое понятие [1]. Это видно уже из приведенных выше римеров. Тем не менее, еще раз подчеркнем, показав, что n - местная функция может рассматриваться как (n+1) - местный предикат. Действительно, функции y = f (x₁,…,x_n), заданной на множестве М, можно поставить в соответствие выражение ' y равно f (x₁,…,x_n)'. Это выражение есть некоторый предикат P (x₁,…,x_n,y). При этом, если элемент b есть значение функции в точке (a₁,…,a_n), то высказывание P (a₁,…,a_n,b) истинно, и обратно. (Подобное 'превращение' функции в предикат мы уже привели в качестве примера выше для сложения натуральных чисел.)

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

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

Пусть предикат P (x₁,…,x_n) задан на множестве M. Рассмотрим прямую степень этого множества Mⁿ = Mx Mx…xM и подмножество D_p множества Mⁿ, определяемое равенством:

D_p = { (a₁,…,a_n) Mⁿ высказывание P (a₁,…,a_n) истинно}.

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

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

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

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

,

Если

.

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

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

1. х + 5 = 1

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

3. х² - 2х + 1 = 0

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

5. х + 2 < Зх - 4

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

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

8. х² + у² > 0

10

Решение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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