УПП_Дискретная математика-1. Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики

• Название: Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики
• Дата: 09.02.2023
• Размер: 6.65 Mb.
• Имя файла: УПП_Дискретная математика-1.doc
• Тип: Учебно-практическое пособие; #929287
• страница: 8 из 19

2.4. Логика предикатов

Для определения понятия предиката рассмотрим следующие примеры.

Примеры.

1. 
   Пусть N – множество натуральных чисел, и буквой P обозначено свойство натурального числа быть простым. Если x представляет собой произвольный элемент из N, тогда выражение «натуральное число x является простым», которое можно записать в виде P(x), уже не является высказыванием, т.к. значение истинности данного утверждения зависит от x. По существу P(x) означает переменное (неопределенное) высказывание, которое становится определенным, когда x заменено определенным элементом из N. Например, P(3) = 1, P(4) = 0. Иначе говоря, P(x) представляет собой функцию, определенную на множестве натуральных чисел и принимающую только два значения: 0 и 1.
   
2. 
   Пусть Z – множество целых чисел и P – свойство пары чисел иметь одинаковый знак. Тогда P(x,y) будет означать: «целые числа x и y имеют одинаковый знак». Это неопределенное высказывание становится определенным, если x и y заменить конкретными числами. Например, P(2,3)=1, P(-1,5)=0. Неопределенное высказывание P(x,y) представляет собой функцию двух переменных.
   
3. 
   Пусть A и B – множество точек, C – множество прямых на евклидовой плоскости, а P(a,b,c) обозначает: «прямая c проходит через точки a и b». В этом примере мы имеем дело с функцией трех переменных, причем a и b принимают значения из множества точек, а c принимает значения из множества прямых евклидовой плоскости.
   

Определение 1. Предикатом называется функция, отображающая множество произвольной природы во множество {0,1}, или (ложно, истинно).

Обратимся теперь к определению предиката в общем случае.

Определение 2. Пусть N={N₁,N₂,N₃,…,N_n} – конечный набор множеств. Всякая функция P(X₁,…,X_n), ставящая в соответствие каждому набору из n элементов {a₁,a₂,…,a_n), где a_iN_i, какой-либо из элементов булевой алгебры {0,1} называется n-местным предикатом на N. Множество N_i называется предметной областью для переменной x_i. Переменные x₁,…,x_n называются предметными переменными. Некоторые из множества N_i могут совпадать.

Если при отображении P образом набора (a₁,a₂,…a_n) является единица, то записывают.
P(a₁,…,a_n)=1
и говорят, что значение предиката P для набора (a₁,…,a_n) является истинным. Если же образом (a₁,…,a_n) является нуль, то записывают

P(a₁,…,a_n)=0
и говорят, что значение предиката P для набора (a₁,…,a_n) является ложным.

n – местный предикат при n = 1 называется унарным, при
n = 2 – бинарным и при n=3 тернарным. Для общности введем еще понятие 0-местного предиката, а именно, 0-местным предикатом называется любе истинное или ложное высказывание.

Поскольку предикаты принимают значения из (0,1), то над ними можно производить все логические операции, рассматриваемые нами в алгебре высказываний (-, , , , ), сохраняя за ними те же определения. Кроме операций алгебры высказываний, мы будем употреблять еще две новые операции, которые связаны с особенностями предикатов и выражают собой утверждения всеобщности и существования.

Кванторы

Пусть P(x) – одноместный предикат, заданный на некотором множестве M. Если переменная x обозначает любой элемент из множества M, то P(x) является неопределенным высказыванием.

Операция  ставит в соответствие неопределенному высказыванию P(x) высказывание xP(x), которое читается так: «для любого x имеет место P(x)» и по определению является истинным тогда и только тогда, когда P(x) истинно для любого элемента xM. Переход от неопределенного высказывания P(x) к высказыванию xP(x) называется операцией навешивания квантора общности по предметному переменному x.

Операция  ставит в соответствие неопределенному высказыванию P(x) высказывание xP(x), которое читается так: «существует такое x, что имеет место P(x)» и по определению является истинным тогда и только тогда, когда P(x) истинно хотя бы для одного элемента xM. Переход от неопределенного высказывания P(x) к высказыванию xP(x) называется операцией навешивания квантора существования по предметному переменному x.

В первом случае мы говорим, что предметная переменная x связана в предикате P(x) квантором всеобщности, во втором случае – квантором существования.

Определим операции навешивания квантора для общего случая n-местного предиката P(x₁,…,x_n). Операции навешивания кванторов  и  по переменному x₁ (в общем случае по переменному x_i, где I= ) ставит в соответствие предикату P(x₁,…,x_n) (n-1) – местные предикаты

x₁P(x_1,…, x_n) и x₁P(x_1,…, x_n)

соответственно.

Истинностные значения этих предикатов определяются для фиксированных наборов значений предметных переменных x₂,…,x_n следующим образом:
x₁P(x_1,a_2…,a_n)=

x₁P(x_1,a_2…,a_n)=
В общем случае, если k1,…,x_k в таком предикате будут связанными, а переменные x_k+1,…,x_n – свободными. При k=n предикат становится высказыванием.
Примеры.

Рассмотрим предикат Д(x₁,x₂) – «число x₁ делится на число x₂», определенный на множестве натуральных чисел. Тогда операция навешивания кванторов приводит к следующим утверждениям:

1. 
   x₁Д(x_1, x₂) – «для любого x₁ имеет место Д(x₁,x₂)», т.е. всякое x₁ делится на x₂. Этот предикат принимает значение истины только для х₂=1.
   
2. 
   x₁ Д(x_1, x₂) – «существует x_1, которое делится на x₂». Этот предикат принимает значение истины для любого значения x₂.
   
3. 
   x₁x₂Д(x_1, x₂) – «для всякого x₁ и для всякого x₂ имеет место делимость x₁ на x_2. Это высказывание является ложным.
   
4. 
   x₁x₂Д(x_1, x₂) – «существует x₁, которое делится на всякое x₂» – ложное высказывание.
   
5. 
   x₂x₁Д(x_1, x₂) – «для всякого x₂ существует x₁ такое, что x₁ делится на x₂» – истинное высказывание.
   

Кванторы как обобщение логических связок.

Пусть предметная область переменной x предикатов P(x,y) конечна: (x₁,x₂,…,x_k). Тогда xP(x,y) означает: P(x₁,y) – истинно, P(x₂,y) – истинно и т.д., т.е.

xP(x,y) =P(x₁,y)P(x₂,y)…P(x_k,y).

Аналогично xP(x,y) является сокращением дизъюнкции:

xP(x,y) =P(x₁,y)P(x₂,y)… P(x_k,y).

Это показывает, что кванторы суть другая форма конъюнкции и дизъюнкции.
Отрицание кванторных предикатов
Два предиката будем считать равносильными, если их значения истинности совпадают при всех значениях входящих в них свободных переменных. При этом имеется в виду, что свободные переменные в одном предикате не являются связанными в другом.

Справедливы следующие равносильности, относящиеся к отрицаниям кванторных предикатов:

.

Действительно, в первой из них левая часть читается: неверно, что для каждого x предикат P(x) истинен; правая – существует x, для которого P(x) ложен. Ясно, что эти два утверждения имеют один и тот же смысл. Аналогичным рассуждением убеждаемся в справедливости второй равносильности.

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

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

Пример.





Формулы, в которых из операций алгебры высказываний имеются только операции ^–, , , а знаки отрицания относятся только к элементарным предикатам, называются приведенными формулами.