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

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

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

3 Аксиомы теории множеств (повт.) Существование множеств 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}}.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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