Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Ответы на экзамен A4.pdf
Скачиваний:
262
Добавлен:
28.03.2015
Размер:
1.14 Mб
Скачать

Оглавление

1.

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

 

Силлогизмы..........................................................................................................................

3

2.

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

5

3.

Понятие математической логики. Ее место и роль среди других наук. ....................

7

4.

Понятие формализации. Алфавиты, слова, языки. ......................................................

9

5.

Формальные теории: определение, построение.........................................................

11

6.

Вывод в формальной теории. Интерпретация, полнота и непротиворечивость

 

формальной теории. ..........................................................................................................

12

7.

Алгебра высказываний. Пропозициональные формулы. ..........................................

15

8.

Интерпретация, тавтология, противоречие. Логическое следование и логическая

эквивалентность. ...............................................................................................................

18

9.

Удаление и восстановление скобок в ПФ...................................................................

21

10. Законы логики..............................................................................................................

23

11. Понятие теоремы. Основная теорема логического вывода и ее доказательство. 25

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

26

13.

!!! Ошибочные доказательства и парадоксы. ...........................................................

27

14.

Дедуктивные и индуктивные доказательства. Примеры индуктивных

 

доказательств. ....................................................................................................................

28

15.

Силлогизмы с точки зрения формальной теории. ...................................................

30

16.

Формальная теория для исчисления высказываний. ...............................................

31

17.

Метод резолюций в логике высказываний. ..............................................................

33

18.

Синтаксис и семантика языка логики предикатов. Формулы логики предикатов.

.............................................................................................................................................

 

35

19.

Ограниченные предикаты ..........................................................................................

37

20.

Метод резолюций в логике предикатов ....................................................................

39

21.

Формальная теория для исчисления предикатов .....................................................

40

22.

!!! Диаграммы Венна (Эйлера) и их использованиие..............................................

42

23. Формальная арифметика. Непротиворечивость формальной арифметики.

 

Теорема Генцена................................................................................................................

43

24.

Неклассические логики: модальная, темпоральная, нечеткая................................

45

25. Логическое программирование..................................................................................

47

26.

Теорема Геделя о неполноте и суть ее доказательства. ..........................................

48

27. Понятие алгоритма. Свойства алгоритмов. Способы записи алгоритмов. ...........

50

28.

Сложность алгоритма. Оценки сложности: двусторонняя, односторонняя.

 

Классификация алгоритмов по сложности.....................................................................

51

29.

Классы сложности P, NP. Трудно решаемые задачи и способы их решения .......

55

30.

Понятие алгоритмической системы. Понятие вычислимости................................

57

31.

Частично-рекурсивные функции. Тезис Черча. .......................................................

59

33.

Машина Тьюринга: определение, построение, использование. Тезис Тьюринга.61

34.

!!! Примеры использования машины Тьюринга. .....................................................

63

35.

!!! Задачи, не решаемые компьютерами. Тест Тьюринга для систем

 

искусственного интеллекта. .............................................................................................

63

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например:

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

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

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

Следовательно, все а суть с.”

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

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

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

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

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

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

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

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

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

3-й этап Современный (20век — …) связан с XX веком и попытками обосновать справедливость математических доказательств, с исследованиями теории

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