Предикат

Обозначение следования 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.