Презентация "Введение в логику" по математике – проект, доклад

21.09.2019

Введение в математическую логику и теорию алгоритмов Лекция 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 можно отождествлять с Bu. Что нужно для существования множества действительных чисел? Что нужно для доказательства свойств («аксиом») действительных чисел?

Пределы расширения

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

Неравномощность множества и множества всех его подмножеств Д. Пусть f – функция, отображающая множество A на множество всех его подмножеств. Будем писать f (x) = y вместо < 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…). Противоречие.

Теорема Кантора

Границы математики

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

Геометрия. Пятый постулат

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

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

Математика. Программа Гильберта

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

Задачи нашего курса

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

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

Логика высказываний

Круг в определении

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

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

Синтаксис логики высказываний.

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

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

Логика высказываний. Семантика

Значение формулы при данной интерпретации  B N . Вычисление индукцией по построению: Значением логической константы является она сама. Значением имени высказывания Ai является i . Значением: - формулы () является отрицание значения , т.е. Зн () = 1- Зн . - формулы (), где ,,,  является результат применения  к значениям формул , . Значение формулы – функция BN  B. Наибольший номер имени высказвания в формуле равен n - 1. формула задает функцию B n  B.

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

Булевы функции

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

Лишние скобки

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

Семантика

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

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

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

Примеры и применения. Распространенные способы рассуждения

╞ 0 ------------ – доказательство от противного ╞     ╞    – контрапозиция (  ), (  ) ╞  – разбор случаев (  ), (  ) ╞ (  ) – доказательство эквивалентности

Распространенные способы рассуждения

Теорема компактности

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

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