Тема3: Элементы математической логики

Тема3: Элементы математической логики

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Высказывания и операции над высказываниями

Высказывание – это повествовательное предложение (утверждение), о котором можно говорить, что оно истинно или ложно.

Пример 1. А: «Москва – столица России» – истинное высказывание. b = «Волга впадает в Черное море» – ложное высказывание. Значения истинности высказываний обозначаются буквами И – «истина» и Л –… Не всякое предложение является высказыванием. Так, к высказываниям не относятся вопросительные, и восклицательные…

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

Рассмотрим предложения: «Он рыжеволос» и «Число делится на 7». Эти предложения не содержат переменных в явном виде, но, тем не менее, являются высказывательными формами: первое из них становится высказыванием (истинным или ложным) только после замены местоимения «он» именем конкретного человека из некоторого множества людей мужского пола; второе становится высказыванием, если вместо слова «число» подставлять целые числа. Иначе эти предложения можно записать так: «Человек х рыжеволос», «Число у делится на 7».

Из высказывательных форм можно получать высказывания также с помощью специальных слов, так называемых кванторов. Их два: 1) квантор всеобщности – (любой, всякий, каждый); 2) квантор существования – (существует, найдется, имеется, некоторый, по меньшей мере, один). Например, из высказывательной формы «Площадь комнаты 20 м²» можно с помощью кванторов получить высказывания: «Площадь любой комнаты 20 м²» – ложное, «Существует комната, площадь которой 20 м²» – истинное.

Из двух данных предложений можно образовывать новые предложения с помощью союзов «и», «или», «либо», «если…, то…», «…тогда и только тогда, когда…» и других. С помощью частицы «не» и словосочетания «неверно, что…» из одного предложения можно получить новое. Наиболее употребительными являются союзы «и», «или», «если…, то…» и «…тогда и только тогда, когда». Остальные союзы считают близкими по смыслу одному из перечисленных союзов.

Союзы «и», «или», «если, то», «тогда и только тогда, когда», а также частицу «не» (словосочетание «неверно, что») называют логическими связками.

Пример 2. Из предложений «Солнце всходит на востоке» и «Солнце заходит на западе» можно получить следующие составные высказывания: «Солнце всходит… В грамматике различают предложения простые и сложные. Предложение, простое по… Возникает вопрос: как определить значение истинности сложного высказывания?

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

По числу логических связок выделяют пять логических операций.

1 Негация (отрицание) – единственная операция, которая может применяться к одному высказыванию.

Негацией высказывания называется новое высказывание, которое истинно тогда и только тогда, когда само высказывание ложно и ложно, когда само высказывание истинно.

Негация обозначается , или ¬b, читается: «не А» или «неверно, что А».

Например, высказывание А = «Луна – спутник Марса» – ложное, а высказывание = «Неверно, что Луна – спутник Марса» – истинное.

Для произвольного высказывания А определение удобно записывать с помощью так называемой таблицы истинности:

А

Пример 3. Сформулировать отрицание высказываний: А = «Курган – большой город»; В = «Сыр делают из молока»; С = «32 не делится на 4»; D = «Все дети любят манную кашу».

Решение. = «Неверно, что Курган – большой город»; = «Сыр делают не из молока»; = «32 делится на 4».

2Конъюнкция (логическое умножение) – от латинского conjunctio – соединение.

Конъюнкцией двух высказываний называется новое высказывание, которое истинно тогда и только тогда, когда оба высказывания истинны.

Таблица истинности для конъюнкции выглядит следующим образом: А В   … Пример 4.Определить значение истинности высказываний «Париж расположен на Сене… Решение. Первое высказывание является конъюнкцией двух высказываний А = «Париж расположен на Сене» и В = «2 + 3 = 5».…

Дизъюнкцией двух высказываний является новое высказывание, которое ложно тогда и только тогда, когда оба высказывания ложны.

Таблица истинности для дизъюнкции выглядит следующим образом: А В   … Пример 5.Определить значение истинности высказываний «Париж расположен на Сене… Решение. Первое высказывание является дизъюнкцией двух высказываний А = «Париж расположен на Сене» и В = «2 + 3 = 5».…

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

Таблица истинности импликации выглядит так: А В   … Пример 6. Чтобы запомнить правило нахождения значения истинности импликации,… 1) = «Если дождь идет, то асфальт мокрый» = 1;

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

Эквиваленция обозначается или , читается «А тогда и только тогда, когдаВ».

Таблица истинности для эквиваленции выглядит так:

А	В

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

Пример 7.Пусть через А обозначено высказывание «9 делится на 3», а через В – высказывание «10 делится на 3». Составьте высказывания, имеющие логическую структуру: а) ; б) ; в) ; г) ; д) ; е) и определите их значения истинности.

Решение. а) = «Если 9 делится на 3, то 10 делится на 3» = 0, т.к. А = 1, а В = 0. б) = «Если 10 делится на 3, то 9 делится на 3» = 1. в) = «9 делится на 3 тогда и только тогда, когда 10 делится на 3» = 0. г) = «10 делится на 3 тогда и только тогда, когда 9 делится на 3» = 0. д) = «Если 9 не делится на 3, то 10 делится на 3» = 1 (т.к. А = 1, то = 0 и В = 0, следовательно, = 1). е) = «9 делится на 3 тогда и только тогда, когда 10 не делится на 3» = 1 (А = 1 и = 1, тогда = 1).

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

Так как смысл высказываний математическую логику не интересует, их вполне можно заменить переменными. Пусть X, Y,…, Z,…, Xi, Yi,…, Zi – переменные, вместо которых можно подставить… Начнем с того, что уточним понятие формулы логики высказываний. Для этого зададим алфавит, т.е. набор символов,…

Всякая высказывательная переменная – формула ЛВ.

Символы И, Л, 1, 0 – формулы ЛВ.

Если F – формула ЛВ, то - формула ЛВ.

Если F1 и F2 – формулы ЛВ, то , , и - формулы ЛВ.

Никаких других формул в логике высказываний нет.

Условимся для упрощения записей не заключать в скобки формулы, не являющиеся частями других формул или стоящие под знаком отрицания. Заметим, что в… Опишем процедуру формализации высказываний: 1 Если высказывание – простое, то ему ставится в соответствие элементарная формула.

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

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

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) и попеременно записываем в строки по одному значению «истина» и «ложь» таким образом, чтобы каждому значению истинности переменной К соответствовали оба значения истинности переменной С:

К	С

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

К	С

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

К	С

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

К	С

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

К	С

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

Формулы, принимающие значение «истина» при всех наборах значений входящих в нее переменных, называются тождественно истинными или тавтологиями.

2 . Данная формула содержит 3 различные переменные и 4 символа логических операций. Число строк в таблице – 23 + 1 = 8 + 1 = 9. Число столбцов –… Определим порядок выполнения операций: 1) отрицание ; 2) отрицание ; 3)… Заполняем первый столбик значениями истинности переменной А, для этого число пустых строк делим пополам (8 : 2 = 4) и…

Формулы F1 и F2 называются равносильными, если их эквиваленция – тавтология.

Проверить, равносильны ли формулы, можно двумя способами: 1) составить их эквиваленцию и с помощью таблицы истинности проверить, не является ли она… Пример 12. Проверить, являются ли формулы и равносильными. Решение.