대수 값 집합의 좁힘

논리 프로그래밍과 마찬가지로, 대수 값 집합을 좁히는 것은^[1][2] 미해결 또는 부분적으로 풀린 방정식의 값에 대한 추론 방법을 제공합니다.논리 프로그래밍이 분해능에 의존하는 경우, 값 집합의 대수는 좁혀지는 규칙에 의존합니다.좁혀진 규칙을 사용하면 해결 중인 방정식과 일치하지 않는 값을 솔루션 집합에서 제거할 수 있습니다.

논리 프로그래밍과 달리 대수 값 집합을 좁히면 역추적이 사용되지 않습니다.대신 모든 값은 값 집합에 포함되며 병렬로 간주됩니다.

이 접근법은 제약조건 논리 프로그래밍에서 제약조건을^[3] 사용하는 것과 비슷하지만 논리 처리 기반이 없습니다.

확률론적 값 집합은 연역적 확률에 대한 값 집합의 자연스러운 확장이다.값 집합 구성은 초기 값의 확률을 기반으로 계산된 값의 확률을 계산하는 데 필요한 정보를 보유합니다.

역사

초기 프로그래밍 언어는 필수적이었다.이러한 기능에서는 변경을 나타낼 수 있도록 함으로써 기능을 구현합니다.assignment 문을 사용하면 변수의 값을 변경할 수 있습니다.

수학에서 변수의 값은 변경되지 않을 수 있습니다.이것은 수학적 접근법의 기본이다.람다 미적분에 기초한 함수 언어는 프로그래밍에 대한 이러한 수학적 접근을 허용합니다.느린 평가를 구현하여 함수를 매개 변수로 전달할 수 있도록 하여 개발된 기능 언어입니다.

게으른 평가는 해스켈과 같은 현대 함수형 프로그래밍 언어의 필수적인 특징입니다.하스켈은 람다 미적분과 렛 표현식에 기초한 일련의 언어 중 최신 언어이다.이러한 언어는 느린 평가를 통해 풍부한 기능을 제공하며, 유형 추론을 이용한 다형성 유형 시스템을 제공합니다.기능 프로그래밍 언어도 자연스럽게 고차 함수를 지원합니다.

기능 프로그래밍과 함께 개발된 해상도에 기반한 논리 프로그래밍.논리 프로그래밍은 값에 대해 추론하는 관계형 프로그래밍의 한 형태입니다.구속 로직 프로그래밍은 구속조건을 지원함으로써 논리 프로그래밍을 확장합니다.ECLiPSe와 같은 제약 로직 프로그래밍 언어는 복잡한 로직 문제를 해결할 수 있는 기능을 제공합니다.그러나 ECLiPSe는 게으르지 않다.

논리 프로그래밍 언어는 비록 더 큰 추론 능력을 가지고 있지만, 기능적인 언어의 힘과 유연성을 결코 얻지 못했습니다.

좁힘은 논리적인 추론을 가능하게 하는 기술이며, 기능적인 언어의 유연성이 있습니다.

서론

수학에서 표현식은 단일 값을 나타냅니다.함수는 하나 이상의 값을 하나의 고유한 값에 매핑합니다.

함수의 반전이 항상 함수로 잘 정의되는 것은 아닙니다.함수의 역함수를 함수의 정의에 적합하게 만들기 위해 추가 조건이 필요할 수 있습니다.

특히 일부 부울 연산에는 함수로 정의할 수 있는 역연산이 없습니다.특히 분리 "or"에는 두 개의 값을 허용하는 역이 있습니다.자연어에서 "또는"은 다른 가능성을 나타냅니다.

좁혀지는 것은 여러 값을 패키지화하여 하나의 값으로 간주할 수 있는 값 집합을 기반으로 합니다.이를 통해 함수의 반전을 항상 함수로 간주할 수 있습니다.

이 값 세트를 달성하려면 값이 속한 컨텍스트를 기록해야 합니다.변수는 가능한 각 세계에서 하나의 값만 가질 수 있습니다.값은 값이 속한 월드와 함께 설정된 값에서 각 값을 태그로 설정합니다.

가능한 세계는 세계 세트에 속합니다.세계 집합은 상호 배타적인 모든 세계의 집합이다.서로 배타적인 가능한 세계들을 결합하는 것을 의미하기 때문에 다른 가능한 세계들의 가치들을 결합하는 것은 서로 배타적인 가능한 세계를 결합하는 것을 의미하기 때문이다.

값 집합에 함수를 적용하면 서로 다른 세계에서 값 집합의 조합이 생성됩니다.범위를 좁히면 동일한 세계 집합에서 서로 다른 세계의 조합을 제거함으로써 이러한 세계가 줄어듭니다.좁혀진 규칙은 또한 세계의 일부 조합이 불가능한 것으로 보이는 상황을 감지한다.

좁히기 사용 시 백트래킹은 필요 없습니다.가능한 값을 값 집합으로 패키징함으로써 모든 값의 조합을 동시에 고려할 수 있습니다.기능언어에 대해서는 값 집합의 값 조합을 조합하고 집합에서 불가능한 값을 제거하는 좁힘 규칙을 사용하여 평가를 진행한다.

값 집합 소개

값 집합은 변수가 가질 수 있는 값 집합을 나타내는 개체입니다.값 세트는 수학적으로 단일 값으로 동작하며 내부적으로는 여러 값을 나타냅니다.이를 위해 값 집합은 값이 발생한 컨텍스트 또는 월드와 함께 값을 추적합니다.

방정식에 대한 다중 솔루션

수학에서 식은 단일 값을 나타내야 합니다.예를 들어 방정식을 생각해 봅시다.

${\displaystyle x^{2}=4}$

즉,

${\displaystyle x=2\lor x=-2}$

그러나 이것은 다소 긴 시간이고 동시에 여러 개의 값을 사용할 수 없습니다.만약 x에 조건이나 제약이 더해진다면 각각의 값이 제약조건과 일치하는지 검토하고 싶습니다.그래서 우리는 순진하게 글을 쓰고 싶다.

${\displaystyle x=\pm 2}$

순진하게.

${\displaystyle x+x\in\lbrace 4,0,-4\rbrace}$

하지만 이건 잘못된 거야각 x는 식에서 단일 값을 나타내야 합니다.x는 2이거나 x = -2입니다.이 문제는 2개의 값을 추적함으로써 해결할 수 있습니다.그러면 값이 일관되게 사용되고 이것이 값 집합의 기능입니다.

표현

'x'에 대해 설정된 값은 다음과 같이 기술됩니다.

${\displaystyle V(\{2:x_{1},-2:x_{2}\})}$

태그 세트, 값 쌍이 있는 컨테이너 V입니다.

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

값 2는 가능한 $월드{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 1$(\$과 관련되어 있습니다.값 -2는 가능한 $월드{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 2$(\$와 관련되어 있습니다.즉, 값은 2와 -2를 동시에 사용할 수 없습니다.${\displaystyle {월드\mathrm{}}_{}}$ x 1$({$x_${$1$$})에서는 값 집합의 값은 2여야 합니다.$x{\displaystyle {}_{}}$의 경우({$displaystyle x_{$2$$}) 값 집합의 값은 -2여야 합니다.

방정식의 해답은

${\displaystyle x^{2}=4}$

즉,

$(\displaystyle x=V(\{2:x_{1},-2:x_{2}\})}$

가능한 세계

여기서 가능한 세계는 비공식 용어로 사용된다.공식적으로 가능한 세계는 부울 조건에 의해 정의됩니다.가능한 세계는 조건에 맞는 세계의 가능성 집합으로 간주될 수 있다.

"가능 세계"라는 용어는 값 집합을 설명하기 쉽게 하기 위해 사용됩니다.

월드 세트

월드 세트는 모든 가능성을 나타내는 가능한 세계의 집합입니다.${\displaystyle {}_{}}{\displaystyle }${ ${\displaystyle {x\mathrm{}}_{}{}_{}}$, x $}({displaystyle$\{$x_{$1},$x_{2}\})$는 x = 2(${\displaystyle {월드\mathrm{}}_{}}$ x 1$${$style x_{1$ 또는 x = - 2($월드{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$2 {$displaystyle x_{2$}})$$로 설정된 월드입니다.다른 가능성은 없다.

같은 세계 집합의 세계는 서로 배타적이므로 $x{\displaystyle {}_{}}$ $($과 x $($ 스타일 $x_{$2})의$$ 명제가 동시에 참일 수는 없습니다.

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

기능 적용

값 집합에 함수를 적용하는 규칙은 다음과 같습니다.

$\displaystyle V(M)\V(\{(m_{v}\n_{v},m_{l}\cap n_{l}):m_{v:m_{l}\in M\land n_{v}:n_{l}\in N\})$

예를들면,

${\displaystyle x+x=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_{2}\cap x_{2})$

${\displaystyle =V(\{-4:x_{1}\cap x_{1},0:x_{2}\land x_{1},+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 =V(\{-4:x_{1}, 0:\{\}, 0:\{\}, 4:x_{2}\})}$

빈 월드 규칙을 사용하면 빈 월드의 태그된 값을 삭제할 수 있습니다.

$(\displaystyle V(K)=V(\{(v,l):(v,l)\in K\land l\neq \{\}\})$

부여,

$(\displaystyle =V(\{-4:x_{1}, 4:x_{2}\})}$

x +$style$ x$+x)$의 결과는 예상대로 -4 또는 4입니다.

Bohans에 대한 응용 프로그램

$(\displaystyle a\land b)$

a, b, true의 관계는 a와 b가 모두 참이어야 한다는 것을 의미합니다.

$(\displaystyle a\lor b)$

a 와 b 에 복수의 값을 사용할 수 있습니다.a의 경우,

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

그럼 b에 대해서

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

즉, a가 false일 경우 b가 true여야 합니다.

자, 생각해 보세요.

${\displaystyle x=2\lor x=-2}$

주다,

$(\displaystyle x=V(\{\:a_{1},2:a_{2}\})}$

그리고.

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

이 두 가지 가치 집합을 통합하면

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

페어${\displaystyle }$- ${\displaystyle 2}$ ${\displaystyle ::}$ ${\displaystyle {}_{}}$ $(\$ - 2$::a_{2})$는 "동일" 규칙 때문에 드롭됩니다.

$\displaystyle \forall m_{v}\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_{l} n_l}\l}\forall n_l}$

${\displaystyle \mathrm{값}}{\displaystyle }$-${\displaystyle {}_{}}$ : : :$$ ( \ $display$ - 2 : : : a _ {$2$} )가$$ 2${\displaystyle }$: : : ${\displaystyle {2\mathrm{}}_{}}$( \ $display style$ 2 : : a _ {$}$ $)$와 $일치$하지 않습니다.

종속 세계

문제를 생각해 보세요.

$(\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}$

$\ display style X+Y > 10 }$

먼저 XY < { $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_{2}\cap y_{2},27:x_{2}\cap)$

${\displaystyle V(\{8<25:x_{1}\cap y_{1},24<25:x_{2}\cap y_{1},32<25:x_{1}\cap y_{2},27<25:x_{2}\cap y_{2},25:x_36}$

$\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}\}}$

이 스테이트먼트가 true라고 단언되면 모든 false 값은 드롭되어 부여됩니다.

$\displaystyle V(\{\text{true})::x_{1}\cap y_{1},{\text{true}:x_{2}\cap y_{2}}$

세상들,

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

${\displaystyle x_{2}\cap y_{2}}$

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

불가능해.세상은 텅 비었다.

월드 세트가 계산에 포함된 경우 월드 세트의 모든 월드 세트가 결과에 포함되어야 합니다.월드를 찾을 수 없는 경우 종속 월드라고 하며 비워 두어야 합니다.$월드{\displaystyle {}_{}}$ ${\displaystyle {X\mathrm{}}_{}}$ 3$({$은 이 값으로 표시되지 않으므로 비워 두어야 합니다.X$(\displaystyle$ X$)$에 $설정$된 값이 작아졌습니다.

$(\displaystyle X=V(\{1:x_{1},3:x_{2}\})}$

두 번째 조건은 값 집합이 작기 때문에 더 단순해졌습니다.

$\ display style X+Y > 10 }$

그러면 값 집합은 다음과 같습니다.

$(\displaystyle X=V(\{1:x_{1},3:x_{2}\})}$

$(\displaystyle Y=V(\{8:y_{1},9:y_{2}\})}$

그리고 그 계산은,

${{1+8:x_{1}\cap y_{1},3+8::x_{2}\cap y_{1},2+9:x_{1}\cap y_{2}\cap y_{2}>10}$

단, ${\displaystyle {x2\mathrm{}}_{}{2\mathrm{}}_{}}$y2 (\$style$ 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 {따라서\mathrm{}}_{}}$ x 1${\displaystyle {}_{}{1\mathrm{}}_{}}$ y$$1 { $display style x _${ \ $cap y$ _ {$$1$$} $x{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 1${\displaystyle {}_{}{}_{}}$ ${\displaystyle {y\mathrm{}}_{}}$2 \ $displaystyle x$ _ {1} \ $cap$y$$ _ ${2$} , 。

$\displaystyle V(\{11>10::x_{2}\cap y_{1}\})$

${\displaystyle {X\mathrm{}}_{}}$ 1$({$ 및$$ ${\displaystyle {Y\mathrm{}}_{}}$ 2$({$는 $표시$되지 않고 종속 월드로 제거됩니다.그렇게,

${\displaystyle X=V(\{3:x_{2}\})=3}$

$\displaystyle Y=V(\{8:y_{1}\})=8}$

모든 계산은 종속된 월드를 제거하여 값 집합의 크기를 줄일 수 있지만 입력 값 집합의 크기를 곱한 새 값 집합을 추가합니다.그런 다음 입력 값 세트의 크기 곱이 가장 작은 곳에서 계산을 먼저 진행해야 합니다.

피자, 맥주, 위스키

지옥에서 온 프로젝트와 함께 미친 마감일을 맞추기 위해 힘든 하루를 보낸 후, 우리 모두가 피자, 맥주, 위스키를 필요로 하는 밤 10시에 절박한 시간이 찾아옵니다.피자 가게가 문을 열어서

${\displaystyle {Pizza Shop}(V(\{\text{Carlton})::p_{1},{\text{Richmond}}::p_{2},{\text{\text})사우스멜버른}::p_{3},{\text{Footscray}::p_{4},{\text{St Kilda}}::p_{5},{\text{\text}Toorak}::p_{6}\}}},$

맥주도 구할 수 있고

$\ display style \ text \ BottleshopWith Beer}}(V(\{\text{})사우스멜버른}::b_{1},{\text{St Kilda}::b_{2},{\text{Carlton}}::b_{3},{\text{Docklands}::b_{4}\}}}$

위스키.

$\ display style \ text \ BottleshopWhiskey}}(V(\{\text{Essendon}): w_{1}, {\text{})사우스멜버른}::w_{2}\}}}},$

경찰이 다가오고 있고 우리는 더 이상 젊어지지 않을 것이다.어디 갈까?

$디스플레이 스타일Where To Go} (x) = 텍스트 {Pizza Shop}} (x) \ text { Bottleshop }With Beer}(x)\land {bottleshop}Whiskey}}(x) 포함$

구속조건이 왼쪽에서 오른쪽 순서로 적용되는 경우,

$\displaystyle x=V(\{\text{Carlton})::p_{1},{\text{Richmond}::p_{2},{\text{\text}사우스멜버른}::p_{3},{\text{Footscray}::p_{4},{\text{St Kilda}}::p_{5},{\text{\text}Toorak}::p_{6}\}}$

그럼 우린 이걸 하나로 묶어야 해

$\displaystyle x=V(\{\text{\text})사우스멜버른}::b_{1},{\text{St Kilda}::b_{2},{\text{Carlton}::b_{3},{\text{Docklands}::b_{4}\}$

그러면 일치하는 조합이 24개 생성됩니다.

$\displaystyle x=V(\{\text{\text})사우스 멜버른}:: b_{1}\cap p_{3}, {\text{St Kilda}:: b_{2}\cap p_{5}, {\text{Calton}:: b_{3}\cap p_{1}\}$

마지막으로 위스키와의 통합이 필요합니다.

$\displaystyle x=V(\{\text{Essendon}):: w_{1},{\text{\text}사우스 멜버른}:: w_{2}\}}$

즉, 6개의 조합이 있습니다.짝이 되는 거죠

$\displaystyle x=V(\{\text{\text})사우스멜버른}: b_{1}\cap p_{3}\cap w_{2}\}$

총 30개의 조합이 생성되었습니다.

구속조건이 오른쪽에서 왼쪽으로 순서대로 적용되는 경우,

$\displaystyle x=V(\{\text{Essendon}):: w_{1},{\text{\text}사우스 멜버른}:: w_{2}\}}$

그럼 우린 이걸 하나로 묶어야 해

$\displaystyle x=V(\{\text{\text})사우스멜버른}::b_{1},{\text{St Kilda}::b_{2},{\text{Carlton}::b_{3},{\text{Docklands}::b_{4}\}$

그러면 일치하는 조합이 8개 생성됩니다.

$\displaystyle x=V(\{\text{\text})사우스 멜버른}: b_{1}\cap w_{2}\}}$

마지막으로 우리는 피자와 통일해야 한다.

${\displaystyle x=\{\text{Carlton}}::p_{1},{\text{Richmond}::p_{2},{\text{}사우스멜버른}::p_{3},{\text{Footscray}::p_{4},{\text{St Kilda}}::p_{5},{\text{\text}Toorak}::p_{6}\}$

즉, 6개의 조합이 있습니다.짝이 되는 거죠

$\displaystyle x=V(\{\text{\text})사우스멜버른}: b_{1}\cap w_{2}\\cap p_{3}\}}$

결과는 동일하지만 결론에 도달하기 위해 생성된 조합은 14개뿐입니다.

모든 계산은 값 집합을 결합하여 입력 값 집합의 크기를 곱한 값 집합을 만듭니다.그러면 값 집합이 잘립니다.그리고 모든 계산이 계산 범위를 좁힐 수 있는 동등한 가능성을 가지고 있습니다.따라서 순서를 제어하고 최소 크기의 곱으로 계산을 진행하면 계산과 조합의 폭발이 줄어듭니다.

식 및 다중 값 사용

함수가 아닌 함수의 반전 문제에 대한 일반적인 해결책이 필요합니다.필요한 것은 값 집합의 멤버로 제한되는 값의 표현입니다.집합의 멤버인 값을 나타내기 위해 let 식을 사용할 수 있습니다.

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

이 $식$에서 x${\displaystyle x}$ X$(\displaystyle$ x$\in$ X$)$는 구속조건입니다.제약조건은 변수가 충족해야 하는 부울식입니다.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)\times Y\operatorname {in}x\y}$

단, 그 자체에 let 식을 적용하는 경우에는 다른 규칙이 적용됩니다.let 표현은 변수 x의 범위를 제한하지 않으므로 x는 두 let 표현에서 같은 변수입니다.

$\displaystyle (\operatorname {let} x\in X\operatorname {in} 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는 한 쌍의 집합으로 정의되며, 각 쌍은 값과 종속 조건의 집합으로 구성된다.종속 조건 집합은 "조건 함수"에 의해 사용되며, 값 집합이 해당 값을 갖는지 여부를 판단합니다.

조건 함수는 3개의 공리에 의해 정의된다.

1. 각 쌍$({\displaystyle }$ ${\displaystyle v}$,${\displaystyle l}$ ) {$displaystyle ( v$ ,$l$ )$$}은$$ 목록에 적용되는 조건 $함수{\displaystyle }$C (${\displaystyle l}$) {$displaystyle$ C$(l$ 가 참일 경우 값 $집합{\displaystyle }$V (${\displaystyle K}$) {$displaystyle$ V$(K)}$ 의$$ 값이 v임을 의미합니다.
2. 조건 중 하나는 사실이다.
3. 조건 중 하나만 해당됩니다.

조건은 조건의 구조를 제어할 수 있도록 종속 조건 집합에 적용되는 함수로 표시됩니다.또한 일련의 조건은 종속 값을 배제함으로써 범위를 좁히는 데 사용된다.그러나 대부분의 경우 값 집합은 값 집합, 조건 쌍으로 간주할 수 있습니다.condition 함수는 세트를 조건으로 변환합니다.

정식으로

이름.	정의.
조건 함수	$(\displaystyle C(l)=bigwedge_{(r,z,u)\in l}z=u})=(\forall r\forall z\forall u(r,z,u)\in l\to z=u)}$
값 조건	$\displaystyle \forall v\forall L((v,l)\land C(l)\to v=V(K))}$
전체 세트	$\displaystyle \exists v(v,l)\land C(l)의 L(v,l)\exists$
제외	$\displaystyle \forall v_{1}\forall v_{2}\forall l_{1}((v_{1},l_{1})\in K\land (v_{2},l_{1}\neq (v_{2},l_{1}\neg2})$

값 함수

값 조건과 완전한 집합 공리를 사용하여

$\displaystyle \displays v(v,l)\land C(l)\land v=V(K)}$

렛 표현으로 말하면

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

단일값

단일 값을 나타내기 위해 설정된 값은 다음과 같습니다.

$\displaystyle k=V(\{(k,\{\})\})}$

그 파생은,

${\displaystyle V(\{(k,\{\})\})}$

${\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(\operatorname {let} x\in X\operatorname {in} x)=\operatorname {let} R=V(\{(w,\{(R,x,w)\}):w\in X\}\operatorname {in} R}$

이 다소 이상한 정의는 종속 조건의 일부로 설정된 값을 추가합니다.이것은 종속 값을 제외함으로써 범위를 좁히는 데 사용됩니다.

이 표현의 값은

${\displaystyle x}$ ${\displaystyle =V}$ (${\displaystyle R}$) { $display$ x =$$V ($R$ )$$}

R은 종속 조건이 속한 값 세트를 식별하고 x는 let 식에서 값을 전달하기 위해 사용되는 변수를 제공하기 때문에 R과 x는 종속 조건에 모두 포함되어야 합니다.

종속 조건에 R을 추가하는 것을 무시하면 표현은 더 단순하고 이해하기 쉬운 형식을 취합니다.

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

그 파생은,

$(\displaystyle V(\{(r,x,w):w\in X\})}$

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

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

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

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

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

기능 적용

값 집합의 함수 적용은 다음과 같이 주어진다.

$\displaystyle V(M)\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)\V(N)}$

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

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

그리고 나서,

${\displaystyle C(m_{l})\land C(n_{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}\cup n_{l}z=u}}}$

${\displaystyle = C(m_{l}\cup 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}$

${\displaystyle =\operatorname {let}(v,l)\in \{(m_{v}\n_{l}\cup n_{l}):(m_{v},m_{l}\in M\land (n_v},n_{l}\in N\l}\land C(l)\operorn} {l} vame} {l} {l}$

$\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)\in s\iff (\forall v(v,l)\in M\land v\in s\in s\neg C(l)\forall v(\forall v(v,l)\forall v(\forall v(l)\f)\in M\land v\in s)\neg C(l)}$

이것은, 다음과 같이 생각할 수 있습니다.

${\displaystyle V(M)\ins}$

$(\displaystyle\to\forall v((v,l)\land C(l)\to(v=V[M]\land V(M)\in s)))$

$(\displaystyle\to\forall v(v,l)\land C(l)\to v\in S)$

$\displaystyle\to\forall l((v,l)\land v\in S)\to\neg C(l)\displaystyle\forall l(\forall v(l)\land v\in S)\neg C(l)\l)$

심플화

단순화 규칙을 사용하면 조건이 false인 값을 삭제할 수 있습니다.

$(\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)\land C(l)\operatorname {in} v}$

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

${\displaystyle=V(K)}$

결과의 개요

이름.	규칙.
값 함수	${\displaystyle V(K)=\operatorname {let}(v,l)\in K\land C(l)\operatorname {in} v}$
단일값	$\displaystyle k=V(\{(k,\{\})\})}$
요소 설정	$\displaystyle \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(\{(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)\in s\iff (\forall v(v,l)\in M\land v\in s\in s\neg C(l)\forall v(\forall v(v,l)\forall v(\forall v(l)\f)\in M\land v\in s)\neg C(l)}$
심플화	$(\displaystyle V(K)=V(\{(v,l):(v,l)\in K\land C(l)\})}$
동등하다고 주장하다	$\displaystyle V(M)=V(N)\to(\forall v(v,l)\land v(M)\in S(M)\neg C(l)\l)\neg C(l)\forall l(\forall v(v,l)\forall l(\forl)\forland v(\forl)\forland v(\f)\for\}$

값은 ID를 설정합니다.

값 집합에 대한 함수 적용을 정의함으로써 값 집합의 동등성에 대한 정의도 재정의되었습니다.값 집합은 쌍의 집합으로 구성되기 때문에 평등에 대한 오래된 정의는 여전히 존재합니다.두 집합이 동일한 요소를 포함하는 경우 동일합니다.값 집합의 평등에 대한 정의는 기껏해야 오해를 불러일으킬 수 있습니다.

필요한 것은 값 집합 구조의 일부로 값 집합이 구성되는 변수의 이름 또는 ID를 사용하는 것입니다.이는 값 집합이 동일한 변수에 기초하지 않는 한, 값 집합을 구별하게 할 것이다.

수학에서 수량화는 공식이 아니라 값보다 크다.값 집합의 정확한 정의를 진행하기 위해서는 공식의 동일성을 비교할 수 있는 방식으로 공식에 대한 정량화가 필요하다.값을 나타내는 공식과 공식의 동일성 사이의 구별은 사용-설명 구별이다.표기법,

$\displaystyle x\#u$

는 공식 x에 대한 평균 정량화에 도입됩니다.여기서 x는 값, u는 표현 또는 언급된 공식의 동일성을 나타냅니다.

이 표기법을 사용하면 집합 정의의 요소는 다음과 같습니다.

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

값 집합에 대한 모든 참조는 값 집합의 추가 구조 수준을 고려하도록 변경해야 하며, 이는 설명을 읽기 어렵게 만듭니다.가독성을 위해 이 추가 수준의 구조는 값 집합의 정의에서 제외되었습니다.

좁히다

"좁음"은 값에 대한 조건이 거짓이어야 하는 시기를 결정하는 것입니다.2개의 값 집합의 값이 동일하다고 판단될 때 좁혀지기 시작합니다.

동등하다고 주장하여 좁히다

두 값 집합이 동일하다는 주장은 좁혀지는 규칙을 제시합니다.

$\displaystyle \forall m_{v}\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 \land (m_{l}\neg})$

도출을 위해, 먼저

${\displaystyle V(M)=V(N)}$

값 조건은 다음과 같습니다.

$(\displaystyle (\forall m_{v}\forall m_{l}(m_{l})\land C\land (m_{l})\to v=V(M)\land (\forall n_{v}\forall n_l}(n_{vk})\land C\forland {l})$

$\displaystyle \forall m_{v}\forall n_{v}\forall n_{l}((m_{v},m_{l})\in M\land C(m_{l})\to m_{v}=V(M)\land (n_{l}\land n}\forall n)\forall n_{l}\forall n}$

$\displaystyle \forall m_{v}\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 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 \land (m_{l}\neg})$

결합에 의한 좁힘

기본 조건 중 하나가 false일 경우 여기서 얻은 모든 조건은 false입니다.

이는 Condition 함수의 정의에서 비롯됩니다.

$({displaystyle C(l)=bigwedge_{(r,z,u)\in l}z=u})}$

(r, z, u)의 기본 조건은 다음과 같다.

$\displaystyle C(\{(r,z,u)\}=(z=u)}$

이것이 $false{\displaystyle }$C일 $($ l ) {$displaystyle$ C$(l)}$는 false입니다.

교차 조건에 따라 좁혀짐

종속 조건 목록에 동일한 값 집합과 다른 두 개의 기본 조건이 있는 경우 false여야 합니다.

이를 도출하려면 제외 규칙부터 시작합니다.

$\displaystyle \forall v_{1}\forall v_{2}\forall l_{2}((v_{1},l_{1})\in K\land (v_{2},l_{1}\neq (v_{2})$

그러면 종속 조건 l에 대해

$\displaystyle((K,x,v_{1})\land(K,x,v_{2})\land v_{1}\neq v_{2}\land$

$\displaystyle \implies (v_{1},\{(K,x,v_{1}\})\in K\land (v_{2}\)\neq (v_{1}\neq (v_2})$

$(\displaystyle \implies \neg (\{(K,x,v_{1}\})\land C(\{(K,x,v_{2}\})))}$

$\displaystyle \implies \neg C(l)}$

따라서 종속 조건 목록이 동일한 값 집합의 두 조건을 기반으로 하는 경우 해당 종속 조건 목록의 조건 값은 false입니다.

종속값의 배제에 의한 축소

각 값 집합은 해당 값 집합이 구성된 기본 값 집합에 제약을 가합니다.기본 값 집합에 종속 값으로 존재하지 않는 값이 포함된 경우 이러한 값의 조건은 false여야 합니다.

이를 도출하려면 완전한 설정 규칙부터 시작합니다.

$\displaystyle \exists v\exists \l(v,l)\in K\to C(l)}$

조건 함수는 다음과 같습니다.

$({displaystyle C(l)=bigwedge_{(r,z,u)\in l}z=u})}$

특정 종속 조건을 선택할 수 있으며, 이는 전체 조건이 암시하는 바와 같다.

$(\displaystyle\forall L(l)\to (L,z,u)\in l=u)$

그렇게

$(\displaystyle\forall L\exists v\in K\to C(l)\to (L,z,u)\in l=u)$

$여기$서 z ${\displaystyle =V}$ ( ${\displaystyle L}$) \ $displaystyle$z$$=$V$( L$$)$$。${\displaystyle V}$ ( L${\displaystyle }$) \ $displaystyle$V ( $L$)이$$ $취할{\displaystyle }$ 수 있는 값 집합을 정의하도록 식을 재배치할 수 있습니다.

$\displaystyle E(K,L)=\{w:(v,l)\in K\land C(l)\land (L,z,w)\in l\}$

그래서...

$\displaystyle V(L)\in E(K,L)}$

그리고 제외 규칙을 사용하여

$\displaystyle V(M)\in s\iff (\forall v(v,l)\in M\land v\in s\in s\neg C(l)\forall v(\forall v(v,l)\forall v(\forall v(l)\f)\in M\land v\in s)\neg C(l)}$

주다,

$\displaystyle (\forall K\forall V\forall L((v,l)\land v\in E(K,L))\neg C(l)\forall L(l)\forall L(l)\forall L(l)\forland v\forall L(l)\land v\in E(\in E(K,L)\l)\in E}$

이것이 좁혀지는 제외 규칙입니다.${\displaystyle E(}$ ${\displaystyle K}$,${\displaystyle L}$) {$style$ E$(K, L)}$는 기본값 L 세트에 포함된 값 집합으로, 값 집합 K에 표시됩니다.다른 값의 조건은 false여야 합니다.

확률론적 값 집합

값 집합은 조건 함수가 적용될 수 있는 종속 조건을 기록하여 값 집합이 특정 값을 갖는다는 명제의 참을 추론합니다.동일한 구조를 사용하여 값 집합이 특정 값과 같을 확률을 제공할 수 있습니다.조건 함수는 다음과 같습니다.

$({displaystyle C(l)=bigwedge_{(r,z,u)\in l}z=u})}$

확률 함수는,

$({displaystyle P(l)=prod _{(r,z,u)\in l}P(z=u)})}}}$

사건이 독립적일 경우 각 베이스 케이스가 특정 값을 유지할 확률입니다.

확률 함수는 세 가지 공리로 정의된다.

1. 각 쌍$({\displaystyle }$ ${\displaystyle v}$,${\displaystyle l}$) {$displaystyle$$( v$ ,$l$${\displaystyle }$) pair$$ 、 pair v $v세트{\displaystyle }$ V${\displaystyle }$( $K$) { $displaystyle$V ( $K$$$)$$} is is is is applied applied applied applied applied applied applied applied applied applied${\displaystyle }applied{\displaystyle }$ applied applied applied applied applied applied applied applied applied applied applied applied applied v v v v v v v v v v v v v v v v v v v v v v v v v v v v v vV ( K${\displaystyle }$)가 v ( K )일 확률은 ${\displaystyle \mathrm{목록}}$에 적용되는 확률함수라는 의미입니다.
2. 전체 값 집합에 대한 확률의 합계는 1입니다.
3. 값 집합에서 두 쌍의 확률은 0입니다.

확률 함수는 부울 유도 추론에 의해 주어진 초기 확률을 기반으로 결과에 대한 확률을 제공합니다.

정식으로

이름.	정의.
확률 함수	$({displaystyle P(l)=prod _{(r,z,u)\in l}P(z=u)})}}}$
값 조건	$\displaystyle \forall vP(v=V(K))=\sum _{(v,l)\in K}P(l)}$
전체 세트	$\displaystyle \sum _{(v,l)\in 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 v_{2}\forall l_{2}((v_{1},l_{1})\in K\land (v_{2},l_{1}\neq (v_{2},l_{2})\in K\land (v_{1}\forall v_{1}\forall v_{2})$

값 집합의 각 값에 대한 확률은 확률 함수와 값 조건을 사용하여 기본 값 집합의 확률로부터 계산할 수 있다.기준값 세트는 단일 값 또는 다중 값 세트 중 하나입니다.

단일 값에 대한 확률

단일 값을 나타내기 위해 설정된 값은 다음과 같습니다.

$\displaystyle k=V(\{(k,\{\})\})}$

완전한 규칙이란,

$\displaystyle \sum _{(v,l)\in K}P(l)}$

${\displaystyle =\sum _{(v,l)\in\{(k,\{\})\}P(l)}$

${\displaystyle =P(\{\})$

${\displaystyle =1}$

그건 공리와 일치합니다.

다중 값에 대한 확률

여러 값을 나타내기 위해 설정된 값은 다음과 같습니다.

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

확률은 허용된 값 규칙에 의해 주어집니다.

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

간단하게 말하면,

$\displaystyle \sum _{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)}$

값이 설정된 값에 포함되지 않으면 확률은 0이 됩니다.

$\displaystyle \forall v\in \operatorname {gset} (V(K), P(x=v)=0}$

그렇게,

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

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

${\displaystyle \forall v\in \operatorname {gset}(V(K), P(x=v)=flac {P_{i}(x=v)}{\sum _{v\in \operatorname {gset}(V(K)})}P_{i}(x=v)}}}$

$\displaystyle \forall v\in \operatorname {gset} (V(K), P(x=v)=0}$

만약 이전의 확률이 모두 같다면,

${\displaystyle \forall v\in \operatorname {gset}(V(K), P(x=v)=parc 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)})},$

값 집합 액세스

범위를 좁히면 변수의 제약 조건을 충족하지 않는 값을 제거할 수 있습니다.방정식을 풀기 위한 알고리즘의 기초로 간주되는 이 좁힘은 변수에 대한 제약 조건과 일치하는 일련의 값을 제공합니다.그러나 수학에서는 이 값 집합에 접근할 방법이 없습니다.

E$)$ {$displaystyle$ E$(x)}$이 변수 x를 제약하는 표현일 $경우{\displaystyle }$ 변수가 취할 수 있는 값 집합은 다음과 같습니다.

$(\displaystyle\{z:E(z)\})$

x의 gset을 x의 제약조건을 만족시키는 값의 집합으로 정의합니다.gset의 정의를 검토해 주십시오.

$\displaystyle \operatorname {gset}(x)=\{z:E(z)\}$

이 정의는 식 E를 아는 것에 달려 있습니다.식 E는 x에 대한 모든 제약을 주는 조건입니다.수학 E는 x에서 얻을 수 없습니다.따라서 값 집합을 요구하기 위해 변수에 적용될 수 있는 수학 함수는 없습니다.그럼 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,\display N,\operatorname {gset}(x)=\operatorname {let} M[u]=x\operatorname {in} \{z:z=N[u]\land T[N]\}$

여기도 표기법입니다.

$\displaystyle x\#u$

변수 x에 대한 수량화를 의미하는 데 사용됩니다. 여기서 x는 값을 나타내고 u는 변수의 고유 ID를 나타냅니다.

예

예를 들어 $제약식{\displaystyle {}^{}}$ ${\displaystyle {x\mathrm{}}^{}}$ 2 ${\displaystyle {}^{}}$ { $displaystyle$ x$^{2$} $=$ 4$$} 를 사용합니다.그리고나서,

${\displaystyle x^{2}=4}$

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

$\displaystyle \land (\forall x\#u,\display 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 x,\displays,(x^{2}=4}$

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

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

${\displaystyle \operatorname {in} T[\_]}$

여기서 u는 변수x의 일의 ID로 여기서 숫자1로 나타납니다(gset 콜에서 사용되는 첫 번째 변수).

${\displaystyle M[1]=x\land s=\{z:z=N[1]\land T[N]\}$

$여기$서${\displaystyle }$T [ $]$ { $display style$T [ $N$]는 M을 N으로 하여 T를 호출합니다.

$\displaystyle s=\{z:z=N[1]\land x^{2}=4\land x=N[1]\}}$

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

「 」를 참조해 주세요.

• 기능 프로그래밍
  • 게으른 평가
  • 다형식계
  • 유형 추론
  • 고차 함수
  • 하스켈
• 람다 미적분
  • 연역 람다 미적분
  • 표현하게 하다
• 논리 프로그래밍
  • 해상도(로직)
  • 제약 로직 프로그래밍
  • 제약
  • ECLiPSe
• 수학
  • 함수(수학)
  • 대수학
  • 절단
• 관계형 프로그래밍

레퍼런스