Сужение наборов алгебраических значений - Narrowing of algebraic value sets

подобно логическое программирование, сужение^[1]^[2] алгебраических наборов значений дает метод рассуждений о значениях в нерешенных или частично решенных уравнениях. Где логическое программирование полагается на разрешающая способность, алгебра наборов значений опирается на правила сужения. Правила сужения позволяют исключить из набора решений значения, несовместимые с решаемыми уравнениями.

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

Подход также похож на использование ограничения^[3] в программирование логики ограничений, но без основы обработки логики.

Наборы вероятностных значений является естественным продолжением наборов значений до дедуктивная вероятность. Конструкция набора значений содержит информацию, необходимую для вычисления вероятностей вычисленных значений на основе вероятностей начальных значений.

История

Ранние языки программирования были императив. Они реализуют функциональные возможности, позволяя отображать изменения. Оператор присваивания позволяет переменной изменять свое значение.

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

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

Логическое программирование на основе разрешение развивалась параллельно с функциональным программированием. Логическое программирование - это форма реляционное программирование это делает выводы о ценностях. Программирование логики ограничений расширяет логическое программирование, поддерживая ограничения. Языки программирования с ограничительной логикой, такие как Затмение дают возможность решать сложные логические задачи. Однако ECLiPSe не ленивый.

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

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

Введение

В математика выражение представляет собой одно значение. А функция отображает одно или несколько значений на одно уникальное значение.

Обратные функции не всегда хорошо определяются как функции. Иногда требуются дополнительные условия, чтобы инверсия функции соответствовала определению функции.

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

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

Для достижения этого набора значений необходимо записать контекст, которому принадлежит значение. Переменная может принимать только одно значение в каждом возможный мир. Наборы значений помечают каждое значение в наборе значений миром, которому оно принадлежит.

Возможные миры принадлежат мировым множествам. Мировой набор - это совокупность всех взаимоисключающих миров. Объединение значений из разных возможных миров невозможно, потому что это означало бы объединение взаимоисключающих возможных миров.

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

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

Введение в наборы значений

А набор значений - объект, который представляет набор значений, которые может иметь переменная. Набор значений математически ведет себя как одно значение, но внутренне представляет несколько значений. Чтобы достичь этого, набор значений отслеживает значение вместе с контекстом или миром, в котором они возникли.

Множественные решения уравнения

В математике выражение должно представлять одно значение. Например, рассмотрим уравнение

{ displaystyle x ^ {2} = 4}

что означает,

{ Displaystyle х = 2 лор х = -2}

Но это немного затянуто, и это не позволяет нам работать с несколькими значениями одновременно. Если к x добавляются дополнительные условия или ограничения, мы хотели бы рассмотреть каждое значение, чтобы увидеть, соответствует ли оно ограничению. Так наивно хотелось бы написать,

{ displaystyle x = pm 2}

Тогда наивно,

{ Displaystyle х + х в lbrace 4,0, -4 rbrace}

но это неправильно. Каждый x должен представлять одно значение в выражении. Либо x равно 2, либо x = −2. Эту проблему можно решить, отслеживая два значения, чтобы убедиться, что значения используются последовательно, и это то, что делает набор значений.

Представление

Значение, установленное для 'x', записывается как,

{ Displaystyle V ( {2 :: x_ {1}, - 2 :: x_ {2} })}

Это контейнер V который имеет набор тегов, пар значений,

${ displaystyle 2 :: x_ {1}}$
${ displaystyle -2 :: x_ {2}}$

Значение 2 связано с возможный мир ${ displaystyle x_ {1}}$ . Значение −2 связано с возможным миром ${ displaystyle x_ {2}}$ . Это означает, что значение не может быть одновременно 2 и -2. В мире ${ displaystyle x_ {1}}$ значение набора значений должно быть 2. В мире ${ displaystyle x_ {2}}$ значение набора значений должно быть -2.

Решение уравнения,

{ displaystyle x ^ {2} = 4}

является,

{ Displaystyle х = V ( {2 :: x_ {1}, - 2 :: x_ {2} })}

Возможные миры

Возможный мир используется здесь как неформальный термин. Формально возможный мир определяется логическим условием. Возможный мир можно рассматривать как набор возможностей для мира, который соответствует условию.

Термин «возможный мир» используется для упрощения описания наборов значений.

Мировые наборы

Набор миров - это набор возможных миров, которые представляют все возможности. Так ${ Displaystyle {х_ {1}, х_ {2} }}$ является миром, установленным как x = 2 (в мире ${ displaystyle x_ {1}}$ ) или x = −2 (в мире ${ displaystyle x_ {2}}$ ). Других возможностей нет.

Миры из одного и того же набора миров являются взаимоисключающими, поэтому невозможно, чтобы утверждения для обоих миров ${ displaystyle x_ {1}}$ и ${ displaystyle x_ {2}}$ верны в то же время.

{ displaystyle (x = 2 land x = -2) = { text {false}}}

Применение функций

Правило для применения функций к наборам значений:

{ Displaystyle V (M) V (N) = V ( {(m_ {v} n_ {v}, m_ {l} cap n_ {l}): m_ {v} :: m_ {l} in M ​​ land n_ {v} :: n_ {l} in N })}

Например,

{ Displaystyle х + х = V ( {2 :: x_ {1}, - 2 :: x_ {2} }) + V ( {2 :: x_ {1}, - 2 :: x_ {2 } })}

является,

{ displaystyle = V ( {- 2 + -2 :: x_ {1} cap x_ {1}, - 2 + 2 :: x_ {1} cap x_ {2}, 2 + -2 :: x_ {1} cap x_ {2}, 2 + 2 :: x_ {2} })}

{ displaystyle = V ( {- 4 :: x_ {1} cap x_ {1}, 0 :: x_ {1} cap x_ {2}, 0 :: x_ {2} land x_ {1}) , 2 + 2 :: x_ {2} cap x_ {1} })}

Пересечение возможного мира с самим собой - это возможный мир,

{ displaystyle x_ {1} cap x_ {1} = x_ {1}}

{ displaystyle x_ {2} cap x_ {2} = x_ {2}}

Пересечение возможного мира с другим возможным миром из того же набора миров пусто,

{ displaystyle x_ {1} cap x_ {2} = {}}

{ displaystyle x_ {2} cap x_ {1} = {}}

Так,

{ Displaystyle = В ( {- 4 :: x_ {1}, 0 :: {}, 0 :: {}, 4 :: x_ {2} })}

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

{ Displaystyle V (K) = V ( {(v, l) :( v, l) in K land l neq {} }}

давая

{ Displaystyle = В ( {- 4 :: x_ {1}, 4 :: x_ {2} })}

Дает результат, который ${ Displaystyle х + х}$ как и ожидалось, равно −4 или 4.

Применение к логическим значениям

{ displaystyle a land b}

Связь между а, б и правда это означает, что оба а и б должно быть правдой.

{ Displaystyle а лор б}

Допускает несколько значений для а и б. Если а является,

{ displaystyle a = V ( { operatorname {false} :: a_ {1}, operatorname {true} :: a_ {2} })}

тогда для б

{ displaystyle b = V ( { operatorname {true} :: a_ {1}, operatorname {false} :: a_ {2}, operatorname {true} :: a_ {2} })}

Это означает, что если а является ложный тогда б должно быть правда.

Теперь рассмотрим,

{ Displaystyle х = 2 лор х = -2}

дает,

{ Displaystyle х = В ( { _ :: а_ {1}, 2 :: а_ {2} })}

и

{ displaystyle x = V ( {- 2 :: a_ {1}, _ :: a_ {2}, - 2 :: a_ {2} })}

объединение этих двух наборов значений дает,

{ Displaystyle х = В ( {- 2 :: а_ {1}, 2 :: а_ {2} })}

Пара ${ displaystyle -2 :: a_ {2}}$ отбрасывается из-за правила "утверждать равное",

{ displaystyle forall m_ {v} forall m_ {l} forall n_ {v} forall n_ {l} ((m_ {v}, m_ {l}) in M ​​ land (n_ {v}, n_ {l}) in N) to (m_ {v} neq n_ {v} to m_ {l} cap n_ {l} = {})}

Его ценность ${ displaystyle -2 :: a_ {2}}$ не совпадает с ${ displaystyle 2 :: a_ {2}}$ .

Зависимые миры

Рассмотрим проблему,

{ Displaystyle X = V ( {1 :: x_ {1}, 3 :: x_ {2}, 4 :: x_ {3} })}

{ Displaystyle Y = V ( {8 :: y_ {1}, 9 :: y_ {2} })}

{ displaystyle X * Y <25}

{ displaystyle X + Y> 10}

Сначала рассчитайте значение, установленное для ${ displaystyle X * Y <25}$ ,

{ Displaystyle V ( {8 :: x_ {1} cap y_ {1}, 24 :: x_ {2} cap y_ {1}, 32 :: x_ {3} cap y_ {1}, 9 :: x_ {1} cap y_ {2}, 27 :: x_ {2} cap y_ {2}, 36 :: x_ {3} cap y_ {2} }) <25}

{ Displaystyle V ( {8 <25 :: x_ {1} cap y_ {1}, 24 <25 :: x_ {2} cap y_ {1}, 32 <25 :: x_ {3} cap y_ {1}, 9 <25 :: x_ {1} cap y_ {2}, 27 <25 :: x_ {2} cap y_ {2}, 36 <25 :: x_ {3} cap y_ { 2} }) <25}

{ Displaystyle V ( {{ text {true}} :: x_ {1} cap y_ {1}, { text {true}} :: x_ {2} cap y_ {1}, { text {false}} :: x_ {3} cap y_ {1}, { text {true}} :: x_ {1} cap y_ {2}, { text {false}} :: x_ {2} cap y_ {2}, { text {false}} :: x_ {3} cap y_ {2} })}

Поскольку это утверждение считается истинным, все ложные значения отбрасываются, давая

{ Displaystyle V ( {{ text {true}} :: x_ {1} cap y_ {1}, { text {true}} :: x_ {2} cap y_ {2}, { text {true}} :: x_ {1} cap y_ {2} })}

Миры,

{ displaystyle x_ {3} cap y_ {1}}

{ displaystyle x_ {2} cap y_ {2}}

{ displaystyle x_ {3} cap y_ {2}}

невозможно. Миры пусты.

Если набор миров включен в вычисление, тогда каждый мир из набора миров должен быть включен в результат. Если мир не найден, он называется зависимым миром и должен быть пустым. Мир ${ displaystyle X_ {3}}$ не представлен в этом значении, поэтому должен быть пустым. Значение, установленное для ${ displaystyle X}$ теперь меньше,

{ Displaystyle X = V ( {1 :: x_ {1}, 3 :: x_ {2} })}

Второе условие теперь проще из-за меньшего установленного значения.

{ displaystyle X + Y> 10}

Тогда наборы значений:

{ Displaystyle X = V ( {1 :: x_ {1}, 3 :: x_ {2} })}

{ Displaystyle Y = V ( {8 :: y_ {1}, 9 :: y_ {2} })}

Расчет такой:

{ Displaystyle V ( {1 + 8 :: x_ {1} cap y_ {1}, 3 + 8 :: x_ {2} cap y_ {1}, 2 + 9 :: x_ {1} cap y_ {2}, 1 + 9 :: x_ {2} cap y_ {2} })> 10}

Но ${ displaystyle x_ {2} cap y_ {2}}$ пусто. Так,

{ Displaystyle V ( {9> 10 :: x_ {1} cap y_ {1}, 11> 10 :: x_ {2} cap y_ {1}, 10> 10 :: x_ {1} cap y_ {2} })}

Так ${ displaystyle x_ {1} cap y_ {1}}$ и ${ displaystyle x_ {1} cap y_ {2}}$ пусты,

{ Displaystyle V ( {11> 10 :: x_ {2} cap y_ {1} })}

Сейчас же ${ displaystyle X_ {1}}$ и ${ displaystyle Y_ {2}}$ не представлены и удаляются как зависимые миры. Так,

{ Displaystyle X = V ( {3 :: x_ {2} }) = 3}

{ Displaystyle Y = V ( {8 :: y_ {1} }) = 8}

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

Пицца, пиво, виски

После тяжелого рабочего дня в попытках уложиться в какой-то сумасшедший срок с адским проектом, в 22:00 наступает то отчаянное время, когда всем нам нужна пицца, пиво и виски. Пиццерия открыта по адресу,

{ displaystyle { text {PizzaShop}} (V ( {{ text {Carlton}} :: p_ {1}, { text {Richmond}} :: p_ {2}, { text {Южный Мельбурн}) } :: p_ {3}, { text {Footscray}} :: p_ {4}, { text {St Kilda}} :: p_ {5}, { text {Toorak}} :: p_ {6} }))}

Пиво можно достать,

{ displaystyle { text {BottleshopWithBeer}} (V ( {{ text {Южный Мельбурн}} :: b_ {1}, { text {St Kilda}}} :: b_ {2}, { text {Carlton) }} :: b_ {3}, { text {Docklands}} :: b_ {4} }))}

Виски,

{ displaystyle { text {BottleshopWithWhiskey}} (V ( {{ text {Essendon}} :: w_ {1}, { text {Южный Мельбурн}} :: w_ {2} }))}

Копы уже на месте, а мы не молодеем. Куда идти?

{ displaystyle { text {WhereToGo}} (x) = { text {PizzaShop}} (x) land { text {BottleshopWithBeer}} (x) land { text {BottleshopWithWhiskey}} (x)}

Если ограничения применяются в порядке слева направо,

{ displaystyle x = V ( {{ text {Carlton}} :: p_ {1}, { text {Richmond}} :: p_ {2}, { text {Южный Мельбурн}} :: p_ {3) }, { text {Footscray}} :: p_ {4}, { text {St Kilda}} :: p_ {5}, { text {Toorak}} :: p_ {6} })}

Затем нам нужно объединить это с

{ displaystyle x = V ( {{ text {Южный Мельбурн}} :: b_ {1}, { text {St Kilda}} :: b_ {2}, { text {Carlton}} :: b_ { 3}, { text {Docklands}} :: b_ {4} })}

Это создаст 24 комбинации, из которых совпадают,

{ Displaystyle x = V ( {{ text {Южный Мельбурн}} :: b_ {1} cap p_ {3}, { text {St Kilda}} :: b_ {2} cap p_ {5}) , { text {Carlton}} :: b_ {3} cap p_ {1} })}

Наконец, нам нужно объединиться с виски.

{ displaystyle x = V ( {{ text {Essendon}} :: w_ {1}, { text {Южный Мельбурн}} :: w_ {2} })}

Что дает 6 комбинаций. Соответствующий:

{ displaystyle x = V ( {{ text {Южный Мельбурн}} :: b_ {1} cap p_ {3} cap w_ {2} })}

Всего было сгенерировано 30 комбинаций.

Если ограничения применяются в порядке справа налево,

{ displaystyle x = V ( {{ text {Essendon}} :: w_ {1}, { text {Южный Мельбурн}} :: w_ {2} })}

Затем нам нужно объединить это с

{ displaystyle x = V ( {{ text {Южный Мельбурн}} :: b_ {1}, { text {St Kilda}} :: b_ {2}, { text {Carlton}} :: b_ { 3}, { text {Docklands}} :: b_ {4} })}

Это создаст 8 комбинаций, из которых соответствует одна,

{ displaystyle x = V ( {{ text {Южный Мельбурн}} :: b_ {1} cap w_ {2} })}

Наконец, нам нужно объединиться с пиццей.

{ displaystyle x = {{ text {Carlton}} :: p_ {1}, { text {Richmond}} :: p_ {2}, { text {South Melbourne}} :: p_ {3}, { text {Footscray}} :: p_ {4}, { text {St Kilda}} :: p_ {5}, { text {Toorak}} :: p_ {6} }}

Что дает 6 комбинаций. Соответствующий:

{ displaystyle x = V ( {{ text {Южный Мельбурн}} :: b_ {1} cap w_ {2} cap p_ {3} })}

Результат тот же, но только 14 комбинаций были сгенерированы, чтобы прийти к заключению.

Каждый расчет объединяет наборы значений для создания набора значений, который является продуктом размеров наборов входных значений. Затем установленное значение будет уменьшено. И каждый расчет имеет равные шансы сузить расчет. Таким образом, контролируя порядок и продолжая вычисления с наименьшим размером продукта, будет меньше вычислений и меньше комбинаторный взрыв.

Пусть выражения и несколько значений

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

{ displaystyle operatorname {let} x in X operatorname {in} x}

В этом выражении ${ displaystyle x in X}$ это ограничение. Ограничение - это логическое выражение, которому должна удовлетворять переменная. В позволять Expression позволяет представить ограничение в виде выражения. Если бы существовало общее правило для применения выражений ограничений к функциям, то ограничение можно было бы рассматривать как значение.

При применении функции одного выражения let к другому,

{ displaystyle ( operatorname {let} x in X operatorname {in} x) ( operatorname {let} y in Y operatorname {in} y)}

{ displaystyle = operatorname {let} x in X land y in Y operatorname {in} x y}

{ displaystyle = operatorname {let} (x, y) in X times Y operatorname {in} x y}

Но для применения выражения let к самому себе применяется другое правило. Выражение let не ограничивает область действия переменной x, поэтому x - это одна и та же переменная в двух выражениях let.

{ displaystyle ( operatorname {let} x in X operatorname {in} x) ( operatorname {let} x in X operatorname {in} x)}

{ displaystyle = operatorname {let} x in X operatorname {in} x x}

Не существует простого правила для объединения выражений let. Требуется общая форма выражения, представляющая переменную, значение которой является членом набора значений. Выражение должно быть основано на переменной и наборе.

Приложение функции, примененное к этой форме, должно давать другое выражение в той же форме. Таким образом, любое выражение функций с несколькими значениями может рассматриваться как имеющее одно значение.

Недостаточно, чтобы форма представляла только набор значений. Каждое значение должно иметь условие, определяющее, когда выражение принимает значение. Результирующая конструкция представляет собой набор пар условий и значений, называемый «набором значений».

Теория наборов ценностей

"Набор значений" K определяется как набор пар, каждая пара состоит из значения и набора зависимых условий. Набор зависимых условий используется «функцией условия», чтобы определить, принимает ли набор значений это значение.

Функция условия определяется тремя аксиомами:

Каждая пара ${ displaystyle (v, l)}$ означает, что значение установленного значения ${ Displaystyle V (K)}$ является v если функция условия применена к списку, ${ Displaystyle C (l)}$ , правда.
Одно из условий верно.
Только одно из условий верно.

Условие представлено как функция, применяемая к набору зависимых условий, чтобы позволить управлять структурой условия. Также набор условий используется в сужение за счет исключения зависимых значений. Однако для большинства целей набор значений можно рассматривать как набор пар значений и условий. Функция условия переводит набор в условие.

Формально,

имя	Определение
Функция условия	${ Displaystyle С (L) = ({ bigwedge _ {(г, z, u) in l} z = u})) = ( forall r forall z forall u (r, z, u) в l to z = u)}$
Условие значения	${ Displaystyle forall v forall l ((v, l) in K land C (l) to v = V (K)}$
Полный комплект	${ Displaystyle существует v существует l (v, l) в К земля C (l)}$
Исключение	${ displaystyle forall v_ {1} forall l_ {1} forall v_ {2} forall l_ {2} ((v_ {1}, l_ {1}) in K land (v_ {2}, l_ {2}) in K land (v_ {1}, l_ {1}) neq (v_ {2}, l_ {2})) to neg (C (l_ {1}) land C (l_ {2}))}$

Функция значения

Используя условие значения и аксиомы полного набора,

{ Displaystyle существует v существует l (v, l) в К земля C (l) земля v = V (K)}

Как выражение let это становится,

{ Displaystyle V (K) = OperatorName {let} (v, l) in K land C (l) operatorname {in} v}

Одно значение

Значение, установленное для представления единственного значения:

{ Displaystyle к = В ( {(к, {}) })}

Вывод:

{ Displaystyle В ( {(к, {}) })}

{ displaystyle = operatorname {let} (v, l) in {(k, {}) } land C (l) operatorname {in} v}

{ displaystyle = operatorname {let} v = k land C ( {}) operatorname {in} v}

{ displaystyle = operatorname {let} v = k operatorname {in} v}

{ displaystyle = k}

Элемент набора

Набор значений для представления элемента набора:

{ displaystyle forall x forall X ( operatorname {let} x in X operatorname {in} x) = operatorname {let} R = V ( {(w, {(R, x, w) }): w in X }) operatorname {in} R}

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

Значение выражения равно

{ Displaystyle х = В (р)}

.

И то и другое р и Икс необходимо включить в зависимое условие, потому что р определяет набор значений, которому принадлежит зависимое условие, и Икс предоставляет переменную, используемую для переноса значения в выражении let.

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

{ displaystyle forall x forall X ( operatorname {let} x in X operatorname {in} x) = V ( {(w, {( _, x, w) }): w в X })}

Вывод:

{ Displaystyle В ( {(вес, {(г, х, ш): вес в Х })}

{ displaystyle = operatorname {let} (v, l) in {(w, {(r, x, w) }): w in X } land C (l) operatorname {in } v}

{ displaystyle = operatorname {let} v in X land ({ bigwedge _ {(r, z, u) in {( _, x, v) }} z = u}) operatorname {in} v}

{ displaystyle = operatorname {let} v in X land ( forall r forall z forall u (r, z, u) in {( _, x, v) } to z = u) operatorname {in} v}

{ displaystyle = operatorname {let} v in X land x = v operatorname {in} v}

{ displaystyle = operatorname {let} x in X operatorname {in} x}

Применение функций

Функциональное применение наборов значений определяется выражением

{ Displaystyle V (M) V (N) = V ( {(m_ {v} n_ {v}, m_ {l} чашка n_ {l}) :( m_ {v}, m_ {l} ) in M ​​ land (n_ {v}, n_ {l}) in N })}

Вывод,

{ Displaystyle В (М) В (Н)}

{ displaystyle = operatorname {let} (m_ {v}, m_ {l}) in M ​​ land C (m_ {l}) operatorname {in} m_ {v}) ( operatorname {let} ( n_ {v}, n_ {l}) in N land C (n_ {l}) operatorname {in} n_ {v})}

{ displaystyle = operatorname {let} (m_ {v}, m_ {l}) in M ​​ land (n_ {v}, n_ {l}) in N land C (n_ {l}) land C (n_ {l}) operatorname {in} m_ {v} n_ {v})}

Затем, используя,

{ Displaystyle С (м_ {l}) земля С (п_ {l})}

{ displaystyle = ({ bigwedge _ {(z, u) in m_ {l}} z = u}) land ({ bigwedge _ {(z, u) in n_ {l}} z = u })}

{ displaystyle = ({ bigwedge _ {(z, u) in m_ {l} чашка n_ {l}} z = u})}

{ displaystyle = C (m_ {l} чашка n_ {l})}

получить,

{ displaystyle = operatorname {let} (m_ {v}, m_ {l}) in M ​​ land (n_ {v}, n_ {l}) in N land C (n_ {l} cup n_ {l}) operatorname {in} m_ {v} n_ {v})}

{ displaystyle = operatorname {let} (v, l) in {(m_ {v} n_ {v}, m_ {l} cup n_ {l}) :( m_ {v}, m_ {l }) in M ​​ land (n_ {v}, n_ {l}) in N } land C (l) operatorname {in} v}

{ displaystyle = V ( {(m_ {v} n_ {v}, m_ {l} cup n_ {l}) :( m_ {v}, m_ {l}) in M ​​ land (n_ { v}, n_ {l}) in N })}

Исключение

Исключение - это правило, определяющее, когда условия должны быть ложными,

{ Displaystyle V (M) в s iff ( forall v forall l ((v, l) in M ​​ land v not in s) to neg C (l))}

Это может быть получено из

{ Displaystyle V (M) in s}

{ Displaystyle к forall v forall l ((v, l) in M ​​ land C (l)) to (v = V [M] land V (M) in s)}

{ displaystyle to forall v forall l ((v, l) in M ​​ land C (l)) to v in S}

{ displaystyle to forall v forall l ((v, l) in M ​​ land v not in S) to neg C (l)}

Упрощение

Правило упрощения позволяет отбрасывать значения, условие которых ложно.

{ Displaystyle V (K) = V ( {(v, l) :( v, l) in K land C (l) }}

Вывод

{ Displaystyle V ( {(v, l) :( v, l) in K land C (l) })}

{ displaystyle = operatorname {let} (v, l) in {(v, l) :( v, l) in K land C (l) } land C (l) operatorname {in } v}

{ displaystyle = operatorname {let} (v, l) in K land C (l) land C (l) operatorname {in} v}

{ displaystyle = operatorname {let} (v, l) in K land C (l) operatorname {in} v}

{ Displaystyle = В (К)}

Резюме результатов

имя	Правило
Функция значения	${ Displaystyle V (K) = OperatorName {let} (v, l) in K land C (l) operatorname {in} v}$
Одно значение	${ Displaystyle к = В ( {(к, {}) })}$
Установить элемент	${ displaystyle forall x forall X ( operatorname {let} x in X operatorname {in} x) = operatorname {let} R = V ( {(w, {(R, x, w) }): w in X }) operatorname {in} R}$
Приложение функции	${ Displaystyle V (M) V (N) = V ( {(m_ {v} n_ {v}, m_ {l} чашка n_ {l}) :( m_ {v}, m_ {l} ) in M land (n_ {v}, n_ {l}) in N })}$
Исключение	${ Displaystyle V (M) в s iff ( forall v forall l ((v, l) in M land v not in s) to neg C (l))}$
Упрощение	${ Displaystyle V (K) = V ( {(v, l) :( v, l) in K land C (l) })}$
Утверждать равное	${ Displaystyle В (М) = В (N) к ( forall v forall l ((v, l) в N land v not in S (M)) к neg C (l) )}$

Ценность устанавливает идентичность

Определив применение функций для наборов значений также было переопределено определение равенства наборов значений. Старое определение равенства все еще существует, потому что наборы значений строятся как набор пар. Два набора равны, если они содержат одинаковые элементы. Это определение равенства для наборов значений в лучшем случае вводит в заблуждение.

Что необходимо, так это использовать имя или идентификатор переменной, из которой создается набор значений, как часть структуры набора значений. Это сделало бы наборы значений разными, если только они не основаны на одной и той же переменной.

В математике количественная оценка - это значения, а не формулы. Чтобы продолжить точное определение наборов значений, необходима количественная оценка по формулам таким образом, чтобы можно было сравнить идентичность формул. Различие между формулой, представляющей значение, и ее сущностью заключается в использование – упоминание различия. Обозначение,

{ displaystyle forall x #u}

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

Используя эти обозначения, элемент набора определение было бы,

{ displaystyle forall x #u forall X ( operatorname {let} x in X operatorname {in} x) = operatorname {let} R = V ((u, {(w, {( R, x, w) }): w in X })) operatorname {in} R}

Затем каждую ссылку на набор значений необходимо будет изменить, чтобы учесть дополнительный уровень структуры в наборе значений, что затрудняет чтение описания. Для удобства чтения этот дополнительный уровень структуры не включен в определение наборов значений.

Сужение

«Сужение» определяет, когда должны быть выполнены условия для значений. ложный. Сужение начинается, когда утверждается, что значения двух наборов значений равны.

Сужение за счет утверждения равенства

Утверждение, что два набора значений равны, дает правило сужения,

{ displaystyle forall m_ {v} forall m_ {l} forall n_ {v} forall n_ {l} ((m_ {v}, m_ {l}) in M ​​ land (n_ {v}, n_ {l}) in N) to (m_ {v} neq n_ {v} to neg (C (m_ {l}) land C (n_ {l})))}

Для вывода начнем с

{ Displaystyle V (M) = V (N)}

Условие ценности дает,

{ Displaystyle ( forall m_ {v} forall m_ {l} ((m_ {v}, m_ {l}) in M ​​ land C (m_ {l}) to v = V (M)) земля ( forall n_ {v} forall n_ {l} ((n_ {v}, k) in N land C (n_ {l})) to n_ {v} = V (N)) land V (M) = V (N)}

{ displaystyle forall m_ {v} forall m_ {l} forall n_ {v} forall n_ {l} (((m_ {v}, m_ {l}) in M ​​ land C (m_ {l) })) к m_ {v} = V (M)) land (((n_ {v}, n_ {l}) in N land C (n_ {l})) to n_ {v} = V (N)) земля V (M) = V (N)}

{ displaystyle forall m_ {v} forall m_ {l} forall n_ {v} forall n_ {l} ((m_ {v}, m_ {l}) in M ​​ land (n_ {v}, n_ {l}) in N) to (C (j) land C (k) to v = u)}

{ displaystyle forall m_ {v} forall m_ {l} forall n_ {v} forall n_ {l} ((m_ {v}, m_ {l}) in M ​​ land (n_ {v}, n_ {l}) in N) to (m_ {v} neq n_ {v} to neg (C (m_ {l}) land C (n_ {l})))}

Сужение соединением

Если какое-либо базовое условие ложно, все условия, полученные из него, ложны.

Это происходит из определения функции Condition,

{ Displaystyle С (л) = ({ bigwedge _ {(г, г, и) в л} г = и}))}

Базовое условие для (r, z, u):

{ Displaystyle С ( {(г, г, и) } = (г = и)}

Итак, если это ложь ${ Displaystyle C (l)}$ ложно.

Сужение перекрещенными условиями

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

Чтобы вывести это, начните с правила исключения:

{ displaystyle forall v_ {1} forall l_ {1} forall v_ {2} forall l_ {2} ((v_ {1}, l_ {1}) in K land (v_ {2}, l_ {2}) in K land (v_ {1}, l_ {1}) neq (v_ {2}, l_ {2})) подразумевает neg (C (l_ {1}) land C (l_ {2}))}

Тогда для любого набора зависимых условий л,

{ Displaystyle ((К, х, v_ {1}) in l land (K, x, v_ {2}) in l land v_ {1} neq v_ {2}}

{ displaystyle подразумевает (v_ {1}, {(K, x, v_ {1}) }) in K land (v_ {2}, {(K, x, v_ {2}) }) in K land (v_ {1}, l_ {1}) neq (v_ {2}, l_ {2}))}

{ displaystyle подразумевает neg (C ( {(K, x, v_ {1}) }) land C ( {(K, x, v_ {2}) }))}

{ displaystyle подразумевает neg C (l)}

Таким образом, если список зависимых условий основан на двух условиях из одного и того же набора значений, значение условия этого списка зависимых условий будет ложным.

Сужение за счет исключения зависимых значений

Каждый набор значений накладывает ограничение на базовый набор значений, из которого он построен. Если набор базовых значений включает значения, которые не представлены в качестве зависимых значений в наборе значений, условия для этих значений должны быть ложными.

Чтобы вывести это, начните с правила полного набора,

{ Displaystyle существует v существует l (v, l) в K к C (l)}

Функция условия:

{ Displaystyle С (л) = ({ bigwedge _ {(г, г, и) в л} г = и}))}

Может быть выбрано конкретное зависимое условие, подразумеваемое всем условием,

{ Displaystyle forall L C (l) к (L, z, u) in l к z = u}

Так

{ Displaystyle forall L существует v существует l (v, l) в K к C (l) to (L, z, u) in l to z = u}

Вот ${ Displaystyle Z = V (L)}$ . Выражение может быть изменено, чтобы определить набор значений, которые ${ Displaystyle V (L)}$ может взять,

{ Displaystyle Е (К, L) = {ш: (v, л) в К земля C (л) земля (L, z, ш) в л }}

и так,

{ Displaystyle V (L) в E (K, L)}

Затем, используя правило исключения,

{ Displaystyle V (M) в s iff ( forall v forall l ((v, l) in M ​​ land v not in s) to neg C (l))}

дает,

{ Displaystyle ( forall K forall L forall v forall l ((v, l) in L land v not in E (K, L)) to neg C (l))}

Это сужающееся правило исключения. ${ Displaystyle E (K, L)}$ это набор значений в базовом значении L набор, который представлен в наборе значений K. Условия для других значений должны быть ложными.

Наборы вероятностных значений

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

{ Displaystyle С (л) = ({ bigwedge _ {(г, г, и) в л} г = и}))}

Функция вероятности:

{ Displaystyle P (l) = ({ prod _ {(г, z, u) in l} P (z = u)}))}

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

Функция вероятности определяется тремя аксиомами:

Каждая пара ${ displaystyle (v, l)}$ означает, что вероятность установленного значения ${ Displaystyle V (K)}$ является v - функция вероятности, примененная к списку, ${ Displaystyle P (l)}$ .
Сумма вероятностей по всему набору значений равна 1.
Вероятность появления любых двух пар в наборе значений равна нулю.

Функция вероятности дает вероятности результатов, основанные на начальных вероятностях, заданных формулой Логический индуктивный вывод.

Формально,

имя	Определение
Функция вероятности	${ Displaystyle P (l) = ({ prod _ {(г, z, u) in l} P (z = u)}))}$
Условие значения	${ Displaystyle forall vP (v = V (K)) = sum _ {(v, l) in K} P (l)}$
Полный комплект	${ Displaystyle сумма _ {(v, l) в K} P (l) = 1}$
Допустимые значения	${ displaystyle sum _ {(v, l) in K land v in operatorname {gset} (V (K))} P (l) = 1}$
Исключение	${ displaystyle forall v_ {1} forall l_ {1} forall v_ {2} forall l_ {2} ((v_ {1}, l_ {1}) in K land (v_ {2}, l_ {2}) in K land (v_ {1}, l_ {1}) neq (v_ {2}, l_ {2})) to P (C (l_ {1}) land C ( l_ {2})) = 0}$

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

Вероятность единственного значения

Значение, установленное для представления единственного значения:

{ Displaystyle к = В ( {(к, {}) })}

Правило полного набора:

{ Displaystyle сумма _ {(v, l) в K} P (l)}

{ Displaystyle = сумма _ {(v, l) in {(k, {}) }} P (l)}

{ Displaystyle = П ( {})}

{ displaystyle = 1}

Что согласуется с аксиомой.

Вероятности для нескольких значений

Для представления нескольких значений установлено следующее значение:

{ displaystyle forall x forall X ( operatorname {let} x in X operatorname {in} x) = V ( {(w, {( _, x, w) }): w в X })}

Вероятность определяется правилом допустимых значений,

{ displaystyle sum _ {(v, l) in K land v in operatorname {gset} (V (K))} P (l) = 1}

что упрощает,

{ Displaystyle сумма _ {v in operatorname {gset} (V (K))} P (x = v) = 1}

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

{ Displaystyle forall v in operatorname {gset} (V (K)), P (x = v) = w * P_ {i} (x = v)}

Если значение не входит в набор значений, вероятности будут равны нулю,

{ Displaystyle forall v not in operatorname {gset} (V (K)), P (x = v) = 0}

Так,

{ displaystyle sum _ {v in operatorname {gset} (V (K))} w * P_ {i} (x = v) = 1}

{ Displaystyle ш = { гидроразрыва {1} { сумма _ {v in operatorname {gset} (V (K))} P_ {i} (x = v)}}}

{ displaystyle forall v in operatorname {gset} (V (K)), P (x = v) = { frac {P_ {i} (x = v)} { sum _ {v in имя оператора {gset} (V (K))} P_ {i} (x = v)}}}

{ Displaystyle forall v not in operatorname {gset} (V (K)), P (x = v) = 0}

Если все априорные вероятности одинаковы, вероятности равны

{ displaystyle forall v in operatorname {gset} (V (K)), P (x = v) = { frac {1} {| operatorname {gset} (V (K)) |}}}

Вероятности общих наборов значений

Общий набор значений создается на основе применения наборов базовых значений. Правило условия значения и функция вероятности могут быть объединены для получения,

{ Displaystyle forall vP (v = V (K)) = sum _ {(v, l) in K land v in operatorname {gset} (V (K))} ({ prod _ { (r, z, u) in l} P (z = u)}))}

Доступ к набору значений

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

Если ${ displaystyle E (x)}$ это выражение, ограничивающее переменную Икс тогда набор значений, которые может принимать переменная:

{ Displaystyle {г: Е (г) }}

Определить gset из Икс быть набором значений, которые удовлетворяют ограничениям на Икс. Рассмотрите возможность определения gset так как,

{ Displaystyle OperatorName {gset} (х) = {z: E (z) }}

Это определение зависит от знания выражения E, что является условием, дающим все ограничения на Икс. В математике E не может быть получено из Икс. Таким образом, нет математической функции, которую можно применить к переменной для запроса набора значений. Так пусть gset функцию добавить в математику?

Мета-математическое определение

Мета-математическое определение gset может быть возможно. Представьте себе, что то, что мы знаем как математику, на самом деле реализуется мета-функция называется математика. математика занимает абстрактное синтаксическое дерево и придает значение переменным и математическим структурам и добавляет кванторы существования для переменных, которые не определены явно.

математика будет выражением в метаматематической среде со своими собственными переменными. Чтобы отличить эти метапеременные от математических переменных, представляйте их заглавными буквами, а математические переменные - строчными буквами.

Теперь предположим, что существует расширенная реализация математики, реализованная xmath функция, определяемая как,

{ displaystyle operatorname {xmath} [E] = forall M, operatorname {let} T [M] = operatorname {math} [E] operatorname {in} T [ _]}

С помощью xmath, gset может быть определено как,

{ displaystyle forall x #u, exists N, operatorname {gset} (x) = operatorname {let} M [u] = x operatorname {in} {z: z = N [u] земля T [N] }}

Вот очередной раз обозначение,

{ displaystyle forall x #u}

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

пример

Например, возьмите выражение ограничения ${ displaystyle x ^ {2} = 4}$ . Потом,

{ displaystyle x ^ {2} = 4}

{ displaystyle land s = operatorname {gset} (x)}

{ displaystyle land ( forall x #u, exists N operatorname {gset} (x) = operatorname {let} M [u] = x operatorname {in} {z: z = N [u ] land T [N] })}

Тогда xmath выражение,

{ displaystyle forall M, operatorname {let} T [M] =}

{ Displaystyle существует х, существует s, (х ^ {2} = 4}

{ displaystyle land s = operatorname {gset} (x)}

{ displaystyle land ( forall x #u, exists N, operatorname {gset} (x) = operatorname {let} M [u] = x operatorname {in} {z: z = N [ u] land T [N] })}

{ displaystyle operatorname {in} T [ _]}

Тогда где u - уникальный идентификатор переменной x, представленной здесь как число 1 (для первой переменной, используемой при вызове gset),

{ Displaystyle M [1] = х земля s = {z: z = N [1] земля T [N] }}

Вот ${ Displaystyle Т [N]}$ призывает Т с M как N.

{ Displaystyle s = {z: z = N [1] земля x ^ {2} = 4 земля x = N [1] }}

{ displaystyle s = {z: z ^ {2} = 4 }}

Смотрите также

использованная литература

^ Киршнер, Элен; Рингайссен, Кристоф (1994). «Решение ограничений путем сужения в комбинированных алгебраических областях». Proc. 11-я Международная конференция по логическому программированию. Пресса Массачусетского технологического института. С. 617–31.
^ Аренас, Пури; Арталехо, Марио Родригес (1997). «Ленивое сужающее исчисление для функционально-логического программирования с алгебраическими полиморфными типами». Proc.Международного симпозиума по логическому программированию (ILPS'97). MIT Press. С. 53–67.
^ Marriott, Ким; Стаки, Питер Дж. (1998). Программирование с ограничениями: введение. MIT Press.

[1] Киршнер, Элен; Рингайссен, Кристоф (1994). «Решение ограничений путем сужения в комбинированных алгебраических областях». Proc. 11-я Международная конференция по логическому программированию. Пресса Массачусетского технологического института. С. 617–31.

[2] Аренас, Пури; Арталехо, Марио Родригес (1997). «Ленивое сужающее исчисление для функционально-логического программирования с алгебраическими полиморфными типами». Proc.Международного симпозиума по логическому программированию (ILPS'97). MIT Press. С. 53–67.

[3] Marriott, Ким; Стаки, Питер Дж. (1998). Программирование с ограничениями: введение. MIT Press.

[1]

[2]

[3]