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

и семантика

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

это Ø
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 ))) [Аксиомы выделения, для каждой Ф]

– функция, отображающая множество 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 г. «О началах геометрии» – «неэвклидова геометрия».

был опубликован в книге его отца в 1832 году.

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

*

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

*

множеств
Изучить полноту и непротиворечивость для построенной системы или ее

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

высказываний
А0, А1, А2,… .
Определение формулы

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

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

с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ». «СЕПУЛЬКАРИИ — устройства для сепуления

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

¬А1
((А1 ∨ А0) ≡ ¬А1),
Как формула

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

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

была):

и 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 ?
Задача. Всякую ли функцию можно задать
подходящей формулой?

скобок.

– значение Φ при интерпретации α равно 1.

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

совместно, если существует интерпретация, при которой все его формулы

истинны.
Множество формул противоречиво, если не существует интерпретации, при которой все его формулы истинны.

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

Тогда α╞ Ψ.
Всюду вычеркнем α (то есть – «при

всех α» ) и запишем:

╞ Φ, ╞ (Φ → Ψ)
-------------------------- – Modus ponens («правило вывода»)
╞ Ψ

То есть, если в каком-то рассуждении мы получили Φ
и Φ → Ψ, то можем получить Ψ.

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

доказательство от противного
╞ Φ

¬ Φ → ¬Ψ╞ Ψ → Φ – контрапозиция

(Ψ → Φ), (¬Ψ → Φ) ╞ Φ – разбор случаев

(Φ → Ψ), (Ψ → Φ) ╞ (Φ ≡ Ψ) – доказательство
эквивалентности

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

можно выбрать конечное подпокрытие.
Т. Топология: Компактное пространство. Семейство замкнутых

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