Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1 2 = , 1 2 = .
Доказательство теоремы 9.2 соответствует доказательству полноты системы Россера-Тьюкетта. Полная система Россера-Тьюкетта является аналогом двузначных представлений в виде СДНФ и СКНФ.
10. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ
10.1. Символы узкого исчисления двузначных предикатов
В [12] мы имели возможность убедиться в том, что основной задачей исчисления высказываний является изучение истинности или ложности сложных высказываний в зависимости от истинности или ложности входящих в них простых высказываний без учета их содержания.
Несмотря на большую важность правил и законов исчисления высказываний, все же этих средств оказывается недостаточно для изучения и описания простых заключений в математике, не говоря уже о более сложных логических выводах в других науках и практических задачах.
Например, из истинных высказываний “3 меньше 5” и “5 меньше 7” выводится истинное заключение “3 меньше 7”, из высказываний “Анна - дочь Павла” и “Петр - сын Анны” - “Петр - внук Павла”. Если несколько изменить содержание этих высказываний, то можно прийти к неверному заключению. Так, из истинных высказываний “3 меньше 5” и “5 не равно 7” нельзя делать заключение (истинное), что “3 меньше 7”, или из истинности высказываний “Анна - дочь Павла” и “Петр - родственник Анны” - что “Петр - внук Павла”.
Эти примеры убеждают нас в том, что истинность или ложность заключений зависит не только от истинности предпосылок, но и от их содержания, что исключает применение правил исчисления высказываний.
Возможности математической логики в этом смысле оказываются значительно расширенными, если помимо рассмотренных однородных двузначных факторов ввести пропозициональные функторы, логические значения которых по-прежнему принадлежат множеству {0,1}, а аргументы функторов являются элементами множеств произвольной природы. Такие функторы называют двузначными предикатами, либо предикатами.
Исчисление предикатов строится на основе исчисления высказываний, и, кроме того, простые высказывания, входящие в заключения, расчленяются.
В исчислении предикатов простые высказывания означают, что некоторые объекты (или объект) обладают определенными свойствами либо находятся между собой в некоторых отношениях. Отсюда появились термины: “предикат-свойство” и “предикат-отношение” (более общий термин). Если имеется некоторое множество объектов , то под предикатом-свойством, определенным на этом множестве, понимается функция, определенная на , которая принимает логические значения “1” (“истина”) или “0” (“ложь”) в зависимости от того, обладают ее аргументы данным свойством или нет.
Предикаты-свойства называются унарными (одноместными) предикатами и относятся к частному случаю предикатов-отношений.
В зависимости от того, между каким числом объектов данным предикатом устанавливается отношение, различают двухместные (бинарные), трехместные (тернарные) и n-местные предикаты. В этом плане удобно считать 0-местными предикатами просто высказывания.
Понятие K-местного предиката эквивалентно понятию K-аргументного предиката, где K = 1, 2, 3, ..., n.
Например, одноаргументными предикатами являются слово “светит” в высказывании “солнце светит” и выражение “четное число” в высказывании
“10 - четное число”, двухаргументными - символ > в высказывании “5 > 3” и слово “кратно” в высказывании “9 кратно 3”, трехаргументными - выражение “расположен между и “ в высказывании “на числовой оси число 3 расположено между числами и “ и выражение “общий делитель d и c” в высказывании
“4 - общий делитель 12 и 20”.
В исчислении предикатов фигурируют следующие символы:
1. Все символы исчисления высказываний.
2. Именные (индивидуальные) переменные
x, y, z, x1, y1, z1, ... . (10.1)
При использовании формул исчисления предикатов в конкретных рассуждениях вместо индивидуальных переменных (10.1) подставляются собственные имена различных объектов.
3. Переменные, представляющие собой пропозициональные функторы от именных аргументов, т.е. предикаты. Иными словами, под предикатами здесь понимаются выражения, которые вместе с некоторой совокупностью имен образуют пропозициональные выражения.
Символами
A, B, C, A1, B1, C1, ... . (10.2)
обозначаются переменные, представляющие собой одноаргументные предикаты, а символами P, Q, R, S, P1, Q1, R1, S1, ... - предикаты от двух и более аргументов.
4. Постоянные и , , называемые кванторами. Символ называется квантором общности и читается “для всех”, символ - квантором существования и читается “для некоторых” или “существует такое ...”.
Та часть исчисления предикатов, которая оперирует перечисленными выше символами вместе с символами исчисления высказываний, называется узким исчислением предикатов первого порядка (УИП).
10.2. Выражения узкого исчисления предикатов (УИП)
Сформулируем индуктивное определение пропозиционального выражения узкого исчисления предикатов (УИП):
1а) пропозициональная переменная есть пропозициональное выражение УИП;
1б) выражения вида A(x), B1(y), xRy, zSx (вместо A, B1 и R(x,y)S(z1,x1)), P(x,y,z), P(x1, x2, ..., xn) и т.п. называются элементарными пропозициональными выражениями УИП;
2а) если и - пропозициональные выражения УИП, то и ~(), ()(), ()(), ()(), ()() - пропозициональные выражения УИП;
2б) если - пропозициональное выражение УИП, а - именная переменная под квантором, то () и () - пропозициональные выражения УИП;
3) множеству пропозициональных переменных УИП принадлежат только те выражения, которые являются пропозициональными переменными или элементарными выражениями, полученными путем последовательного применения правил пунктов “2а” и “2б”.
Из пунктов “1а” и “2а” следует, что любое выражение исчисления высказываний есть выражение исчисления предикатов.
В выражениях, построенных согласно пункту “2б”, скобки опускаются, если - элементарное выражение либо оно начинается квантором.
Например, вместо (A(x)) пишем A(x), вместо (x Ry) - x Ry.
Выражение , непосредственно следующее за квантором, называется областью действия квантора. Выражение xRx содержит квантор с областью действия x Rx и читается “для всех x имеет место отношение R между x и x”. Выражение x Sy имеет квантор общности по x с областью действия x Sy и квантор существования по y с областью действия xSy и читается “для всех х существует такой y, что между x и y имеет место отношение S”. Выражение содержит квантор общности с областью действия , квантор общности с областью действия xRy(xRzzRy) и квантор существования с областью действия xRzzRy.
Все выражение читается так: “для всех x справедливо, что для всех y из имеющего место соотношения R между x и y следует существование такого z, что между x,z и z,y имеет место соотношение R0”.
Если некоторая переменная в выражении находится в области действия данного квантора и совпадает с переменной под квантором, то такую переменную называют связанной в выражении .
Известно, что данный квантор связывает ту переменную, которая находится под квантором. В противном случае переменную называют свободной в выражении (т.е. при невыполнении условий связанности). Например, в выражении zRy переменная z - свободна, а y - связана, в формуле A(x)A(x), переменная x за импликацией свободна, а переменная x до импликации связана.
В исчислении предикатов имеются выражения, содержащие так называемые пропозициональные функции.
Пропозициональной функцией называется выражение, содержащее свободные переменные и преобразующееся в высказывание при подстановке постоянных вместо этих переменных.
Различают пропозициональные функции от одной свободной переменной (например, “x - четное число”), от двух свободных переменных (например, “x > y”) и т.п. Подставляя в эти пропозициональные функции вместо переменных имена чисел, получим высказывания: “12 - четное число”, “7 > 2”. Кроме того, формулы исчисления предикатов интерпретируют так, что, например, выражение A(x) представляет собой пропозициональную функцию со свободной переменной x. Иными словами, вместо A(x) можно подставлять пропозициональные функции, содержащие x в качестве свободной переменной. Например, из выражения
xRy подстановкой вместо xRy пропозициональной функции x = y+1 можно получить предложение (высказывание)
x = y+1.
Кроме обычных рассмотренных кванторов в исчислении предикатов используются так называемые ограниченные кванторы. Например, выражению
(x > 0 = x) соответствует ограниченный квантор
= x, (10.3)
который читается так: “для каждого x больше 0 имеет место = x“. Выражению x(x 0 a x = a) соответствует ограниченный квантор
a x = a, (10.4)
который читается так: “для некоторых x, отличных от 0, имеет место ax = a“.
В общем виде имеем эквивалентные соотношения
, (10.5)
, (10.6)
где (), () - пропозициональные функции, в которых - свободная переменная.
11. ИСПОЛЬЗОВАНИЕ ВЫРАЖЕНИЙ ИСЧИСЛЕНИЙ ПРЕДИКАТОВ ДЛЯ ЗАПИСИ МАТЕМАТИЧЕСКИХ ВЫСКАЗЫВАНИЙ
Выражения исчисления предикатов, особенно кванторы и ограниченные кванторы, часто используются для записи математических определений и теорем.
Проиллюстрируем сказанное примерами.
Пусть переменные x, y, z пробегают множество действительных, а переменные k, m, n - множество натуральных чисел. Тогда имеют место следующие примеры выражений:
Пример 11.1
x > y = y + z,
x < y < z < y,
m : n = n k.
Пример 11.2
Предел последовательности можно выразить следующим образом:
.
Пример 11.3
Определение непрерывной функции в данной точке x0:y = f(x) - непрерывная функция в точке .