Предикаты: определения и примеры
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
РЕФЕРАТ
на тему: "Предикаты: определения
и примеры"
Оглавление
Введение
Предикаты: определения и примеры
Заключение
Список используемых источников
Введение
В чем состоит необходимость введения предикатов в
математику?
Дело в том, что сама по себе логика высказываний обладает
довольно слабыми выразительными возможностями. Пользуясь только логикой, нельзя
выразить даже очень простые, с математической точки зрения, рассуждения.
Возьмем, например, следующее умозаключение. "Всякое
целое число является рациональным. Число 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".
Предикат с заменяемыми переменными x1,…,xn обычно
обозначается заглавной латинской буквой, после которой в скобках указываются
эти переменные. Например, P (x1,x2), Q (x2,x3),
R (x1). Среди переменных в скобках могут быть и фиктивные [2].
Определение 2. Предикат (n-местный, или n-арный
<#"815917.files/image003.gif"> (или " Истина " и " Ложь
"), определённая на n-й декартовой степени
<#"815917.files/image004.gif">,
если на любом наборе аргументов он принимает значение 1.
Предикат называют тождественно - ложным [2] и пишут:
если на любом наборе аргументов он принимает значение 0.
Предикат называют выполнимым, если хотя бы на одном наборе
аргументов он принимает значение 1 [5].
Например, обозначим предикатом EQ (x, y) отношение равенства
(" x = y "), где x и y принадлежат множеству
вещественных чисел
<#"815917.files/image006.gif">{ x1,…,xn}, то местность нового предиката
равна n [3].
Если предикат 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.
При этом, правда, возникают некоторые трудности при определении
операций над отношениями, аналогичными операциям над предикатами [4].
Во-вторых, предикат P (x1,…,xn), заданный на
M, можно отождествить с функцией fp: Mn {0,1}, определяемой равенством:
Говорят, что предикат Р (х) является следствием предиката Q
(х) [5]: , если ; и предикаты Р (х) и Q (х) равносильны:
,
Если
.
Приведём примеры к изложенному материалу.
Пример 1. Среди следующих предложений выделить предикаты и для каждого из
них указать область истинности, если M = R для одноместных предикатов и M
= R×R для
двухместных предикатов [1]:
. х + 5 = 1
. х2 - 2х + 1 = 0
. Существует такое число х, что х3 - 2
. х + 2 < Зх - 4
. Однозначное неотрицательное число х кратно 3
. (х + 2) - (3х - 4)
. х2 + у2 > 0
Решение.
1) Предложение является одноместным предикатом Р (х), IP
= { - 4};
2) Предложение не является предикатом. Это ложное высказывание;
3) Предложение является одноместным предикатом Р (х), IP
={1};
4) Предложение не является предикатом. Это истинное
высказывание;
5) Предложение является одноместным предикатом Р (х),
IP = (3; +∞);
) Предложение является одноместным предикатом Р (х), IP
= {0; 3; 6; 9};
) Предложение не является предикатом;
) Предложение является двухместным предикатом Q (х,y),
IQ = R×R \ { (0,0) }.
Пример 2. Изобразить на декартовой плоскости область
истинности предиката [2].
Решение. Неравенство, составляющее исходный предикат,
ограничивает часть плоскости, заключенную между ветвями параболы х = у2,
она изображена серой частью рисунка:
Рисунок 1. График параболы х = у2
Предикаты, вслед за высказываниями, являются следующим важным
предметом, исследуемым математической логикой.
Таким образом, в основном, термин " предикат "
понимается в смысле исходного определения, т.е. как языковое выражение. Связано
это с тем, что одной из главных целей введения предикатов, как уже отмечалось
во введении, является изучение выразительных возможностей логики первого
порядка, возможности представления средствами этой логики информации,
выраженного на каком - либо естественном языке людей, например, на русском или
английском языке.
предикат декартова плоскость математика
Заключение
Логика предикатов, как и традиционная формальная логика, расчленяет
элементарное высказывание на субъект (буквально - подлежащее, хотя оно может
играть и роль дополнения) и предикат (буквально - сказуемое, хотя оно может
играть и роль определения).
Субъект - это то, о чем что - то утверждается в высказывании,
а предикат - это то, что утверждается о субъекте. Логика предикатов - это
расширение логики высказываний за счет использования предикатов в роли
логических функций.
Итак, актуальность темы реферата несомненна. Цель достигнута
и задачи выполнены. Литература просмотрена, выбрана, проанализирована,
результаты представлены в данном реферате.
Список
используемых источников
1. Эвнин
А.Ю. Дискретная математика. Конспект лекций. 1998.
2. Ерусалимский
А.Я. Дискретная математика. Теория. Задачи. Приложения. 2000.
3. Электронный источник.
URL: http://forum. vopr.net <http://forum.vopr.net>
. Электронный
источник. http://lib. mexmat.ru/books/109887
<http://lib.mexmat.ru/books/109887>
. Электронный
источник. http://lib. mexmat.ru/books/81214 <http://lib.mexmat.ru/books/81214>