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

отношений
Исчисления
Породимые множества
Грамматики. Тезис Поста

– исчисления («игры»)
Доказательство непротиворечивости и полноты «надежными», «финитными» средствами

(анализом «игры»)

∑, Зн
Свободные переменные x1,…
Задача. Формулы R(x) и Q(x) эквивалентны

в структуре M т. е. M ⊨ R(x) ≡ Q(x) титтк
значения R(x) и Q(x) (отношения в DN ) совпадают.
О. Формулы эквивалентны, если они эквивалентны в любой структуре (данной сигнатуры).

Отношения, задаваемые формулами логики отношений (Семантика)

(п.н.ф.), если она не содержит кванторов, или имеет вид:
Q1x1…

QnxnФ, где все Qi – это ∀ или ∃, а в Ф кванторов нет.
Задача. Дать индуктивное определение формулы (находящейся) в п.н.ф.
Задача. Построить алгоритм, который по всякой формуле логики отношений строит формулу (находящуюся) в п.н.ф., ей эквивалентную (ее предваренную нормальную форму).
Можно переименовывать связанные переменные…

(∃u Φ[u/x]) ≡ (∃v Φ[v/x])
⊨ (Qu Φ[u/x]) τ Ψ

≡ (Qu (Φ[u/x] τ Ψ)), τ∈{∧,∨}, Q∈{∀,∃}, Ψ не содержит u
⊨ (¬ (∀u Φ[u/x])) ≡ (∃v ¬Φ[v/x])
⊨ (¬ (∃u Φ[u/x])) ≡ (∀v ¬Φ[v/x])

перечислимо: есть процесс деятельности, позволяющий для всякой общезначимой формулы

когда-нибудь узнать, что она общезначима.
Теорема компактности для счетного множества утверждений.
Если любое конечное подмножество теории имеет модель, то и вся теория имеет модель.
Задача. Как обстоит дело с общезначимыми и с необщезначимыми формулами в логике высказываний?

определение выводимой формулы, формализующее практику математических доказательств.

Возьмем тавтологию логики высказываний, например:
А1 → (А2 →

А1). (*)
Подставим в (*) вместо имен высказываний А1 и А2 формулы (замкнутые или незамкнутые) логики отношений.
Например, вместо А1 подставим ∀u1(P5(u1)),
а вместо А2 подставим P4(x1,x1):
∀u1(P5(u1)) → ( P4(x1,x1) → ∀u1(P5(u1)) ).
То, что получилось, называется частным случаем тавтологии (*) логики высказываний в логике отношений.
Любая такая формула истинна в любой структуре при любой интерпретации.
Вместо «частный случай тавтологии…» говорим просто «тавтология».

(одно для данной сигнатуры) задаётся аксиомами (являющимися формулами сигнатуры

Σ) и правилами вывода.
Аксиомы:
A1. частные случаи тавтологий логики высказываний,
A2. формулы вида ∀u Φ[u/x] → Φ[t/x],
A3. формулы вида Φ[t/x] → ∃u Φ[u/x],
где Φ – формула, x – свободная переменная (x∈FVar), u – связанная переменная (u∈BVar), не входящая в Φ, t – свободная переменная.

(modus ponens, (MP))

R2

R3

В R2, R3 x не входит в Φ.
Правила R2 и R3 называются правилами Бернайса.

– аксиома или выводима из предшествующих в цепочке.

Пример 1.

(1) ⊢ ∀u P(x) [u/x] → P(x) [x/x] (аксиома A2)
⊢ ∀u P(u) → P(x) (аксиома A2)
(2) ⊢ ∀u P(u) → ∀v P(v) (по правилу R2 из (1))
(В этом выводе P – имя одноместного отношения.)

Пример 2. Пусть Φ - любая формула в нашей сигнатуре.

⊢ (∀u Φ[u/x] → Φ) → ((Φ → ∃u Φ[u/x]) → (∀u Φ[u/x] → ∃u Φ[u/x]))
(Частный случай тавтологии (A → B) →((B → C) →(A → C)). )
(2) ⊢ ∀u Φ[u/x] → Φ (A2, Φ – это Φ[ x/x ])
(3) ⊢ (Φ → ∃u Φ[u/x]) → (∀u Φ[u/x] → ∃u Φ[u/x]) (по MP из (2) и (1))
(4) ⊢ Φ → ∃u Φ[u/x] (A3)
(5) ⊢ ∀u Φ[u/x] → ∃u Φ[u/x] (по MP из (4) и (3))

отношения «меньше или равно».)
(1) ⊢ ∀u (u≤y) →

x≤y (A2, терм t = x)
(2) ⊢ x≤y → ∃v (x≤v) (A3, терм t = y)
(3) ⊢ (∀u (u≤y) → x≤y) →
→ ((x≤y → ∃v (x≤v)) → (∀u (u≤y) → ∃v (x≤v))) (частный случай тавтологии (A → B) →((B → C) → (A → C)) )
(4) ⊢ (x≤y → ∃v (x≤v)) → (∀u (u≤y) → ∃v (x≤v)) (по MP из (1) и (3))
(5) ⊢ ∀u (u≤y) → ∃v (x≤v) (по MP из (2) и (4))
(6) ⊢ ∀u (u≤y) → ∀u ∃v (u≤v) (по R2 из (5))
(7) ⊢ ∃v ∀u (u≤v) → ∀u ∃v (u≤v) (по R3 из (6))

Заметим, что полученная формула – общезначима.

является общезначимой.
Структура доказательства (индукция по построению).
A1

Частные случаи тавтологий логики высказываний – общезначимы.
A2 Формулы вида ∀u Φ[u/x] → Φ[ t / x] – общезначимы.
A3 Формулы вида Φ[ t / x] → ∃u Φ[u/x] – общезначимы.
R1 Если формулы Φ и Φ → Ψ общезначимы, то формула
Ψ – общезначима.
R2 Если формула Φ→Ψ общезначима и Φ не содержит x, то
формула Φ → ∀u Ψ[u/x] – общезначима.
R3 Если формула Ψ→Φ общезначима и Φ не содержит x, то
формула ∃u Ψ[u/x] → Φ – общезначима.
Доказательство рассматривает определение истинности, значения на последовательности, и т. д.

отношений совпадает с выводимостью в исчислении логики отношений.
Теорема в

курсе не доказывается
Задача. Доказать теорему.
Решение – не обязательно.

пустой – Λ. Длина цепочки – число элементов в

ней.
Алфавит = конечная цепочка символов
Слово (в данном алфавите) – цепочка символов этого алфавита.
Ансамбль слов в данном алфавите – все слова. Часто: 0 1
Ансамбль цепочек слов в данном алфавите – все цепочки слов.
Ансамбль списков в данном алфавите – все цепочки, элементами которых являются слова или списки (индуктивное определение).
Задача. Дать подробные индуктивные определения для понятий с этого экрана.

Общее понятие исчисления. Предварительные определения

Действие:
Слово, являющееся текстом (цепочкой) на понятном человеку языке;
Его можно

применить к любому исходному данному из фиксированного ансамбля, при этом ясно, что всегда получается результат применения – элемент (возможно, другого) фиксированного ансамбля
Оно может применяться, выполняться и человеком, и каким-то устройством,
Действие – задает всюду определенную функцию
Проверка – действие с результатом 0 или 1
Проверка задает характеристическую функцию множества (где она дает 1), мы говорим, что она допускает его элементы (а другие – не допускает)

пара из двух проверок:
.
проверка возможности

(создания) применяется к цепочке объектов, проверка завершения (окончания)– к объекту.
создаваемый исчислением объект индуктивно определяется так:
Если проверка возможности допускает цепочку объектов a1,… an и все элементы этой цепочки, кроме последнего – создаваемы,
то и последний элемент создаваем.
Если проверка возможности допускает цепочку из одного элемента, то его называют начальным объектом (в некоторых контекстах – аксиомой).
Задача. Что, если таких у данного исчисления нет?
Общее представление о деятельности, использующей уже имеющиеся условия.

его допускает проверка завершения.
Исчисление порождает множество из всех порождаемых

им объектов – множество, порождаемое этим исчислением.
Породимое множество – множество, порождаемое каким-то исчислением.
Эмиль Пост
(11.02.1897 — 21.04.1954)

Исчисления. Породимые множества

возможности, то говорим. что an создается из a1, …,

an-1 (в данном исчислении).
Вывод объекта a – цепочка объектов S, каждый из которых создается из какой-то цепочки объектов, встретившихся в S раньше него.
Шаг вывода – добавление одного элемента в цепочку
Задача. Объект создаваем тогда и только тогда, когда у него имеется вывод.
Задача. Пусть дано исчисление. Как организовать процесс выписывания всех выводов?
Задача. Пусть дано исчисление. Как организовать процесс выписывания всех порождаемых (в нем) объектов (и только их)?

Вывод

возможности допускает:
Цепочки из одной формулы (аксиомы)
Тавтологии
Все формулы □

(A → B) → ( □ A → □ B ).
Цепочки из двух формул

.
Цепочки из трех формул
.
Проверка завершения
Все подходит.
Задача. Описать все проверки подробно.
Задача. Почему определение формулы – это исчисление.

Объединение.
А: ,

Б: < Проверка возможности Б, Проверка завершения Б>.
Идея:
Создаем слова, следуя Проверке А и следуя Проверке Б,
Берем то, что создано или по той или по другой проверке.
Проблема: как не перемешивать «по ходу дела» проверки А и Б?
Выход: Метки для объектов, создаваемых по разным проверкам: Аx, Бy. Считаем, что символы А и Б в алфавит исчисления не входят.

Теоремы замкнутости для исчислений

или иную Проверку возможности , в начале символы А

или Б.
Объединим полученные проверки.
Проверка возможности допускает еще все пары <Аx,x>, где проверка завершения А допускает x, и пары <Бx, x>, где проверка завершения Б допускает x.
Задача. Проверка завершения ?
Задача. Почему пересечение (конъюнкция) проверок – проверка?
Задача. Доказать теорему для пересечения.
Задача. Как обстоит дело с дополнением?

Продолжение. Породимость объединения

это цепочка
Σ – основной алфавит Γ
Ω – вспомогательный

алфавит Γ
S – начальный символ Γ, S ∈ Ω
Σ∩Ω=Ø, объединение Σ и Ω – это алфавит Γ, обозначим его Δ.
Π – это конечное множество пар слов в алфавите Δ. Эти пары называются заменами.

вывод в исчислении начинается с S.
Для каждой

замены из Π все пары вида , где t,p – произвольные слова в алфавите Δ
Один шаг вывода состоит в замене в слове некоторого входящего в него u на v.
Проверка завершения для грамматики Γ допускает все слова в алфавите Σ.
Порождаемые слова не могут содержать букв из вспомогательного алфавита.
Описание грамматики – слово в конечном алфавите.

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

породить все цепочки из 0 и 1?
Решение. Г = 〈 Σ, Ω, П, S 〉, основной алфавит Σ = {0, 1}, вспомогательный алфавит Ω = {S },
П = {S → S 0, S → S 1, S →Λ}.
Пример вывода: S → S 0 → S 10 → S 010 → S 0010 → 0010.
Задача. Как породить все десятичные числа? (Пример десятичного числа: -3.141592.) Как породить все свободные переменные логики отношений?
Задача. Что делает грамматика с основным алфавитом {a}, вспомогательным {S, B, M, E} и заменами
П = {S → BaE, B → BM, Ma → aaM, ME → E, B → Λ, E → Λ} ?
Задача. Построить грамматику порождающую все слова, состоящие из одинакового количества букв a и b ?
Задача. Построить множество, которое породить грамматикой нельзя.