Предикат

Оглавление:

Введение…………………………………………………………………………2

§1.  Понятие предиката…………………………………………………………4

§2.  Классификация предикатов………………………………………………..6

§3.  Множество истинности предиката………………………………………..8

§4. Равносильность и следование предикатов……………………………….10

§5. Логические операции над предикатами…………………………………..12

Заключение……………………………………………………………………...15

Обозначение символов…………………………………………………………16

Библиографический список литературы……………………………………...17

Введение

Логика - наука очень старая. Она возникла тогда, когда развитие специальных наук и вообще человеческого мышления сделало актуальным вопрос о том, как надо рассуждать, чтобы получить правильные выводы. Несомненен интерес к логике среди математиков и философов эпохи расцвета греческой культуры в VI-IV вв. до н.э. Но первое дошедшее до нас большое сочинение, посвященное специально логике ("Аналитики" Аристотеля, 384-322 гг. до н.э.), принадлежит уже позднегреческой эпохе. Независимо возникла буддистская логика, но дальнейшее развитие логики в Европе имеет своим исходным пунктом изучение Аристотеля. 

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

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

Целью данной курсовой работы является раскрытие понятия предиката, классификации предикатов, множества истинности предиката.

В соответствии с целью исследования были поставлены следующие задачи:

- собрать, изучить  и систематизировать теоретический  материал по теме исследования;

- дать понятие предиката;

- привести классификацию предикатов и множество истинности предиката;

- сформулировать понятие равносильности  и следования предикатов;

- рассмотреть  логические операции над предикатами.

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

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

В высказывании все четко: это — повествовательное предложение, о котором можно сказать истинное оно или ложное. Предикат — предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно. Дадим точное определение.

Определение. Определённым на множествах M1, M2, …, Mn n-местным предикатом называется предложение, содержащее n переменных x1, x2, …, xn, превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств M1, M2, …, Mn соответственно.

Обозначение для n-местного предиката: P(x1, x2, …, xn).

x1, x2, …, xn – предметные переменные.

Элементы множеств M1, M2, …, Mn называются конкретными предметами.

Всякий n-местный предикат P(x1, x2, …, xn), определенный на множествах M1, M2, …, Mn, представляет собой функцию n аргументов, заданную на указанных множествах и принимающую значения в множестве всех высказываний. Поэтому предикат называют также функцией-высказыванием.

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

1. P(x) – «x делится на восемь».
2. Q(x, y) – «x – отец у».
3. D – «Луна меньше Земли».
4. R(x) – «x2  – 6x + 0,5 = 0».
5. H(x) – «x разгоняется до 100 км./ч. за 2 секунды».
6. L(x, y, z) – «x>y и x<z».
7. Предложение "Река x впадает в озеро Байкал" является одноместным предикатом, определенным над множеством всех названий рек. Подставив вместо предметной переменной x название "Баргузин", получим высказывание "Река Баргузин впадает в озеро Байкал". Это высказывание истинно. Подставив вместо предметной переменной x название "Днепр", получим ложное высказывание "Река Днепр впадает в озеро Байкал".
8. Предложение (выражение) "х2 + y2 ≤ 9" является двухместным предикатом, заданным над множествами R, R. Множества, на которых задан двухместный предикат, совпадают (говорят, что "двухместный предикат задан на множестве R2"). Пара действительных чисел 2, 2 превращает данный предикат в истинное высказывание:

"22 + 22 ≤ 9", а пара чисел 2, 3 — в ложное: "22 + 32 ≤ 9".

Отметим еще один подход к понятию предиката. Как отмечалось, предикат P(x1, x2, …, xn), определенный на множествах M1, M2, …, Mn, превращается в конкретное высказывание P(x1, x2, …, xn), если вместо предметных переменных x1, x2, …, xn подставить в него конкретные предметы (элементы a1,a2,…,a3) из множеств M1, M2, …, Mn соответственно. Это высказывание может быть либо истинным, либо ложным, т. е. его логическое значение равно 1 или 0. Следовательно, данный предикат определяет функцию n аргументов, заданную на множествах M1, M2, …, Mn принимающую значение в двухэлементном множестве {0; 1}. Иногда эту функцию и называют предикатом.

§2.  Классификация предикатов

Определение. Предикат P(x1, x2, …, xn), заданный на множествах M1, M2, …, Mn называется:

а) тождественно истинным, если при любой подстановке вместо переменных x1, x2, …, xn любых конкретных предметов a1, a2,…, a3 из M1, M2, …, Mn соответственно, он превращается в истинное высказывание P(a1, a2, …, a3);

б) тождественно ложным, если при любой подстановке вместо переменных x1, x2, …, xn любых конкретных предметов из множеств M1, M2, …, Mn соответственно он превращается в ложное высказывание;

в) выполнимым (опровержимым), если существует по меньшей мере один набор конкретных предметов a1, a2, …, a3 из множеств M1, M2, …, Mn соответственно, при подстановке которых вместо соответствующих предметных переменных в предикат P(x1, x2, …, xn) последний превратится в истинное (ложное) высказывание P(a1, a2, …, a3).

Примеры тождественно истинных  предикатов:

1. Одноместный предикат "sin2x + cos2x = 1", определенный на множестве действительных чисел, тождественно истинный. Наконец, двухместный предикат "x2 + y2 < 0", заданный также на множестве действительных чисел, является тождественно ложным предикатом, потому что любая пара действительных чисел превращает его в ложное высказывание (не удовлетворяет ему).
2. Примером тождественно истинного предиката может служить трехместный предикат, заданный неравенством (x +y)2 + z2 ≥ 0, где х, у, z - рациональные переменные.
3. P(x):|x| ≥ 0.

Примеры тождественно ложных  предикатов:

1. Тождественно ложным является предикат х+1=х, где х — целочисленная переменная.
2. T(x): cos x > 1.
3. P(x; y): x2 + y2 < 0.

Примеры выполнимых (опровержимых) предикатов:

1. Одноместный предикат "Город x расположен на берегу реки Волги", определенный на множестве названий городов, является выполнимым, потому что существуют города, названия которых превращают данный предикат в истинное высказывание, или, иначе, удовлетворяют этому предикату (например, Ульяновск, Саратов и т. д.). Но данный предикат не будет тождественно истинным, потому что существуют города, названия которых превращают его в ложное высказывание, или, иначе, не удовлетворяют этому предикату (например, Прага, Якутск и т.д.). Этот же предикат являет собой пример опровержимого, но не тождественно ложного предиката.
2. Выполнимыми являются предикаты «х - простое число», «х делится на у», «x2 – 5x + 6 = 0», где х - целочисленная переменная.
3. W(x; y): 2x + 3y = 1, где x, y – действительные переменные.

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

1) каждый тождественно  истинный предикат является выполнимым, но     обратное  неверно; 
2) каждый тождественно ложный предикат является опровержимым, но обратное неверно; 
3) каждый не тождественно истинный предикат будет опровержимым, но, вообще говоря, не будет тождественно ложным; 
4) каждый не тождественно ложный предикат будет выполнимым, но, вообще говоря, не будет тождественно истинным.

§3.  Множество истинности предиката.

Определение. Множеством истинности предиката P(x1, x2, …, xn), заданного на множествах M1, M2, …, Mn называется совокупность всех упорядоченных n-систем (a1, a2, …, an), в которых a1∈M1, a2∈M2, …, an∈Mn, таких, что данный предикат P(x1, x2, …, xn) превращается в истинное высказывание P(a1, a2, …, an) при подстановке x1=a1, x2=a2, …, xn=an.

Обозначение Р+:  Р+= {(a1, a2, …, an) : λ( P(a1, a2, …, an)) = 1}.

Множество Р+  истинности n-местного предиката P(x1, x2, …, xn) представляет собой n-арное отношение между элементами множеств M1, M2, …, Mn . Если предикат Р(х)  — одноместный, заданный над множеством М, то его множество истинности  Р+ является подмножеством множества

 М: Р+⊆ М. 

Пример:

1. Множеством истинности двухместного предиката "Точка x принадлежит прямой y", заданного на множестве E всех точек плоскости и на множестве F  всех прямых этой плоскости, является бинарное отношение принадлежности (инцидентности) между точками и прямыми плоскости.
2. Множество истинности двухместного предиката S(x,y): x2 + y2 =9, заданного на множестве R2, есть множество всех таких пар действительных чисел, которые являются координатами точек плоскости, образующими окружность с центром в начале координат и радиуса 3. Наконец, если A(x): " |а| > 2" — одноместный предикат над R, то 

A+ = (-∞; - 2) ∪ (2; +∞).

В терминах множества истинности легко выразить понятия, связанные с классификацией предикатов. В самом деле, n-местный предикат P(x1, x2, …, xn), заданный на множествах M1, M2, …, Mn, будет:

а) тождественно истинным тогда и только тогда, когда

P+ = M1 × M2 × ... × Mn;  
б) тождественно ложным тогда и только тогда, когда P+= ∅; 
в) выполнимым тогда и только тогда, когда P+ ≠ ∅; 
г) опровержимым тогда и только тогда, когда P+≠ M1×M2× …×Mn.

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

§4. Равносильность и следование предикатов.

Определение 1. Два n-местных предиката P(x1, x2, …, xn) и Q(x1, x2, …, xn), заданных над одними и теми же множествами M1, M2, …, Mn, называются равносильными, если набор предметов (элементов) a1∈M1, a2∈M2, …, an∈Mn превращает первый предикат в истинное высказывание P(a1, a2, …, an), в том и только том случае, когда этот набор предметов превращает второй предикат в истинное высказывание Q(a1, a2, …, an).

Обозначение равносильности: P↔Q .

Определение 2. Предикат Q(x1, x2, …, xn) заданный над множествами называется следствием предиката P(x1, x2, …, xn), заданного над теми же множествами M1, M2, …, Mn, если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат

P(x1, x2, …, xn).

Обозначение следования P→Q.

Теорема 1. Каждые два тождественно истинных (тождественно ложных) предиката, заданных на одних и тех же множествах, равносильны. Обратно, всякий предикат, равносильный тождественно истинному (тождественно ложному) предикату, сам является тождественно истинным (тождественно ложным) предикатом.

Теорема 2. Каждый тождественно истинный n-местный предикат является следствием любого другого n-местного предиката , определённого на тех же множествах. Каждый n-местный предикат является следствием любого тождественно ложного n-местного предиката, определённого на тех же множествах.

Теорема 3. Пусть P(x1, x2, …, xn) и Q(x1, x2, …, xn)– два n-местных предиката, определённые на одних и тех же множествах, такие, что P ⇒Q, тогда

1) Если P(x1, x2, …, xn) тождественно истинный (выполнимый), то и Q(x1, x2, …, xn) тождественно истинный (выполнимый);

2) Если Q(x1, x2, …, xn) тождественно ложный (опровержимый), то и P(x1, x2, …, xn) тождественно ложный (опровержимый).

§5. Логические операции над предикатами.

К основным операциям над предикатами относятся отрицание предиката, конъюнкция предикатов, дизъюнкция предикатов, импликация предикатов, эквивалентность предикатов и кванторные операции. Рассмотрим все операции, за исключением кванторных.

1. Отрицание  предиката.

Определение. Дополнением множества А в множестве U, называется

множество обозначаемое Ā, состоящее из тех элементов множества U, которые не принадлежат к множеству А.

Ā=U\A={x: x ∈U и x ∉ A}

Теорема. Для n-местного предиката P(x1, x2, …, xn), определённого на

множествах M1, M2, …, Mn, множество истинности его отрицания ¬P(x1, x2, …, xn) совпадает с дополнением множества истинности данного предиката:

(¬P )+ = P+.

Следствие. Отрицание предиката будет тождественно истинным тогда и только тогда, когда исходный предикат будет тождественно ложен.

2. Конъюнкция  предикатов.

Определение. Конъюнкцией n-местного предиката P(x1, x2, …, xn), определённого на множествах M1, M2, …, Mn и m-местного предиката Q(y1, y2, …, ym), определённого на множествах N1, N2, …, Nm называется новый (n+m)-местный предикат, определённый на множествах M1, M2, …, Mn, N1,N2, …, Nm обозначаемый P(x1, x2, …, xn) ∧ Q(y1, y2, …, ym), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания.

Теорема. Для n-местных предикатов P(x1, x2, …, xn) и Q(x1, x2, …, xn), определённых на множествах M1, M2, …, Mn, множество истинности конъюнкции P(x1, x2, …, xn) ∧ Q(x1, x2, …, xn) совпадает с пересечением множеств истинности исходных предикатов: (P ∧ Q)+=P+∩Q+.

3. Дизъюнкция предикатов.

Определение. Дизъюнкцией n-местного предиката P(x1, x2, …, xn), определённого на множествах M1, M2, …, Mn и m-местного предиката Q(y1, y2, …, ym), определённого на множествах N1, N2, …, Nm называется новый (n+m)-местный предикат, определённый на множествах M1, M2, …, Mn, N1, N2, …, Nm обозначаемый P(x1, x2, …, xn)∨Q(y1, y2, …, ym), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один из исходных предикатов.

Теорема. Для n-местных предикатов P(x1, x2, …, xn) и Q(x1, x2, …, xn), определённых на множествах M1, M2, …, Mn, множество истинности дизъюнкции P(x1, x2, …, xn) ∧ Q(x1, x2, …, xn) совпадает с объединением множеств истинности исходных предикатов: (P ∧ Q)+=P+∪Q+.

4. Импликация предикатов.

Определение. Импликацией n-местного предиката P(x1, x2, …, xn) и m-местного предиката Q(y1, y2, …, ym) называется предикат, обозначаемый P(x1, x2, …, xn) → Q(y1, y2, …, ym), такой, что для любых предметов a1∈M1, a2∈M2, …, an∈Mn и в b1∈N1, b2∈N2, …, bm∈Nm высказывание P(a1, a2, …, an) → Q(b1, b2, …, bm) является импликацией высказываний P(a1, a2, …, an) и Q(b1, b2, …, bm).

5. Эквивалентность предикатов.

Определение. Эквивалентностью n-местного предиката P(x1, x2, …, xn) и m-местного предиката Q(y1, y2, …, ym) называется предикат, обозначаемый P(x1, x2, …, xn) ↔ Q(y1, y2, …, ym), такой, что для любых предметов a1∈M1, a2∈M2, …, an∈Mn и в b1∈N1, b2∈N2, …, bm∈Nm высказывание P(a1, a2, …, an) ↔ Q(b1, b2, …, bm) является эквивалентностью высказываний P(a1, a2, …, an) и Q(b1, b2, …, bm).

Задача на применение операции над предикатами.

Выразить множество истинности предиката

(P(x)⟶Q(x)) ⋀ (Q(x)⟶R(x)) ⋀ (Q(x)⟶¬R(x))

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

[(P(x)⟶Q(x)) ⋀ (Q(x)⟶R(x)) ⋀ (Q(x)⟶¬R(x))]+ ≅ [(¬P(x) ⋁ Q(x)) ⋀

(¬Q(x) ⋁ R(x)) ⋀ (¬Q(x) ⋁ ¬R(x))]+ = [(¬P(x) ⋀ ¬Q(x) ⋀ ¬Q(x)) ⋁

(¬P(x) ⋀ ¬Q(x) ⋀ ¬R(x)) ⋁ (¬P(x) ⋀ R(x) ⋀ ¬Q(x)) ⋁ (¬P(x) ⋀ R(x) ⋀

¬R(x)) ⋁ (Q(x) ⋀ ¬Q(x) ⋀ ¬Q(x)) ⋁ (Q(x) ⋀ ¬Q(x) ⋀ ¬R(x)) ⋁ (Q(x) ⋀

R(x) ⋀¬Q(x)) ⋁ (Q(x) ⋀ R(x) ⋀¬R(x))]+=[(¬P(x) ⋀ ¬Q(x)) ⋁ (¬P(x) ⋀

¬Q(x) ⋀ ¬R(x)) ⋁ (¬P(x) ⋀ R(x) ⋀ ¬Q(x))]+=[¬P(x) ⋀ ¬Q(x)]+=

P+ ∪ Q+.

Заключение.

В ходе написания работы была достигнута её цель – раскрытие вопроса: что такое предикат, классификация предикатов, множество истинности предиката, равносильность и следование предикатов, логические операции над предикатами.

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

Структура курсовой работы определяется её целью и задачами.

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

Обозначения символов

>  - больше,

< - меньше,

≥ - больше или равно,

≤ - меньше или равно,

{ , } – множество,

1 или И – истина,

0 или Л – ложь,

∈ - принадлежит,

∉ - не принадлежит,

{ : } - множество всех… таких, что верно…,

⊆ - является подмножеством,

⊂ - включено в,

⊇ - является надмножеством,

⊃ - включает в себя,

∪ - объединение,

⋂ - пересечение,

| | - абсолютная величина (модуль),

⇒, → - импликация, следование,

⇔, ↔ - эквивалентность, равносильность,

∧ - конъюнкция,

∨ - дизъюнкция,

¬ - отрицание,

R - вещественные (действительные) числа,

≠ - неравно,

∅ - пустое множество,

≅ - изморфизм.

Библиографический список литературы

1. Игошин В.И. Математическая логика и теория алгоритмов. — Academia, 2008.

2. П. С. Новиков, “Элементы математической логики”, государственное издательство физико-математической литературы, М., 1959. 
3. Бочаров В.А, Маркин В.И. Основы логики. - М.: Космополис, 2008.
4. Гетманова А.Д. Учебник по логике. - М.: Владос, 2007.
5. Ивин А.А. Элементарная логика. - М.: "Дидакт". 2007.
6. Ивлев Ю.В. Логика. - М.: Изд-во МГУ, 2009.
7. Кириллов В.И., Старченко А.А. Логика. - М.: Высшая школа, 2006.
8. Уёмов А.И. Задачи и упражнения по логике. - М.: Высшая школа,2006.

9. Гуц А.К. Математическая логика и теория алгоритмов. — Наследие, Диалог-Сибирь, 2003.

10. Ершов Ю.Л., Палютин Е.А. Математическая логика. — М.: Наука, Физматлит, 1987.

11. Клини С.К. Математическая логика. — М.:Мир, 1973.

12. Мендельсон Э. Введение в математическую логику. — М. Наука, 1971.