Классическая логика и логика предикатов

Математическая логика и теория алгоритмов Глава 1. Классическая логика и логика предикатов Параграф 1. Введение Logos (греч.) - слово, понятие, рассуждение, разум. Логика - Совокупность правил, которым подчиняется процесс мышления. Логика изучает абстрактное мышление как средство познания мира, исследует формы и законы, в которых происходит отражение мира в процессе мышления. Этапы развития логики Этап 1. (формальная логика, 3-4 века до н.э.) Связан с работами Аристотеля "Органон" и "Первая аналитика", в которых описывается систематическое изложение логики и учение о силлогизме и возникла формальной логики. Силлогизм (греч.) - новое суждение, полученное из двух предыдущих. Находило свое применение в судебной и политической практике. Этап 2. (появление формализованных языков, 16-19 века) Связан с работами Ф. Бэкона "Новый органон", в которых описывается развитие индуктивной логики, т.е. причинно-следственных связей, путем эмпирических исследований. Дальнейшее развитие связано с В. Лейбницом, который заложил основы символической логики, т.е. заменил рассуждения знаками и правилами (алгебра высказываний). Развил символьную логику Д. Буль, а именно он создал алфавит, орфографию и грамматику. де Морган, Пирс, Рассел, Фреге, Гильберт и др. Этап 3. (нач. с 20 века ) Новым толчком к бурному развитию математической логики послужило появление вычислительной техники. Применение математической логики 1) проектирование цифровых схем (промышленность); 2) исследование семантики языков программирования; 3) спецификация, верификация и синтез программ; 4) спецификация и верификация параллельных процессов; 5) системы искусственного интеллекта. Параграф 2. Предикаты и логические операции над ними Центральная идея математической логики состоит в том, чтобы записывать математические утверждения в виде последовательностей символов и оперировать ими по формальным правилам. Не всякие высказывания и не любые логические рассуждения могут быть описаны на языке логики высказываний. Кроме того, необходимо иметь возможность утверждать, что любые или какие-то объекты обладают определенными свойствами или находятся в некоторых отношениях. Таким образом, расширив логику высказываний, построим логическую систему - логика предикатов. Логика предикатов – это расширение возможностей логики высказываний, позволяющее строить высказывания с учетом свойств изучаемых объектов или отношений между ними. Предикат (термин восходит к Аристотелю) - утверждение, содержащее одну или несколько неизвестных. Одноместным предикатом P(x) называется произвольная функция одной переменной x, значениями которой являются высказывания об объектах, представляющих значения аргумента. Предметная область (область определения) предиката – это множество M, на котором определен предикат. Предметные переменные – это элементы множества M, на котором определен предикат. Областью истинности предиката P(x), заданного на множестве M, называется совокупность всех x из M, при которых данный предикат обращается в истинное высказывание. M Область истинности I p = { x ∈ M|P(x) ≡ 1 } Ip Предикат P(x), определенный на множестве M, называется тождественно истинным, если I p = M. Предикат P(x), определенный на множестве M, называется тождественно ложным, если I p = ∅. Предикат P(x), определенный на множестве M, называется выполнимым, если существует по меньшей мере один элемент x i ∈ M, при котором P(x i ) = 1. n-местным предикатом называется произвольная функция переменных P(x 1 , x 2 , … , x n ), определенная на множестве M = M 1 × M 2 ×…× M n и принимающая (логические) значения из множества { 0, 1 }. Логические операции над предикатами: • Отрицанием предиката P(x) называется новый предикат ⏨⏨ P(x) (¬P(x)), который принимает значение «истина» при всех значениях x ∈ M, при которых предикат P(x) принимает значение «ложь», и принимает значение «ложь» при тех значениях x ∈ M, при которых предикат P(x) принимает значение «истина». Область истинности имеет вид I P⏨ = M \ I P . • Конъюнкцией двух предикатов – P(x) и Q(x) называется новый предикат P(x) ∧ Q(x), который принимает значение «истина» при тех и только тех значениях x ∈ M, при которых каждый из предикатов принимает значение «истина», а значение «ложь» – во всех остальных случаях. Область истинности имеет вид I P∧Q = I P ∩ I Q . • Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат P(x) ∨ Q(x), который принимает значение «ложь» при тех и только тех значениях x ∈ M, при которых каждый из предикатов принимает значение «ложь», и принимает значение «истина» во всех остальных случаях. Область истинности имеет вид I P∨Q = I P ∪ I Q . • Импликацией предикатов P(x) и Q(x) называется новый предикат ⏨⏨ P(x) → Q(x) ⇔ P (x) ∨ Q(x), который является ложным при тех и только тех значениях x ∈ M, при которых одновременно P(x) принимает значение «истина», а Q(x) принимает значение «ложь», и принимает значение «истина» во всех остальных случаях. Область истинности имеет вид I P → Q = I P⏨∪ I Q . • Эквиваленцией предикатов P(x) и Q(x) называется новый предикат P(x) ↔ Q(x), который принимает значение "истина" при тех же значениях x ∈ M, при которых истинные значения предикатов P(x) и Q(x) одинаковы. Область истинности имеет вид I P↔Q = (I P ∩ I Q ) ∪ (I ⏨ P ∩ I⏨ Q ). Параграф 3. Кванторы Специфика природы предикатов позволяет ввести такие операции над ними, которые не имеют аналогов среди операций над высказываниями. Квантор – это общее название для логических операций, ограничивающих область истинности какого-либо предиката. Были впервые введены (Г. Фреге в работе "Исчисление понятий" в 1879 г.), а сам термин квантор был введен Ч. Пирс. Символику для кванторов в виде перевернутых латинских букв ввел Дж. Пеано в конце 19 века. Виды кванторов: • ∀ – квантор всеобщности Операцией связывания квантором всеобщности называется правило, по которому каждому одноместному предикату P(x), определенному на множестве M, сопоставляется высказывание, обозначаемое ∀xP(x), которое истинно в том и только в том случае, когда предикат P(x) тождественно истинен, и ложно в противном случае. • ∃ – квантор существования Операцией связывания квантором существования называется правило, по которому каждому одноместному предикату P(x), определенному на множестве M, ставится в соответствие высказывание, обозначаемое ∃xP(x) , которое ложно в том и только в том случае, когда P(x) тождественно ложен, и истинно в противном случае. Следует отметить, что если некоторый предикат P(x) определен на конечном множестве P(a 1 , a 2 , … , a n ), то справедливы следующие тождества: ∀xP(x) ≡ P(a 1 ) ∧ P(a 2 ) ∧…∧ P(a n ) ∃xP(x) ≡ P(a 1 ) ∨ P(a 2 ) ∨…∨ P(a n ) Математическая логика и теория алгоритмов Глава 2. Теория алгоритмов Параграф 1. Предварительные сведения Алгоритм - точная конечная система предписаний, определяющих содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения искомого результата. Под алгоритмом понимается некоторый вычислительный процесс чисто механического характера, с помощью которого искомые величины целого класса задач вычисляются последовательно из данных искомых величин по определенным правилам. Каждый алгоритм имеет дело с классом однотипных задач, как говорят, имеет дело с массовой проблемой. Другими словами, алгоритмом называется общий единообразный, точно определенный способ решения любой задачи из данной массовой проблемы. При этом алгоритм должен удовлетворять следующим требованиям: 1. Дискретность. Выполнение алгоритма разбивается на конечную последовательность действий. Только выполнив одно действие, можно приступить к выполнению другого действия. Выполнить каждое отдельное действие предписывает указание в алгоритме, называемое командой. 2. Детерминированность. Способ решения однозначно определен. Если алгоритм многократно применяется к одному и тому же набору данных, то каждый раз получаются одни и те же промежуточные и выходные данные. 3. Понятность. Исполнитель должен однозначно воспринимать смысл предстоящих действий. 4. Результативность. При точном исполнении команд алгоритма процесс должен закончиться за конечное число действий и должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть вывод о том, что задача не имеет решения. 5. Массовость. Алгоритм применяется для решения любой задачи определенного класса задач, который называется областью применения алгоритма. Понятие алгоритма, определяемого требованиями 1.-5., не строгое. Такое нестрогое понятие алгоритма называется интуитивным понятием алгоритма. Оно вполне устраивало математику до начала XX века. Но затем выдвинулись такие алгоритмические проблемы, существование положительного решения которых было сомнительным. А для отрицательного решения уже требуется строго определить, что такое алгоритм. Официально рождением теории алгоритмов считается 1900-й год. В этом году на II Международном конгрессе математиков в Париже немецкий математик Давид Гильберт сформулировал 23 проблемы, которые определили развитие математики во все последующие годы. Среди них была 10-я проблема: "Построить алгоритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение или нет". Все попытки найти такой алгоритм привели к мысли, а существует ли вообще данный алгоритм. Чтобы ответить на этот вопрос, надо было дать точное (не интуитивное) определение алгоритма. В дальнейшем появилось множество других алгоритмических проблем, положительное решение которых вызывало сомнение. Так, уже отмечалось, что любое утверждение в математике можно записать в виде формулы логики предикатов. И естественно возникает задача: "Построить алгоритм, позволяющий для любой такой формулы определять, является ли эта формула тождественно истинной или нет". Существование такого алгоритма позволяло бы доказывать всевозможные теоремы в математике единым способом. В подходах к строгому определению понятия алгоритма выделилось 3 основных направления: 1. Первый поход связан с именами таких математиков, как Чёрч, Гёдель, Клини. Суть его заключается в следующем. Любой алгоритм, фактически, сводится к вычислению некоторой числовой функции f(x 1 , x 2 , … , x n ), зависящий от натуральных значений аргументов в x 1 , x 2 , … , x n . Любая такая функция, для вычисления значений которой существует алгоритм, называется алгоритмически вычислимой. Понятие функции - строгое понятие. И первый подход заключается в следующем. Выделить некоторый класс строго определенных целочисленных функций и увязать понятие алгоритма (не строгое) с функциями (строго определенными) из этого класса. 2. Авторами второго направления, в плане уточнения понятия алгоритма, являются Тьюринг и Пост. Идея этого направления заключается в том, что для вычисления функции создать некоторую машину, которая сводит процесс вычисления к механическим действиям, и увязать понятие (не строгое) алгоритма с понятием (строгим) таких машин. 3. Третье направление связано с понятием нормальных алгоритмов, которое ввел в рассмотрение российский математик Марков. В результате этих уточнений с помощью понятия алгоритма удалось решить многие алгоритмические проблемы. В частности, советский математик Матиясевич в 1968 году дал отрицательное решение 10-й проблемы Гильберта, а именно, он доказал, что не существует алгоритма, позволяющего для любого диофантова уравнения дать ответ на вопрос о существовании целочисленного решения у такого уравнения. Параграф 2. Основные вычислимые функции и операторы В дальнейшем рассматриваем функции из N × N × ⋯ × N, где N - множество натуральных чисел с добавленным нулем. Причем функции не обязательно всюду определены, т.е. рассматриваемые функции, вообще говоря, являются частичными. Простейшими числовыми функциями являются следующие функции: 1) 0(x) = 0 - оператор аннулирования; 2) 𝜆(x) = x + 1 - оператор сдвига; n 3) I m (x 1 , x 2 , … , x n ) = x m , 1 ⩽ m ⩽ n, - оператор проектирования. Очевидно, что все эти функции всюду определены и являются алгоритмически вычислимыми. Пусть заданы n функций f 1 (x 1 , x 2 , … , x m ), f 2 (x 1 , x 2 , … , x m ), … , f n (x 1 , x 2 , … , x m ) и задана частичная функция f(x 1 , x 2 , … , x n ). Тогда можно построить суперпозицию этих функций g(x 1 , … , x m ) = f(f 1 (x 1 , … , x m ), f 2 (x 1 , … , x m ), … , f n (x 1 , … , x m )). Говорят, что функция g(x 1 , … , x m ) получается из функций f 1 (x 1 , … , x m ), f 2 (x 1 , … , x m ), … , f n (x 1 , … , x m ) и f(x 1 , … , x n ) с помощью оператора подстановки. Оператор подстановки будем обозначать как S n+1 , т.е. g = S n+1 (f, f 1 , … , f n ). Если F n - совокупность всех частичных функций от n переменных, а F m - множество всех частичных функций m переменных, то понятно, что S n+1 - это всюду определенная функция из F n × F m × ⋯ × F m (n + 1 раз) в F m . Если же F - множество всех числовых функций, то S n+1 - частичная функция F × F × ⋯ × F (n + 1 раз) в F. Очевидно, что если функции f, f 1 , … , f n всюду определены и g = S n+1 (f, f 1 , … , f n ), то функция g также всюду определена. И если f, f 1 , … , f n алгоритмически вычислимы, то g тоже вычислима. Пусть задана n-местная функция g и (n + 2)-местная функция h. Говорят, что (n + 1)местная функция f получается из функций g и h примитивной рекурсией, если для всех натуральных x 1 , x 2 , … , x n , y имеют место равенства: 1) f(x 1 , … , x n , 0) = g(x 1 , … , x n ); 2) f(x 1 , … , x n , y + 1) = h(x 1 , … , x n , y , f(x 1 , … , x n , y)). В этом определении неявно подразумевается, что n ⩾ 1. Уточним это определение для случая n = 0. В этом случае под 0-местной функцией g понимается некоторая функция const. Говорят, что одноместная функция f(x) получается примитивной рекурсией из константы a и 2-местной функции h(x, y), если выполнены условия: 1) f(0) = a; 2) f(x + 1) = h(x, f(x)). Итак, мы имеем некоторый оператор R, который по функциям g и h строит новую функцию f, т.е. f = R(g, h). Понятно, что этот оператор является частичным, т.к. для построения функции f необходимо, чтобы g была n-местной, а h - (n + 2)-местной. Если же функции g и h удовлетворяют данному условию, то функция f всегда определена. Теорема. Для заданной n-местной функции g(x 1 , … , x n ) и (n + 2)-местной функции h(x 1 , … , x n ) функция f(x 1 , … , x n ) = R(g(x 1 , … , x n ), h(x 1 , … , x n , x n+1 , x n+2 )) всегда существует и определена однозначно. Доказательство: Чтобы определить функцию f, надо определить значение f(x 1 , … , x n , x n+1 ) для любого набора чисел x 1 , … , x n , x n+1 . Если x n+1 = 0, то f(x 1 , … , x n , 0) = g(x 1 , … , x n ) по определению. Пусть x n+1 ≠ 0. Находим последовательно числа b 0 = g(x 1 , … , x n ) = f(x 1 , … , x n , 0) b 1 = h(x 1 , … , x n , 0, b 0 ) = f(x 1 , … , x n , 0 + 1) b 2 = h(x 1 , … , x n , 1, b 1 ) = f(x 1 , … , x n , 1 + 1) b 3 = h(x 1 , … , x n , 2, b 2 ) = f(x 1 , … , x n , 2 + 1) ⋯ b xn+1 = h(x 1 , … , x n , x n - 1, b xn+1 -1 ) = f(x 1 , … , x n , x n + 1) По определению f(x 1 , … , x n , x n+1 ) = b xn+1 . Пусть для функций g и h существуют две функции f и 𝜑, удовлетворяющие условиям определения примитивной рекурсии. Тогда по определению f(x 1 , … , x n , 0) = g(x 1 , … , x n ) = b 0 = 𝜑(x 1 , … , x n , 0) f(x 1 , … , x n , 1) = h(x 1 , … , x n , 0, b 0 ) = b 1 = 𝜑(x 1 , … , x n , 1) f(x 1 , … , x n , 2) = h(x 1 , … , x n , 1, b 1 ) = b 2 = 𝜑(x 1 , … , x n , 2) и т.д. Таким образом, для любых x 1 , … , x n , x n+1 f(x 1 , … , x n , x n+1 ) = 𝜑(x 1 , … , x n , x n+1 ). А это и означает, что функции f и 𝜑 совпадают. Пусть функция f(x 1 , … , x n , x n+1 ) получена из g и h с помощью примитивной рекурсии. Процедура вычисления значений функции f(x 1 , … , x n , x n+1 ), описанная при доказательстве теоремы, является алгоритмом вычисления ее значений исходя из значений функций g и h. Отсюда получаем следующее: 1) Если функции g и h алгоритмически вычислимы, то функция f тоже алгоритмически вычислима. 2) Если функции g и h всюду определены, то и функция f тоже всюду определена. Отметим, во-первых, что процедура, описанная в теореме, часто называется процессом рекурсии. А во вторых, в определении примитивной рекурсии, рекурсия проводится по последней переменной x n+1 . Можно определить рекурсию по любой из переменных. Следовательно, при фиксированных функциях g и h, можно получить различные функции f, в зависимости от того, по каким переменным проводится рекурсия. Мы же будем, в основном, ограничиваться ранее описанными случаями, связанными с примитивной рекурсией. Функция f(x 1 , … , x n ) называется примитивно рекурсивной, если она может быть получена из простейших числовых функций с помощью конечного числа операторов подстановки и примитивной рекурсии. Из определения следует: 1) простейшие числовые функции примитивно рекурсивны; 2) примитивно рекурсивные функции всюду определены; 3) если функции g и h примитивно рекурсивны, и функция f получена из них с помощью примитивной рекурсии, то f тоже примитивно рекурсивна. 4) суперпозиция примитивно рекурсивных функций примитивно рекурсивна. Параграф 3. Нумерация пар и n-ок Рассмотрим так называемую канторовскую нумерацию пар. В ней пары идут в порядке возрастания суммы их членов, а при равенстве сумм - в порядке возрастания первой координаты. Итак, это выглядит следующим образом: < 0, 0 > , < 0, 1 > , < 0, 2 > , < 1, 1 > , < 2, 0 > , < 0, 3 > , < 1, 2 > , < 2, 1 > , … Обозначим через C(x, y) номер пары < x, y > , начиная с нулевой пары и номера. Скажем C(0, 0) = 0, C(2, 0) = 5. Через l(n) = x и r(n) = y обозначим левую и правую координаты пары с номером n. Например, l(2) = 1, r(7) = 2 и т.д. Найдем формулы для вычисления этих функций. По определению, пара < x, y > находится в промежутке < 0, x + y > , < 1, x + y - 1 > , … , < x, y > , … , < x + y, 0 > на x-ом месте. Перед парой < 0, x + y > находится x + y отрезков, содержащих всего 1 + 2 +…+ (x + y) пар. В таком случае C(x, y) = 1 + 2 +…+ (x + y) + x = (x + y)(x + y + 1) 2 +x = (x + y) 2 + 3x + y Итак, номер C(x, y) можно вычислить либо по формуле C(x, y) = (x + y) 2 + 3x + y (x + y)(x + y + 1) 2 . + x, либо C(x, y) = . 2 2 Пусть теперь C(x, y) = n, найдем формулы для l(n) = x и r(n) = y. (x + y) 2 + 3x + y Итак, C(x, y) = = n, т.е. 2n = (x + y) 2 + 3x + y. Отсюда можно 2 получить два равенства: 8n + 1 = (2x + 2y + 1) 2 + 8x и 8n + 1 = (2x + 2y + 3) 2 - 8x - 8. Следовательно, (2x + 2y + 1) 2 ⩽ 8n + 1 < (2x + 2y + 3) 2 Отсюда получаем, 2x + 2y + 1 ⩽ x+y+1 ⩽ x+y+1 = 8n + 1 + 1 2 < x + y + 2. Это означает, что 8n + 1 + 1 2 8n + 1 < 2x + 2y + 3 или . Тогда из формулы l(n) = x = n -␒ (x + y)(x + y + 1) 2 (x + y)(x + y + 1) 2 + x = n получаем, =. 8n + 1 + 1 1 1 = n -␒ (x + y + 1 - 1)(x + y + 1) = n -␒ 2 2 8n + 1 -␒ 1 2 Теперь можно найти формулу для вычисления r(n). Имеем, 8n + 1 + 1 r(n) = y = (x + y + 1) -␒ (x + 1) = 2 2 . -␒ (l(n) + 1). Таким образом, для нахождения пары с номером n имеем формулы 8n + 1 + 1 1 l(n) = n -␒ 2 r(n) = 8n + 1 -␒ 1 2 8n + 1 + 1 2 2 -␒ (l(n) + 1). Формулы, для вычисления C(x, y), l(n) и r(n) показывают, что эти функции примитивно рекурсивны. Из определения функций C(x, y), l(n) и r(n) следует, что C(l(n), r(n)) = n и l(C(x, y)) = x, r(C(x, y)) = y. Оказывается, эти тождества не зависят от выбора нумерации пар. Т.е. если мы возьмем какую-то другую нумерацию пар ⏨(x, y) < x 0 , y 0 > , < x 1 , y 1 > , < x 2 , y 2 > , … , < x n , y n > , … и введем функции C номер пары относительно данной нумерации, ⏨ l (n) = x n , ⏨ r (n) = y n для пары ⏨( ⏨ < x n , y n > относительно этой нумерации, то C l (n), ⏨ r (n)) = n, ⏨ l (C(x, y)) = x, r (C(x, y)) = y. Более того, пусть у нас есть три функции f(x, y), 𝜑(x), 𝜓(y), связанные ⏨ соотношениями f(𝜑(x), 𝜓(x)) = x, 𝜑(f(x, y)) = x, 𝜓(f(x, y)) = y. Определив значение f(x, y) как номер пары < x, y > , мы получим нумерацию всех пар, т.е. каждая пара получит единственный номер, разные пары - разные номера, каждое натуральное число будет номером какой-то пары. Таким образом, любая нумерация пар натуральных чисел определяется функциями со свойствами f(𝜑(x), 𝜓(x)) = x, 𝜑(f(x, y)) = x, 𝜓(f(x, y)) = y, т.е. суть нумерации заключается в свойствах этих функций f(x, y), 𝜑(x), 𝜓(y). Поэтому и рассматривают обычно канторовскую нумерацию, т.к. для нее соответствующие функции C(x, y), l(n), r(n) легко вычисляются. Исходя из канторовской нумерации пар, определим канторовскую нумерацию n-ок. Обозначим через C n (x 1 , x 2 , … , x n ) номер n-ки . Далее, полагаем: C 2 ( x 1 , x 2 ) = C( x 1 , x 2 ) , C 3 ( x 1 , x 2 , x 3 ) = C 2 ( C( x 1 , x 2 ) , x 3 ) = C( C( x 1 , x 2 ) , x 3 ) , C 4 ( x 1 , x 2 , x 3 , x 4 ) = C 3 ( C( x 1 , x 2 ) , x 3 , x 4 ) = C 2 ( C( C( x 1 , x 2 ) , x 3 ) , x 4 ) , ⋯, C n+1 (x 1 , x 2 , … , x n+1 ) = C n (C(x 1 , x 2 ), x 3 , … , x n+1 ). Пусть C n (x 1 , x 2 , … , x n ) = x. Тогда по определению имеем x n = r(x) = C n,n (x) x n-1 = r(l(x)) = C n,n-1 (x) x n-2 = r(l(l(x))) = C n,n-2 (x) ⋯ x 2 = r(l(l( … l(x)))) = C n,2 (x) x 1 = l(l(l( … l(x)))) = C n,1 (x) Легко проверить, что C n (C n,1 (x), C n,2 (x), … , C n,n (x)) = x и C n,i C n (x 1 , x 2 , … , x n ) = x i . Функции C n (x 1 , x 2 , … , x n ) и C n,i (x) являются аналогами функций C(x, y), l(n) и r(n) для нумерации пар. Эти функции однозначно определяют нумерацию n-ок, и, по их заданию, они примитивно рекурсивны.