Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



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

Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. «Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или логика первого порядка.

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

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

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

Пример. Пусть М есть множество натуральных чисел N. Тогда выражения «x – простое число», «x – четное число», «x – больше 10» являются одноместными предикатами. При подстановке вместо x натуральных чисел получаются высказывания: «2 – простое число», «6 – простое число», «3 – четное число», «5 больше 10» и т.д. Выражения «x больше y», «x делит y нацело», «x плюс y равно 10» являются двухместными предикатами. (Конечно, последнее выражение можно было записать и так: «x+y=10»). Примеры трехместных предикатов, заданных на множестве натуральных чисел: число z лежит между «x и y», «x плюс y равно z», «|x-y|£ z».

Будем считать, что высказывание – нульместный предикат, то есть предикат, в котором нет переменных для замены.

Надо отметить, что местность предикатов не всегда равна числу всех переменных, содержащихся в выражении. Например, выражение «существует число x такое, что y=2x» на множестве натуральных чисел определяет одноместный предикат. По смыслу этого выражение в нем можно заменять только переменную y. Например, замена y на 6 дает истинное высказывание: «существует число x такое, что 6=2x», а замена y на 7 дает ложное (на множестве N) высказывание «существует число x такое, что 7=2x».

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

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

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

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

В логике предикатов первого порядка вводятся и две новые операции. Называются они квантором общности и квантором существования. Эти операции рассмотрим вначале на примерах. Пусть дано выражение «существует х такой, что x+y=10». На множестве натуральных чисел это предложение определяет одноместный предикат P(y), так Р(2) и Р(9) – истинные высказывания, Р(11) – ложное. Если обозначить предикат «x+y=10» через S(x, y) (а это предикат двухместный), то P(y) можно записать так: «существует х такой, что S(x, y)». В этом случае говорят, что предикат P(y) получен из предиката S(x, y) навешиванием квантора существования на x и пишут P(y)=($x)S(x, y). Рассмотрим другой пример. Выражение «для всех х справедливо, что y³ -х2» определяет на множестве целых чисел одноместный предикат Q(y). Если предикат «y³ -х2» обозначить через T(x, y), то Q(y) можно записать так: «для всех x справедливо T(x, y)». В таком случае говорят, что предикат Q(y) получен из предиката T(x, y) навешиванием квантора общности на х и пишут Q(y)=(" x)T(x, y).

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

Определение. Пусть P(x1, …, xn) – предикат, заданный на множестве M, y – переменная. Тогда выражение «для всякого y выполняется P(x1, …, xn)» – предикат, полученный из P навешиванием квантора общности на переменную y, а выражение «существует y такой, что выполняется P(x1, …, xn)» – предикат, полученный из P навешиванием квантора существования на переменную y.

Обозначения операций были введены выше.

Заметим, что в определении не требуется, чтобы y была одна из переменных x1, …, xn, хотя в содержательных примерах, которые будут ниже, квантор навешивается на одну из переменных x1, …, xn. Указанное требование не накладывается, чтобы избежать усложнения определения формулы логики предикатов. Если y – одна из переменных x1, …, xn, то после навешивания квантора на y новый предикат является (n-1)-местным, если yÏ { x1, …, xn}, то местность нового предиката равна n.

Если предикат W(x1, …, xn) получен из предикатов U(x1, …, xn) и V(x1, …, xn) с помощью связок, то истинность высказывания W(a1, …, an) определяется таблицами истинности этих связок. Пусть 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) истинно.

Интерпретация в логике первого порядка

Необходимо соотнести формулы логики предикатов первого порядка и предикаты. Как и в логике высказываний, подобное соотнесение осуществляет функция, называемая интерпретацией.

 

Определение. Интерпретацией на непустом множестве М называется функция, заданная на сигнатуре FÈ R, которая

1) константе ставит в соответствие элемент из М;

2) символу n-местной функции ставит в соответствие некоторую n-местную функцию, определенную на множестве М;

3) символу n-местного предиката ставит в соответствие n-местный предикат, заданный на М.

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

Приведем примеры. Пусть сигнатура состоит из символа одноместного предиката P и двухместного предиката D, M={2, 3, 6, 9, 12, 15} и

F=(P(x)& (" y)(P(y)®D(x, y))

 

Поставим в соответствие (проинтерпретируем) P(x) предикат «x – простое число», D(x, y) – предикат «x меньше или равно y». Тогда формула F получит в соответствие предикат «x=2». На этом же множестве можно рассмотреть и другую интерпретацию: P(x) ставится в соответствие «x – нечетное число», D(x, y) – предикат «x делит y». В таком случае, формула F получает в соответствие предикат «x=3». Если j – интерпретация, то предикат, соответствующий формуле F будем обозначать через j(F).

Пример интерпретации.

 

Логическое следствие

Определение. Формула G(x1, …, xn) называется логическим следствием формул F1(x1, …, xn), …, Fk(x1, …, xn), если для любой интерпретации j с областью М и любых a1, …, anÎ M из истинности высказываний (jF1)(a1, …, an), …, (jFk)(a1, …, an) следует истинность высказывания (jG)(a1, …, an).

Приведем примеры. Пусть F1=(" x)(P(x)®Q(x)& R(x)), F2=P(c), G=Q(c). Покажем, что формула G является логическим следжствием формул F1 и F2. Возьмем интерпретацию j с областью М такую, что высказывания jF1 и jF2 истинны. Элемент j(c) обозначим буквой b. Истинность jF2 означает, что высказывание (jP)(b) истинно. А истинность высказывания jF1 означает, что для любого элемента xÎ M истинно высказывание (jP)(x)®(jQ)(x)& (jR)(x). Поскольку это высказывание истинно для любого х, то, в частности, истинно для x=b. Мы видим, что истинна импликация (jP)(b)®(jQ)(b)& (jR)(b) и ее посылка (jP)(b). Из таблицы истинности импликации следует истинность заключения (jQ)(b)& (jR)(b). Следовательно, истинно высказывание (jQ)(b). А это и есть jG. Мы доказали, что если истинны высказывания jF1 и jF2, то истинно высказывание jG, т.е. что G –логическое следствие F1 и F2.

В качестве второго примера докажем нелогичность рассуждения о первокурсниках. Мы записали это рассуждение в виде последовательности формул Н1, Н2, и Н3. Для доказательства нелогичности рассуждения надо найти интерпретацию j, при которой формулы Н1 и Н2 истинны, а формула Н3 ложна. Пусть множество М состоит из трех элементов 2, 3, 4. Символы С, Л и П проинтерпретируем следующим образом:

 

(jС)(х)=«х – простое число»,

(jЛ)(х)=«х – четное число»,

(jП)(х)=’’х> 4»,

 

т.е. П интерпретируется как тождественно ложный предикат. Тогда формулы Н1 и Н2 истинны, поскольку посылки импликаций этих формул ложны при любом х. А формула Н3 ложна. Чтобы убедиться в этом достаточно взять х=2. Следовательно, рассуждение о первокурсниках нелогично.

Определение. Множество формул

K={F1(x1, …, xl), …, Fm(x1, …, xl)}

называется выполнимым, если существует интерпретация j с областью М и элементы a1, …, alÎ M такие, что все высказывания (jF1)(a1, …, al), …, (jFm)(a1, …, al) истинны.

Множество формул K = { F1=(" x)($y)(P(y)& Q(x, y)), F2=(" y)Q(c, y), F3=Ø P(c) } выполнимо. Возьмем в качестве области интерпретации множество натуральных чисел N. Символы P, Q и C проинтерпретируем следующим образом:

(jP)(u)=«u – простое число»,

(jQ)(u, v)=«u меньше или равно v»,

(j(C)=1.

Тогда высказывание jF1 означает, что для любого натурального числа х найдется простое число y, которое не меньше х, высказывание jF2 означает, что 1 –наименьшее натуральное число, а высказывание jF3 означает, что 1 – непростое число. Ясно, что все эти высказывания истинны, и поэтому множество формул K выполнимо.

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

Теорема 2. Формула G(x1, …, xn) является логическим следствием формул F1(x1, …, xn), …, Fk(x1, …, xn) тогда и только тогда, когда множество формул {F1(x1, …, xn), …, Fk(x1, …, xn), Ø G(x1, …, xn)} невыполнимо.

 

Пример.

Пример.

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

Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. «Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или логика первого порядка.

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

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

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

Пример. Пусть М есть множество натуральных чисел N. Тогда выражения «x – простое число», «x – четное число», «x – больше 10» являются одноместными предикатами. При подстановке вместо x натуральных чисел получаются высказывания: «2 – простое число», «6 – простое число», «3 – четное число», «5 больше 10» и т.д. Выражения «x больше y», «x делит y нацело», «x плюс y равно 10» являются двухместными предикатами. (Конечно, последнее выражение можно было записать и так: «x+y=10»). Примеры трехместных предикатов, заданных на множестве натуральных чисел: число z лежит между «x и y», «x плюс y равно z», «|x-y|£ z».

Будем считать, что высказывание – нульместный предикат, то есть предикат, в котором нет переменных для замены.

Надо отметить, что местность предикатов не всегда равна числу всех переменных, содержащихся в выражении. Например, выражение «существует число x такое, что y=2x» на множестве натуральных чисел определяет одноместный предикат. По смыслу этого выражение в нем можно заменять только переменную y. Например, замена y на 6 дает истинное высказывание: «существует число x такое, что 6=2x», а замена y на 7 дает ложное (на множестве N) высказывание «существует число x такое, что 7=2x».

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

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

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

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

В логике предикатов первого порядка вводятся и две новые операции. Называются они квантором общности и квантором существования. Эти операции рассмотрим вначале на примерах. Пусть дано выражение «существует х такой, что x+y=10». На множестве натуральных чисел это предложение определяет одноместный предикат P(y), так Р(2) и Р(9) – истинные высказывания, Р(11) – ложное. Если обозначить предикат «x+y=10» через S(x, y) (а это предикат двухместный), то P(y) можно записать так: «существует х такой, что S(x, y)». В этом случае говорят, что предикат P(y) получен из предиката S(x, y) навешиванием квантора существования на x и пишут P(y)=($x)S(x, y). Рассмотрим другой пример. Выражение «для всех х справедливо, что y³ -х2» определяет на множестве целых чисел одноместный предикат Q(y). Если предикат «y³ -х2» обозначить через T(x, y), то Q(y) можно записать так: «для всех x справедливо T(x, y)». В таком случае говорят, что предикат Q(y) получен из предиката T(x, y) навешиванием квантора общности на х и пишут Q(y)=(" x)T(x, y).

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

Определение. Пусть P(x1, …, xn) – предикат, заданный на множестве M, y – переменная. Тогда выражение «для всякого y выполняется P(x1, …, xn)» – предикат, полученный из P навешиванием квантора общности на переменную y, а выражение «существует y такой, что выполняется P(x1, …, xn)» – предикат, полученный из P навешиванием квантора существования на переменную y.

Обозначения операций были введены выше.

Заметим, что в определении не требуется, чтобы y была одна из переменных x1, …, xn, хотя в содержательных примерах, которые будут ниже, квантор навешивается на одну из переменных x1, …, xn. Указанное требование не накладывается, чтобы избежать усложнения определения формулы логики предикатов. Если y – одна из переменных x1, …, xn, то после навешивания квантора на y новый предикат является (n-1)-местным, если yÏ { x1, …, xn}, то местность нового предиката равна n.

Если предикат W(x1, …, xn) получен из предикатов U(x1, …, xn) и V(x1, …, xn) с помощью связок, то истинность высказывания W(a1, …, an) определяется таблицами истинности этих связок. Пусть 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) истинно.


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-06-04; Просмотров: 683; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.026 с.)
Главная | Случайная страница | Обратная связь