Решетка поглощения - Википедия - Subsumption lattice

Рис. 1: Немодульная подрешетка N₅ в решетке подчинения

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

Определение

А срок т₁ говорят относить термин т₂ если замена σ существует такое, что σ применительно к т₁ дает т₂. В этом случае, т₁ также называется более общий, чем т₂, и т₂ называется более конкретный, чем т₁, или же экземпляр т₁.

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

• считать два члена равными, если они различаются только именами переменных,^[1]
• добавить искусственный минимальный элемент Ω ( сверхуказанный срок), который считается более конкретным, чем любой другой термин.

Эта решетка называется решеткой включения. Два члена называются объединяемыми, если их пересечение отличается от Ω.

Характеристики

Рис. 2: Часть решетки подчинения, показывающая, что члены ж(а,Икс), ж(Икс,Икс), и ж(Икс,c) попарно объединимы, но не одновременно. (ж опущено для краткости.)

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

Если ж символ двоичной функции, грамм является унарным функциональным символом, а Икс и у обозначают переменные, то термины ж(Икс,у), ж(грамм(Икс),у), ж(грамм(Икс),грамм(у)), ж(Икс,Икс), и ж(грамм(Икс),грамм(Икс)) образуют минимальная немодульная решетка N₅ (см. рис. 1); его внешний вид не позволяет решетке подчинения модульный а значит, и быть распределительный.

Набор терминов, унифицированных с данным термином, не обязательно закрыто в отношении встретиться; Рис. 2 показан контрпример.

Обозначая Gnd (т) совокупность всех основных экземпляров термина т, выполняются следующие свойства:^[2]

• т равно объединению всех членов Gnd (т), переименование по модулю,
• т₁ это пример т₂ тогда и только тогда, когда Gnd (т₁) ⊆ Земля (т₂),
• члены с одинаковым набором наземных экземпляров равны по модулю переименования,
• если т это встреча т₁ и т₂, то Gnd (т) = Земля (т₁) ∩ Земля (т₂),
• если т это соединение т₁ и т₂, то Gnd (т) ⊇ Земля (т₁) ∪ Земля (т₂).

«Подрешетка» линейных членов

Рис. 5: Дистрибутивная подрешетка линейных членов

Рис. 4: M3 построен из линейных условий

Рис. 3: N5 построен из линейных условий

Набор линейный Термины, то есть термины без множественных вхождений переменной, являются подмножеством решетки подчинения и сами являются решеткой. В эту решетку также входят N₅ и минимальная недистрибутивная решетка M₃ как подрешетки (см. рис. 3 и рис. 4) и, следовательно, не является модулярным, не говоря уже о дистрибутивном.

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

Присоединяйтесь и познакомьтесь с двумя собственными^[3] линейные члены, т. е. их анти-объединение и объединение, соответствует пересечению и объединению их дорожка наборы соответственно. Следовательно, любая подрешетка решетки линейных термов, не содержащая Ω, изоморфна решетке множеств и, следовательно, дистрибутивна (см. Рис. 5).

Источник

По-видимому, решетку подчинения впервые исследовал Гордон Д. Плоткин, в 1970 году.^[4]

Рекомендации