Логика высказываний и булевы алгебры (Boolean Algebra and Logic)

Лекции – 18 часов
Практические занятия – 18 часов
Лабораторные работы – 18 часов
Экзамен

ВВЕДЕНИЕ

Математическая логика (ее называют также формальной логикой, теорией доказательств) изучает законы и формы корректных человеческих рассуждений.
Этот раздел математики имеет особое значение в изучении математических наук.

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

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

Главная цель математической логики − дать точное и адекватное определение понятия "математическое доказательство".
Поскольку математика является наукой, в которой все утверждения доказываются с помощью умозаключений, математическая логика может представляться как инструмент (как совокупность средств) для описания правил построения множества других математических теорий.

С точки зрения построения математической теории весь комплекс знаний в некоторой предметной области удобно разделить на две части:
Содержательная часть теории (семантика).
Формальная часть теории (синтаксис).

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

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

Пример.
Рассмотрим цепочку логических рассуждений:
- из А следует В;
- из С следует А.
Вывод: из С следует В.
Эта цепочка рассуждений может иметь практически любое содержание.

Например:
Все люди смертны.
Сократ − человек.
Следовательно, Сократ смертен.
Все студенты сдали сессию.
Петров − студент.
Следовательно, Петров сдал сессию.

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

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

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

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

История развития
Интерес к логике возник еще в VI − IV вв. до н.э. Оформление же ее как самостоятельной науки произошло в трудах греческого философа Аристотеля (384 − 322 гг. до н.э.), который в своих "Аналитиках" систематизи-ровал известные до него сведения, и эта система стала впоследствии называться формальной логикой.

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

Развитие математики выявило недостатки логики, разработанной Аристотилем, и потребовало дальнейшего ее развития. Идеи о построении логики на математической основе были высказаны немецким математиком
Г. Лейбницем (1646 − 1716) в конце XVII века.

Он считал, что основные понятия логики должны быть обозначены символами, которые соединяются по особым правилам. Это позволит всякое рассуждение заменить вычислением.
Лейбниц говорил: «Мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, что­бы облегчить сам процесс нашего мышления».

Первая реализация идей Лейбница, положившая начало современному аппарату математической логики (точнее, алгебре логики), принадлежит английскому ученому Дж. Булю (1815 − 1864). Он создал алгебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний.

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

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

Существенное развитие математическая логика получила в работах Г.Фреге (1848 − 1925), посвященных теории формальных языков, и Д.Пеано (1858 − 1932), который применил математическую логику для обоснования арифметики и теории множеств.

Однако особое значение этот раздел математики приобрел после инициативы Д.Гильберта (1862 − 1943), выступившего в 20-х годах прошлого века с программой обоснования математики на базе математической логики, именно с этого момента и начинается активное развитие современной математической логики.

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

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

Для математиков это открытие логических парадоксов, затронувших основы теории множеств. Распространение аксиоматического метода в построении различных математических теорий, в первую очередь геометрии, а затем арифметики, теории групп и т.д.
В аксиоматическом построении математической теории предварительно выбираются некоторая система базовых понятий и отношения между ними. Эти понятия и отношения часто называются основными. Далее без доказательства принимаются основные положения рассматриваемой теории − аксиомы. Все дальнейшее содержание теории выводится логически из аксиом.

Впервые аксиоматическое построение математической теории было предпринято Евклидом в построении геометрии.

Изложение этой теории в «Началах» Евклида не безупречно. Евклид здесь пытается дать определение исходных понятий (точки, прямой, плоскости).
В доказательстве теорем используются нигде явно не сформулированные положения, которые считаются очевидными. Таким образом, в этом построении отсутствует необходимая логическая строгость, хотя истинность всех положений теории не вызывает сомнений.
Такой подход к аксиоматическому построению теории оставался единственным до XIX века, позднее появляются различные варианты неклассических логик.

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

Первым идею применимости математической логики для формального описания сложных цепей, состоящих из технических объектов, вступающих в дискретные отношения, высказал в 1910 г. профессор С.-Петербургского университета П.Эренфест. Он предложил описывать релейные схемы, имевшие уже в то время большое значение для техники связи, с помощью аппарата логики. Но поскольку эти цепи были довольно примитивны и не требовали для своей разработки теоретической базы, идеи Эренфеста были надолго забыты.

И лишь в 1938 г. американский инженер К.Шеннон использовал на практике алгебру логики Дж. Буля для анализа и расчета релейных схем.
В дальнейшем достижения математической логики стали использоваться при создании технических средств для информационных и вычислительных систем.
Кроме того, результаты, полученные в логической теории языков, применяются при создании формальных языков программирования и элементов искусственного интеллекта.

Рекомендуемая литература по курсу