Как устроена математическая логика Алексей Львович Семенов

2 Цель математической логики – ответить на вопросы : Что значит, что математическое утверждение доказано? Что значит определить математическое отношение? Что значит, что математическая функция вычислима? (теория алгоритмов) Давид Гильберт, II Международный математический конгресс, Париж, Проблемы Гильберта I, II, X проблемы относятся к математической логике и теории алгоритмов Из семи математических Проблем тысячелетия первая также относится к нашему предмету

Программа Гильберта основания (и обоснования) математики Курт Гёдель ( – ) указание возможности и доказательства невозможности, начало 1930-х гг.

Цепочки Цепочка = конечная последовательность, она может быть и пустой – Λ (длина – 0). Обозначения:, или a 1,… a n Алфавит = конечное множество символов. B = {0 1} Слово (в алфавите) – конечная последовательность символов (частный случай цепочки). Длина слова – число элементов цепочки. Слова записываем без запятых: a 1 … a n. Ансамбль над S – множество всех слов в алфавите S Слово v входит в w, если w = uvs для некоторых u,s. Вхождение v в w это слово вида u*v*s, где uvs= w. первое вхождение и т. д. Основные понятия

Основные понятия Множества Объединение, пересечение, дополнение Произведение: AxB = { |a A и b B} Степень: AxAxA и т. д. n-местное отношение – подмножество степени n-местная функция – n+1-местное отношение

6 Цепочка слов – тоже слово в расширенном алфавите – добавляем запятую после каждого элемента пустая цепочка – это пустое слово, цепочка из одного пустого слова, это слово из одного символа,. Код цепочки слов в алфавите B в алфавите B: удвоить каждую букву 0 или 1, запятую заменить на 01 функция из ансамбля из трех букв в ансамбль над 01. Задача: можно ли кодировать покороче? Короче чего кодировать нельзя? Многоместные функции и свойства можно заменять одноместными

Логические константы: символы И, Л, или символы 0, 1. Логические операции: & (и, конъюнкция), (или, дизъюнкция), (не, отрицание) применяются к символам 0 (И) и 1 (Л) : AB A A&B A B Логика

Характеристическая функция Свойство – функция со значениями И и Л (не обязательно всюду определенная) свойство задает отношение – множество, где значение функции – И.

Действия и проверки Действие – исходное понятие. Действие: описано на понятном человеку языке, может осуществляться и человеком и каким-то (реальным или абстрактным) устройством, можно применить к любому исходному данному из некоторого ансамбля слов, при этом ясно, что всегда получается и однозначно определен результат применения – элемент (возможно, другого) фиксированного ансамбля слов. Действие задает всюду определенную функцию Кодирование – пример действия. Проверка – действие с результатом И или Л Действие – базовое понятие теории алгоритмов.

Исчисления. Породимые множества Исчисление – это пара из двух проверок:. над некоторым алфавитом. множество создаваемых исчислением объектов: Если правило создания выполнено для кода цепочки объектов a 1,… a n и все элементы этой цепочки, кроме последнего – создаваемы, то и последний элемент создаваем. Если правило создания выполнено для цепочки из одного элемента, то он создаваем; его называют начальным объектом. Задача: Что, если таких объектов у данного исчисления нет? Объект, порождаем данным исчислением, если он создаваем и для него выполнено правило окончания. Множество, порождаемое исчислением. Породимое множество

11 Пример. Правило создания (коды не пишем): здесь x – пробегает все непустые слова в алфавите цифр. Правило окончания: слово не пусто и не начинается с 0 Задача: что порождается?

Пример Правило создания для всех x,y из ансамбля a b Правило окончания: ансамбль над a b Задача: что порождается?

Грамматики (Ноам Хомски, ) Определение. Грамматика Γ – это цепочка Σ – основной алфавит Γ Ω – вспомогательный алфавит Γ S – начальный символ Γ ΣΩ=Ø, объединение Σ и Ω – это алфавит Γ, обозначим его Δ. Π – это конечное множество пар слов в алфавите Δ - замен Вместо пишем u v

Грамматика задает исчисление Правило создания: Для каждой замены u v из Π, все пары вида, где t,p – произвольные слова в алфавите Δ – Создание – замена u на v. Правило окончания для грамматики Γ состоит из всех слов в алфавите Σ. – Породимые слова не могут содержать букв из Ω. правило создания – бесконечно, его описание - слово в конечном алфавите (можно считать – в алфавите 01).

Задачи: Будут ли объединение, пересечение и дополнение породимых множеств породимыми? Как последовательно выписать (перечислить) все элементы породимого множества?

Математика Сто лет назад было построено исчисление для математики. Математика: порождение новых слов по известным правилам

17 Что такое формула? Формулы логики высказываний Что такое логическое имя? (Скоро у них появятся значения) A267 – имя, обычно пишут A 267 Имя – это буква А, за которой идет десятичное число Десятичное число – это цифра (в индексе), кроме нуля, за которой идет десятичное число или пустое слово Грамматика N – начальный символ N AЧ Ч 1, Ч 2 …Ч Ч 0, Ч Ч 1 … Используем и для переходов (применения замен) N АЧ АЧ 0 АЧ 50 А 250 Задача: доказать, что эта грамматика подходит

Индуктивное определение (исчисление) Логические константы, логические имена – формулы Если, - формулы,,, то ( ), ( ) – формулы Грамматика Расширяем грамматику имен Начальный символ Ф Ф N, Ф ( Ф), Ф (Ф Ф) Ф (Ф & Ф) Что такое формула?

Ф (Ф Ф) (Ф (Ф & Ф)) (N (Ф & Ф)) (АЧ (Ф & Ф)) (A 2 (Ф & Ф)) (A 2 (Ф & ( Ф))) (A 2 (Ф & ( N))) (A 2 (Ф & ( АЧ))) (A 2 (Ф & ( A 2 ))) (A 2 (N & ( A 2 ))) (A 2 (АЧ & ( A 2 ))) (A 2 (АЧ 5 & ( A 2 ))) (A 2 (А 35 & ( A 2 ))) Пример

Анализ формулы: Задача 1. Дано слово. Как узнать, формула это или не формула? Задача 2. Дана формула. Тогда это: 1. или логическая константа 2. или логическое имя 3. или ( ), 4. или ( ) 5. или ( ) Как узнать, какой это случай, и в случаях 3, 4, 5 найти формулы, ? Однозначно ли определяется случай и эти формулы?

Тезис Поста Всякое породимое множество порождается некоторой грамматикой Вычислимость Т. Функция вычислима тогда и только тогда, когда ее график породим «Тезис Черча» Функция вычислима тогда и только тогда ее график породим грамматикой

Логика высказываний Семантика. B - множество бесконечных последовательностей 0 и 1. Фиксируем интерпретацию = 1,..., i B. Значение формулы при данной интерпретации. Индукция по построению : 1. Значением логической константы является она сама. 2. Значением логического имени A i является i. 3. Значением формулы ( ) является отрицание значения формулы, т.е. Зн = 1- Зн. 4. Значением формулы ( ), где, является результат применения операции к значениям формул,. Задача. Однозначность значения. Значение формулы – функция B B. Пусть наибольший индекс переменной в формуле равен n. Тогда формула задает функцию B n B.

Построение функции по формуле А0А0 А1А1 А 2А 2 (А 0 А 1 ) (А 2 А 0 )

Построение функции по формуле А0А0 А1А1 А 2А 2 (А 0 А 1 ) (А 2 А 0 )

Построение функции по формуле А0А0 А1А1 А 2А 2 (А 0 А 1 ) (А 2 А 0 )

Построение функции по формуле А0А0 А1А1 А 2А 2 (А 0 А 1 ) (А 2 А 0 )

Задача 1. Сколько существует функций от n аргументов? Задача 2. Всякая ли функция задается формулой? Как построить формулу по функции? Задача 3. Сколько нужно времени, чтобы проверить, что формула тождественно истинна? Проблема перебора. Задача о ранце: a, мешок b 1,…b n, можно ли из b составить a. 27

Логика высказываний Построение сложных высказываний из простых Для простых – существенна только их истинность. О чем высказывания – не существенно и не видно. Дальше – логика отношений

Отношения Множество D n-местное отношение (n-местное свойство) на D – любое подмножество в D n. -местное отношение – подмножество в D ( = {0, 1, 2,..}) Отношение – отображение из D в B = {0,1}, высказывание об элементах D Примеры 2-местное отношение равенства – множество всех пар, x D Отношения на натуральных числах: следования y= x+1 порядка x

Логика отношений Синтаксис 1. Начало Алфавит имен предметов Ob={a 1, a 2,… } Алфавит имен отношений Pr={P 1, P 2,… }, каждому имени сопоставлена его арность (число аргументов) Алфавит имен функций Fn={f 1, f 2,… }, каждому имени сопоставлена его арность (число аргументов) Сигнатура = Можно обойтись без имен функций, сводя функции к отношениям.

Логика отношений Семантика 1. Начало Структура данной сигнатуры – это набор, где Зн ставит в соответствие: имени предмета – элемент из D имени отношения – отношение на D (с нужным числом аргументов) имени функции – функцию на D (с нужным числом аргументов)

Примеры структур Синтаксис Вместо 5

Логика отношений Синтаксис 2. Продолжение Фиксируем упорядоченный алфавит свободных переменных FVar= Термы: Имя предмета - терм Свободная переменная – терм Функциональное имя, примененное к термам - терм Атомные формулы Если P - имя n-местного отношения и t 1,…t n-1 - термы, то P (t 1,…t n ) – атомная формула Если t 0, t 1 - термы, то t 0 = t 1 – атомная формула Пример: P 2 (a 1, x 2, x 2 ) – атомная формула

Логика отношений Семантика 2. Продолжение Пусть задана структура: и интерпретация = 1, 2,... из D Интерпретация задает значения свободных переменных Задача Придумать определение значения терма и атомной формулы. Зн атомной формулы – это отображение D B, то есть - -местное отношение, если номера всех переменных формулы не больше n, то она задает n-местное отношение

Логика отношений

Синтаксис 3 Еще один алфавит – связанных переменных Bvar, тоже термы Формула (заданной сигнатуры), индуктивное определение: Атомные формулы – формулы. Если, - формулы,,, то ( ), ( ) – формулы. Если - формула, x – свободная переменная (x FVar), u – связанная переменная (u BVar), не входящая в, то ( u [x/u] ), ( u [x/u] ), – формулы (в эти формулы x – не входит). - для всех, - существует

Логика отношений Пусть задана структура: и интерпретация = 1, 2,… из D Зн формулы B определяется индуктивно… Задача. Построить семантику

Логика отношений Задана структура M= Значение формулы зависит только от значений ее (свободных) переменных (от соответствующих членов последовательности ) Если все свободные переменные имеют номера < n, то выражает n-местное отношение на D. Это отношение определимо (или выразимо) в M.

Истинность Формула без свободных переменных истинна или ложна Общезначимые формулы – истинные в любой структуре данной сигнатуры Множество общезаначимых формул – породимо

Утверждение, которое вы сейчас видите на экране, – ложно. Теорема Гёделя. Формализация Утверждение в формальном языке, говорящее о собственной истинности (ложности)

41 Структура M Ансамбль слов. Кодирование Определение: А есть код слова T, U получается подстановкой Б вместо свободной переменной х в T. Подст (А, Б) - это код слова U. Функция подстановки Подст выразима в М. M может быть, например, арифметикой.

42 Гёделева диагональ Ф – формула с одной свободной переменной x Г = Ф (Подст(x,x)) Г (код Г) = Ф (Подст (код Г, код Г)) = Ф (код Г (код Г)) Теорема Тарского. Не существует формулы Ф, выражающей свойство: «быть кодом истинного в структуре М утверждения». Д. Предположим, такая формула Ф существует. Рассмотрим формулу: Г (код Г), определенную выше через Ф… Задача: завершить доказательство

43 Гёделева диагональ Ф – формула с одной свободной переменной Г = Ф (Подст(x,x)) Г (код Г) = Ф (Подст (код Г, код Г)) = Ф (код Г (код Г)) Пусть в нашей структуре М для всякого исчисления над алфавитом {0,1} выразимо свойство «быть кодом выводимого в этом исчислении слова». Теорема Гёделя. Не существует исчисления, порождающего в точности истинные формулы в структуре М. Д. Пусть такое исчисление существует, и Ф выражает свойство «быть кодом выводимого слова». Рассмотрим формулу Г (код Г) – истинна… Задача: завершить доказательство