Введение в математическую логику и теорию алгоритмов Лекция 2 Алексей Львович Семенов

План Аксиомы теории множеств (повторение и продолжение) Трудности с полнотой Логика высказываний. Синтаксис и семантика

Построение математики Программа Гильберта Математика, как игра по правилам Аксиоматическая теория Теория множеств: – Кантор – Больцано

Аксиомы теории множеств (повт.) Существование множеств x y (y x) [Аксиома пустого множества] u v s w (w s (w = u w = v)) [Аксиома пары] Пример: существует {Ø} – непустое множество. Существование объединения множества: {{1,2,4},{4,5},{8,7,{9}}} = {1,2,4,5,8,7,{9}}.

Один из способов Построение каждого отдельного числа: – 0 – это Ø – 1 – это {0} – 2 – это {0,1} = {0,{0}} ……Операция S (x) = x {x} Существование множества всех натуральных чисел – аксиома. Задача. Написать аксиому существования множества натуральных чисел. Построение натуральных чисел

Какие еще аксиомы нужны? Существование множества всех подмножеств данного множества: u s v( w(w v w u) v s) [Аксиома степени] Множество всех подмножеств множества u можно отождествлять с B u. Что нужно для существования множества действительных чисел? Что нужно для доказательства свойств («аксиом») действительных чисел?

Пределы расширения Существует множество всех объектов с данным свойством – Аксиома? Для каждого свойства Ф(x) добавить аксиому: s v ( v s Ф( v )) Что такое Ф(x)? Можно рассмотреть только свойства, определяемые формулами. Формула Ф(x): (x x) [Диагональ Рассела] Задача. Может ли существовать требуемое s ? Можно добавить для каждой формулы Ф: u s v (v s (v u Ф(v ))) [Аксиомы выделения]

Теорема Кантора – Бернштейна. Пусть существует биекция между множеством A и подмножеством множества B, а также биекция между множеством B и подмножеством множества A. Тогда множества A и B – равномощны. Задача (из первой лекции). Доказать Теорему Кантора – Бернштейна.

Соображение f g B ? A f g -1 a

Неравномощность множества и множества всех его подмножеств Д (полуформальное). Приведем к противоречию существование функции f, отображающей множество A на множество всех его подмножеств. Будем писать f (x) = y вместо f, и x y вместо (x y) Формула Ф(x) : x f (x) Аксиома выделения дает B A: x (x B (x A x f (x))). По предположению для некоторого b A выполнено f (b) = B b B (b A b f ( b ) ). Противоречие. Теорема Кантора

Границы математики Диагональ Рассела – противоречие. Диагональ Кантора – теорема. Множество действительных чисел не равномощно множеству натуральных. Существует ли бесконечное множество действительных чисел, не равномощное ни всему множеству действительных чисел, ни множеству натуральных чисел? Кантор считал, что нет (Гипотеза Континуума) – содержание Первой Проблемы Гильберта.

Гедель доказал в 1940 году, что Гипотезу Континуума нельзя опровергнуть: она не приводит к противоречию (если теория множеств без нее – не противоречива). Пол Коэн ( – ) доказал в 1964 году, что Гипотезу Континуума нельзя доказать, если принять естественную систему аксиом о множествах. Границы математики

Геометрия. Пятый постулат Через точку, лежащую вне данной прямой, можно провести не более одной прямой, не пересекающейся с данной. «И если прямая, падающая на две прямые, образует внутренние и по одну сторону углы, [в сумме] меньшие двух прямых, то продолженные неограниченно эти прямые встретятся с той стороны, где углы меньше двух прямых.» Попытки доказательства: привести к противоречию отрицание. Николай Иванович Лобачевский ( ) пришел к убеждению: если к геометрии Евклида добавить утверждение о существовании нескольких прямых, проведенных через одну точку и параллельных данной, то противоречия не возникнет, 1829 г. «О началах геометрии» – «неэвклидова геометрия».

Геометрия. Пятый постулат Янош Бо́йяи ( ) Результат был опубликован в книге его отца в 1832 году. Отец Бо́йяи привлек внимание Карла Фридриха Гаусса ( ) к этой публикации. Гаусс – давно знал! Доказательство утверждения Лобачевского получено Феликсом Клейном ( ) в 1871 году. Принципиально выдвижение и отстаивание гипотезы известным ученым – Лобачевским

Математика. Программа Гильберта Гипотеза Континуума – не поправимый случай, а неизбежная ситуация Гедель: полная и не противоречивая математика невозможна

Задачи нашего курса Построить систему доказательств Построить систему аксиом теории множеств Изучить полноту и непротиворечивость для построенной системы или ее частей Будут рассмотрены произвольные системы доказательства, и еще более общие математические объекты – исчисления Вычислимость… В наших рассмотрениях мы (как и других разделах математики) используем неформальную теорию множеств

Первый из логических языков нашего курса (первый шаг в построении системы доказательств для Математики). Последовательность имен высказываний А 0, А 1, А 2,…. Определение формулы (логики высказываний). 1. Логические константы 0 и 1 – формулы. 2. Если А – имя высказывания, то А – формула. 3. Если Ф, Ψ – формулы, τ – связка: (конъюнкция), (дизъюнкция), (импликация), (эквивалентность), то Ф, (Ф τ Ψ) – формулы. Индуктивное определение (построение) «Порочный круг» (цикл в определении – circulus in definiendo) – определение понятия через его же само? Логика высказываний

Круг в определении «СЕПУЛЬКИ важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ». «СЕПУЛЬКАРИИ устройства для сепуления (см.)». «СЕПУЛЕНИЕ занятие ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКИ». Лем С. «Звёздные дневники Ийона Тихого. Путешествие четырнадцатое.»

Примеры формул: А 2, (А 1 А 0 ), А 1 ((А 1 А 0 ) А 1 ), Как формула строилась: А 1 А 0 (А 1 А 0 ) А 1 ((А 1 А 0 ) А 1 ) Задача. Как проверить, является ли слово формулой? Например, формулы ли: )))А 0, ((А 1 А 2 )) ? Синтаксис логики высказываний.

Логика высказываний Семантика. B = {0,1}. Семантика связок (таблица была): AB AA B

B N - множество бесконечных последовательностей из 0 и 1. Пояснение: Выбор элемента = 0, 1,..., i … B N означает фиксацию значений имен высказываний А 0, А 1,…, А i,…. Всякий элемент B N – интерпретация. Фиксируем интерпретацию. Замечание. Нам удобно задавать значения сразу для всех имен высказываний. Логика высказываний. Семантика

Значение формулы при данной интерпретации B N. Вычисление индукцией по построению: 1. Значением логической константы является она сама. 2. Значением имени высказывания A i является i. 3. Значением: - формулы ( ) является отрицание значения, т.е. Зн ( ) = 1- Зн. - формулы ( ), где,,, является результат применения к значениям формул,. Значение формулы – функция B N B. Наибольший номер имени высказвания в формуле равен n - 1. формула задает функцию B n B.

Логика высказываний. Семантика Нахождение значения Задача. Почему процесс заканчивается? Задача. Почему результат процесса однозначно определен? (однозначность анализа) Может ли быть, например: = ( 1 1 ) = ( 2 2 )?

Булевы функции - Функции B n B. Формула задает функцию B n B. Задача. Сколько существует функций: B n B ? Задача. Всякую ли функцию можно задать подходящей формулой?

Лишние скобки Задача. Придумать разумные правила опускания и восстановления скобок.

Семантика Терминология и обозначения для формул Обозначение: – значение при интерпретации равно 1. выполнена в (при) интерпретации. Обозначение: – значение при любой интерпретации равно 1 ( всегда истинно). Такие называются тавтологиями. ложные (получающие значение 0) при любой интерпретации называются противоречиями., для которой существует интерпретация, в которой она истинна, называется выполнимой.

Семантика Терминология и обозначения для множеств формул Множество формул совместно, если существует интерпретация, при которой все его формулы истинны. Множество формул противоречиво, если не существует интерпретации, при которой все его формулы истинны. Пусть Δ – множество формул. Обозначение: Δ – при всякой интерпретации значение равно 1, если значение всех формул из Δ в той же интерпретации – это 1. следует из Δ.

Пусть ( ) и. Тогда. Всюду вычеркнем (то есть – «при всех » ) и запишем:, ( ) – Modus ponens («правило вывода») То есть, если в каком-то рассуждении мы получили и, то можем получить. Примеры и применения. Распространенные способы рассуждения

– доказательство от противного – контрапозиция ( ), ( ) – разбор случаев ( ), ( ) ( ) – доказательство эквивалентности Распространенные способы рассуждения

Теорема компактности О. Компактное пространство: Из любого покрытия открытыми можно выбрать конечное подпокрытие. Т. Топология: Компактное пространство. Семейство замкнутых множеств. Если всякое конечное подсемейство имеет непустое пересечение, то и пересечение всех множеств семейства не пусто. Т. Логика. Семейство формул. Если всякое конечное подсемейство выполнимо, то и все семейство выполнимо. Задача. Доказать Теоремы компактности в топологии (для множеств на прямой, например) и логике.

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