Исчисление предикатов

Теоретические сведения

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

Одноместным предикатом Р(х) называется всякая функция одной переменной, аргумент которой х определен на некотором множестве М, а значение функции определены на множестве {0, 1} [1].

Множество М, на котором задан предикат, называется областью определения предиката.

Таким образом, мы видим, что понятие предиката более общее, чем логическая функция. И для предиката, и для логической функции область значения определяется как «истина» либо «ложь». Но область определения у предиката может быть любой, а у логической функции — только {0, 1}.

Множество 1р, на котором предикат принимает только истинные значения, называется областью истинности предиката Р(х).

Предикат Р(х) называется тождественно истинным (тождественно ложным) на множестве М, если Ip = М (/ = 0).

N-местным предикатом Q(xx, х2,..., хп) называется всякая функция п переменных, определенная на множестве М = М{ х М2 х х ... х Мп и принимающая значение на множестве {0, 1}.

Предикат Р(х) является следствием Q(x) (Q(x) => Р(х)), если

I рIq'

Предикаты Р(х) и Q(x) равносильны (Q(x) = Р(х)), если / = /0, т.е. они являются следствием друг друга.

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

Логические операции над предикатами. Так как предикаты принимают значения 0 и 1, к ним можно применять все операции алгебры высказываний. Пусть на некотором множестве Мзаданы два предиката Р(х) и Q(x).

Конъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Q(x) & Р(х), который равен единице при тех и только при тех значениях х є М, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.

Обратите внимание, что областью истинности предиката Q(x) & Р(х) является n Iq.

Например, предикат Р(х) задает признак делимости на 2 для натуральных чисел на отрезке [0, 20], а предикат Q(x) — признак делимости на 5 на отрезке [9, 81]. Новый предикат Q(x) & Р(х) задает признак делимости на 10 на отрезке [9, 20].

Конъюнкция предиката Р(х) с тождественно ложным предикатом даст тождественно ложный предикат, а конъюнкция с тождественно истинным предикатом даст сам Р(х).

Дизъюнкцией двух предикатов Р(х) и Q(x) называется новый предикат Q(x) V Р(х), который равен нулю при тех и только при тех значениях х є М, при которых каждый из предикатов принимает значение «ложь», и принимает значение «истина» во всех остальных случаях.

Обратите внимание, что областью истинности предиката Q(x) V Р(х) является IpKj Iq.

Например, предикат Р(х) задает признак делимости на 2 для натуральных чисел на отрезке [0, 20], а предикат Q(x) — признак делимости на 5 на отрезке [9, 81]. Новый предикатах) v Р(х) задает признак делимости на 2 на отрезке [0, 8], делимости на 10 на отрезке [9, 20], делимости на 5 на отрезке [21,81].

Дизъюнкция предиката Р(х) с тождественно ложным предикатом даст сам Р(х), а дизъюнкция с тождественно истинным предикатом даст тождественно истинный предикат.

Отрицанием предиката Р(х) называется новый предикат Р(х), который равен нулю при всех значениях х є М, при которых Р(х) равен значению «истина», и равен единице при всех значениях х є М, при которых Р(х) равен значению «ложь».

Очевидно, что областью истинности предиката Р(х) является

1- = м1Рр.

Отрицание от тождественно ложного предиката даст тождественно истинный. А в результате отрицания тождественно истинного предиката получается тождественно ложный.

Импликацией предикатов Р(х) и Q(x) называется новый предикат Q(x) —> Р(х), который равен нулю при тех и только при тех значениях х е М, при которых Q(x) принимает значение «истина», а Р(х) — значение «ложь», и принимает значение «истина» во всех остальных случаях.

Обратите внимание, что областью истинности предиката Q(x) —> Р(х) является Ip^q = /^ u Iр - Iq и IР.

Рассмотрим применение логических операций. Обозначим через х переменную «кот», через Р(х) предикат «х рыжий», а через Q(x) предикат «х толстый». Тогда следующие предикаты соответствуют логическим операциям над Р{х) и Q(x) (табл. 4.3).

Таблица 4.3

Применение логических операций

Предикат

Логическая операция

«Рыжий толстый кот»

Р(х) & Q(x)

«Тощий рыжий кот»

Р(х) & Q(x)

«Неверно, что из того, что кот рыжий, следует, что он толстый»

Р(х)Q(x)

Рассмотрим несколько примеров.

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

Пусть задан предикат Р(х), определенный на множестве М.

Тогда под выражением МхР(х) понимаем высказывание, истинное тогда и только тогда, когда Р(х) истинен для каждого элемента х из М, и ложное в противном случае. Это высказывание не зависит от х, его словесное выражение выглядит так: «Для любого х Р(х) истинно». Символ V называется квантором всеобщности.

Переменная х в предикате Р(х) свободна, в высказывании Vx/>(x) переменная х связана квантором всеобщности.

Под выражением ЗхР(х) понимаем высказывание, истинное тогда и только тогда, когда существует элемент х из М, для которого Р(х) истинен, и ложное в противном случае. Это высказывание не зависит отх, его словесное выражение выглядит так: «Существует х, для которого Р(х) истинно». Символ 3 называется квантором существования.

Переменная х в предикате Р(х) свободна, в высказывании ЗхР(х) переменная х связана квантором существования.

Рассмотрим применение кванторных операций. Обозначим через х переменную «кот», а через Р(х) предикат «у х есть усы». Тогда следующие высказывания соответствуют кванторным операциям над Р(х) (табл. 4.4).

Таблица 4.4

Применение кванторных операций

Высказывание

Кванторная операция

«У всех котов есть усы»

/хР(х)

«Найдется кот без усов»

ЗхР(х)

«Не бывает котов с усами»

/хР(х)

Кванторные операции применяются и к многоместным предикатам. Например, применение кванторной операции ЗхР(х, у) к двухместному предикату превращает его в одноместный, зависящий только от переменной у.

Рассмотрим предикат Р(х), определенный на множестве М={аь а2,..., ап}. Если Р(х) тождественно истинен, то истинными будут высказывания Р(ах)...Р(ап). При этом истинными будут выказывание УхР(х) и конъюнкция Р(а{) & Р(а2) & ...& Р(ап). Если найдется хотя бы один элемент а: из М, на котором Р(а) = 0, то ложными будут высказывания /хР(х) и конъюнкция Р(ах) & Р(а2) & ... & Р(ап). Следовательно, существует равносильность

/хР(х) = Р(ах) & Р(а2) & ... & Р(ап).

Рассмотрим предикатах), определенный на множестве М- {ах, а2,..., ап}. Если Q(x) тождественно ложен, то ложными будут высказывания Q{?)...Q{an). При этом ложными будут выказывание 3х0(х) и дизъюнкция Q{ay) v Q(a2) v ... v Q{an). Если найдется хотя бы один элемент ?jиз М, на котором Q(?j) = 1, то истинными будут высказывания 3х0(х) и дизъюнкция Q{? ) v ОШ v ... v Q(an). Следовательно, существует равносильность

3х0(х) = Q(ax) v Q(a2) v ... v Q{an).

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

Рассмотрим формальное определение исчисления предикатов.

Исчисление предикатов — это формальная теория, в которой определены следующие компоненты [2].

алфавит А:

основные связки

&, V

вспомогательные связки

(,)

служебные символы

^3

кванторы

а, 6,, Ь

предметные константы

х,у,

предметные переменные

р, 0, Л,...

предикаты

и 8, Ь,...

функторы

формулы Р (определены в нотации Бэкуса—Наура):

<формула> ::= <атом> | <формула> | <формула> —> <формула> | /<переменная> <формула> | 3<пере-менная> <формула>

<атом> ::= <предикат> (<список термов>)

<список термов> ::= <терм> | <терм>, <списоктер-мов>

<терм> ::= <константа> | <переменная> | <функтор> (<список термов>)

аксиомы В:

А, : (АА))

Л7 : ((А -4 -» С)) -»((А В)^(А^ С)))

А, : ((В —>А)—> ((В —> А) —> В))

Р, : VxA(x) -4 А(0

Р2 : АУ) —> Зху4(х)

правила вывода /?:

А, А —> В ...

правило заключения

^ 1 ТА 1/и 1Л о укупъпо

А —> /хА

правило обобщения

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

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

Рассмотрим основные равносильности исчисления предикатов. Их можно разбить на четыре группы [1, 3].

1. Равносильности для двойственности:

ЗхР(х) = /хР(х); УхР(х) = ЗхР(х);

ЗхР(х) = /хР(х); /хР(х) = 3 хР(х).

2. Равносильности для конъюнкции и квантора всеобщности:

/х(Р(х) & 0(х)) = /хР(х) & /х()(х)‘, /х/уР(х, у) = /у/хР(х, у).

  • 3. Равносильности для дизъюнкции и квантора существования:
  • 3х(Р(х) V 0(х)) = ЗхР(х) V 3х0(х); ЗхЗуР(х, у) = ЗуЗхР(х, у).
  • 4. Вынесение константы: Vx(C & Q(x)) = С & Vx0(x);

Vx(C v Q(x)) = C v VxQ(x);

3x(C & Q(x)) = C & 3xQ(x); 3x(C v Q(x)) = C v 3x0(x);

Vx(C -» (?(*)) = C -> Vjc0(x); 3x(C -» 0(x)) = C -» 3xQ(x). Рассмотрим интерпретацию предикатов.

Возьмем множество А/= {0, 1} и заданный на нем предикат Р(х,у) (табл. 4.5).

Таблица 4.5

Таблица истинности предиката P(jc, у)

X

У

Р(х, У)

0

0

0

0

1

1

і

0

1

і

1

1

Нужно определить, на каких областях истинны высказывания Зх/уР(х, у) и /хЗуР(х, у).

При х = 1 высказывание 3х/уР(х, у) истинно при любых значениях у.

При у = 1 высказывание /хЗуР(х, у) истинно при любых значениях у.

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

Формула А выполнима в области М, если существуют значения переменных, входящих в эту формулу и отнесенных к области М, при которых формула принимает истинные значения.

Формула А выполнима, если существует область, на которой она выполнима.

Формула Л тождественно истинна в области М, если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

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

Формула Л общезначима, если она тождественно истинна во всякой области.

Из этих определений следуют следующие утверждения.

  • 1. Если формула А общезначима, то она и выполнима на любой области.
  • 2. Если формула А тождественно истинна в области М, то она и выполнима в этой области.
  • 3. Если формула А невыполнима, то она тождественно ложна в любой области.

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

Ответ на этот вопрос для бесконечных областей дает теорема Черча.

Теорема 4.6. Теорема Черча

Проблема разрешимости исчисления предикатов в общем виде неразрешима.

Известно, что проблема разрешимости для конечных областей разрешима [2].

Задачи

Задача 4.12. Заданы предикаты Р(х) и Q(x) на множестве натуральных чисел N: Р(х): «число Xделится на 5»; Q(x): «число Учетное».

Найти область истинности предикатов Q(x) & Р(х), Q(x) v Р(Х), Q(x) => Р(х).

Решение.

Так как 1р = {5, 10, 15, 20,..., 5п,...} и Iq = {2, 4, 6, 8, 10,..., 2я,...}, то Iqslp = = 20,..., 20п,...},

IQvP = IQ u Ip = {2, 4, 5, 6, 8, 10,..., 2n, 5n,...},

Iq^p = Iq u /P- {5, 10, 15,..., 5n,...} и {1, 3, 5,..., 2n - 1,...} =

= {1, 3, 5, 7, 9, 10,..., In - 1, 5n, ...}.

Задача 4.13. Задан предикат P(x):

> 0 на множестве

x + 2x + 1

х^ + Зх + 2

рациональных чисел Я. Найти область истинности предиката. Решение.

Найдем область, на которой данный предикат может быть определен. Поскольку знаменатель дроби не может быть равен нулю, то х Ф -1,х Ф -2. Для того чтобы наша дробь была положительной, необходимо, чтобы знаки числителя и знаменателя совпадали.

Отсюда Iр = (-оо, -2) и (-1, +°°).

Задача 4.14. Показать равносильность

Ух(Р(х) & Q(x)) = VxP(x) & VxQ(x).

Решение.

Если предикаты Р(х) и Q(x) тождественно истинны, то тождественно истинен предикат Р(х) & Q(x), а поэтому будут истинны высказывания:

/хР(х)', /xQ(x); /х(Р(х) & Q(x)),

т.е. обе части равносильности принимают значение «истина».

В случае если один из предикатов, например Р(х) (а как следствие — Р(х) & Q(x)), будет не тождественно истинен, то ложными будут:

/хР(х); VxQ(x); /х(Р(х) & Q(x)).

Таким образом, для любых предикатов Р(х) и Q(x) левая часть формулы равносильна правой части.

Задача 4.15. Определить, являются ли равносильными

/х(Р(х) v 0(х)) = /хР(х) v /xQ(x).

Решение.

Если предикаты Р(х) и Q(x) тождественно истинны, то тождественно истинен предикат Р(х) v Q(x), а поэтому будут истинны высказывания:

VxP(x)-, VxQ(x); Ух(Р(х) v Q(x)),

т.е. обе части равносильности принимают значение «истина».

В случае если один из предикатов, например Р(х), будет не тождественно истинен, то можно рассмотреть случай Р(х) = Q(x). В этом случае ложными будут:

/хР(х); /xQ(x); /хР(х) v VxQ(x)).

Но Vx(Q(x) v Q(x)) = Vxl будет тождественно истинен, следовательно, указанные предикаты не являются равносильными.

Задача 4.16. Показать, что формула Vx(C & Q(x)) = С & VxQ(x) общезначима.

Решение.

Обозначим формулу как R = (Vx(C & (?(х)) = С & VxQ(x)).

Обратите внимание: эта формула зависит от логической константы С. Рассмотрим значение С.

При С = 0 левая часть формулы превращается в тождественно ложное высказывание V(0 & Q(x)) = 0, правая часть 0 & VxQ(x) = О также равна 0. Это означает, что Я тождественно истинная в области С= 0.

При С = 1 левая часть формулы /(1 & 0(х)) = xQix) приобретает тот же вид, что правая 1 & xQix) = xQix). Значит, Я = (/х()(х) = = /х()(х)) = 1 тождественно истинная в области С= 1.

Таким образом, Я тождественно истинная в любой области, следовательно, она общезначима.

Задача 4.17. Показать, что формула

Л{х) -> В Зх/4(.х) —> В

не общезна-

чима.

Решение.

Обозначим формулу как Я = (Л(х) -» В) —> (Зх4(х) -> В). Применим следующие аксиомы и равносильности.

Аксиому для представления импликации выразим через дизъюнкцию и отрицание.

Я = (А(х) V В) -» (Эл4(х) V В).

Равносильность для двойственности

Я = (А(х) V В)(УхА(х) V В).

Равносильность для вынесения константы

Я = (Мх) V В) -» Ух(Дх) V В).

Нельзя утверждать, что формула Я тождественно истинна

Я = Z(x) —» xZix), где Z(x) = А(х) V В, так как если Z(x) не тождественно истинное высказывание и не тождественно ложное высказывание, то есть области, где Я = 0. Например, при В = 0 зададим /1(0) = 1, А( 1) = 0. Тогда Я(В, х) = Я(0, 1) = (1 -» 0) = 0.

Так как Я не тождественно истинна во всякой области, значит, Я не общезначима.

Задача 4.18. Указать на декартовой плоскости область истинности предиката Р: х2 + у2 < 5.

Задача 4.19. Указать на декартовой плоскости область истинности предиката Р: х2 + у2 > 5.

Задача 4.20. Указать на декартовой плоскости область истинности предиката Р: х2 + у2 < 5.

Задача 4.21. Указать на декартовой плоскости область истинности предиката Р: х2 + у2 > 5.

Задача 4.22. Дана формула исчисления предикатов

Л = (Ух((х-2)г+(у + 2)2 =0».

Указать область, на которой она выполнима.

Задача 4.23. Дана формула исчисления предикатов

Я = (3x3у((х - 2)2 + (у + 2)2 = 0)).

Указать область, на которой она выполнима.

Задача 4.24. Дана формула исчисления предикатов

В = (Ух/у((х - 2)2 +(у + 2)2 = 0)).

Указать область, на которой она выполнима.

Задача 4.25. Дана формула исчисления предикатов

Я = (Зх((х - 2)2 + (у + 2)2 = 0)).

Указать область, на которой она выполнима.

Задача 4.26. Дана формула исчисления предикатов

Я = (Ух((х + 2)2 + + 2)2 = 0)).

Указать область, на которой она выполнима.

Задача 4.27. Дана формула исчисления предикатов

Я = (ЗхЗу((х + 2)2 +(у + 2)2 = 0)).

Указать область, на которой она выполнима.

Задача 4.28. Дана формула исчисления предикатов

Л = (VхЧу((х + 2)2 + (у + 2)2 = 0)).

Указать область, на которой она выполнима.

Задача 4.29. Дана формула исчисления предикатов

/г = (Зх((х + 2)2 + (у + 2)2 = 0)).

Указать область, на которой она выполнима.

Задача 4.30. Даны формулы. Какие из них являются аксиомами исчисления предикатов?

4 ; -> -> А));

А2 : ((А С)) -> ((А -> В) -> -» С)));

Я4 : УхР(х) = ЗхР(х);

Я5 : УхР(х) = УхР(х);

Я6 : УхР(х) = УхР(х)-Р{ : /хА(х) -> А(0;

Р2 : ДО —> ЗхДл:).

Задача 4.31. Даны следующие формулы. Определить, какие из них являются равносильными.

Я : ЗхР(х) = /хР(х);

Я2 : ЗхР(х) = /хР(х)',

ЯЗ : УхР(х) = ЗхР(х)',

Я4 : УхР(х) = ЗхР(х)-

Р5 : УхР(х) = УхР(х)-Я6 : УхР(х) = УхР(х)-

Я7: ЗхР(х) = ЗхР(х);

/?8 : УхР(х) = УхР(х).

Задача 4.32. Даны следующие формулы. Определить, какие из них являются равносильными.

Я : Ух(Р(х) & 0(х)) = УхР(х) & УхО(х);

Я2 : /хР(х) = V* Дх);

ЯЗ : Зх(Р(х) V 0(х)) = ЗхР(х) V Зх(2(х);

Я4 : УхР(х) = /х~Р(хУ,

Я5 : Ух/уР(х, у) = /у/хР(х, у);

Я6 : /х(Р(х) V (2(х)) = /хР(х) V /х()(х)‘,

Я7 : ЗхЗуР(х, у) = ЗуЗхР(х, у);

/?8 : Зх(Р(х) & 0(х)) = ЗхР(х) & 3х0(х).

Задача 4.33. Даны следующие формулы. Определить, какие из них являются равносильными.

Я : УхР(х) = /хР(х)-Я2 : ЗхР(х) = /хР(х);

ЯЗ : 3хЗуР(х, у) = Уу/хР(х, у); Я4 : ЗхЗуР(х, у) = ЗуЗхР(х, у);

Я5 : ЗхР(х) = ЗхР(х);

Яв : /хР(х) = ЗхР(х);

Я7 : Зх(/>(х) & 0(х)) = ЗхР(х) & 3х0(х);

Л8 : Ух(Р(х) & 0(х)) = УхР(х) & Vx{2(x).

Задача 4.34. Даны следующие формулы. Определить, какие из них являются равносильными.

Я : Ух(С & 0(х)) = С & 3х0(х);

Я2 : /х(С V 0(х)) = С V 3х0(х);

ДЗ : Ух(С V 0(х)) = Cv VxQ(x);

Я4 : 3 х(С & 0(х)) = С& 3х0(х);

Я5 : УхР(х) = УхР(х);

Яв : УхР(х) = 3хЩх).

Задача 4.35. Даны следующие формулы. Определить, какие из них являются равносильными.

Я : Ух(С & 0(х)) = С & 3х0(х);

Я2 : /х(С V ()(х)) = С V Зх()(х);

/?3 : Ух(С -> 0(х)) = С -> Ух0(х);

У?4 : Зх(С —> (9(х)) = С —> Зх()(х);

Д5 : УхР(х) = Ух~Р(х);

Яв : Зх(С & 0(х)) = С& VxQ(x);

Я7 : Ух(С & 0(х)) = С & Ух0(х);

Л8 : Ух/>(х) = УхР(х).

Задача 4.36. Даны следующие формулы. Определить, какие из них являются равносильными.

Я : /х(С & 0(х)) = С & Зх{?(х);

У?2 : /х(С V 0(х)) = С V 3х0(х);

/?3 : Ух(С -> 0(х)) = С —> Ух0(х);

/?4 : Зх(С —> 0(х)) = С —> Зх(2(х);

Я5 : УхР(х) = /хР(х);

Я6 : 3х(С & 0(х)) = С & Ух0(х).

Задача 4.37. Даны следующие формулы. Определить, какие из них являются равносильными.

Я : У*(С & 0(х)) = С& БхО(х);

Я2 : ЗхР(х) = /хР(х);

ЯЗ : Ух(С -> 0(х)) = С ->

/?4 : Зх(С —> 0(х)) = С —> 3х0(х);

Д5 : УхР(х) = Ух~Р(х);

Я6 : Зх(С & 0(х)) = С& VxQ(x);

Я7 : Ух(С & 0(х)) = С& УхО(х).

Задача 4.38. Даны следующие формулы. Определить, какие из них являются равносильными.

Я : Ух(С & (?(*)) = С & 3х0(х);

Я2 : /х(С V 0(х)) = С V 3х0(х);

ДЗ : Ух(С -» 0(х)) = С -> Ух<2(х);

Д4 : Зх(С —> 0(х)) = С —> ЗхО(х);

Я5 : УхР(х) = УхР(х);

Я6 : /х(Р(х) V 0(х)) = /хР(х) V /х()(х)‘,

Я7 : Ух(С & 0(х)) = С & Ух0(х);

Д8 : У*Д(х) = УхД(х).

 
< Пред   СОДЕРЖАНИЕ     След >