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

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

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

Л.Э. Гуревич, Э.Б. Глинер

Введение

Слово «логика» всем хорошо знакомо. Его часто можно встретить на страницах всевозможных печатных изданий, услышать в разговорной речи. Что же означает это слово? Заглянем в толковый словарь С.И. Ожегова. Там сказано: «Логика – наука о законах мышления и его формах» и еще – «Логика – ход рассуждений». Если второе толкование смысла слова «логика» более или менее понятно каждому, то в связи с первым сразу возникает вопрос: а что такое формы и законы мышления?

Подобно Журдену из пьесы Мольера «Мещанин во дворянстве», который очень обрадовался, узнав, что всю жизнь говорит прозой, вам будет приятно узнать, что в большинстве случаев вы мыслите и говорите по законам логики.

Слово «логика» происходит от греческого logos, что, с одной стороны, означает «слово», а с другой – «мысль, рассуждение». Логика изучает акты мышления, зафиксированные в языке в виде слов, предложений и их совокупностей. Таким образом, логика имеет непосредственное отношение к языку, речи, т.е. соприкасается с грамматикой и, более широко, с лингвистикой (наукой о языке). С помощью логических средств наш естественный язык уточняется, приобретает четкость и определенность. Как справедливо заметил польский логик А.Тарский, – логика создает возможность лучшего взаимопонимания между теми, кто к этому стремится.

Многим хорошо известно, что логика – неотъемлемая составная часть математики. Без логики в математике – ни шагу: ни тебе теорему доказать, ни формулу вывести, ни задачу решить. Ироническая фраза: «Нематематики считают, что математики считают» намекает на то, что основное занятие математиков – вовсе не счет (как многие полагают), а логические или, иначе говоря, дедуктивные рассуждения – выводы, доказательства. (Слово дедукция происходит от латинского deduction, что значит – выведение). С помощью логики математики выводят из уже имеющихся в их распоряжении математических фактов новые факты.

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

Логика входит в арсенал методов любой науки, является частью ее методологии. Многие естественнонаучные факты были открыты с помощью логики.

Однако в математике логика выступает в наиболее отчетливом, нестертом, незавуалированном виде, а ее «удельный вес» несравненно больше, чем в естественных науках. В математической теории количество предложений, содержащих исходное знание (аксиом), сводится к минимуму; основное же содержание теории заключено в предложениях, полученных в результате логических рассуждений (теоремах). Поэтому математику называют дедуктивной наукой в отличие от естественных наук (физики, химии, биологии), в которых основной, ведущий метод – эксперимент. Впрочем, естественные и даже многие гуманитарные науки по мере своего развития все более активно и плодотворно используют математические и логические методы, а возможность представления содержания какой-либо науки (или ее раздела) в виде аксиоматической теории считается показателем высокой степени развития этой науки. Как полагал великий немецкий философ Эммануил Кант (1724-1804 гг.), – «каждая наука в той или иной мере является наукой, в какой мере содержит математику». Быть может, это сказано слишком сильно, однако, этой фразой емко и выразительно определено значение математики для других наук и ее место среди них. Недаром другой знаменитый ученый, наш соотечественник, физик Лев Ландау (1908-1968 гг.) назвал математику «наукой сверхъестественной».

Итак, логика в большей или меньшей степени используется как один из методов в любой науке. Необходима логика и в повседневной жизни. С ее помощью обеспечивается полноценное (адекватное) общение в мире людей и компьютеров. Логика присутствует или, по крайней мере, должна присутствовать в любом споре, судебном разбирательстве, расследовании преступления (Шерлок Холмс и его дедуктивный метод!).

В высшей степени важна логика в законотворчестве: формулировка закона должна исключать возможность его неоднозначного толкования. «Логика – это необходимый инструмент, освобождающий от лишних, ненужных запоминаний, помогающий найти в массе информации то ценное, что нужно человеку. Без логики – это слепая работа» – так сказал о роли логики в познавательной, в частности в учебной деятельности, академик П. Анохин.

Почему же логика – столь универсальный инструмент, полезный, более того – необходимый в любой интеллектуальной деятельности? Чем объясняется ее общезначимость? Рассмотрим три рассуждения.

1. Все насекомые – шестиногие. У паука – не шесть ног (а восемь!). Следовательно, паук не насекомое.

2. Все числа, кратные 10, оканчиваются нулем. Число п не оканчивается нулем. Следовательно, число п не кратно 10.

3. Все отличники в Петином классе занимаются спортом. Петя не занимается спортом. Следовательно, Петя – не отличник.

Все эти короткие, одношаговые рассуждения (умозаключения) имеют одну и ту же форму: Все А – это В; не В. Следовательно, не А. Умозаключение такой формы всегда приводит к верному (истинному) выводу (заключению, следствию), если исходные утверждения (посылки) истинны. Формы рассуждений, обладающие свойством «перерабатывать» любые истины в новые истины, называются правильными. Логика дает нам свод правильных форм основных, простейших рассуждений (умозаключений) и правила построения из них сколь угодно длинных и сложных дедуктивных рассуждений, которые применимы в любой области знаний. Этим и объясняется универсальность и «вездесущность» логики, ни с чем не сравнимое многообразие сфер ее применения.

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

Логика как наука сформировалась очень давно – в IV в. до н.э. Ее создал древнегреческий ученый Аристотель. В течение многих веков логика сколько-нибудь существенно не развивалась. Это, конечно, свидетельствует о гениальности Аристотеля, которому удалось создать столь полную научную систему, что, казалось, «не убавить, не прибавить». Однако в силу такой неизменности логика приобрела славу мертвой, застывшей науки и вызывала у многих скептическое к себе отношение. Сухость и кажущуюся закостенелость, бесплодность логики высмеяли в своих бессмертных произведениях Ф. Рабле и Д. Свифт («Гаргантюа и Пантагрюэль» и «Путешествие Гулливера»). В XVII в. великий немецкий ученый Готфрид Лейбниц (1646-1716) задумал создать новую логику, которая была бы «искусством исчисления». В этой логике, по мысли Лейбница, каждому понятию соответствовал бы символ, а рассуждения имели бы вид вычислений. Эта идея Лейбница, не встретив понимания современников, не получила в то время распространения и развития.

Только в середине XIX в. ирландский математик и логик Джордж Буль (1815-1864) частично воплотил в жизнь идею Лейбница. Им была создана алгебра логики, в которой действуют законы, схожие с законами обычной алгебры, но буквами обозначаются не числа, а предложения. На языке булевой алгебры можно описывать рассуждения и «вычислять» их результаты; однако, ею охватываются далеко не всякие рассуждения, а лишь определенный тип их, в некотором смысле – простейший.

Алгебра логики Буля явилась зародышем новой науки – математической логики. В отличие от нее логику, восходящую к Аристотелю, называют традиционной или классической формальной логикой. Таким образом, математическая логика – это логика, использующая язык и методы математики.

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

Формулы логики высказываний

В логике высказываний – первом и основном разделе математической логики – элементарные высказывания рассматриваются как нерасчленяемые «атомы», а составные высказывания – как молекулы, образованные из «атомов» применением к ним логических операций. Логика высказываний интересуется единственным свойством элементарных высказываний – их значением истинности; составные же высказывания изучаются ею со стороны их логической структуры, отражающей способ, которым они образованы. Структура составных высказываний определяет зависимость их значений истинности от значений истинности составляющих элементарных высказываний.

Так как смысл высказываний математическую логику не интересует, их вполне можно заменить переменными.

Пусть X, Y,…, Z,…, X_i, Y_i,…, Z_i – переменные, вместо которых можно подставить любые элементарные высказывания (или их значения истинности). Такие переменные называют пропозициональными или высказывательными переменными. С помощью высказывательных переменных и символов логических операций любое высказывание можно формализовать, т.е. заменить формулой, отражающей его логическую структуру.

Начнем с того, что уточним понятие формулы логики высказываний. Для этого зададим алфавит, т.е. набор символов, которые мы будем употреблять в логике высказываний:

1) Х, Y,…, Z,…, X_i, Y_i,…, Z_i (i – натуральное число) – символы для обозначения высказывательных переменных;

2) И, Л, 1, 0 – символы, обозначающие логические константы «истина» и «ложь»;

3) – символы логических операций;

4) (,), [, ] – скобки (вспомогательные символы, служащие для указания порядка выполнения операций).

Дадим теперь строгое определение формулы логики высказываний (будем говорить формула ЛВ):

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

При вычислении значения формулы ЛВ логические операции (если нет скобок) вычисляются в определенном порядке:

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

Пример 10: Даны формулы. Определить порядок вычисления формул:

1. . Порядок вычисления следующий:

1) отрицание ; 2) конъюнкция ; 3) дизъюнкция ; 4) импликация и, наконец, эквиваленция .

2. . Порядок вычисления следующий:

1) отрицание ; 2) импликация ; 3) конъюнкция ; 4) дизъюнкция ; и 5) эквиваленция .

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

Для начала научимся определять количество строк в таблице. Если высказывание одно, то оно может принимать только два значения истинности – «истина» и «ложь», поэтому строк в такой таблице 3 (две строки для значений переменной и строка заголовка). Примером такой таблицы служит таблица истинности в определении негации. Если переменных в формуле две, то они могут принимать одновременно такие значения: оба высказывания истинны, первое – истинно, а второе – ложно, первое – ложно, а второе – истинно и, наконец, оба они могут быть ложными. Число строк в такой таблице равно 5 (плюс строка заголовка). Вообще, число наборов значений, которые могут принимать п переменных, находится как 2^п.

Сформулируем алгоритм построения таблицы истинности сложного высказывания:

1. Вычислить количество строк и столбцов в таблице истинности.

Пусть в формуле п различных переменных и k операций. Переменные считаем каждую только один раз, а символы операций – все, сколько есть. Тогда число строк в таблице равно 2^п + 1 (число наборов значений переменных плюс строка заголовка), а число столбцов в таблице равно n + k.

2. Начертить таблицу.

3. Заполнить строку заголовка.

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

4. Заполнить оставшиеся строки таблицы, начиная с первого столбца.

При вычислении значений промежуточных формул, надо помнить, что в каждой операции участвует не более двух формул (может быть и не элементарных).

Пример 11: Составить таблицы истинности для формул: 1) ; 2) .

1. . Эта формула содержит 2 различные переменные (К и С) и 4 символа логических операций, т.е. n = 2 и k = 4. Тогда строк в таблице 2² + 1 = 4 + 1 = 5, а столбцов – 2 + 4 = 6. Рисуем таблицу:

Определим порядок выполнения операций: 1) отрицание ; 2) дизъюнкция ; 3) конъюнкция и 4) импликация .

Заполняем строку заголовка, начиная с элементарных формул:

К	С

По-другому строка заголовка может выглядеть так:

К	С

Заполняем первый столбик значениями истинности переменной К, для этого число пустых строк делим пополам (4: 2 = 2) и в половине пишем значение «истина», а в оставшейся половине – «ложь»:

К	С

Заполняем второй столбик значениями истинности переменной С. Для этого число пустых строк делим на 4 (4: 4 = 1) и попеременно записываем в строки по одному значению «истина» и «ложь» таким образом, чтобы каждому значению истинности переменной К соответствовали оба значения истинности переменной С:

К	С

Начиная с третьего столбика, заполняем строки результатами выполнения операций. В третьем столбике записываем результат выполнения операции отрицания . При этом смотрим на соответствующие значения переменной С:

К	С

В четвертом столбике записываем результаты выполнения дизъюнкции , обращая внимание на значения истинности переменных К и С в соответствующей строке:

К	С

В пятом столбике записываем результаты выполнения операции конъюнкции . При этом используем значения истинности соответствующих операций из третьего и четвертого столбиков:

К	С

И, наконец, в шестом столбике записываем результаты выполнения итоговой операции импликации , используя результаты предыдущей операции конъюнкции и значения истинности переменной К:

К	С

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

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

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

Л.Э. Гуревич, Э.Б. Глинер

Введение

Слово «логика» всем хорошо знакомо. Его часто можно встретить на страницах всевозможных печатных изданий, услышать в разговорной речи. Что же означает это слово? Заглянем в толковый словарь С.И. Ожегова. Там сказано: «Логика – наука о законах мышления и его формах» и еще – «Логика – ход рассуждений». Если второе толкование смысла слова «логика» более или менее понятно каждому, то в связи с первым сразу возникает вопрос: а что такое формы и законы мышления?

Подобно Журдену из пьесы Мольера «Мещанин во дворянстве», который очень обрадовался, узнав, что всю жизнь говорит прозой, вам будет приятно узнать, что в большинстве случаев вы мыслите и говорите по законам логики.

Слово «логика» происходит от греческого logos, что, с одной стороны, означает «слово», а с другой – «мысль, рассуждение». Логика изучает акты мышления, зафиксированные в языке в виде слов, предложений и их совокупностей. Таким образом, логика имеет непосредственное отношение к языку, речи, т.е. соприкасается с грамматикой и, более широко, с лингвистикой (наукой о языке). С помощью логических средств наш естественный язык уточняется, приобретает четкость и определенность. Как справедливо заметил польский логик А.Тарский, – логика создает возможность лучшего взаимопонимания между теми, кто к этому стремится.

Многим хорошо известно, что логика – неотъемлемая составная часть математики. Без логики в математике – ни шагу: ни тебе теорему доказать, ни формулу вывести, ни задачу решить. Ироническая фраза: «Нематематики считают, что математики считают» намекает на то, что основное занятие математиков – вовсе не счет (как многие полагают), а логические или, иначе говоря, дедуктивные рассуждения – выводы, доказательства. (Слово дедукция происходит от латинского deduction, что значит – выведение). С помощью логики математики выводят из уже имеющихся в их распоряжении математических фактов новые факты.

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

Логика входит в арсенал методов любой науки, является частью ее методологии. Многие естественнонаучные факты были открыты с помощью логики.

Однако в математике логика выступает в наиболее отчетливом, нестертом, незавуалированном виде, а ее «удельный вес» несравненно больше, чем в естественных науках. В математической теории количество предложений, содержащих исходное знание (аксиом), сводится к минимуму; основное же содержание теории заключено в предложениях, полученных в результате логических рассуждений (теоремах). Поэтому математику называют дедуктивной наукой в отличие от естественных наук (физики, химии, биологии), в которых основной, ведущий метод – эксперимент. Впрочем, естественные и даже многие гуманитарные науки по мере своего развития все более активно и плодотворно используют математические и логические методы, а возможность представления содержания какой-либо науки (или ее раздела) в виде аксиоматической теории считается показателем высокой степени развития этой науки. Как полагал великий немецкий философ Эммануил Кант (1724-1804 гг.), – «каждая наука в той или иной мере является наукой, в какой мере содержит математику». Быть может, это сказано слишком сильно, однако, этой фразой емко и выразительно определено значение математики для других наук и ее место среди них. Недаром другой знаменитый ученый, наш соотечественник, физик Лев Ландау (1908-1968 гг.) назвал математику «наукой сверхъестественной».

Итак, логика в большей или меньшей степени используется как один из методов в любой науке. Необходима логика и в повседневной жизни. С ее помощью обеспечивается полноценное (адекватное) общение в мире людей и компьютеров. Логика присутствует или, по крайней мере, должна присутствовать в любом споре, судебном разбирательстве, расследовании преступления (Шерлок Холмс и его дедуктивный метод!).

В высшей степени важна логика в законотворчестве: формулировка закона должна исключать возможность его неоднозначного толкования. «Логика – это необходимый инструмент, освобождающий от лишних, ненужных запоминаний, помогающий найти в массе информации то ценное, что нужно человеку. Без логики – это слепая работа» – так сказал о роли логики в познавательной, в частности в учебной деятельности, академик П. Анохин.

Почему же логика – столь универсальный инструмент, полезный, более того – необходимый в любой интеллектуальной деятельности? Чем объясняется ее общезначимость? Рассмотрим три рассуждения.

1. Все насекомые – шестиногие. У паука – не шесть ног (а восемь!). Следовательно, паук не насекомое.

2. Все числа, кратные 10, оканчиваются нулем. Число п не оканчивается нулем. Следовательно, число п не кратно 10.

3. Все отличники в Петином классе занимаются спортом. Петя не занимается спортом. Следовательно, Петя – не отличник.

Все эти короткие, одношаговые рассуждения (умозаключения) имеют одну и ту же форму: Все А – это В; не В. Следовательно, не А. Умозаключение такой формы всегда приводит к верному (истинному) выводу (заключению, следствию), если исходные утверждения (посылки) истинны. Формы рассуждений, обладающие свойством «перерабатывать» любые истины в новые истины, называются правильными. Логика дает нам свод правильных форм основных, простейших рассуждений (умозаключений) и правила построения из них сколь угодно длинных и сложных дедуктивных рассуждений, которые применимы в любой области знаний. Этим и объясняется универсальность и «вездесущность» логики, ни с чем не сравнимое многообразие сфер ее применения.

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

Логика как наука сформировалась очень давно – в IV в. до н.э. Ее создал древнегреческий ученый Аристотель. В течение многих веков логика сколько-нибудь существенно не развивалась. Это, конечно, свидетельствует о гениальности Аристотеля, которому удалось создать столь полную научную систему, что, казалось, «не убавить, не прибавить». Однако в силу такой неизменности логика приобрела славу мертвой, застывшей науки и вызывала у многих скептическое к себе отношение. Сухость и кажущуюся закостенелость, бесплодность логики высмеяли в своих бессмертных произведениях Ф. Рабле и Д. Свифт («Гаргантюа и Пантагрюэль» и «Путешествие Гулливера»). В XVII в. великий немецкий ученый Готфрид Лейбниц (1646-1716) задумал создать новую логику, которая была бы «искусством исчисления». В этой логике, по мысли Лейбница, каждому понятию соответствовал бы символ, а рассуждения имели бы вид вычислений. Эта идея Лейбница, не встретив понимания современников, не получила в то время распространения и развития.

Только в середине XIX в. ирландский математик и логик Джордж Буль (1815-1864) частично воплотил в жизнь идею Лейбница. Им была создана алгебра логики, в которой действуют законы, схожие с законами обычной алгебры, но буквами обозначаются не числа, а предложения. На языке булевой алгебры можно описывать рассуждения и «вычислять» их результаты; однако, ею охватываются далеко не всякие рассуждения, а лишь определенный тип их, в некотором смысле – простейший.

Алгебра логики Буля явилась зародышем новой науки – математической логики. В отличие от нее логику, восходящую к Аристотелю, называют традиционной или классической формальной логикой. Таким образом, математическая логика – это логика, использующая язык и методы математики.

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