2.3 Модели формальных систем

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

1) – конъюкция, логическое И;

2) – дизъюкция, логическое ИЛИ;

3) – отрицание, логическое НЕ.

Смысл логических операций разъясняется в таблицах истинности. В качестве примера рассмотрим таблицу 1, в которой И – истина, Л – ложь.

Таблица 1 – Пример задания таблицы истинности

И	И	И	И	Л
И	Л	Л	И	Л
Л	И	Л	И	И
Л	Л	Л	Л	И

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

^.

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

^.

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

Задачей принятия решения называют кортеж (совокупность):

,

где – множество вариантов решения задачи;

– принцип предпочтения решений друг перед другом.

Решением задачи считается такой вариант решения , при котором удовлетворяется наилучшим образом.

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

Для принятия решений на основе знаний, характеризующих некоторую предметную область, их представляют в виде фактов, правил и вопросов.

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

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

Заметим, что в математике фактами и правилами называют аксиомы, а вопросы – теоремами, которые нужно доказать или опровергнуть.

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

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

Таблица 2 – Набор правил

Номер	А	B	C	D	E	F	Правило
1	+	+
2			+	+		+
3		+		+	+	+

Рассмотрим простейший пример.

Сформулируем высказывания и введем их обозначения: – деталь цилиндрической формы; – обрабатывать на токарном станке;  нужен резец.

Сформулируем базу знаний задачи в виде правил: , .

Зададимся фактами. Деталь цилиндрическая: .

Поставим вопрос. Нужен ли резец:

Теперь задачу можно записать в виде системы:

.

(8)

Решение задачи (8) можно осуществлять на любом алгоритмическом языке, включающем логические операции или с использованием графов.

Представим, например, задачу (8) в виде графа (рисунок 13).

Рисунок 13 – Задача (8) в виде графа

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

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

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

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

Стратегии поиска определяют последовательность перехода от одной вершины к другой и могут быть двух видов: в глубину и в ширину (рисунок 14).

Рисунок 14 – Стратегии поиска: а) в глубину, б) в ширину

При поиске в глубину (см. рисунок 14, а): сначала для первой родительской вершины находятся все ее потомки, затем – для второй и т.д. Такой способ поиска целесообразен, когда требуется найти любое из конечных решений. При поиске в ширину (см. рисунок 14, б) рассматриваются последовательно все вершины родительского поколения, затем все вершины дочернего поколения и т.д.

Другим методом решения задач является метод резолюций. Использование этого метода предполагает представление правил в такой форме, в которой присутствуют только отрицания и дизъюнкция. Тогда любое высказывание в базе знаний рассматривается как дизъюнкт. Логическое следствие двух дизъюнктов называют резольвентой. Если в резольвенту входит контрарная пара, например, и (рисунок 15, а), то она убирается. Если заданы противоречивые дизъюнкты, то их резольвента представляется пустым дизъюнктом (рисунок 15, б) и является тождественно-ложной.

Рисунок 15 – Получение резольвенты

Представим, например, правила задачи (8) в требуемой форме:

Перейдем от вопроса к его отрицанию (  резец не нужен) и запишем преобразованную систему:

.

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

Рисунок 16 – Решение задачи (8) методом резолюций

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

Следует заметить, что метод резолюций реализован на языке программирования Prolog (Programming in Logic), популярном у разработчиков систем искусственного интеллекта и экспертных систем.