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

Базовыми понятиями математической логики являются «высказывание», «предикат», «логические функции» (операции), «кванторы», «логический базис», «логические законы» (законы алгебры логики).

Таблица 4.2. Функции бинарной алгебры логики

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

В простейших случаях используется два значения истинности: «истинно» — «ложно», «да» — «нет», «» — «О». Такая алгебра логики, в которой переменная может принимать только два значения истинности, называется бинарной алгеброй логики Буля (по имени ее создателя).

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

При замене переменных элементами соответствующего подмножества предикат обращается в высказывание. Обычно переменная стоит в предикативной части предложения, лежащего в основе высказывания (например, «быть Х-м карандашом», где X может принимать значения «красным», «синим» и т. д.), но в принципе это не обязательно (и возможны предикаты " X — река", где X — «Волга», «Днепр» и т. д.).

Частным случаем предиката является пропозиционная функция — функция одной или нескольких переменных, принимающих значения в множестве, состоящем из двух элементов: «», «О» .

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

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

Число простейших логических функций в конкретной алгебре логики зависит от количества значений истинности п:

Для двузначной булевой алгебры логики Л' определяется числом возможных двоичных наборов (п = 2): N = 16. При /г = 3 можно образовать N = 256 логических функций.

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

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

Таблица 4.3. Кванторы

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

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

Примеры этих теорем, или логических законов, приведены в табл. 4.4.

Таблица 4.4. Законы алгебры логики

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

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

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

Минимальными базисами бинарной алгебры логики являются базисы, включающие только две функции {—I, и}, {—I, п}. Функция отрицания не сохраняет константы ноль и единицу и не является монотонной, функции дизъюнкции и и конъюнкции п обеспечивают нелинейность и не являются самодвойственными (в силу приведенных в табл. 4.4 теорем деМоргана).

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

Па рис. 4.2 и 4.3 проиллюстрирована разная запись одного и того же алгоритма (соответствие обозначений рис. 4.2 и 4.3 приведено на рис. 4.4).

Рис. 4.4.

Этот же алгоритм может быть записан следующим образом:

Существует много форм записи логических алгоритмов: в виде функций алгебры логики (4.7), в форме таблиц или матриц, «машин Тьюринга», логических схем по А. А. Ляпунову, с помощью рекурсивных функций, на языке нормальных алгоритмов А. А. Маркова, в виде программ для вычислительных машин на одном из языков программирования, в форме диаграмм Насси — Шнайдермана.

Логические алгоритмы можно преобразовывать с использованием логических законов. Пример применения одного из законов (теоремы А. де-Моргана) приведен на рис. 4.5.

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

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

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

Таким образом, при логическом анализе задача сводится к минимизации ФАЛ, т. е. к оптимизации в некотором смысле логического алгоритма. Задача логического синтеза сложнее, она обычно решается путем последовательных приближений, а на промежуточных этапах также может быть полезна минимизация ФАЛ.

Минимизация осуществляется путем применения законов алгебры логики, приведенных в табл. 4.4. Наиболее известными методами минимизации ФАЛ являются: метод минимизирующих карт или таблиц (конъюнктивных или дизъюнктивных, импликатных); метод неопределенных коэффициентов; геометрические методы, метод Блека — Порецкого.

При возрастании числа переменных для минимизации ФАЛ применяют ЭВМ. При этом логический алгоритм нужно перевести на один из языков программирования или — при логическом анализе сложных ситуаций — разработать промежуточный язык проектирования или моделирования процессов управления.

Специфические особенности задачи логического синтеза при описании системы логическим автоматом вызвали возникновение и развитие самостоятельной научной дисциплины — теории автоматов.

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

Логические представления сыграли большую роль в развитии теоретической основы алгоритмизации и программирования. В частности, они лежат в основе теории алгорифмов (в дальнейшем — алгоритмов) А. А. Маркова. Они широко применяются при исследовании и разработке автоматов разного рода, автоматических систем контроля, при решении задач распознавания образов, при исследовании новых структур систем (в основном технических объектов), в которых характер взаимодействия между элементами еще не настолько ясен, чтобы возможно было их представление аналитическими методами, а статистические исследования либо затруднены, либо не привели к выявлению устойчивых закономерностей. На их основе развивается самостоятельный раздел теории формальных языков моделирования проблемных ситуаций и текстов.

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

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