Лекция: ВОПРОС 44. Основы математической логики.

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

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

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

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

Основными формами мышления являются понятия, суждения и умозаключения.

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

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

Суждения рассматриваются не с точки зрения их смысла и содержания, а только с точки зрения их истинности или ложности. Истинным будет суждение, в котором связь понятий правильно отражает свойства и отношения реальных объектов. «Дважды два равно четырем» — истинное суждение, а вот «Процессор предназначен для печати» — ложное. Суждения могут быть простыми и сложными. «Весна наступила, и грачи прилетели» — сложное суждение, состоящее из двух простых.

Простые суждения (высказывания) выражают связь двух понятий. Сложные — состоят из нескольких простых суждений.

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

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

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

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

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

Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например, {0, 1}). Иногда вместо термина «алгебра логики» употребляют термин «двузначная логика».

Отцом алгебры логики по праву считается английский математик XIX столетия Джордж Буль (1815-1864). Именно он построил один из разделов формальной логики в виде некоторой «алгебры», аналогичной алгебре чисел, но не сводящейся к ней. Алгебра в широком смысле этого слова — наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только над числами, но и над другими математическими объектами. Существуют алгебры натуральных чисел, многочленов, векторов, матриц, множеств и т. д.

Большой вклад в становление и развитие алгебры логики внесли Августус де Морган (1806-1871), Уильям Стенли Джевонс (1835-1882), Платон Сергеевич Порецкий (1846-1907), Чарлз Сандерс Пирс (1839-1914), Андрей Андреевич Марков (1903-1979), Андрей Николаевич Колмогоров (1903-1987) и др.

Долгое время алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 году выдающийся американский математик и инженер Клод Шеннон (1916-2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно-контактных и электронно-ламповых схем.