Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Факультет _______________________________________________
Кафедра _________________________________________________
РЕФЕРАТ
по дисциплине_______________
на тему: «Предикаты»
Автор работы: ________________ _______________
(ФИО) (подпись)
Преподаватель ________________ _____________
(ученая степень, звание, ФИО) (подпись)
Дата сдачи:
«____»______________2014 г. Дата защиты:
«____»_____________2014 г. Оценка: __________________
2014
Оглавление
Введение……………………………….…………………………….……........…….3
Основная часть. Предикаты: определения и примеры............................…....5
Заключение……………………………………..............................................….…12
Список используемых источников………………………………………..…......13
Введение
В чем состоит необходимость введения предикатов в математику?
Дело в том, что сама по себе логика высказываний обладает довольно слабыми выразительными возможностями. Пользуясь только логикой, нельзя выразить даже очень простые, с математической точки зрения, рассуждения.
Возьмем, например, следующее умозаключение. «Всякое целое число является рациональным. Число 5 – целое. Следовательно , 5 – рациональное число ». Все эти три утверждения с точки зрения логики высказываний являются атомарными. Т.е. только средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Средства, предоставляемые логикой высказываний, оказываются недостаточными для анализа многих математических рассуждений. В алгебре логики не рассматриваются ни структура высказываний, ни тем более, их содержание. В то же время и в науке, и в практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.
Например , в рассуждении « Всякий ромб – параллелограмм ; ABCD – ромб ; следовательно , ABCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний , и с точки зрения этой логики рассматриваются как целые, неделимые, без учёта их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.
3
Поэтому возникает необходимость в расширении логики высказываний и построении такой логической системы, средствами которой можно исследовать структуру и содержание тех высказываний, которые в логике высказываний рассматриваются как элементарные.
В силу изложенного материала, можно заключить, что актуальность данной работы несомненна.
Цель данного реферата заключается в том, чтобы совершить обзор
литературных источников по проблеме предикатов в дискретной математике.
Для достижения поставленной цели необходимо решить следующие задачи:
Объектом исследования является архив материалов по математическим предикатам.
Предметом исследования являются предикаты в дискретной математике.
Реферат состоит из введения, основной части, заключения и списка использованной литературы.
4
Основная часть.
Предикаты: определения и примеры
Введем основное понятие темы.
Определение 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].
Причем местность предикатов не всегда равна числу всех переменных, содержащихся в выражении.
5
Например, выражение « существует число 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].
Определение 2. Предикат ( n-местный, или n-арный ) – это функция с областью значений ( или « Истина » и « Ложь » ), определённая на n-й декартовой степени множества M. Таким образом, каждую n-ку элементов M предикат характеризует либо как «истинную», либо как «ложную»[5].
Предикат можно связать с математическим отношением: если n-ка принадлежит отношению, то предикат будет возвращать на ней 1 [3].
Предикат – один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам [3].
Предикат называют тождественно – истинным [2] и пишут:
P ,
если на любом наборе аргументов он принимает значение 1.
Предикат называют тождественно – ложным [2] и пишут:
P ,
если на любом наборе аргументов он принимает значение 0.
6
Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 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 ( x1,…,xn ) называется конъюнкцией предикатов U ( x1,…,xn ) и V ( x1,…,xn ), заданных на множестве М, если для любых а1,…,аn из М высказывание W ( а1,…,аn ) есть конъюнкция высказываний U ( а1,…,аn ) и V ( а1,…,аn ) [2].
Аналогично приводятся определения и других упомянутых выше операций.
В логике предикатов первого порядка вводятся и две новые операции. Называются они квантором общности и квантором существования [1]. Эти операции рассмотрим сначала на примерах.
.
7
Пусть дано выражение: « существует число х, такое, что 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[1].
Заметим, что в определении не требуется, чтобы y была одна из переменных x1,…,xn, хотя в содержательных примерах, квантор навешивается на одну из переменных x1,…,xn. Указанное требование не накладывается, чтобы избежать усложнения определения формулы логики предикатов. Если y – одна из переменных x1,…,xn, то после навешивания квантора на y новый предикат является ( n-1 ) - местным, если y{ x1,…,xn}, то местность нового предиката равна n[3].
8
Если предикат W ( x1,…,xn ) получен из предикатов U ( x1,…,xn ) и V ( x1,…,xn ) с помощью связок, то истинность высказывания W ( a1,…,an ) определяется таблицами истинности этих связок[3]. Пусть 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 ) истинно[4].
Вообще понятие предиката – весьма широкое понятие[1]. Это видно уже из приведенных выше римеров. Тем не менее, еще раз подчеркнем, показав, что 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.
9
При этом, правда, возникают некоторые трудности при определении операций над отношениями, аналогичными операциям над предикатами[4].
Во-вторых, предикат P ( x1,…,xn ), заданный на M, можно отождествить с функцией fp:Mn {0,1}, определяемой равенством:
Говорят, что предикат Р (х) является следствием предиката Q (х)[5]:
,
если
;
и предикаты Р (х) и Q (х) равносильны:
,
если
.
Приведём примеры к изложенному материалу.
Пример 1. Среди с ледующих предложений выделить предикаты и для каждого из них указать область истинности, если M = R для одноместных предикатов и M = R×R для двухместных предикатов[1]:
1. х + 5 = 1
2. При х = 2 выполняется равенство х2 – 1 = 0
3. х2 – 2х + 1 = 0
4. Существует такое число х, что х3 – 2
5. х + 2 < Зх – 4
6. Однозначное неотрицательное число х кратно 3
7. (х + 2) – (3х – 4)
8. х2 + у2 > 0
10
Решение.
5) Предложение является одноместным предикатом Р(х), IP =(3;+∞);
6) Предложение является одноместным предикатом Р (х), IP = {0; 3; 6; 9};
7) Предложение не является предикатом;
8) Предложение является двухместным предикатом Q(х,y), IQ = R×R \ {(0,0)}.
Пример 2. Изобразить на декартовой плоскости область истинности предиката [2].
Решение. Неравенство, составляющее исходный предикат, ограничивает часть плоскости, заключенную между ветвями параболы х = у2, она изображена серой частью рисунка:
Рисунок 1. График параболы х = у2
Предикаты, вслед за высказываниями, являются следующим важным предметом, исследуемым математической логикой.
11
Понятие предиката обобщает понятие высказывания, а теория предикатов представляет собой более тонкий инструмент, по сравнению с теорией высказываний, для изучения закономерностей процессов умозаключения и логического следования, составляющих предмет математической логики[1].
Таким образом, в основном, термин « предикат » понимается в смысле исходного определения, т.е. как языковое выражение. Связано это с тем, что одной из главных целей введения предикатов, как уже отмечалось во введении, является изучение выразительных возможностей логики первого порядка, возможности представления средствами этой логики информации, выраженного на каком - либо естественном языке людей, например, на русском или английском языке.
Заключение
Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект ( буквально – подлежащее, хотя оно может играть и роль дополнения ) и предикат ( буквально – сказуемое, хотя оно может играть и роль определения).
Субъект – это то, о чем что - то утверждается в высказывании, а предикат – это то, что утверждается о субъекте. Логика предикатов – это расширение логики высказываний за счет использования предикатов в роли логических функций.
Итак, актуальность темы реферата несомненна. Цель достигнута и задачи выполнены. Литература просмотрена, выбрана, проанализирована, результаты представлены в данном реферате.
12
Список используемых источников
13