Диссертация (Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств), страница 7

Аналогично, 2 * 1 . Следовательно, 1 ∩ 2 – замкнуто и ′′ ⊆ 1 ∩ 2 , что невозможно. Поскольку |J|равно числу псевдосодержаний, мы получили, что для каждой импликации → ∈ J найдется ровно псевдосодержание такое, что ⊆ и * . Рассмотрим любую импликацию → ∈ J и соответствующее ейпсевдосодержание . Если квазизамыкание = не совпадает с , то ⊆ (т.к. каждое псевдосодержание квазизамкнуто), но ′′ = ′′ * иследовательно = .С другой стороны, для любого базиса импликаций J замена импликации → ∈ J на импликацию ∖(→) → никак не влияет на45систему замыканий, которую задает этот базис. Таким образом мы показали, что базис импликаций J минимален тогда и только тогда, когдадля любой импликации → ∈ J квазизамыкание посылки являетсяпсевдосодержанием и у различных импликаций квазизамыкания посылокразличны.2.3.Функциональные зависимости и импликацииРассмотрим многозначный контекст K(, , , ).

Признак на-зывается полным, если для любого объекта ∈ , найдется ∈ такое, что (, , ) ∈ . В терминах теории баз данных, многозначный контекст является отношением. Многозначный контекст называется полным,если все его признаки полны. Для полного многозначного контекста значение признака на объекте обозначается, как (), таким образом,(, , ()) ∈ .Функциональная зависимость → выполнена в полном многозначном контексте (, , , ), если каждая пара объектов , ℎ, ∈ : удовлетворяет условию(∀ ∈ () = (ℎ)) ⇒ (∀ ∈ () = (ℎ)).В [54] было показано, что для любого полного многозначного контекста K = (, , , ), можно построить формальный контекст K :=(2 (), , ), где 2 () – множество всех пар различных объектов из ,а определяется как{, ℎ} ⇔ () = (ℎ).46Тогда, множество ⊆ функционально зависимо от множества ⊆ в контексте K, если и только если в контексте K выполненаимпликация → .В работе [70] было показано обратное сведение: для формального контекста K = (, , ) можно построить многозначный контекст K такой,что импликация → выполнена тогда и только тогда, когда функционально зависимо от в K .

Для контекста K соответствующий многозначный контекст определяется, как K = (, , ∪ {×}, ), где длялюбого ∈ , ∈ () = , если не выполнено и () = ×, если.2.4.Распознавание псевдосодержанийВ этом разделе мы обсудим вычислительную сложность задачи рас-познавания псевдосодержания.Задача 1. Распознавание псевдосодержания (PI)ВХОД: Формальный контекст K = (, , ) и подмножество признаков ⊆ .ВОПРОС: Является ли псевдосодержанием контекста K?Чтобы доказать -трудность задачи PI, мы рассмотрим наиболееизвестную -полную задачу – выполнимость КНФ.Задача 2. Выполнимость КНФ (SAT)ВХОД: Булева КНФ формула (1 , . .

. , ) = 1 ∧ . . . ∧ ВОПРОС: Выполнима ли ?Рассмотрим произвольный вход задачи SAT – КНФ 1 , . . . , с пе-47ременными 1 , . . . , , где = (1 ∨ . . . ∨ ) (1 ≤ ≤ ) – дизъюнкциии ∈ {1 , . . . , } ∪ {¬1 , . . . , ¬ } (1 ≤ ≤ , 1 ≤ ≤ ) – некоторыеперемнные или их отрицания, называемые литералами. По этой КНФ мыпостроим контекст K = (, , ). Определим = {, 1 , . . . , , 1 , ¬1 , . . . , , ¬ , } = {1 , ¬1 , . . .

, , ¬ , , , 1 , . . . , }¬∪ { | 1 ≤ ≤ , 1 ≤ ≤ } ∪ {| 1 ≤ ≤ , 1 ≤ ≤ }Для 1 ≤ ≤ мы определим множества = {1 , ¬1 , . . . , , ¬ } ∖{ , ¬ }. Также для 1 ≤ ≤ и 1 ≤ ≤ мы определим множества¬ = ∖ { } и = ∖ {¬ }.Теперь мы готовы определить отношение .

Отношение состоит издвух частей. Первая часть определяется как: ∩ {1 , ¬1 , . . . , , ¬ } × = ∪ ℐ̸= = {( , ) | ∈/ , 1 ≤ ≤ , 1 ≤ ≤ }∪ {(¬ , ) | ¬ ∈/ , 1 ≤ ≤ , 1 ≤ ≤ }ℐ̸= = {1 , ¬1 , . . . , , ¬ } × {1 , ¬1 , . . . , , ¬ },∖ {(1 , 1 ), (¬1 , ¬1 ), . . . , ( , ), (¬ , ¬ )}следовательно ′ ∩ {1 , ¬1 , . . .

, , ¬ } это множество объектов, которые соответствуют не входящих в литералам (1 ≤ ≤ ), и ℐ̸= этоотношение контраноминальной шкалы. Остальная часть определяетсяобъектными содержаниями:′= ∖ {, }′ = {} ∪ {1 , . . . , }48′ = {} ∪ , 1 ≤ ≤ ′ = {} ∪ , 1 ≤ ≤ , 1 ≤ ≤ ¬ ′¬= {} ∪ , 1 ≤ ≤ , 1 ≤ ≤ Отметим, что у контекста K есть некоторые объекты с одинаковыми содержаниями (например 1 и 11 ), но это не важно.49 1 2 · · · 1 ¬1 · · · ¬ 1¬1...ℐ̸=× ······ ×× ············ ׬×1×111×1 11¬×1......1׬×1......× ······ ×1¬1...1 ¬1...×1×11¬×......׬×1¬...¬Таблица 2.1.

Контекст K.Для любого подмножества ⊆ {1 , ¬1 , . . . , , ¬ }, которое удо-50влетворяет условию ∩ { , ¬ } ̸= ∅ для 1 ≤ ≤ , мы определим Булевоназначение переменных :⎧⎪⎪⎪, if ∈/ and ¬ ∈ ;⎪⎪⎪⎨ ( ) = , if ¬ ∈/ and ∈ ;⎪⎪⎪⎪⎪⎪⎩ , otherwise ( ∈ and ¬ ∈ );В случае ∈/ и ¬ ∈/ для некоторого 1 ≤ ≤ , назначение не определено. Отметим, что для ⊆ {1 , ¬1 , . . . , , ¬ } Булевоназначение переменных (корректно) определено, если только если * для всех 1 ≤ ≤ .Симметрично, для назначения , определим множество = {¬ |( ) = } ∪ { | ( ) = }.Перед тем, как доказать -трудность задачи PI мы докажемнесколько вспомогательных утверждений. Следующая лемма являетсяключевой в SAT к дополнению задачи PI.Лемма 1.

Если подмножество ⊆ {1 , ¬1 , . . . , , ¬ } замкнуто и *′ для любого 1 ≤ ≤ , то – определено и выполняет т.е. ( ) =. С другой стороны, если назначение выполняет , то замкнуто и * ′ для всех 1 ≤ ≤ .Доказательство. Пусть ⊆ {1 , ¬1 , . . . , , ¬ } и не содержится нив одном ′ (1 ≤ ≤ ), тогда * для всех 1 ≤ ≤ и следовательно (поопределению ) корректно определено. Поскольку ℐ̸= это отношениеконтраноминальной шкалы и любое содержание может быть представленокак пересечение объектных содержаний, то мы получаем ′ = { | ∈/} ∪ {¬ | ¬ ∈/ } ∪ , где ⊆ − {1 , ¬1 , .

. . , , ¬ }. Поскольку51¬ * для любого 1 ≤ ≤ мы также получаем * и * длякаждого 1 ≤ ≤ и 1 ≤ ≤ . Таким образом, = { }.Допустим – замкнуто т.е. ′′ = . Тогда ∩ {1 , . . . , } = ∅ иследовательно для каждого 1 ≤ ≤ найдется некоторый объект ∈ ′′и ′ = { | ∈такой, что ∈/ ′ . Поскольку ∈ / } ∪ {¬ | ¬ ∈/} ∪ { } последнее означает, что ∈ { | ∈/ } ∪ {¬ | ¬ ∈/ }.Тогда, по определению отношения , существует литерал ∈/ или ¬ ∈/, который принадлежит дизъюнкции . Поэтому выполняет длявсех 1 ≤ ≤ .Теперь пусть – Булево назначение переменных и () = .Очевидно, * ′ для всех 1 ≤ ≤ (по определению ). Тогда ′ = { | ∈/ } ∪ {¬ | ¬ ∈/ } ∪ { }.

Заметим, что′′′ ∩ {1 , ¬1 , . . . , , ¬ } = ∩ {1 , ¬1 , . . . , , ¬ } и ⊆ . Сле-довательно замкнуто тогда и только тогда, когда ∩ {1 , . . . , } = ∅.Предположим, что ∈ ∩ {1 , . . . , } для некоторого 1 ≤ ≤ . Это′означает, что ∈ ′ и ∈ ¬для всех ∈/ и ¬ ∈/ .

Отсюдаи по определению отношения следует, что дизъюнкция не выполненапри назначении .2Утверждение 1. Если существует такое 1 ≤ ≤ , что ⊆ ′ , то замкнуто.⋂︀ ′Доказательство. Пусть ⊆ ′ и ∈ . Тогда ′′ = ∈/ ∩⋂︀¬ ′= . В случае когда ∈/ мы можем представить ′′ как¬ ∈/ ′′′ = ( ∪ {})′′ ∩ = .Теперь мы готовы доказать -трудность задачи PI.252Теорема 1.

Задача PI co -трудна.Доказательство. Мы сведем SAT к PI. По данному входу задачи SAT – = 1 ∧ . . . ∧ , мы построим контекст K, который был описан выше (см.Таблицу 2.1). Мы рассмотрим множество = ∖ {} как множество, прокоторое нужно узнать является ли оно псевдосодержанием. Таким образом,соответствующий вход задачи PI это (K, ) и нужно доказать, что КНФ выполнима тогда и только тогда, когда не является псевдосодержаниемконтекста K. Не ограничивая общности можно считать, что для любого1 ≤ ≤ дизъюнкция ∨ ¬ входит в (добавление таких дизъюнкцийне влияет на выполнимость).(⇒) Пусть выполнима и пусть – булево назначение переменных,которое выполняет т.е.

() = . Рассмотрим множество = {}∪ .Как мы позже увидим является псевдосодержанием, ⊂ и ′′ = * , а это значит, что – не может быть псевдосодержанием. Для началапроверим, что ′′ = . Поскольку ∈ нам следует проверить только,¬что * ′ , где ∈ { , 1 , .

. . , } ∪ { | 1 ≤ ≤ , 1 ≤ ≤ } ∪ {|1 ≤ ≤ , 1 ≤ ≤ }. Очевидно * ′ потому, что не пусто. ПоЛемме 1 для любого 1 ≤ ≤ , * ′ , поэтому * . Следовательно ′¬ ′ * и * (1 ≤ ≤ , 1 ≤ ≤ ). Для того, чтобы доказать,что является псевдосодержанием мы покажем, что любое собственноеподмножество замкнуто. Рассмотрим произвольное множество ⊂ .Если ∈ тогда (т.к. ̸= ) найдется литерал ∈ {1 , ¬1 , . . . , , ¬ }такой, что ∈ и ∈/ . Таким образом, по Утверждению 1 подмножество замкнуто. Теперь пусть ∈/ тогда, если = ∖ {} = поЛемме 1 подмножество замкнуто. Если ̸= ∖ {} тогда ⊂ и по53Утверждению 1 подмножество замкнуто.(⇐) Теперь пусть псевдосодержание является собственным подмножеством (т.е. ⊂ ) и ′′ * .