Шпаргалка по "Математическая логика"

L_Lawliet

L_Lawliet19@bk.ru

Аннотация

Великолепные ответы

Ответы на вопросы экзамена

Математическая  логика

 

 

Оглавление

1. Логика традиционная и математическая логика. Предмет математической логики. История развития математической логики. 2

2. Высказывания и логические операции над ними. Таблицы истинности. 3

3. Понятие формулы алгебры высказываний. Порядок выполнения логических операций. 3

4. Логическая равносильность формул. Основные равносильности. Закон двойственности. 4

5. Дизъюнктивная нормальная форма и совершенная 'дизъюнктивная нормальная форма (ДНФ и СДНФ). 5

6. Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма (КНФ и СКНФ). 5

7. Критерии тождественной истинности и ложности формулы. 5

8. Понятие булевой функции. Способы задания булевых функций. 6

9. Нормальные формы булевых функций. 6

10. Принцип двойственности для булевых функций. Самодвойственные функции. 7

11. Системы булевых функций. Специальные классы булевых функций. Теорема Поста. 7

12. Формальные аксиоматические теории. Основные этапы построения. 8

13. Исчисление высказываний как формальная аксиоматическая теория. Алфавит, формулы и подформулы исчисления высказываний. 8

14. Система аксиом исчисления высказываний. Основные и производные правила вывода. 9

15. Определение доказуемой (выводимой) формулы. Примеры доказательств. 10

16. Построение выводов из совокупности формул. Правила выводимости. Теорема дедукции. 10

17. Связь алгебры высказываний с исчислением высказываний. 11

18. Разрешимость и непротиворечивость исчисления высказываний. 12

19. Полнота исчисления высказываний. Независимость системы аксиом исчисления высказываний. 13

20. Другие формализации исчисления высказываний. 13

 

 

1. Логика  традиционная и математическая логика. Предмет математической логики. История  развития математической логики.

 
Логика  – наука о способах доказательств и опровержений; совокупность научных теорий, в каждой из которых рассматриваются определенные способы доказательств и опровержений. 
 
Логика изучает познавательную деятельность человека. 
 
Традиционная логика - этап в развитии формальной логики, связанный с анализом элементарных структур мышления, выведения доказательства и правил предупреждения логических ошибок в рамках естественных языков и простейших приемов символизации. Она не использует формализованных языков, как это делает математическая логика. 
 
Традиционная логика при получении новых знаний использует следующие логические методы: анализ, синтез, дедукция, абстрагирование, конкретизация, аналогия и сравнение. 
 
Характерным для математической логики является использование формальных языков с точным синтаксисом и чёткой семантикой. С помощью специального языка формул достигается адекватное описание логической структуры доказательства и осуществляется построение строгих логических теорий. Математическая логика базируется на логике высказываний и ее расширении – логике предикатов.

История развития математической логики.

Как самостоятельная наука, логика оформилась в трудах греческого философа Аристотеля (384 – 322 гг. до н.э.). 

В XIX в. - начале XX в. в логике произошла научная революция и на смену традиционной логике пришла современная логика, называемая также математической или символической логикой. Развитие математики выявило недостаточность Аристотелевой логики и поставило задачу о ее дальнейшем построении на математической основе. Впервые в истории идеи о таком построении логики были высказаны немецким математиком Готфридом Лейбницем (1646 — 1716)   в конце XVII века. Он считал, что основные понятия логики должны быть обозначены символами, которые соединяются по определенным правилам, и это позволяет всякие рассуждения заменить вычислением. Джордж Буль  (1815 - 1864)  в своей работе «Исследование законов мысли» (1854 г.) истолковывал умозаключения как результат решения логических равенств, в результате чего логическая теория приняла вид обычной алгебры и  получила название алгебры высказываний. Буль рассматривал свою алгебру как инструмент изучения законов человеческого мышления.

Введение символических  обозначений в логику имело для  этой науки такое же решающее значение, как и введение буквенных обозначений  для математики. Именно благодаря  введению символов в логику была получена основа для создания новой науки  — математической логики. Предметом  математической логики служат рассуждения, при изучении которых она пользуется математическими методами.

При этом на первых порах  развитие математической логики позволило  представить логические теории в  новой удобной форме и применить  вычислительный аппарат к решению  задач, малодоступных человеческому  мышлению, что, конечно, расширило область  логических исследований. Однако главное  назначение математической логики определилось в конце XIX века, когда стала ясна необходимость обоснования понятий  и идей самой математики. Эти задачи имели логическую природу и, естественно, привели к дальнейшему развитию математической логики.

В этом отношении показательны работы немецкого математика Готлоба Фрёге (1848 -1925) и итальянского математика Джузеппе Пеано (1858 - 1932), которые применили математическую логику для обоснования арифметики и теории множеств.

В развитие логики значительный вклад внесли Бертран Рассел (1872 – 1970), А. Уайтхед (1861 – 1947), Д. Гильберт (1862 – 1943), К. Гёдель (1906 – 1978), А. Тарский (1901 – 1983) и др.

2. Высказывания  и логические операции над ними. Таблицы истинности.

Под высказыванием понимают повествовательное предложение, про которое можно сказать, что оно либо истинно, либо ложны.Восклицательные и вопросительные предложения высказываниями не являются.

 

Высказывание  представляющее собой одно утверждение  называется простым.

Высказывание ,которое получается из элементарных с помощью грамматических связок называется сложным (составным).

 

С помощью  пяти логических операций можно образовать сложные высказываний.

Основные:

Отрицание:    НЕ А, ¬А, NOT A, А'

Дизъюнкция:    А или B, А V B, А|В, А+В, A OR В

Конъюнкция:   А и B, А^В, А & В, А * В, A AND В

Импликация:    А —>, А => В

Эквивалентность:  А ~ B, А <=> В, А = В

Таблица истинности операций

   A    B  ¬А А∧В А∨В А⇒В А⇔В

1 1 0 1 1 1 1

1 0 0 0 1 0 0

0 1 1 0 1 1 0

0 0 1 0 0 1 1

Дополнительные:

Штрих Шеффера:  |

Стрелка Пирса: ↓

Кольцевая сумма: ⊕

Таблица истинности дополнительных операций

     A       B     А|B    А↓В    А⊕В 

1 1 0 0 0

1 0 1 0 1

0 1 1 0 1

0 0 1 1 0

3. Понятие формулы алгебры высказываний. Порядок  выполнения логических операций.

Определение 2.1

Теперь дадим  точное определение формулы алгебры высказываний.

1. Каждая отдельно взятая пропозициональная переменная есть формула алгебры высказываний.
2. Если  и  — формулы алгебры высказываний, то выражения также являются формулами алгебры высказываний: ¬F₁ , F₁^ F₂, F₁ V F₂, F₁-> F₂, F₁ <-> F₂.
3. Никаких других формул алгебры высказываний, кроме получающихся согласно пунктам 1 и 2, нет.

 

Приведем  примеры выражений, не являющихся формулами. Это в каком-то смысле нелепые  выражения. К примеру, выражение (XY)->Z было бы формулой на основании п. 2 определения 2.1, если бы формулами были выражения (XY)  и Z. Выражение Z есть пропозициональная переменная и потому на основании п. 1 определения 2.1 является формулой. Рассмотрим выражение (XY). Оно было бы формулой, если бы между формулами  X и Y стоял один из знаков логических связок. Но такого знака нет. Следовательно, выражение (XY) не формула, и исходное выражение (XY)->Z  формулой также не является.

 

Порядок выполнения операций

1. инверсия (отрицание, логическое не),
2. конъюнкция (логическое и),
3. дизъюнкция (логическое или),
4. импликация (следование),
5. эквивалентность (тождество).

4. Логическая  равносильность формул. Основные равносильности. Закон двойственности.

Определение: Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулы элементарных высказываний (переменных).

Обозначение: A≡B

Определение. Формула A называется тождественно истинной (тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.

Определение. Формула A называется тождественно ложной (противоречием), если она принимает значение 0 при всех значениях входящих в нее переменных.

Определение. Формула A называется выполнимой (опровержимой), если существует такой набор значений ее переменных, при которых формула A принимает истинное (ложное) значение.

I. Основные равносильности
1	x ˄ x ≡ x	Законы идемпотентности
2	x ˅x ≡ x
3	x ˄ 1≡ x	Законы нуля и еденицы
4	x ˅ 1 ≡ 1
5	x ˄ 0 ≡ 0
6	x ˅ 0 ≡ x
7	x ˄ x ≡ 0	Закон протеворечия
8	x ˅ x ≡ 1	Закон исключённого третьего
9	x ≡ x	Закон двойного отрицания
10	x ˄ ( y ˅ x ) ≡ x	Законы поглощения
11	x ˅ ( y ˄ x ) ≡ x
12	( x ˄ y ) ˅ ( x ˄ y) ≡ x	Формулы расщепления
13	(x ˅ y ) ˄ ( x ˅ y) ≡ x
II. Равносильности, выражающие одни логические операции через другие
1	x ↔ y ≡ (x → y) ˄ (y → x)	Основная формула доказательств  теорем существования
2	x → y ≡ x ˅ y
3	x ˄ y ≡ x ˅ y	Законы де Моргана
4	x ˅ y ≡ x ˄ y
5	x ˄ y ≡ x ˅ y
6	x ˅ y≡ x ˄ y
III. Равносильности, выражающие основные законы алгебры высказываний
1	x ˄ y ≡ y ˄ x	Коммутативные законы
2	x ˅ y ≡ y ˅ x
3	x ˄ (y ˄ z)≡ (x ˄ y) ˄ z	Ассоциативные законы
4	x ˅ (y ˅ z) ≡ (x ˅ y) ˅ z
5	x ˄ (y ˅ z) ≡ (x ˄ y) ˅ (x ˄ z)	Дистрибутивные законы
6	x ˅ (y ˄ z) ≡ (x ˅ y) ˄ (x ˅ z)
7	x → y ≡ y → x	Закон контрапозиции

 

Закон двойственности:

Определение : Формулы A и A* называются двойственными формулами, если А* получается из А путем замены в ней каждой операции на двойственную.

5. Дизъюнктивная нормальная форма и совершенная 'дизъюнктивная нормальная форма (ДНФ  и СДНФ).

Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые.

Всякую дизъюнкцию элементарных конъюнкций  
Назовём дизъюнктивной нормальной формой, то есть ДНФ. 

 

Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами

1. Каждое  логическое слагаемое формулы  содержит все переменные, входящие  в функцию F(x₁,x₂,...x_n)

2. Все логические  слагаемые формулы различны

3. Ни одно  логическое слагаемое не содержит  переменную и её отрицание

4. Ни одно  логическое слагаемое формулы  не содержит одну и ту же  переменную дважды.

6. Конъюнктивная нормальная форма и совершенная  конъюнктивная нормальная форма (КНФ  и СКНФ).

Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые.

Всякую конъюнкцию элементарных дизъюнкций  
Назовём конъюнктивной нормальной формой, то есть КНФ.

Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:

1. Все элементарные дизъюнкции  содержат все переменные, входящие  в функцию F(x₁,x₂,...x_n)

2. Все элементарные дизъюнкции  различны

3. Каждая элементарная  дизъюнкция содержит переменную  один раз

4. Ни одна элементарная  дизъюнкция не содержит переменную  и её отрицание

7. Критерии  тождественной истинности и ложности формулы.

Все формулы  алгебры логики делятся на три  класса:

1. тождественно истинные,
2. тождественно ложные и
3. выполнимые.

Формулу А называют выполнимой, если она принимает значение «истина» хотя бы на одном наборе значений входящих в нее переменных и не является тождественно истинной.

 

Алгоритм  определения класса формулы А

1.Применить критерий тождественной истинности к формуле А. Если А - тождественно истинная, 
то задача решена. В противном случае перейти к шагу 2.