тема РоссераТьюкетта является аналогом двузначных представлений в виде СДНФ и СКНФ.html
Работа добавлена на сайт samzan.net:
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) - непрерывная функция в точке .
2. Центр развития ребенка детский сад 35 города Перми Конспект мастеркласса для ро
3. Языки и символы культуры
4. Оборудование предприятий общественного питания
5. чтото к чему вы стремились в итоге окажется в ваших руках.
6. Никакое богатство не сможет перекупить влияние обнародованной мысли Кто мы Национальноосвободите
7. Тема 6 Бухгалтерський облік і механізми його реалізації в програмі 1С-Підприємство
8. Какие изменения произошли в учете расчетных операций безналичных расчетов в банке в 2012г
9. Тема 2- Философия Древнего Востока
10. ТЕМА ЗАНЯТИЕ 41
11. икОнопись 2 облегчИть 3
12. 1диагностика выявления причин вызвавших отклонение 2 лечение по результатам обсл
13. военного коммунизма привела экономику страны к полному развалу
14. Детский сад 137 компенсирующего вида для детей с нарушениями центральной нервной системы и опорнодвигател
15. DK 2 DMC 444 LemonDK
16. Такер Италия- вино еда любовь Среди холмов итальянской Умбрии в живописной долине утопающей в оливковы
17. мы ведь не дети и отлично понимаем что сила современной философии не в силлогизмах а в авиационной подд
18. Екологічна психопедагогіка.html
19. Аналитическая журналистика в России
20. реферату- Форми інвестуванняРозділ- Економіка підприємства Форми інвестування Фінансові інвестиції Ос