Задача получения продукции

Хорновские формулы

Определим вначале один интересный класс булевых формул - Хорновские формулы.

Определение 6.1. Пусть A - это множество логических (булевых) переменных. Хорновская (H-) формула - это формула вида

где

Содержательно, такая Хорновская формула утверждает, что из истинности всех условий набора {a₁, a₂,..., a_r}следует истинность заключения b. Утверждения такого вида находят широкое применение в различных разделах информатики. В частности, в теории баз данных такой вид имеют "функциональные зависимости", в логическом программировании - правила логических программ, в автоматическом синтезе программ - " аксиомы вычислимости". В таком же виде формулируются правила вывода во многих экспертных системах.

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

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

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

Предложение 6.1. H-формула является следствием множества H -формул F тогда и только тогда, когда формула

(*)

является истинной на всех наборах значений переменных (т.е. тождественно истинной).

Доказательство непосредственно следует из определения значений конъюнкции и импликации.

Как уже отмечалось в п.3, проблема проверки по булевой формуле ее тождественной истинности является весьма сложной. Известный нам метод такой проверки с помощью построения таблицы значений на всех наборах переменных практически не работает уже для формул с несколькими десятками переменных. В то же время во многих практических задачах число логических параметров исчисляется сотнями. Оказывается, что для установления тождественной истинности формул вида (*) или, что то же самое, для задачи проверки условия для H -формул имеется простой и очень эффективный алгоритм, позволяющий ее решать для формул с сотнями и тысячами переменных.

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

Задача получения продукции

Пусть задано некоторое множество A={ a₁, a₂,..., _N} имен товаров (продуктов, сырья и т.п.) и имеется некоторое множество F технологических процессов (производств), описывающих возможности получения одних продуктов из других. Каждый технологический процесс задается множеством исходных продуктов (входов) этого процесса и результирующим продуктом (выходом) , т.е. процесс t позволяет из исходных продуктов L_t получить продукт b_t - его выход. Будем задавать технологический процесс в виде t: L_t -> b_t. Продукт, полученный в одном процессе, может далее использоваться в других процессах.

Определение 6.3. Задача получения продукции состоит в том, чтобы выяснить по заданному набору исходных продуктов и результирующему продукту можно ли с помощью технологических процессов из F получить выход y по входным продуктам из X.

(Можно обобщить эту задачу и рассматривать возможность получения по X некоторого множества результирующих продуктов .)

Пример 6.1. Пусть A= { дерево, клей, гвозди, кирпич, стекло, окна, полы, стены, крыша, столы}. Множество технологических процессов F={t₁, t₂, t₃, t₄, t₅, t₆} задается соответствующими множествами входов и выходов.

• t₁: { дерево, клей, гвозди } -> столы
• t₂: { дерево, гвозди} -> полы
• t₃: { дерево, клей, стекло} -> окна
• t₄: { стены, полы, крыша} -> дача
• t₅: { кирпич, окна, дерево} -> стены
• t₆: { дерево, гвозди } -> столы

Рассмотрим для этой системы технологических процессов задачу получения продукта дача по исходному множеству продуктов: {дерево, клей, гвозди, стекло, кирпич, крыша}.

Нетрудно понять, что эта задача решается положительно с помощью следующей цепочки процессов: t₃; t₅; t₂; t₄. Действительно, в t₃ получаются окна, которые используются в t₅ для получения стен, в t₂ производятся полы, а затем произведенные ранее стены, полы, крыша используются в t₄ для получения результата дача.

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

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

Будем рассматривать A как множество булевых переменных. Каждому процессу t с параметрами L_t={a₁,..., a_r} и b_t сопоставим следующую H-формулу :

Например, процессу t₅ из нашего примера соответствует формула :

Сохраним для множества H -формул, соответствующих процессам, обозначение F.

Справедлива следующая теорема, которая показывает, что задача о возможности получения продукции и задача о следствии из множества H-формул эквивалентны.

Теорема 6.1. Для любых множества продуктов A, множества технологических процессов F, множества исходных продуктов и результирующего продукта задача получения продукта y по входным продуктам из X с помощью процессов из F разрешима тогда и только тогда, когда , где

Доказательство Предположим, что с помощью набора процессов из множества F={t₁,..., t_h } из множества исходных продуктов X можно получить y. Пусть - это последовательность процессов из F, которая приводит к получению y. Докажем, что тогда . Рассмотрим произвольный набор значений переменных , на котором истинны все формулы из F. Если хотя бы для одной переменной ее значение , то формула истинна, поскольку ее левая часть ложна. Предположим теперь, что для любой переменной ее значение .

Тогда индукцией по номеру r процесса в покажем, что для каждого r=1,..., m значение соответствующей результирующей переменной . Действительно, при r=1 из применимости процесса следует, что , но тогда для любой переменной и левая часть импликации истинна на наборе . Но так как и вся формула истинна на , то и ее заключение тоже истинно на , т.е. . Пусть теперь для некоторого k > 1\ при r < k. Докажем, что и . Поскольку процесс применим после процессов , то . Тогда все переменные из истинны на и, следовательно, .

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

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

Шаг 0. Положим , X₀=X.

Шаг 1. Положим и .

Пусть уже определены и X_i.

Шаг i+1. Положим , и (процессы внутри упорядочиваются в произвольном порядке).

Если или X_i=X_i+1, то положим и закончим процедуру.

Заметим вначале, что эта процедура построения обязательно завершится через конечное число шагов, так как размер X_i не может превысить размер множества всех продуктов A. Покажем, что процесс построения завершится на таком шаге (i+1), для которого впервые , т.е. что последовательность процессов приводит к производству y. Действительно, предположим, что процедура завершилась после этапа (i+1) из-за выполнения равенства X_i=X_i+1 (при этом . Покажем, что тогда существует набор значений переменных на котором все формулы из Fистинны, а формула ложна. Положим при и при . Так как , то для каждого значение , а так как , то , т.е. формула на наборе ложна. Каждая формула \ для истинна, поскольку и, следовательно, . Ложной могла бы оказаться лишь такая формула , для такого процесса , у которого заключение . Но для такого процесса t обязательно имеется продукт , который не входит в X_i (иначе бы b_t попало в X_i+1 и процедура не остановилась бы на (i+1) -ом шаге). Для этого a значение . Но тогда условие импликации ложно на , а вся формула на нем истинна. Таким образом, мы пришли к противоречию, которое показывает, что и процесс приводит к производству y.