Модель поиска новых технических решений

 

Для поиска ФПД (или новых технических решений) необходимо использовать некоторую модель представления и хранения знаний, в которой учитывают:

- физико-технические эффекты ФТЭ;

- физические операции ФО;

- базу параметров;

- приборы измерения параметров;

- приборы изменения параметров, которые фактически представляют собой реализованные технические решения;

Имеется прямое соответствие между операцией Коллера в ФО и объектом в ФТЭ. Для большего удобства операцию Коллера E и объект B следует заключить в одну структуру, объединив таким образом ФО и ФТЭ.

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

Покажем общую структуру поиска, представленную на следующем рисунке.

 

 

Рисунок 1. Поиск цепочек при известных ФТЭ

 

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

 

Абдукция

 

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

Пусть ABD и OBS - некоторые множества формул пропозициональных формул. Элементы ABD представляют собой те формулы, которые могут быть результатами абдукции; они называ­ются абдуцентами. Элементами OBS служат те формулы, которые могут представлять результа­ты наблюдений. Пусть KB - некоторое конечное множество формул, называемое базой знаний; КВ = {α₁, α₂, …, α_n}.

Задача абдукции заключается в поиске таких формул X Î ABD, что множество KB и {X} вы­полнимо (логически непротиворечиво) и что из KB u {X}логически следует данное наблюдение δ Î OBS. (При этом предполагается, что наблю­дение δ не следует из КВ). Ясно, что следует пред­почитать кратчайшие и логически минимальные формулы X.

Задачу абдукции можно сформулировать так:

Найти все кратчайшие логически сильнейшие решения X Î ABD уравнения

α₁ & α₂, … α_n & X & ~δ ==0,

не являющийся решением уравнения

α₁ & α₂, … α_n & X ==0

Рассмотрим также задачу дедукции в следую­щей форме. Пусть KB = { α₁, α₂, …, α_n } - база зна­ний и GL - некоторое множество формул, рассма­триваемых как цели дедукции. Нужно найти все кратчайшие и логически минимальные формулы X Î GL, которые логически следовали бы из КВ. Переформулируем задачу:

Найти все кратчайшие и логически сильнейшие решения X Î GL уравнения

α₁ & α₂, … α_n & ~X ==0

Этих два примера имеют общую форму:

Пусть Φ[Х] и Ψ[X] - какие-либо формулы, составленные из обычных логических свя­зок и пропозициональных переменных, а также с использованием метапеременной X,значениями которой служат формулы от пропозициональных переменных, входящих в формулы Φ и Ψ. Пусть C- некоторое мно­жество формул (от тех же пропозицио­нальных переменных). Нужно найти все кратчайшие и логически сильнейшие фор­мулы из C, которые служат решениями уравнения Ф[Х] = = 0, но не являются реше­ниями уравнения Ψ [Х] = = 0.

Эту общую задачу обозначим Z(Φ, Ψ, C). Рассмотрим некоторые подходы к решению этой задачи.

1. Уравнение Ф[Х]==0. Формулу Ф[Х] можно разложить по переменной X:.

Ф[Х] = = Ф[1] & X v Ф[0] & ~X.

где Ф[0] и Ф[1] - формулы, полученные из Ф[Х] подстановками X=0 и X=1.

Доказывая справедливость логической экви­валентности, заметим, что в произвольной интерпретации I будем иметь

I(Ф[1] & X v Ф[0] & ~X) = I(Ф[1]) & I(X) v I(Ф[0]) & ~I(X)

Возможны два случая: I(X)=0, I(X)=1. В первом случае имеем

I(Ф[1] & X v Ф[0] & ~X) = I(Ф[1]) & 0 v I(Ф[0]) & 1 = I(Ф[0]) = I(Ф[X]),

а во втором

I(Ф[1] & X v Ф[0] & ~X) = I(Ф[1]) & 1 v I(Ф[0]) & 0 = I(Ф[1]) = I(Ф[X]).

Таким образом, в обоих случаях Ф[Х] и Ф[1] & X v Ф[0] & ~X имеют одинаковые значения в интерпретации I.

2. Решение задачи Z(Φ, Ψ, C). Мы рассматриваем здесь эту задачу в самом общем случае, ког­да Ф и Ψ - произвольные формулы, содержащие
метапеременную X, а С- множество всех формул. Метод решения этой задачи включает 5 этапов.

Этап 1. Подставляя 0 и 1 вместо X в формулу Ф[Х], получаем Ф[0] и Ф[1], которые затем упрощаем, применяя правила замены ~~αÞα; α& 0Þ0; α & 1Þα; α v 0Þα; α v 1Þ1; 0→α =1; α ↔ 0Þ ~α; α ↔ 0Þα. Пусть Ф` и Ф`` - формулы, полученные в результате этих упрощений.

Этап 2. Проверяем, верно ли, что Ф` ╞ Ф``. Если неверно, то задача не имеет решения.

Этап 3. Приводим формулы Ф` и ~Ф`` к СДНФ. Пусть D(Ф`) и D(Ф``) – полученные СДНФ. Найдём все СДНФ Y такие, что D(Ф`):< Y:< D(Ф``). Пусть Y₁, Y₁,…, Y_m, - найденные СДНФ.

Этап 4. Находим среди Y_i такие, что формула Ψ[Y_i] не является тождественно ложной. Из найденных формул выбираем минимальные по отношению:<. Пусть Z₁, Z₂,…, Z_r – отобранные формулы. Таким образом, не верно, что Z_i ╞ Z_j, если i ≠ j, и для каждой формулы Y_k, такой, что Ψ[Y_k] нетождественно ложна, существует форму­ла Z_i, такая, что Z_i ╞ Y_k .

Этап 5. Для каждой формулы Z_i находим кратчайшую формулу X_i, эквивалентную Z_i. Мно­жество {X₁, X₂,..., X_r} представляет все кратчай­шие и логически сильнейшие формулы, которые являются решениями уравнения Ф[Х] == 0, но не являются решениями уравнения Ψ[Х] = = 0.

3. Задача абдукции. Мы рассматриваем задачу абдукции следующего типа. Пусть множество используемых в задаче пере­менных разбито на два подмножества: P = {p₁, p₂,...,p_m} и Q = {q₁, q₂,..., q_n}. Переменные p_i назы­ваются абдуцируемыми, а переменные q_j - наблюдаемыми. Любую конъюнкцию из абдуцируемых переменных или их отрицаний будем счи­тать абдуцентом, а любую конъюнкцию из наблюдаемых переменных или их отрицаний бу­дем считать наблюдением. Множество всех абдуцентов и всех наблюдений обозначаем через ABD и OBS соответственно. Пусть КВ = {α₁, α₂, …, α_n} – база знаний из произвольных формул α_j, состав­ленных из переменных p_i и q_j .

Фрейм абдукции – это F = (P, Q, ABD, OBS, KB). При заданном наблюдении δ Î OBS задача абдук­ции <F, δ> во фрейме F заключается в нахождении кратчайших и логически сильнейших абдуцентов X Î ABD, таких, что KB, X ╞ δ, но не верно, что KB╞ δ. Ясно, что задача абдукции <F, δ> совпада­ет с задачей Z(Φ, Ψ,ABD), где

Ф = α₁ & α₂ & … & α_k & ~δ & X,

Ψ = α₁ & α₂ & … & α_k & X.