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

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