Предикаты и кванторы реферат

Обновлено: 30.06.2024

2. Аксиоматическое представление узкого исчисления предикатов.

3. Натуральное узкое исчисление предикатов.

4. Погружение аристотелевской силлогистики в узкое исчисление предикатов.

5. Расширенное исчисление предикатов.

1. ПРЕДИКАТЫ И КВАНТОРЫ

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

Если обозначить ту часть высказываний, в которой говорится о свойствах или отношениях большими латинскими буквами Р, Q, R, … с индексами или без них, а переменные – традиционно малыми латинскими буквами х, y, z ,… с индексами или без них, то обозначение предиката примет вид Р (х), Q(х,у), L(х,y,z) и т.д. Число n переменных или аргументов, от которых зависит предикат называется n -местностью предиката, так что можно говорить об одноместном предикате, двухместном и т.д.

При подстановке в предикат, вместо переменных имен предикатов он превращается в высказывание. Так что предикат, скажем предикат Р(х), можно рассматривать записью некоторого множества высказываний, мощность которого равна мощности множества значений аргумента.

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

Если Р (х₁, х₂, …, х_п) – n-местный предикат и m его переменных (m £n) связываются кванторами, то он превращается в (n-m) местный предикат.

В выражении "_х "_у Р(х,у) знаки общности могут быть переставлены без изменения смысла высказывания. То же самое имеет место в выражении $_х $_у Р(х,у).

Напротив, в выражении "_х$_у Р(х,у) порядок следования знаков"_х и $_у играет существенную роль. Например, высказывание "_х$_у (х n) переменная m связана, а переменная n свободна. Если мы вместо n подставим m+1, то получим ложное выражение: $m (m> m+1).

Правило удаление квантора общности:

У" .

Примером рассуждения по правилу У":

Правило введения квантора общности:

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

Примером рассуждения по правилу

В": .

Правило введение квантора существования :

В$ .

Примером рассуждения по правилу В$:

2 – четное и простое число

$х (х – четное и простое).

Правило удаления квантора существования:

У$ ,

где у₁, …у_n - все свободные именные переменные выражения j, отличные от переменной х, а выражение j(х/σ у₁, …у_n) – результат подстановки в выражение j постоянной σ, отмеченной индексами у₁, …у_n вместо х. Заметим, что переменные у₁, …у_n, входящие в выражение σ у₁, …у_n рассматриваются в качестве свободных. Поэтому выражение σ у₁, …у_n можно подставлять в выражение j вместо переменной х тогда, и только тогда, когда эта переменная не находится в области действия квантора, связывающего переменные у₁, …у_п_.

В качестве примеров вывода формул в натуральном узком исчислении предикатов рассмотрим вывод аксиом e),f), а также формул (37), (38).

е) "х F(х)® F(у)

Доказательство:

f) F(у) ® $х F(х)

Доказательство:

Докажем формулу (37):

р®"х (рÚ F(х))

Доказательство:

Докажем теперь формулу (38):

"х F(х) ®$х F(х)

Доказательство:

5. ПОГРУЖЕНИЕ АРИСТОТЕЛЕВСКОЙ СИЛЛОГИСТИКИ В УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

"х ( S(х) ®Р(х)) (39)

`$х (S(х) Ù Р(х)) (40) или по другому "х ( S(х) ®`R(х)) (40 1 )

$х (S(х) Ù Р(х)) (41)

$х (S(х) Ù`R(х)) (42)

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

Модус АSР® ISР, пользуясь (39)-(42) запишем так:

"х ( S(х) ®Р(х)) ®$х (S(х) Ù Р(х)) (43)

Доказательство:

"х ( S(х) ®Р(х))
S(у) ®Р(у)
S(у)
Р(у)
S(у) ÙР(у)

Модус ЕSР®ОSР опять-таки с помощью (39-42) записываем так:

"х ( S(х) ®`R(х)) ® $х (S(х) Ù`R(х)) (44)

Доказательство:

"х ( Sх ®`R(х))
"х ( S(х) ®`R(х)) ®(S(у) ®`R(у)) е)>
S(у) ®`R(у)
S(у)
`R(у)
S(у) Ù `R(у)

Модус АSР® IРS записываем в виде:

"х ( Sх ®R(х)) ®$х (S(х) ÙR(х)) (45)

Доказательство:

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

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

Используя (39)-(42), записываем первый модус первой фигуры силлогизма АМРÙАSМ®АSР так:

"х (М(х)®Р(х)) Ù "х (S(х) → М(х)) →"х(S(х) →Р(х)) (46)

Доказательство:

"х (М(х)®Р(х)) Ù "х (S(х) → М(х))
"х (М(х)®Р(х))
"х (S(х) → М(х))
М(у)®Р(у)
S(у) ® М(у)
S(у) ® Р(у)

Докажем справедливость первого модуса второй фигуры силлогизма

ЕРМÙ АSМ→ЕSР.

Используя (39)-(42), записываем его в виде:

"х (Р(х) ®`М(х)) Ù "х (S(х) → М(х)) →"х(S(х) →`Р(х)) (47)

Доказательство:

"х (Р(х) ®`М(х)) Ù "х (S(х) → М(х))
"х (Р(х) ®`М(х))
"х (S(х) → М(х))
Р(у)®`М(у)

S_ (у) ® М(у)
`М(у)®`Р(у)
М(у)®`Р(у)
S (у)®`Р(у)

Наконец, докажем первый модус третьей фигуры силлогизма

АМРÙАSМ→ІSР.

Используя (39)-(42), записываем его в виде:

"х (М(х)®Р(х)) Ù "х (М(х)→S(х)) →$х(S(х) Ù Р(х))

Доказательство:

"х (М(х)®Р(х)) Ù "х (М(х)→S(х))
"х (М(х)®Р(х))
"х (М(х)→S(х))
М(у)® Р(у)
М(у)® S (у)
М(у)
S (у)
Р(у)
S (у) ÙР(у)

6. РАСШИРЕННОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

В узком исчислении предикатов переменные являются пропозициональные переменные, именные переменные и переменные представляющие предикаты. В формулах этого исчисления кванторы связывают только именные переменные. Это исчисление явно не завершено. Например, формула "R"х (Р(х)ÚР(х)) выполняется для любого предиката Р. значит, мы должны располагать квантором общности для предиката. С другой стороны формула "хF(х) явно не общезначима. Но она выполняется для некоторых F. Чтобы выразить это мы должны располагать и кванторами существования для предиката, и выполнимость этой формулы записать так: $F "хF(х).

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

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

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

ГОСТ

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

Предикат - утверждение, которое содержит переменные, принимающие значение $1$ или $0$ (истинно или ложно) в зависимости от значений переменных.

Например, выражение $x=x^5$ является предикатом, т.к. оно является истинным при $x=0$ или $x=1$ и ложным при всех остальных значениях $x$.

Множество, на котором предикат принимает только истинные значения, называется множеством истинности предиката $I_p$.

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

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

$P (x_1, \dots, x_n)=1$

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

$P (x_1, \dots, x_0)=0$

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

Т.к. предикаты могут принимать только два значения (истинно/ложно или $0/1$), то к ним можно применять все операции алгебры логики: отрицание, конъюнкция, дизъюнкция и т.д.

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

Таким образом, предикатом является все то, что утверждается или отрицается о субъекте суждения.

Готовые работы на аналогичную тему

Операции над предикатами

Рассмотрим применение операций алгебры логики к предикатам.

Логические операции:

Дизъюнкция двух предикатов $A(x)$ и $B(x)$ -- предикат , который принимает ложное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает ложное значение и принимает истинное значение во всех остальных случаях. Множество истинности предиката -- объединение областей истинности предикатов $A(x)$ и $B(x)$.

Отрицание предиката $A(x)$ -- предикат, который принимает истинное значение при всех значениях $x$ из $T$, при которых предикат $A(x)$ принимает ложное значение и наоборот. Множество истинности предиката $A(x)$ -- дополнение $T'$ к множеству $T$ в множестве $x$.

Множество истинности предиката -- объединение множества истинности предиката $B(x)$ и дополнения к множеству истинности предиката $A(x)$.

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

Кванторы

Кванторы -- логические операторы, применение которых к предикатам превращает их в ложные или истинные высказывания.

Квантор -- логические операции, которые ограничивают область истинности предиката и создают высказывание.

Чаще всего используют кванторы:

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

Примеры применения кванторов

С помощью квантора всеобщности можно записать следующие ложные высказывания:

любое натуральное число делится на $7$;

каждое натуральное число делится на $7$;

все натуральные числа делятся на $7$;

который будет иметь вид:

Для записи истинных высказываний используем квантор существования:

существуют натуральные числа, которые делятся на $7$;

найдётся натуральное число, которое делится на $7$;

хотя бы одно натуральное число делится на $7$.

Запись будет иметь вид:

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

Операции над кванторами

Для построения отрицания высказываний, которые содержат кванторы, применяется правило отрицания кванторов:

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

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

Определение. Предложения, содержащие переменные, истинность или ложность которого зависит от значения переменного, входящего в него, называется предикатом. Другими словами, это функция, заданная на определенном множестве. Обозначение Р(х), Р(х,у), …, Р(х1,х2, …,хn).

Основные множества для предикатов

Считается, что с каждым предикатом задано множество, из которого выбирают значение переменных. Такое множество называют областью определения предиката. Обозначение D(P).

Пример. Р(х)=«х+3 . Какое бы число не поставить вместо х, будем получать либо ложное либо истинное высказывание.

Подмножеством области определения предиката, на котором он принимает значение истинность, называется множеством истинности данного предиката. Обозначение М(Р). М(Р) D(P).

Пример для Р(х)=«х+3

Операции над предикатами

Отрицанием предиката Р(х) называется новый предикат , определённый на множестве D(Р) и истинный при тех значениях переменных х, при которых предикат Р(х) ложен.

Пример. =\ =то есть убрать из D(P) все числа, делящиеся на 9.

Конъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х)⋀Q(x), определённый на множестве D(Р) и истинный при тех значениях переменных х, при которых истины одновременно оба предиката P(x) и Q(x).

Пример. = =

Дизъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х)VQ(x), определённый на множестве D(Р) и истинный при тех значениях переменных х, при которых истинен хотя бы один из предикатов P(x) и Q(x).

= =

Импликацией двух предикатов Р(х) и Q(x) называется новый предикат Р(х) Q(x), определённый на множестве D(Р) и ложный при тех значениях переменных х, при которых предикат P(x) истинен, а предикат Q(x) ложен.

Пример. =\ =

Эквиваленцией двух предикатов Р(х) и Q(x) называется новый предикат Р(х) ↔ Q(x), определённый на множестве D(Р) и истинный при тех значениях переменных х, при которых либо оба предиката истины, либо оба предиката ложны.

= ,

Кванторы. Операции навешивания квантора

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

Задания для самостоятельной работы

Объяснить, почему следующие выражения имеют значение истина или ложь, описать выражения словами

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

однозначное число х кратно 3;

На множестве M = определены предикаты: P(x) - "число Х делится на 6" и Q(x) - "число Х 30". Найдите область истинности предикатов , , , ,

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

а) Некоторые машины умнее людей.

б) Любой играет в теннис лучше Фрэда.

в) Для каждого действует существует равное и противоположно направленное противодействие.

г) Каждый игрок в гольф, в конце концов, будет обыгран более сильным игроком

Содержание

Введение……………………………….…………………………….……. …….3
Основная часть. Предикаты: определения и примеры. …. 5
Заключение……………………………………. ….…12
Список используемых источников……………

Вложенные файлы: 1 файл

ПРЕДИКАТЫ.docx

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

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

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

Факультет ______________________________ _________________

Кафедра ______________________________ ___________________

Автор работы: _______________ _ _______________

Преподаватель ________________ _____________

(ученая степень, звание, ФИО) (подпись)

Основная часть. Предикаты: определения и примеры. . …. 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что в определении не требуется, чтобы y была одна из переменных x1,…,xn, хотя в содержательных примерах, квантор навешивается на одну из переменных x1,…,xn. Указанное требование не накладывается, чтобы избежать усложнения определения формулы логики предикатов. Если y – одна из переменных x1,…,xn, то после навешивания квантора на y новый предикат является ( n-1 ) - местным, если y< 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].

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

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

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

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

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

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

Читайте также: