Список решений

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

Язык, заданный списком решений длины k, включает в себя в качестве подмножества язык, заданный деревом решений глубины k .

Списки решений по обучению можно использовать для эффективного обучения по атрибутам .

Определение

Список решений (DL) длины r имеет вид:

if f1 then 
    output b1
else if f2 then
    output b2
...
else if fr then
    output br

где f _i — i -я формула, а b _i -е — i логическое значение для $i\in \{1...r\}$. Последнее if-then-else является случаем по умолчанию, что означает, что формула f _r всегда равна true. A k -DL — это список решений, в котором все формулы содержат не более k членов. Иногда «список решений» используется для обозначения 1-DL, где все формулы являются либо переменной, либо ее отрицанием .

См. также

• Решение тупик