Вопросы к экзамену математическая логика

Вопросы к экзамену по «математической логике и теории алгоритмов»

1. Предмет и задачи
науки логики. Логика и мышление. Логические
парадоксы.

Силлогизмы.

Логика — Logos (греч.) — слово, понятие,
рассуждение, разум, наука о правильном
мышлении, как правильно мыслить, чтобы
получать истинные знания. Логика изучает
абстрактное мышление как средство
познания объективного мира, исследует
формы и законы, в которых происходит
отражение мира в процессе мышления.

Человек может приобретать знания 3-мя
способами:

• Опытный (чувствительный) – ощущает и
  выражает свои мысли, при этом предметы
  воспринимаются в том виде, в котором
  они являются человеку.

• Авторитетный – человек получает знания
  от кого-то и верит ему, т. К. этот человек
  пользуется авторитетом.

• Логический – позволяет из истинного
  знания получить истинное знание путем
  лог7ического мышления.

Три основных формы мышления:

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

• Суждение — мысль, повествовательное
  предложение в котором что-либо
  утверждается или отрицается
  относительно понятий.

• Умозаключение — прием мышления,
  когда из одного или нескольких
  исходных высказываний мы получаем
  новое.

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

Логические парадоксы:

«Некто говорит: ’’я лгу’’. Если он при
этом лжет, то сказанное им есть ложь, и
, следовательно он не лжет. Если же он
не лжет, то то сказанное им есть истина,
и следовательно, он лжет. В любом случае
оказывается, что он лжет и не лжет
одновременно.»

Парадокс военного парикмахера: « Приказ:
стричь призывников должен только
парикмахер, но кто пострижет его, он же
тоже призывник…»

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

Например:

Все млекопитающие имеют скелет.→Все
киты — млекопитающие.→Следовательно,
все киты имеют скелет.

Все квадраты – ромбы → все ромбы —
параллелограммы→Следовательно, все
квадраты — параллелограммы.

В общем виде этот силлогизм имеет форму:
”Все а суть в,
все в суть с.
Следовательно, все а суть
с.”

Пример силлогизма неправильной формы:
Все квадраты — ромбы. →Некоторые ромбы
имеют острый угол. →Следовательно,
некоторые квадраты имеют острый угол.

2.
Основные этапы развития логики.
Классическая и современная логики.

1-й этап Классический (4век до Н.Э. – 16
век Н.Э.) связан с работами ученого и
философа Аристотеля. Он пытался найти
ответ на вопрос ”как мы рассуждаем”,
изучал ”правила мышления. Он подверг
анализу человеческое мышление, его
формы — понятие, суждение, умозаключение
и рассмотрел мышление со стороны
строения, структуры, то есть с формальной
стороны. Так возникла формальная
логика. Формальная логика связана с
анализом наших обычных содержательных
умозаключений, выражаемых разговорным
языком. Аристотель исследовал различные
формы рассуждений и их комбинаций, ввел
понятие силлогизма, т.е. рассуждения,
в котором из заданных двух суждений
выводится третье. Например:

Все млекопитающие имеют скелет.→Все
киты — млекопитающие.→Следовательно,
все киты имеют скелет.

Все квадраты – ромбы → все ромбы —
параллелограммы→Следовательно, все
квадраты — параллелограммы.

Пример силлогизма неправильной формы:
Все квадраты — ромбы. →Некоторые ромбы
имеют острый угол. →Следовательно,
некоторые квадраты имеют острый угол.

Логика, основанная на теории силлогизмов
называется классической. Доказано, что
общее число силлогизмов, которые можно
составить из рассуждений указанного
вида, равно 256, из них правильными являются
лишь 24.

В конце XVI в. чтобы облегчить выполнение
алгебраических преобразований, была
создана буквенная символика. Точно
также, чтобы облегчить проверку и
преобразование сложных цепочек
рассуждений, было создано особое
буквенное исчисление, которое получило
название алгебры логики.

2-й этап Переходный (17век – 19 век Н.Э.)
— появление математической или
символической логики. Основы ее заложил
немецкий ученый и философ Г. В. Лейбниц.
Он попытался построить первые логические
исчисления, считал, что можно заменить
простые рассуждения действиями со
знаками и привел правила. Но Лейбниц
высказал только идею, а развил ее
окончательно англичанин Джордж Буль.
Буль считается основоположником
математической логики как самостоятельной
дисциплины. В его работах логика обрела
свой алфавит, свою орфографию и грамматику.
Недаром начальный раздел математической
логики называют алгеброй логики, или
булевой алгеброй.

3-й этап Современный (20век — …) связан
с XX веком и попытками обосновать
справедливость математических
доказательств, с исследованиями теории
чисел, а также с попыткой разрешить
известные логические парадоксы. Самым
знаменитым следует считать парадокс
лжеца. «Некто говорит: ’’я лгу’’. Если
он при этом лжет, то сказанное им есть
ложь, и, следовательно он не лжет. Если
же он не лжет, то то сказанное им есть
истина, и следовательно, он лжет. В любом
случае оказывается, что он лжет и не
лжет одновременно.» Развитие математической
логики особенно активизировалось в
XX нашего века в связи с развитием
вычислительной техники и программирования.

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.
Понятие формализации. Алфавиты, слова,
языки.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

НА ЭКЗАМЕНЕ МОЖНО ПОЛЬЗОВАТЬСЯ:

1. Списком правил вывода и поиска вывода в натуральном исчислении.

2. Списком правил вывода в секвенциальном исчислении.

ВОПРОСЫ.

1. Язык логики предикатов: синтаксис и семантика. (Формула, свобод-

ные и связанные вхождения переменных, замкнутая формула, интерпретация.

Примеры вычисления истинности формул в конечных интерпретациях.)

2. Модель, контрпример, общезначимость и логическое следование.

(Содержательный смысл логического следования. Теорема о дедукции. Приме-

нение теоремы о дедукции к незамкнутым формулам.)

3. Поиск логического вывода в секвенциальном исчислении. (Примеры

построения выводов и контрпримеров. Пример формулы, не являющейся общез-

начимой и не имеющей конечных контрпримеров.)

4. Корректность секвенциального исчисления. (Понятие корректности

исчисления. Теорема о корректности.)

5. Полнота секвенциального исчисления. (Понятие полноты исчисления.

Стандартная стратегия поиска вывода. Теорема о полноте.)

6. Исчисление натурального вывода как модель содержательного дока-

зательства. (Примеры натуральных выводов и соответствующих им содержа-

тельных доказательств. Исключение гипотез. Особенности применения пра-

вил, вводящих и уничтожающих кванторы.)

7. Поиск логического вывода в натуральном исчислении. (Правила по-

иска вывода. Примеры построения выводов по этим правилам.)

8. Корректность натурального исчисления. (Понятие корректности ис-

числения. Теорема о корректности.)

9. Полнота натурального исчисления. (Понятие полноты исчисления.

Теорема о полноте.)

10. Эквивалентные преобразования в логике предикатов. (Отношение эк-

вивалентности. Три вида эквивалентности логических формул, связь между

ними.)

11. Теоремы об отношении эквивалентности |=(А>B)&(В>A). (Пары экви-

валентных формул, замена эквивалентных подформул, приведение к предва-

ренной и конъюнктивной нормальным формам.)

12. Теоремы об отношениях эквивалентности |=А<=>|=B и А|=<=>B|=.

(Замыкание формул кванторами общности, приведение к скулемовской нор-

мальной форме.)

13. Поиск логического вывода методом резолюций. (Общая схема и при-

меры построения выводов.)

14. Корректность метода резолюций. (Понятие корректности исчисле-

ния. Теорема о корректности.)

15. Полнота метода резолюций. (Понятие полноты исчисления. Теорема

о полноте.)

16. Эрбрановские интерпретации. (Эрбрановские универсум и базис.

Теорема о невыполнимости в эрбрановских интерпретациях. Теорема Эрбрана)

17. Логика высказываний: синтаксис, семантика, секвенциальный вы-

вод. (Логика высказываний как частный случай логики предикатов. Истин-

ностные таблицы. Секвенциальное исчисление для логики высказываний: от-

личия поиска вывода и построения контрпримеров от логики предикатов.)

18. Дедуктивный поиск ответов на вопросы. (Примеры поиска ответов

на вопросы методом резолюций. Неконструктивность классической логики и

ее конструктивность по отношению к логическим программам.)

19. Модели множеств хорновских дизъюнктов. (Примеры эрбрановских

базисов, универсумов и моделей множеств хорновских дизъюнктов. Теорема о

пресечении эрбрановских моделей.)

20. Наименьшая эрбрановская модель. (Теорема об устройстве наимень-

шей эрбрановской модели множества хорновских дизъюнктов. Содержательный

смысл и примеры построения наименьшей эрбрановской модели.)

21. Декларативная семантика Пролога. (Теоремы главном свойстве наи-

меньшей эрбрановской модели и о декларативной семантике.)

22. Подстановки и унификаторы. Наиболее общий унификатор. (Теорема

о композиции подстановок. Алгоритм унификации. Теорема об алгоритме уни-

фикации.)

23. SLD-резолюция: поиск логического вывода. (Примеры построения

SLD-выводов. SLD-резолюция, как стратегия метода резолюций.)

24. Корректность SLD-резолюции.

25. Полнота SLD-резолюции с правилом выбора.

26. Полнота SLD-резолюции с наиболее общим унификатором.

27. Процедурная семантика Пролога. (Примеры построения SLD-деревь-

ев. Стандартная стратегия построения SLD-дерева. Примеры программ, для

которых стандартная стратегия неполна.)

28. Семантика операторов fail, cut и not. Гипотеза замкнутости ми-

ра.

29. Алгоритмическая полнота Пролога.

30. Теорема Черча о неразрешимости логики предикатов.

ТИПИЧНЫЕ ЗАДАЧИ.

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

2. Построить модель/контрпример формулы.

3. Построить вывод формулы в натуральном/секвенциальном исчислении.

4. Построить вывод формулы методом резолюций.

5. Написать Пролог-программу.

6. Построить наименьшую эрбрановскую модель для Пролог-программы.

7. Построить дерево вычислений для Пролог-программы.

Предложите, как улучшить StudyLib

(Для жалоб на нарушения авторских прав, используйте

другую форму
)

Материал из Викиконспекты

Перейти к: навигация, поиск