Логика Скачать
презентацию
<<  Жизнь и логика Математическая логика  >>
Введение в математическую логику
Введение в математическую логику
План
План
Аксиомы теории множеств
Аксиомы теории множеств
Построение натуральных чисел
Построение натуральных чисел
Аксиомы
Аксиомы
Пределы расширения
Пределы расширения
Теорема Кантора
Теорема Кантора
Границы математики
Границы математики
Геометрия
Геометрия
Янош Бойяи
Янош Бойяи
Математика
Математика
Системы доказательства
Системы доказательства
Логика высказываний
Логика высказываний
Круг в определении
Круг в определении
Синтаксис логики высказываний
Синтаксис логики высказываний
Семантика связок
Семантика связок
Семантика
Семантика
Значение формулы
Значение формулы
Нахождение значения
Нахождение значения
Булевы функции
Булевы функции
Лишние скобки
Лишние скобки
Терминология
Терминология
Множество формул
Множество формул
Примеры и применения
Примеры и применения
Распространенные способы рассуждения
Распространенные способы рассуждения
Теорема компактности
Теорема компактности
Построение сложных высказываний
Построение сложных высказываний
Слайды из презентации «Введение в логику» к уроку алгебры на тему «Логика»

Автор: Win7. Чтобы увеличить слайд, нажмите на его эскиз. Чтобы использовать презентацию на уроке, скачайте файл «Введение в логику.ppt» бесплатно в zip-архиве размером 573 КБ.

Скачать презентацию

Введение в логику

содержание презентации «Введение в логику.ppt»
СлайдТекст
1 Введение в математическую логику

Введение в математическую логику

и теорию алгоритмов Лекция 2.

Алексей Львович Семенов

1

01.11.2014

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}}.

3

01.11.2014

4 Построение натуральных чисел

Построение натуральных чисел

(повт.).

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

4

01.11.2014

5 Аксиомы

Аксиомы

Какие еще аксиомы нужны? (повт.).

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

5

01.11.2014

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

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

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

6

01.11.2014

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

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

Неравномощность множества и множества всех его подмножеств Д. Пусть 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…). Противоречие.

7

01.11.2014

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

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

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

8

01.11.2014

9 Геометрия

Геометрия

Пятый постулат.

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

9

01.11.2014

10 Янош Бойяи

Янош Бойяи

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

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

10

01.11.2014

11 Математика

Математика

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

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

11

01.11.2014

12 Системы доказательства

Системы доказательства

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

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

12

01.11.2014

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

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

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

13

01.11.2014

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

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

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

14

01.11.2014

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

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

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

15

01.11.2014

16 Семантика связок

Семантика связок

A.

B

?A

A?B

A?B

A?B

A?B

0

0

1

0

0

1

1

0

1

1

0

1

1

0

1

0

0

0

1

0

0

1

1

0

1

1

1

1

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

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

17 Семантика

Семантика

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

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

17

01.11.2014

18 Значение формулы

Значение формулы

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

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

19 Нахождение значения

Нахождение значения

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

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

19

01.11.2014

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

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

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

20

01.11.2014

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

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

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

21

01.11.2014

22 Терминология

Терминология

Семантика.

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

22

01.11.2014

23 Множество формул

Множество формул

Семантика.

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

23

01.11.2014

24 Примеры и применения

Примеры и применения

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

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

24

01.11.2014

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

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

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

25

01.11.2014

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

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

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

26

01.11.2014

27 Построение сложных высказываний

Построение сложных высказываний

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

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

«Введение в логику»
http://900igr.net/prezentatsii/algebra/Vvedenie-v-logiku/Vvedenie-v-logiku.html
cсылка на страницу
Урок

Алгебра

34 темы
Слайды
Презентация: Введение в логику.ppt | Тема: Логика | Урок: Алгебра | Вид: Слайды
900igr.net > Презентации по алгебре > Логика > Введение в логику.ppt