Математична Логіка

Конспекти лекцій з математичної логике.

1. Теорія алгоритмів 1.1 Різні підходи до визначення алгоритма:

10. Неформальне поняття алгоритму (послідовність інструкцій до виконання действия).

20. Машина із необмеженим регістрами (МНР).

30 Машина Тьюринга — Посту (МТ-П).

40 Нормальні алгоритми Маркова (НАМ).

1.1.1 Машина із необмеженим регістрами (МНР).

Є якесь пристрій, у якому рахункове число осередків памяти.

(регістрів), де зберігаються цілі числа. Допустимі команды:

Z (n) — обнуління регістру Rn.

S (n) — збільшити кількість в регістрі Rn на 1.

T (m, n) — копіює вміст Rm в регистор Rn.

I (p, q, n) — якщо вміст Rp = Rq то виконується команда з номером n, якщо ні наступна. Програма для МНР мусить бути послідовністю команд Z, P. S, T, I з певним порядком, що їх последовательно.

Теза Черча (Churcha): Перше й друге визначення алгоритму еквівалентні між собою. Будь-який неформальний алгоритм то, можливо представлено програмі для МНР.

1.1.2 Машина Тьюринга — Посту. Є пристрій просматривающее нескінченну стрічку, де є осередки містять елементи алфавіту: [pic], де [pic] - порожній символ (порожній слово), котрі можуть належати і належати А. Існує також управляюча голівка (пристрій) (УУ)/(УГ), що у початковий момент лежить у певному місці, може [pic]. Також є внутрішні стану машини: [pic] Слово у цьому алфавіті - будь-яка кінцева упорядкована послідовність літер даного алфавіту, притому довжина слова на цю кількість літер у ньому (у порожнього слова довжина 0). Допустимі команди: |1) [pic], де [pic]. |Послідовність команд | |2) [pic] (зупинка програми). |називається програмою, тоді як цієї| | |послідовності не зустрічається | | |команд з лівими | | |частинами. Машина зупиняється | | |якщо вона знаходить команди з | | |лівої частиною як і поточної. |.

1.1.3 Нормальні алгоритми Маркова. Тип машини переробний слова, у якій існує певний алфавіт [pic], котрій W — безліч всіх слів. Допустимі команди: (Для машин цього важлива послідовність команд.) |[pic] де [pic] |Приклад: [pic] [pic] | | |Програма: [pic] | | |[pic] |.

1.1.4 Реалізація функції натурального змінного. [pic] [pic] однак коли ми допускаємо не скрізь певну функцію. [pic] це означатиме, що [pic] притому [pic], якщо f не визначено, те й програма має нічого видавати. [pic] [pic][pic][pic] притому [pic], якщо f не визначено, те й програма має нічого видавати. ([pic], а числа видаються як [pic], наприклад [pic] .) 1.2 Еквівалентність трьох підходів до поняття алгоритм.

1.2.1 Теорему про еквівалентність поняття вычислимой функції. [pic] вычислима: ([pic]) 1) Якщо існує програма МНР, яка обчислює цю функцію. 2) Якщо існує програма МТ-П, яка обчислює цю функцію. 3) Якщо існує програма НАМ, яка обчислює цю функцию.

Використання НАМ: [pic] [pic] [pic] [pic].

Теор.: Класи функцій вычислимых на МТ-П, з допомогою НАМ і з допомогою МНР совпадают.

Нехай [pic] яка обчислюється на МТ-П, обчислимо її в НАМ.

МТ-П: [pic].

НАМ: [pic].

Команда МТП: [pic] перетвориться за правилами: [pic] Команда МТП: [pic] [pic] [pic].

2. Булевы функції. 2.1 Основні визначення 2.1.1 Декартово твір [pic] - мн-во різноманітних упорядкованих пар елементів з Проте й У. Приклад: [pic] [pic] [pic] [pic].

2.1.2 Декартова ступінь довільного безлічі. Опр: [pic] - безліч різноманітних упорядкованих наборів довжини n, елементів безлічі А. [pic].

2.1.3 Визначення булевой функції від n змінних. Будь-яке відображення [pic] - називається булевой функцією від n змінних, притому безліч [pic] [pic].

2.1.4 Приклади булевой функції. 1) [pic] логічна сума (диз'юнкція). 2) [pic] логічне множення (сполучення). 3) [pic] складання по модулю два. 4) [pic] логічний наслідок (імплікація). 5) [pic] отрицание.

2.1.5 Основні булевы тождества.

1) [pic] (ассоциативность).

2) [pic] (коммутативность).

3) [pic] (властивість нуля).

4) [pic] (закон поглинання для 1).

5) [pic] (ассоциативность).

6) [pic] (коммутативность).

7) [pic] (властивість нуля по умножению).

8) [pic] (властивість нейтральності 1 по умножению).

9) [pic] (дистрибутивность) 10) [pic] (дистрибутивность 2) 11) [pic] (закон поглинання) 12) [pic] (Закони 13) [pic] де Моргана) 14) [pic] (закон зняття подвійного заперечення) 15) [pic] (tertium non datur — третього просто немає) 16) [pic] (асоціативність) 17) [pic] 18) [pic] 19) [pic] 20) [pic] 21) [pic] (Властивості 22) [pic] идемпотентности).

2.2 Диз’юнктивні нормальні формы.

2.2.1 Основні визначення. [pic] - кінцевий алфавіт з змінних. Розглянемо слово: [pic] Экспоненциальные позначення: [pic] [pic] - елемент конъюнкции. P. S — довжина елемента конъюнкции. ДНФ — диз’юнкція кількох різних елементарних конъюнкций. [pic] Будь-яка булева функція то, можливо представлена як ДНФ.

2.2.2 Теорему про досконалої ДНФ. Будь-яка булева функція [pic] тотожний не рівна 0 то, можливо розкладена в ДНФ наступного виду: [pic].

Опр: Носій булевой функції [pic] [pic]. Лема: [pic] 1) [pic] це елементарно [pic] 2) [pic] візьмемо набір [pic] а) [pic] б) [pic] Доказ: [pic], доводитимемо, что[pic]. 1) Доведемо, що [pic]. Візьмемо [pic] він потрапляє у число суммируемых наборів і за ним здійснюватиметься сумирование. [pic] 2) Доведемо, що [pic]. Візьмемо інший набір з [pic] [pic] Отже [pic].

2.2.3 Деякі решта видів ДНФ. Опр: [pic] - називається мінімальної ДНФ, якщо вона не має [pic] - найменшу можливу довжину із усіх ДНФ даної функции.

Опр: [pic] - називається тупикової ДНФ, коли з неї не можна викинути жодного доданка зі збереженням булевой функции.

(Легко зрозуміти, будь-яка мінімальна ДНФ тупикова, а зворотне не верно.).

Опр: К-мерной межею називається таке підмножина [pic], що є носієм деякою елементарної конъюнкции довжини: n-k.

Опр: Припустимо дана функція [pic] це і є [pic]. Межа називається завваженої, якщо цілком міститься у носії Т.

Опр: Максимальна грань — це такий грань, яка міститься жодного як і межі вищої размерности.

Пропозиція: Будь-яку відзначену грань можна вкласти у максимальну грань.

Пропозиція: [pic].

(Носій будь-який функції розкласти до об'єднання кількох граней різною размерностей).

Пропозиція: Носій будь-який функції розкладається до об'єднання всіх своїх максимальних граней. [pic].

Опр: Елементарна сполучення називається мінімальної, якщо її носій є максимальної межею. Отже всяка булева функція розкладається в диз’юнкцію всіх своїх елементарних конъюнкций.

Опр: Скорочена ДНФ — розкладання даної булевой функції на відповідні ДНФ, які відповідають об'єднанню її максимальних граней.

Теор: Мінімальна ДНФ може бути отримана з скороченою відкиданням певної кількості доданків, можливо пустого.

3 Логічні Исчисления.

3.1 Обчислення висловлювання (ИВ).

3.1.1 Определения.

[pic] [pic] [pic] Опр: V — словом в алфавіті А, називається будь-яка кінцева упорядкована послідовність його букв.

Опр: Формативная послідовність слів — кінцева послідовність слів і висловлювань [pic], якщо вони теж мають формат виду: [pic] Опр: F — формулою ІВ, називається будь-яке слово, яке у якусь формативную последовательность.

Приклад: [pic] [pic] [pic].

Опр: Аксіоми — спеціально виділений підмножина формул. [pic] 1) [pic] 2) [pic] 3) [pic] 4) [pic] 5) [pic] 6) [pic] 7) [pic] 8) [pic] 9) [pic] 10) [pic] 11) [pic].

Reg — правила виведення ІВ (деякі правила перетворення першого слова до іншого). a — символ перемінної [pic].

[pic] - довільне слово ІВ (формула).

Відображення [pic] діє отже цього разу місце кожного входження символу а.

пишеться слово [pic].

Приклад: [pic].

Правило modus ponens: [pic] [pic].

3.1.2 Формальний вывод.(простейшая модель докази теоремы).

Опр: Послідовність формул ІВ, називається формальним висновком, якщо кожна формула цієї послідовності має наступний вид:

[pic].

Опр: Виведений формулою (теоремою) ІВ називається будь-яка формула що входить у який-небудь формальний висновок. [pic] - виведена формула ИВ.

Приклад: [pic] |1) |[pic] |[pic] | |2) |[pic] |[pic] | |3) |[pic] |[pic] | |4) |[pic] |[pic] | |5) |[pic] |[pic] | |6) |[pic] |[pic] |.

Правило одночасної подстановки.

Зауваження: Якщо формула [pic] виведена, то виведена і [pic].

Візьмемо формативную послідовність виведення [pic] [pic] і додамо в неё.

[pic], отримана послідовність є формальним выводом.

(Якщо виведена [pic] то якщо [pic], то виведена [pic]).

Теор: Якщо виведена формула [pic], то [pic] ([pic] - різні символи змінних) выводима.

Виберемо [pic] - символи змінних які різні між собою і злочини не входять над жодну з формул [pic], зробимо підстановку [pic] і послідовно застосуємо [pic] і нового слові робимо послідовну підстановку: [pic], де [pic] - є формальним выводом.

3.1.3 Формальний вихід із гипотез.

Опр: Формальним висновком з гіпотез [pic](формулы), називається така послідовність слів [pic], кожна з яких задовольняє условию:

[pic].

[pic] якщо формулу [pic] можна включити в певний формальний вихід із гіпотез [pic].

Лема: [pic]; [pic]: тоді [pic].

Напишемо список:

[pic] [pic] [pic].

Лемма:[pic].

Док: [pic] [pic] [pic].

3.1.4 Теорему Дедукции.

Якщо из.

[pic] [pic].

1) і 2а) [pic], де [pic] [pic] за правилом m.p. [pic], ч.т.д.

2б) [pic] - вже виводили [pic], ч.т.д.

Базис індукції: N=1 [pic] - формальний вихід із чималого списку [pic].

[pic] (хіба що доведено), можна здійснити перехід по индукции:

[pic].

[pic] по индукции.

[pic] і з лемме 2.

[pic].

Приклад: [pic].

[pic] по теоремі дедукції [pic].

3.2 Критерій выводимости в ИВ.

3.2.1 Формулювання теоремы.

[pic] - тавтологія за будь-якої інтерпретації алфавіту (символів переменных).

[pic].

3.2.2 Поняття интерпретации.

[pic] символ перемінної [pic] [pic] зміну поставимо в соответствие.

[pic], де [pic] - проекція на [pic].

[pic].

; [pic] - лише символ змінних, т.к. це найголовніше слово формативной последовательности вида:

Де: [pic].

3.2.3 Доказ теоремы.

формальний висновок [pic].

1).

3.3 Несуперечність ІВ. 3.3.1 Определение.

1) ІВ суперечливо, якщо формула, А виведена у ньому. [pic].

2) [pic]формула виведена в ИВ)[pic]ИВ противоречиво.

3) [pic]ИВ суперечливо. ІВ несуперечливо, якщо вона є противоречивым.

Теорему: ІВ є несуперечливим обчисленням стосовно будь-якій з трьох визначень. Док-во: (1) Якщо [pic], то відповідна їй булева функція буде тотожний дорівнює 1. [pic].

(2) Якщо будь-яка формула виведена, то виведена й О, що він відповідає пункту 1. (3) Нехай [pic] і [pic] [pic] - булева функция.

[pic] - противоречие.

3.4 Формальні обчислення. Алфавіт — кінцеве чи рахункове безліч символів, можливо, розбитих на групи. Алфавіт може бути упорядкованим безліччю. Слово — кінцева упорядкована послідовність символів алфавіту, зокрема. порожній слово. V — безліч всіх слов.

Вычислимая функція і від кількох натуральних змінних [pic] (f — може бути скрізь певної) f — називається вычислимой, якщо [pic] така машина Тьюринга, що її вычисляет.

[pic] - можна розв’язати безліч, якщо характеристичне функція [pic] - є вычислимой. Безліч [pic] називається перечислимым, якщо [pic] така вычислимая функція [pic] М — вирішується [pic] М і N M перечислимы. М — перечислимо [pic] М — область визначення деякою вычислимой функції. Безліч всіх формул F — деяке можна розв’язати підмножина V. Т — рахункове безліч, якщо [pic] його биективное відображення на V. [pic] - позначення лічильного безлічі. ([pic] - алеф-нуль).

Якщо [pic] і зафіксовано биективное і вычислимое відображення [pic] (вычис.), то L — ансамбль. V — ансамбль (слова лексикографічно упорядковані і занумерованы).

Визначення: У довільному формальному обчисленні: [pic] - безліч всіх аксіом — можна розв’язати підмножина безлічі всіх формул. [pic] Правило виведення: [pic], при [pic] вирішується. Для ІВ N=2. Приклад: [pic] [pic] (порожній слово), [pic] [pic].

1 і 2 — формальні выводы.

3 — перестав бути формальним выводом.

4 Предикати і кванторы.

4.1 Визначення предиката. [pic] [pic] - висловлювання, що містить зміну. [pic] - предметна область предиката. [pic].

Нехай, А — безліч об'єктів довільній природи (предметна область предиката).

[pic]-местный предикат — довільне відображення [pic] [pic].

Безліч істинності даного предиката [pic] [pic] ;

— характеристичний функція від x на безлічі А — збігаються з предикатами.

[pic] [pic] [pic].

4.2 Поняття квантора. k — пов’язана змінна n — вільна переменная.

[pic] t — вільна, x — пов’язана. [pic], a, b, y — вільні перемінні, x — пов’язана. [pic] [pic] [pic] [pic] [pic] [pic].

4.3 Геометрична інтерпретація навішування кванторов.

|[pic] |[pic] |[pic] | | |[pic] |[pic] | | |[pic][pic] - | | | |ортогональна проекція | | | |на вісь x | |.

Пронесение заперечення через кванторы.

[pic] [pic] Геометричне «доказ »: [pic] не має здатність, що пряма [pic] повністю лежать у [pic] [pic] [pic] [pic] ч.т.д.

[pic].

[pic].

———————————- [pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

???/???-??/?[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].

[pic].