- •1. Предмет и задачи науки логики. Логика и мышление. Логические парадоксы. Силлогизмы.
- •2. Основные этапы развития логики. Классическая и современная логики.
- •3. Понятие математической логики. Ее место и роль среди других наук.
- •4. Понятие формализации. Алфавиты, слова, языки.
- •5. Формальные теории: определение, построение.
- •6. Вывод в формальной теории. Интерпретация, полнота и непротиворечивость формальной теории.
- •7. Алгебра высказываний. Пропозициональные формулы.
- •8. Интерпретация, тавтология, противоречие. Логическое следование и логическая эквивалентность.
- •9. Удаление и восстановление скобок в ПФ
- •10. Законы логики.
- •11. Понятие теоремы. Основная теорема логического вывода и ее доказательство.
- •12. Основная теорема логического вывода
- •13. !!! Ошибочные доказательства и парадоксы.
- •14. Дедуктивные и индуктивные доказательства. Примеры индуктивных доказательств.
- •15. Силлогизмы с точки зрения формальной теории.
- •16. Формальная теория для исчисления высказываний.
- •17. Метод резолюций в логике высказываний.
- •18. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов.
- •19. Ограниченные предикаты
- •20. Метод резолюций в логике предикатов
- •21. Формальная теория для исчисления предикатов
- •22. !!! Диаграммы Венна (Эйлера) и их использованиие.
- •23. Формальная арифметика. Непротиворечивость формальной арифметики. Теорема Генцена.
- •24. Неклассические логики: модальная, темпоральная, нечеткая.
- •25. Логическое программирование.
- •26. Теорема Геделя о неполноте и суть ее доказательства.
- •27. Понятие алгоритма. Свойства алгоритмов. Способы записи алгоритмов.
- •28. Сложность алгоритма. Оценки сложности: двусторонняя, односторонняя. Классификация алгоритмов по сложности.
- •29. Классы сложности P, NP. Трудно решаемые задачи и способы их решения
- •30. Понятие алгоритмической системы. Понятие вычислимости.
- •31. Частично-рекурсивные функции. Тезис Черча.
- •33. Машина Тьюринга: определение, построение, использование. Тезис Тьюринга.
- •34. !!! Примеры использования машины Тьюринга.
- •35. !!! Задачи, не решаемые компьютерами. Тест Тьюринга для систем искусственного интеллекта.
3. Понятие математической логики. Ее место и роль среди других наук.
Мат. Логика – современная форма логики, целиком опирающаяся на формальный математический метод. Она изучает только умозаключения, для которых можно однозначно решить, истинны они или ложны.
Предметом логики являются высказывание, суждение о различных объектах.
Высказывание - это повествовательное предложение, в котором что-то утверждается или отрицается относительно предметов. Высказывания могут быть истинными И или ложными Л.
Примеры: Земля - планета Солнечной системы. (Истинно); Каждый параллелограмм есть квадрат (Ложно)
Существуют два основных подхода к установлению истинности высказываний: эмпирический (опытный) и логический. При эмпирическом подходе истинность высказывания устанавливается с помощью наблюдений, измерений, проведением экспериментов. Логический подход заключается в том, что истинность высказывания устанавливается на основе истинности других высказываний, то есть без обращения к фактам, к их содержанию, то есть формально. Такой подход основан на выявлении и использовании логических связей между высказываниями, входящими в рассуждение.
Рассмотрим пример.
Имеется настольная лампа с выключателем, подсоединенная к розетке. При нажатии на выключатель лампочка не загорается. Начинаем разбираться в чем дело.
1. Для того, чтобы лампочка горела, необходимо совместное соблюдение следующих условий (каждое из которых есть высказывание):
•выключатель включен (A)
•лампочка исправна (B1)
•вилка исправлена (B2)
•электричество присутствует (В3)
•розетка исправна (B4)
Если A,B1,B2,В3,B4 имеют место, то лампочка должна гореть, то есть высказывание ‖лампочка горит‖ (С) также истинно. На языке логики мы можем написать это как Если A и B1 и B2 и B3 и B4, то - (D).
2. В нашем случае высказывание С ложно (из наблюдения).
3.Если D истинно, а С - ложно, то ложно высказывание A и B1 и B2 и B3 и B4 (логическое рассуждение).
4.Отсюда следует, что ложно хотя бы одно из высказываний A , B1 , B2 , B3 , B4, то есть истинно высказывание: ‖не A или не B1 или не B2 или не B3 или не B4‖ (логическое рассуждение).
5.Поскольку А - истинно (из опыта), опытным путем можно проверить истинность других 4-х высказываний.
6.Если высказывания В оказываются истинными, а лампочка не горит, то следует логический вывод: гипотеза D неверна и нуждается в пересмотре (например рассмотреть неисправность шнура и патрона).
7.Если некоторые высказывания В оказываются ложными, то после устранения соответствующих неисправностей лампочка должна загореться.
4. Понятие формализации. Алфавиты, слова, языки.
Понятие формализации
При использовании разговорного языка при передачи знаний от одного человека к другому возможно появление неоднозначностей. В то же время знание требует однозначного восприятия, поэтому ФОРМАЛИЗАЦИЯ – процесс перехода от словесного описания к более точному символьному.
При формализации надо некоторое множество символов, из которых по некоторым правилам составляются слова формального языка, некоторые слова принимаются за исходные (их смысл не может оспариваться), кроме того задается набор правил по которым из одного слова можно получать другое. Многократно применяя эти правила, из одних истин мы получаем другие.
Формализация теорий связана с отказом от употребления естественного языка, таящего много неопределенностей. То, что проделано по формальным правилам, легко поддается проверке. Если все этапы последовательных формальных преобразований выдержали проверку, то достоверность связи между исходными и окончательными выражениями сомнений не вызывают. Нельзя спорить по поводу самих правил или исходных выражений теории, ибо формальный подход исключает необходимость ссылок на смысл или истинность правил и выражений.
Так, в цепочке преобразований (a + b)(a - b) = a(a - b) + b(a - b) = a2 - ab + ba - b2 = a2 - b2 использовано:
Во-первых, целый набор равенств, выражающих свойства чисел и операций над ними:
Во-вторых, применен общий принцип подстановки: если выражение содержит в себе другое выражение, а выражение получается заменой на равное ему выражение D, то выражения и равны.
В-третьих, цепочка равенств A=B=C=D представляет сокращенную запись равенств:
A = B, B = C, C = D.
В-четвертых, неявно использован еще один принцип: если A = B и B = C, то A = C. Его двукратное применение позволяет придти к равенству: (a + b)(a - b) = a2 - b2
Алфавиты, слова, языки
Формальные теории, не пользуясь естественным (разговорным) языком, нуждаются в собственном формальном языке, на котором записываются встречающиеся в нем выражения. Опишем используемые для этого средства:
Алфавит - конечное множество A = {a1, a2, ..., an}, элементы которого называются буквами или символами.
Слово в алфавите - любая конечная последовательность символов α=b1b2b3...bk, где bi €A, для i = 1...k. Слово может состоять только из одной буквы, а может вообще не содержать букв, тогда оно называется пустым и обозначается λ(Е). Число букв в слове ' называется его длиной и обозначается | λ |. В частности, | λ |= 0.
Множество всех слов в алфавите A, включая пустое слово, обозначается A*. Любое подмножество множества A*. называется языком в алфавите A, а совокупность правил, позволяющих установить принадлежность слова языку, - грамматикой этого языка. Иногда такую грамматику называют распознающей, в отличие от порождающей грамматики, позволяющей выписывать произвольные слова данного языка и только их. Порождение и распознавание должно осуществляться эффективно, то есть за конечное и небольшое число шагов.