Предикат

Оглавление:

Введение…………………………………………………………………………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).