Zawężanie zbiorów wartości algebraicznych

Podobnie jak programowanie logiczne , zawężanie zbiorów wartości algebraicznych daje metodę wnioskowania o wartościach w nierozwiązanych lub częściowo rozwiązanych równaniach. Tam, gdzie programowanie logiczne opiera się na rozdzielczości , algebra zestawów wartości opiera się na regułach zawężania. Reguły zawężające pozwalają na eliminację ze zbioru rozwiązań wartości niezgodnych z rozwiązywanymi równaniami.

W przeciwieństwie do programowania logicznego, zawężanie zestawów wartości algebraicznych nie wykorzystuje cofania się . Zamiast tego wszystkie wartości są zawarte w zestawach wartości i są rozpatrywane równolegle.

Podejście to jest również podobne do stosowania ograniczeń w programowaniu logiki z ograniczeniami , ale bez podstawy przetwarzania logicznego.

Probabilistyczne zestawy wartości to naturalne rozszerzenie zestawów wartości do prawdopodobieństwa dedukcyjnego . Konstrukcja zestawu wartości zawiera informacje wymagane do obliczenia prawdopodobieństw obliczonych wartości na podstawie prawdopodobieństw wartości początkowych.

Historia

Wczesne języki programowania były koniecznością . Implementują one funkcjonalność, umożliwiając reprezentację zmian. Instrukcja przypisania umożliwia zmiennej zmianę jej wartości.

W matematyce wartość zmiennej może się nie zmieniać. Ma to fundamentalne znaczenie dla podejścia matematycznego. funkcyjne oparte na rachunku lambda umożliwiają takie matematyczne podejście do programowania. Języki funkcyjne opracowane przez wdrożenie leniwej oceny i umożliwienie przekazywania funkcji jako parametrów.

Leniwa ocena jest istotną cechą nowoczesnych funkcjonalnych języków programowania, takich jak Haskell . Haskell jest najnowszym z serii języków opartych na rachunku lambda i wyrażeniach let . Języki te zapewniają bogatą funkcjonalność dzięki leniwej ocenie i polimorficznemu systemowi typów wykorzystującemu wnioskowanie o typie . Funkcjonalne języki programowania w naturalny sposób obsługują również funkcje wyższego rzędu .

Programowanie logiczne oparte na rozdzielczości opracowanej równolegle z programowaniem funkcjonalnym. Programowanie logiczne jest formą programowania relacyjnego , która dokonuje dedukcji na temat wartości. Programowanie w logice z ograniczeniami rozszerza programowanie w logice, obsługując ograniczenia . Języki programowania w logice z ograniczeniami, takie jak ECLiPSe, umożliwiają rozwiązywanie złożonych problemów logicznych. Jednak ECLiPSe nie jest leniwy .

Języki programowania logiki, choć mają większe możliwości dedukcji, nigdy nie zyskały mocy i elastyczności języków funkcjonalnych.

Zawężanie to technika, która umożliwia dedukcję logiczną z elastycznością języków funkcjonalnych.

Wstęp

W matematyce wyrażenie reprezentuje pojedynczą wartość. Funkcja jedną lub więcej wartości na jedną unikalną wartość.

Odwrotności funkcji nie zawsze są dobrze zdefiniowane jako funkcje. Czasami wymagane są dodatkowe warunki, aby odwrotność funkcji pasowała do definicji funkcji.

W szczególności niektóre operacje boolowskie nie mają odwrotności, które można by zdefiniować jako funkcje. W szczególności dysjunkcja „lub” ma odwrotności, które dopuszczają dwie wartości. W języku naturalnym „lub” reprezentuje alternatywne możliwości.

Zawężanie jest oparte na zestawach wartości, które umożliwiają pakowanie wielu wartości i traktowanie ich jako jednej wartości. Pozwala to zawsze traktować odwrotności funkcji jako funkcje.

Aby to osiągnąć, zestawy wartości muszą rejestrować kontekst, do którego należy wartość. Zmienna może przyjąć tylko jedną wartość w każdym możliwym świecie . Zestawy wartości oznaczają każdą wartość w zestawie wartości ze światem, do którego należy.

Światy możliwe należą do zbiorów światów. Zbiór światów to zbiór wszystkich wzajemnie wykluczających się światów. Łączenie wartości z różnych możliwych światów jest niemożliwe, ponieważ oznaczałoby to łączenie wzajemnie wykluczających się możliwych światów.

Zastosowanie funkcji do zestawów wartości tworzy kombinacje zestawów wartości z różnych światów. Zwężenie zmniejsza te światy, eliminując kombinacje różnych światów z tego samego zestawu światów. Zawężające reguły wykrywają również sytuacje, w których niektóre kombinacje światów okazują się niemożliwe.

W przypadku zwężania nie jest wymagane śledzenie wsteczne. Dzięki spakowaniu możliwych wartości w zestawie wartości wszystkie kombinacje wartości mogą być brane pod uwagę w tym samym czasie. Ocena przebiega jak dla języka funkcjonalnego, łączącego kombinacje wartości w zbiorach wartości, z regułami zawężania eliminującymi ze zbiorów wartości niemożliwe.

Wprowadzenie do zestawów wartości

Zestaw wartości to obiekt, który reprezentuje zestaw wartości, które może mieć zmienna. Zestaw wartości zachowuje się matematycznie jak pojedyncza wartość, podczas gdy wewnętrznie reprezentuje wiele wartości. Aby to osiągnąć, zestaw wartości śledzi wartość wraz z kontekstem lub światem, w którym wystąpiły.

Wiele rozwiązań równania

W matematyce wyrażenie musi reprezentować pojedynczą wartość. Rozważmy na przykład równanie,

{\ displaystyle x ^ {2} = 4}

co implikuje,

{\ Displaystyle x = 2 \ lor x = -2}

Jest to jednak trochę zagmatwane i nie pozwala nam pracować z wieloma wartościami jednocześnie. Jeśli dodatkowe warunki lub ograniczenia zostaną dodane do x, chcielibyśmy rozważyć każdą wartość, aby zobaczyć, czy pasuje do ograniczenia. Tak naiwnie chcielibyśmy napisać,

{\ displaystyle x = \ pm 2}

Naiwnie wtedy

{\ Displaystyle x + x \ w \ lbrace 4,0, -4 \ rbrace}

ale to jest złe. Każdy x musi reprezentować pojedynczą wartość w wyrażeniu. Albo x wynosi 2, albo x = −2. Można to rozwiązać, śledząc te dwie wartości, aby upewnić się, że są one używane konsekwentnie, a to właśnie robi zestaw wartości.

Reprezentacja

Wartość ustawiona dla „x” jest zapisywana jako,

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

Jest to kontener V , który posiada zestaw tagów, par wartości,

${\ Displaystyle 2:: x_ {1}}$
${\ Displaystyle -2:: x_ {2}}$

Wartość 2 jest powiązana z możliwym światem ${\ displaystyle x_ {1}}$ . Wartość -2 jest powiązana z możliwym światem ${\ displaystyle x_ {2}}$ . Oznacza to, że wartość nie może być jednocześnie 2 i −2. $Na$ świecie $wartość zestawu$ wartości musi wynosić 2. Na świecie wartości musi wynosić

Rozwiązanie równania,

{\ displaystyle x ^ {2} = 4}

Jest,

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

Możliwe światy

Możliwy świat jest tu używany jako termin nieformalny. Formalnie możliwy świat jest definiowany przez warunek logiczny. Możliwy świat można uznać za zbiór możliwości dla świata, które pasują do warunku.

Termin „możliwy świat” jest używany, aby ułatwić śledzenie opisu zestawów wartości.

Zestawy świata

Zbiór światów to zbiór możliwych światów, które reprezentują wszystkie możliwości. Więc ${\ Displaystyle \ {x_ {1}, x_ {2} \}}$ to świat ustawiony jako x = 2 (w świecie) lub ${\ Displaystyle x_ {1}}$ = −2 (w świecie ${\ displaystyle x_ {2}}$ ). Nie ma innych możliwości.

$displaystyle$ $x_ {2}}$ nie jest możliwe, aby zdania dla obu światów i były prawdziwe w tym samym czasie.

{\ Displaystyle (x = 2 \ ziemia x = -2) = {\ tekst {fałsz}}}

Zastosowanie funkcji

Reguła stosowania funkcji do zbiorów wartości brzmi:

{\ 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}\w N\})}

Na przykład,

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

Jest,

{\ Displaystyle = V (\ {-2 + -2::x_ {1}\ czapka x_ {1}, -2 + 2:: x_ {1} \ czapka x_ {2}, 2 + -2:: x_ {1}\cap x_{2},2+2::x_{2}\})}

{\ Displaystyle = V (\ {-4:: x_ {1} \ czapka x_ {1}, 0:: x_ {1} \ czapka x_ {2}, 0:: x_ {2} \ ziemia x_ {1} ,2+2::x_{2}\cap x_{1}\})}

Przecięcie świata możliwego z samym sobą jest światem możliwym,

{\ Displaystyle x_ {1} \ czapka x_ {1} = x_ {1}}

{\ Displaystyle x_ {2} \ czapka x_ {2} = x_ {2}}

Przecięcie możliwego świata z innym możliwym światem z tego samego zestawu światów jest puste,

{\ Displaystyle x_ {1} \ czapka x_ {2} = \ {\}}

{\ Displaystyle x_ {2} \ czapka x_ {1} = \ {\}}

Więc,

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

Reguła pustych światów umożliwia odrzucanie oznaczonych wartości z pustych światów

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

dający,

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

Dając wynik, że zgodnie z oczekiwaniami ${\ displaystyle x + x}$ wynosi -4 lub 4.

Zastosowanie do Booleanów

{\ Displaystyle a \ ziemia b}

Jest związkiem między a , b i prawdą , z którego wynika, że zarówno a, jak i b muszą być prawdziwe.

{\ Displaystyle a \ lor b}

Zezwala na wiele wartości dla a i b . jeśli jest ,

{\ Displaystyle a = V (\ {\ nazwa operatora {fałsz}:: a_ {1}, \ nazwa operatora {prawda}:: a_ {2} \})}

wtedy dla b

{\ Displaystyle b = V (\ {\ nazwa operatora {prawda}:: a_ {1}, \ nazwa operatora {fałsz} ::a_{2},\nazwa_operatora {true} ::a_{2}\})}

Oznacza to, że jeśli a jest fałszywe , to b musi być prawdziwe .

Teraz rozważ,

{\ Displaystyle x = 2 \ lor x = -2}

daje,

{\ Displaystyle x = V (\ {\ _:: a_ {1}, 2:: a_ {2} \})}

I

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

ujednolicenie tych dwóch zestawów wartości daje,

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

Para $jest$ odrzucana z powodu zasady „twierdzenia równości”

{\ Displaystyle \ forall m_ {v} \ forall m_ {l} \ forall n_ {v} \ forall n_ {l} ((m_ {v}, m_ {l}) \ w M \ ziemia (n_ {v}, n_{l})\in N)\to (m_{v}\neq n_{v}\to m_{l}\cap n_{l}=\{\})}

${\ displaystyle 2:: a_ {2}}$ wartość ${\ displaystyle -2:: a_ {2}}$ nie pasuje do .

Zależne światy

Rozważ problem,

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

Najpierw oblicz wartość ustawioną dla ${\ Displaystyle X * Y <25}$ ,

{\ Displaystyle V (\ {8:: x_ {1} \ czapka y_ {1}, 24:: x_ {2} \ czapka y_ {1}, 32:: x_ {3} \ czapka 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} \ czapka 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 (\ {{\ tekst {prawda}}:: x_ {1} \ czapka y_ {1}, {\ tekst {prawda}}:: x_ {2} \ czapka y_ {1}, {\ tekst {fałsz}}::x_{3}\cap y_{1},{\text{true}}::x_{1}\cap y_{2},{\text{fałsz}}::x_{2} \cap y_{2},{\text{false}}::x_{3}\cap y_{2}\})}

Ponieważ to stwierdzenie jest prawdziwe, wszystkie fałszywe wartości są odrzucane, dając,

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

Światowy,

{\ Displaystyle x_ {3} \ czapka y_ {1}}

{\ Displaystyle x_ {2} \ czapka y_ {2}}

{\ Displaystyle x_ {3} \cap y_{2}}

są niemożliwe. Światy są puste.

Jeśli zestaw światów jest uwzględniony w obliczeniach, to każdy świat ze zbioru światów musi zostać uwzględniony w wyniku. Jeśli świat nie zostanie znaleziony, jest nazywany światem zależnym i musi być pusty. Świat $wartości$ więc musi być pusty Wartość ustawiona dla jest teraz mniejsza, ${\ displaystyle X}$

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

Drugi warunek jest teraz prostszy ze względu na mniejszy zestaw wartości.

{\ Displaystyle X + Y> 10}

Wtedy zestawy wartości są,

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

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

A kalkulacja jest taka,

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

Ale ${\ displaystyle x_ {2} \ cap y_ {2}}$ jest pusty. Więc,

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

Więc ${\ Displaystyle x_ {1} \ cap y_ {1}}$ i ${\ Displaystyle x_ {1} \ cap y_ {2}}$ są puste,

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

Teraz $jako$ nie są reprezentowane i są $usuwane$ Więc,

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

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

Każde wykonane obliczenie może zmniejszyć rozmiar zestawów wartości poprzez usunięcie zależnych światów, ale dodać nowy zestaw wartości, którego rozmiar jest iloczynem rozmiarów wejściowych zestawów wartości. Następnie obliczenia należy przeprowadzić najpierw tam, gdzie iloczyn wielkości wejściowych zbiorów wartości jest najmniejszy.

Pizza, piwo, whisky

Po ciężkim dniu pracy, próbując dotrzymać jakiegoś szalonego terminu z projektem z piekła rodem, nadchodzi ta desperacka godzina o 22:00, kiedy wszyscy potrzebujemy pizzy, piwa i whisky. Pizzerie czynne są w godz.

{\ Displaystyle {\ text {PizzaShop}} (V (\ {{\ 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} \}))}

Piwo, które możesz dostać,

{\ Displaystyle {\ tekst {BottleshopWithBeer}} (V (\ {{\ text{South Melbourne}}::b_{1},{\text{St Kilda}}::b_{2},{\text{Carlton}}::b_{3},{\text{Docklands}}: :b_{4}\}))}

Whisky,

{\ Displaystyle {\ tekst {Bottleshop With Whisky}} (V (\ {{\ tekst {Essendon}}:: w_ {1}, { \text{Południowe Melbourne}}::w_{2}\}))}

Policja jest w pobliżu, a my nie stajemy się młodsi. Gdzie iść?

{\ Displaystyle {\ tekst {Dokąd iść}} (x) = {\ tekst {PizzaShop}} (x) \ ziemia {\ tekst {BottleshopWithBeer }}(x)\land {\text{BottleshopWithWhiskey}}(x)}

Jeśli wiązania są stosowane w kolejności od lewej do prawej ,

{\ Displaystyle x = V (\ {{\ tekst {Carlton}}:: p_ {1}, {\ tekst {Richmond}}:: p_ {2}, {\ tekst {Południowe Melbourne}}:: p_ {3 },{\text{Footscray}}::p_{4},{\text{St Kilda}}::p_{5},{\text{Toorak}}::p_{6}\})}

Następnie musimy ujednolicić to z,

{\ Displaystyle x = V (\ {{\ tekst {South Melbourne}}: :b_{1},{\text{St Kilda}}::b_{2},{\text{Carlton}}::b_{3},{\text{Docklands}}::b_{4}\} )}

Spowoduje to utworzenie 24 kombinacji, z których są pasujące,

{\ Displaystyle x = V (\ {{\ tekst {South Melbourne }}::b_{1}\cap p_{3},{\text{St Kilda}}::b_{2}\cap p_{5},{\text{Carlton}}::b_{3}\ czapka p_{1}\})}

W końcu musimy ujednolicić się z whisky.

{\ Displaystyle x = V (\ {{\ tekst {Essendon}}:: w_ {1}, {\ tekst {South Melbourne}} ::w_{2}\})}

Co daje 6 kombinacji. Pasujący jest,

{\ Displaystyle x = V (\ {{\ tekst {South Melbourne}}:: b_ {1} \ cap p_ {3} \ cap w_{2}\})}

Łącznie wygenerowano 30 kombinacji.

Jeśli wiązania są stosowane w kolejności od prawej do lewej ,

{\ Displaystyle x = V (\ {{\ tekst {Essendon}}:: w_ {1}, {\ tekst {South Melbourne}} ::w_{2}\})}

Następnie musimy ujednolicić to z,

{\ Displaystyle x = V (\ {{\ tekst {South Melbourne}}: :b_{1},{\text{St Kilda}}::b_{2},{\text{Carlton}}::b_{3},{\text{Docklands}}::b_{4}\} )}

Spowoduje to utworzenie 8 kombinacji, z których będzie pasować,

{\ Displaystyle x = V (\ {{\ tekst {South Melbourne}}:: b_ {1} \ cap w_ {2} \})}

W końcu musimy ujednolicić się z pizzą.

{\ Displaystyle x = \ {{\ text{Carlton}}::p_{1},{\text{Richmond}}::p_{2},{\text{Południowe Melbourne}}::p_{3},{\text{Footscray}}:: p_{4},{\text{St Kilda}}::p_{5},{\text{Toorak}}::p_{6}\}}

Co daje 6 kombinacji. Pasujący jest,

{\ Displaystyle x = V (\ {{\ tekst {South Melbourne}}:: b_ {1} \ czapka w_ {2} \ \ czapka p_{3}\})}

Wynik jest taki sam, ale wygenerowano tylko 14 kombinacji, aby dojść do wniosku.

Każde obliczenie łączy zestawy wartości w celu utworzenia zestawu wartości, który jest iloczynem rozmiarów wejściowych zestawów wartości. Ustawiona wartość zostanie następnie zmniejszona. A każda kalkulacja ma taką samą szansę na zawężenie kalkulacji. Tak więc kontrolując kolejność i kontynuując obliczenia z najmniejszym iloczynem rozmiarów, będzie mniej obliczeń i mniej kombinatorycznej eksplozji .

Niech wyrażenia i wiele wartości

Potrzebne jest ogólne rozwiązanie problemu odwrotności funkcji, które nie są funkcjami. Wymagana jest reprezentacja wartości, która jest ograniczona do przynależności do zbioru wartości. Wyrażenie let może być użyte do przedstawienia wartości, która jest członkiem zbioru,

{\ Displaystyle \ nazwa operatora {niech} x \ w X \ nazwa operatora {w} x}

$W$ tym . Ograniczenie jest wyrażeniem boolowskim, które musi spełniać zmienna. Wyrażenie let umożliwia przedstawienie ograniczenia w wyrażeniu. Gdyby istniała ogólna reguła stosowania funkcji wyrażeń z ograniczeniami, wówczas ograniczenie można by traktować jak wartość.

W ramach zastosowania funkcji, jednego wyrażenia pozwól drugiemu,

{\ Displaystyle (\ nazwa operatora {niech} x \ w X \ nazwa operatora {w} x) \ (\ nazwa operatora {niech} y \ w Y \ nazwa operatora {w} y)}

{\ Displaystyle = \ nazwa operatora {niech} x \ w X \ ziemia y \ w Y \ nazwa operatora {w} x \ y }

{\ Displaystyle = \ nazwa operatora {niech} (x, y) \ w X \ razy Y \ nazwa operatora {w} x \ y}

Ale inna reguła dotyczy zastosowania wyrażenia let do samego siebie. Wyrażenie let nie ogranicza zakresu zmiennej x, więc x jest tą samą zmienną w dwóch wyrażeniach let.

{\ Displaystyle (\ nazwa operatora {niech} x \ w X \ nazwa operatora {w} x) \ (\ nazwa operatora {niech} x \ w X \ nazwa operatora {w} x)}

{\ Displaystyle = \ nazwa operatora {niech} x \ w X \ nazwa operatora {w} x \ x}

Wydaje się, że nie ma prostej reguły łączenia wyrażeń let. Wymagana jest ogólna forma wyrażenia reprezentująca zmienną, której wartość należy do zbioru wartości. Wyrażenie powinno być oparte na zmiennej i zbiorze.

Zastosowanie funkcji zastosowane do tego formularza powinno dać inne wyrażenie w tej samej postaci. W ten sposób dowolne wyrażenie na funkcjach o wielu wartościach może być traktowane tak, jakby miało jedną wartość.

Nie wystarczy, aby forma reprezentowała tylko zbiór wartości. Każda wartość musi mieć warunek określający, kiedy wyrażenie przyjmuje wartość. Wynikowa konstrukcja jest zbiorem par warunków i wartości, zwanym „zbiorem wartości”.

Teoria zbiorów wartości

„Zestaw wartości” K jest zdefiniowany jako zbiór par, z których każda para składa się z wartości i zestawu warunków zależnych. Zestaw warunków zależnych jest używany przez „funkcję warunkową” do określenia, czy zestaw wartości przyjmuje tę wartość.

Funkcja warunku jest zdefiniowana przez 3 aksjomaty,

Każda para ${\ Displaystyle (v, l)}$ $wartość$ zestawu wartości wynosi v , jeśli warunku została zastosowana do listy, ${\ Displaystyle C (l)}$ , jest prawdą.
Jeden z warunków jest prawdziwy.
Tylko jeden z warunków jest prawdziwy.

Warunek jest reprezentowany jako funkcja zastosowana do zestawu warunków zależnych, aby umożliwić kontrolowanie struktury warunku. Również zestaw warunków służy do zawężania przez wykluczenie wartości zależnych . Jednak w większości przypadków zestaw wartości można traktować jako zbiór par wartości i warunków. Funkcja warunkowa tłumaczy zbiór na warunek.

Formalnie,

Nazwa	Definicja
Funkcja warunkowa	${\ 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 )}$
Warunek wartości	${\ Displaystyle \ forall v \ forall l ((v, l) \ w K \ ziemia C (l) \ do v=V(K)}$
Kompletny zestaw	${\ Displaystyle \ istnieje v \ istnieje l (v, l) \ w K \ ziemia C (l)}$
Wykluczenie	${\ 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})\kraina C(l_{2}))}$

Funkcja wartości

Używając warunku wartości i kompletnych aksjomatów,

{\ Displaystyle \ istnieje v \ istnieje l (v, l) \ w K \ ziemia C (l) \ ziemia v = V(K)}

Jako wyrażenie let staje się to,

\ Displaystyle V (K) = \ nazwa operatora {niech} (v, l) \ w K \ ziemia C (l) \ nazwa_operatora {w} v}

Pojedyncza wartość

Wartość ustawiona do reprezentowania pojedynczej wartości to,

{\ Displaystyle k = V (\ {(k, \ {\}) \})}

wyprowadzenie jest,

{\ Displaystyle V (\ {(k, \ {\}) \})}

{\ Displaystyle = \ nazwa operatora {niech} (v, l) \ in \ {(k, \ {\}) \} \ ziemia C (l) \ nazwa operatora {w} v}

{\ Displaystyle = \ nazwa operatora {niech} v = k \ ziemia C (\ {\}) \ nazwa operatora {w} v} = niech ⁡

= \ nazwa operatora {niech} v = k \ nazwa operatora {w} v}

{\ Displaystyle = k}

Element zestawu

Zestaw wartości reprezentujący element zestawu to:

{\ Displaystyle \ forall x \ forall X (\ nazwa operatora {niech} x \ w X \ nazwa operatora {w} x) = \ nazwa operatora {niech} R = V (\ {(w, \ {(R, x, w) \}):w\w X\})\nazwa_operatora {w} R}

Ta dość dziwna definicja dodaje wartość ustawioną jako część warunku zależnego. Służy to zawężaniu przez wykluczenie wartości zależnych .

Wartość wyrażenia to

{\ Displaystyle x = V (R)}

.

Zarówno R, jak i x muszą być zawarte w warunku zależnym, ponieważ R identyfikuje zestaw wartości, do którego należy warunek zależny, a x dostarcza zmienną używaną do przenoszenia wartości w wyrażeniu let.

Jeśli pominie się dodanie R do warunku zależnego, wyrażenie przybiera prostszą i bardziej zrozumiałą postać,

{\ Displaystyle \ forall x \ forall X (\ nazwa operatora { let} x\in X\nazwaoperatora {in} x)=V(\{(w,\{(\_,x,w)\}):w\in X\})}

wyprowadzenie jest,

{\ Displaystyle V (\ {(w, \ {(r, x, w): w \ w X \})}

{\ Displaystyle = \ nazwa operatora {niech} (v, l) \ w \ {(w, \ {(r, x, w) \}): w \ w X \} \ ląd C (l)\operatorname {w} v}

{\ Displaystyle = \ nazwa operatora {niech} v \ w X \ ziemia ({\ bigwedge _ {(r, z, u) \ w \ {(\ _, x, v) \}} z = u}) \ nazwa operatora {w} v}

{\ Displaystyle = \ nazwa operatora {niech} v \ w X \ ziemia (\ forall r \ forall z \ forall u (r, z, u) \ in \ {(\ _, x, v) \} \ do z = u) \ nazwa operatora {w} v}

{\ Displaystyle = \ nazwa operatora {niech} v \ w X \ ziemia x = v \ nazwa operatora {w} v}

{\ Displaystyle = \ nazwa operatora {niech} x \ w X \ nazwa operatora {w} x}

Zastosowanie funkcji

Zastosowanie funkcji zestawów wartości jest podane przez,

{\ Displaystyle V (M) \ V (N) = V (\ {(m_ {v} \ n_ {v}, m_ {l} \ kubek n_ {l}): (m_ {v}, m_ {l} )\w M\kraju (n_{v},n_{l})\w N\})}

Pochodzenie,

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

{\ Displaystyle = \ nazwa operatora {niech} (m_ {v}, m_ {l}) \ w M \ ziemia C (m_ {l}) \ nazwa operatora {w} m_ {v}) \ (\ nazwa operatora {let} (n_{v},n_{l})\in N\land C(n_{l})\operatorname {in} n_{v})}

{\ Displaystyle = \ nazwa operatora {niech} (m_ {v}, m_ {l}) \ w M \ ziemia (n_ {v}, n_ {l}) \ w N \ ziemia C (n_ {l})\land C(n_{l})\nazwa operatora {w} m_{v}\ n_{v})}

Następnie używając,

{\ Displaystyle C (m_ {l}) \ ziemia C (n_ {l})}

{\ Displaystyle = ({\ bigwedge _ {(z, u) \ w m_ {l}} z = u}) \ ziemia ({\ bigwedge _ {(z, u) )\w n_{l}}z=u})}

{\ Displaystyle = ({\ bigwedge _ {(z, u) \ w m_ {l} \ kubek n_ {l}} z = u}) }

{\ Displaystyle = C (m_ {l} \ kubek n_ {l})}

Dostawać,

{\ Displaystyle = \ operatorname {niech} (m_ { v},m_{l})\in M\land (n_{v},n_{l})\in N\land C(n_{l}\cup n_{l})\nazwa operatora {in} m_{v }\ n_{v})}

{\ Displaystyle = \ nazwa operatora {niech} (v, l) \ w \ {(m_ {v} \ n_ {v}, m_ {l} \ kubek 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} \ kubek n_ {l}): (m_ {v}, m_ {l}) \ w M \ ziemia (n_ { v},n_{l})\w N\})}

Wykluczenie

Wykluczenie to reguła określająca, kiedy warunki muszą być fałszywe,

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

Może to wynikać z,

{\ Displaystyle V (M) \ w s}

{\ Displaystyle \ do \ forall v \ forall l ((v, l) \ w M \ ziemia C (l)) \ do (v = V [M] \ ziemia V (M) \ w s)}

{\ Displaystyle \ do \ forall v \ forall l ((v, l) \ w M \ ziemia C (l)) \ do v\in S}

{\ Displaystyle \ do \ forall v \ forall l ((v, l) \ w M \ ląd v \ nie \ w S) \ do \ neg C (l)}

Uproszczenie

Reguła uproszczenia pozwala na odrzucanie wartości, których warunek jest fałszywy.

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

Pochodzenie

{\ Displaystyle V (\ {(v, l): (v, l) \ w K \ ziemia C (l) \})}

{\ Displaystyle = \ nazwa operatora {niech} (v, l) \ w \ {(v, l): (v, l) \ w K \ ziemia C (l) \ } \ ziemia C (l) \ nazwa operatora {w} v}

{\ Displaystyle = \ nazwa operatora {niech} (v, l )\in K\land C(l)\land C(l)\operatorname {in} v}

{\ Displaystyle = \ nazwa operatora {niech} (v, l) \ w K \ ziemia C (l) \ nazwa operatora {w} v

{\ Displaystyle = V (K)}

Podsumowanie rezultatów

Nazwa	Reguła
Funkcja wartości	$C (l) \ nazwa_operatora {w} v}$
Pojedyncza wartość	${\ Displaystyle k = V (\ {(k, \ {\}) \})}$
Ustaw element	${\ Displaystyle \ forall x \ forall X (\ nazwa operatora {niech} x \ w X \ nazwa operatora {w} x) = \ nazwa operatora {niech} R = V (\ {(w, \ {(R, x, w) \}):w\w X\})\nazwa_operatora {w} R}$
Zastosowanie funkcji	${\ Displaystyle V (M) \ V (N) = V (\ {(m_ {v} \ n_ {v}, m_ {l} \ kubek n_ {l}): (m_ {v}, m_ {l} )\w M\kraju (n_{v},n_{l})\w N\})}$
Wykluczenie	${\ Displaystyle V (M) \ w s \ iff (\ forall v \ forall l((v,l)\in M\land v\not \in s)\to \neg C(l))}$
Uproszczenie	${\ Displaystyle V (K) = V (\ {(v, l): (v, l )\w K\land C(l)\})}$
Twierdź równe	${\ Displaystyle V (M) = V (N) \to (\forall v\forall l((v,l)\in N\land v\not \in S(M))\to \neg C(l))}$

Wartość ustawia tożsamość

Definiując zastosowanie funkcji do zbiorów wartości, zdefiniowano również na nowo definicję równości zbiorów wartości. Stara definicja równości nadal istnieje, ponieważ zbiory wartości są konstruowane jako zbiór par. Dwa zbiory są równe, jeśli zawierają te same elementy. Ta definicja równości zestawów wartości jest w najlepszym razie myląca.

Potrzebne jest użycie nazwy lub tożsamości zmiennej, z której zbudowany jest zestaw wartości, jako części struktury zestawu wartości. Dzięki temu zestawy wartości byłyby odrębne, chyba że byłyby oparte na tej samej zmiennej.

W matematyce kwantyfikacja dotyczy wartości, a nie formuł. Aby przejść dalej z dokładną definicją zestawów wartości, potrzebna jest kwantyfikacja na podstawie formuł, w sposób umożliwiający porównanie identyczności formuł. Rozróżnienie między formułą reprezentującą wartość a tożsamością formuły to rozróżnienie użycie-wzmianka . notacja,

{\ Displaystyle \ forall x \ # u}

wprowadza się jako średnią kwantyfikacji względem wzoru x , gdzie x odnosi się do wartości, jako zastosowania, a u odnosi się do tożsamości wzoru przedstawionego lub wspomnianego.

Używając tej notacji, elementem definicji zestawu byłoby:

{\ 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\}))\nazwa_operatora {in} R}

Każde odniesienie do zestawu wartości musiałoby wówczas zostać zmienione, aby uwzględnić dodatkowy poziom struktury w zbiorze wartości, co utrudniłoby czytanie opisu. Ze względu na czytelność ten dodatkowy poziom struktury został pominięty w definicji zestawów wartości.

Zwężenie

„Zawężanie” określa, kiedy warunki dla wartości muszą być fałszywe . Zawężanie rozpoczyna się, gdy wartość dwóch zestawów wartości jest równa.

Zawężenie przez zapewnienie równego

Stwierdzenie, że dwa zestawy wartości są równe, daje regułę zawężania,

{\ Displaystyle \ forall m_ {v} \ forall m_ {l} \ forall n_ {v} \ forall n_ {l} ((m_ {v}, m_ {l}) \ w M \ ziemi (n_ { v},n_{l})\in N)\to (m_{v}\neq n_{v}\to \neg (C(m_{l})\land C(n_{l}))}}

Do wyprowadzenia zacznij od,

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

Warunek wartości daje,

{\ Displaystyle (\ forall m_ {v} \ forall m_ {l} ((m_ {v}, m_ {l}) \ in M\land C(m_{l})\to v=V(M))\land (\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}) \ w M \ kraina C(m_{l}))\to m_{v}=V(M))\land (((n_{v},n_{l})\w N\land C(n_{l}))\ do 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 (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}))}}

Zwężenie przez spójnik

Jeśli dowolny warunek bazowy jest fałszywy, wszystkie otrzymane z niego warunki są fałszywe.

Wynika to z definicji funkcji Warunek,

{\ Displaystyle C (l) = ({\ bigwedge _ {(r, z, u) \ w l} z = u} ))}

Warunek bazowy dla (r, z, u) to:

{\ Displaystyle C (\ {(r, z, u) \} = (z = u)}

$fałszywe$ jeśli to jest fałszywe

Zawężenie przez skrzyżowane warunki

Jeśli lista warunków zależnych ma dwa różne warunki podstawowe z tego samego zestawu wartości, musi to być fałsz.

Aby to wywnioskować, zacznij od reguły wykluczenia, która jest:

{\ 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}))\implikuje \neg (C(l_{1})\kraina C(l_{2}))}

Wtedy dla dowolnego zestawu warunków zależnych l ,

{\ Displaystyle ((K, x, v_ {1}) \ w l \ \ ziemia (K ,x,v_{2})\w l\land v_{1}\neq v_{2}}

{\ Displaystyle \ implikuje (v_ {1}, \ {(K. ,x,v_{1})\})\w K\land (v_{2},\{(K,x,v_{2})\})\w K\land (v_{1},l_{ 1})\neq (v_{2},l_{2}))}

\ Displaystyle \ implikuje \ negacja (C (\ {(K, x, v_ {1}) \}) \ ziemia do (\ {(K, x, v_ {2}) \})}}

{\ Displaystyle \ implikuje \ neg C (l)}

Jeśli więc zależna lista warunków jest oparta na dwóch warunkach z tego samego zestawu wartości, wartość warunku tej zależnej listy warunków jest fałszywa.

Zawężanie przez wykluczenie wartości zależnych

Każdy zestaw wartości nakłada ograniczenie na podstawowy zestaw wartości, z którego jest zbudowany. Jeśli zestaw wartości podstawowych zawiera wartości, które nie występują jako wartości zależne w zestawie wartości, warunki dla tych wartości muszą być fałszywe.

Aby to wyprowadzić, zacznij od pełnej reguły zestawu,

{\ Displaystyle \ istnieje v \ istnieje \ l (v, l) \ w K \ do C (l)}

Funkcja warunku to

{\ Displaystyle C (l) = ({\ bigwedge _ {(r, z, u) \ w l} z = u} ))}

Można wybrać konkretny warunek zależny, ponieważ implikuje to cały warunek,

{\ Displaystyle \ forall L \ C (l) \ do (L, z, u) \ w l \ do z = u}

Więc

{\ Displaystyle \ forall L \ istnieje v \ istnieje l \ (v, l) \in K\to C(l)\to (L,z,u)\in l\to z=u}

tutaj ${\ Displaystyle z = V (L)}$ . Wyrażenie można zmienić, aby zdefiniować zestaw wartości, które może przyjąć ${\ Displaystyle V (L)}$

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

a więc,

{\ Displaystyle V (L) \ w E (K, L)}

Następnie stosując regułę wykluczenia,

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

daje,

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

Jest to zawężająca reguła wykluczania. $, L)}$ K to zbiór wartości w zestawie wartości bazowej L , które są reprezentowane w zbiorze wartości K. Warunki dla innych wartości muszą być fałszywe.

Zestawy wartości probabilistycznych

Zestaw wartości rejestruje zależne warunki, do których można zastosować funkcję warunku w celu wydedukowania prawdziwości twierdzenia, że zestaw wartości ma określoną wartość. Tej samej struktury można użyć do podania prawdopodobieństwa, że zestaw wartości będzie równy określonej wartości. Funkcja warunku to

{\ Displaystyle C (l) = ({\ bigwedge _ {(r, z, u) \ w l} z = u} ))}

Funkcja prawdopodobieństwa to

{\ Displaystyle P (l) = ({\ prod _ {(r, z, u) \ w l} P. (z=u)}))}

Jest to prawdopodobieństwo, że każdy przypadek bazowy ma określoną wartość, jeśli zdarzenia są niezależne.

Funkcja prawdopodobieństwa jest zdefiniowana przez 3 aksjomaty,

Każda para $l)} oznacza$ $wynosi$ że prawdopodobieństwo zestawu wartości v jest funkcją prawdopodobieństwa zastosowaną do listy, ${\ Displaystyle P (l)}$ .
Suma prawdopodobieństw dla całego zbioru wartości wynosi 1.
Prawdopodobieństwo wystąpienia dowolnych dwóch par w zbiorze wartości wynosi zero.

Funkcja prawdopodobieństwa podaje prawdopodobieństwa wyników na podstawie prawdopodobieństw początkowych określonych przez wnioskowanie indukcyjne Boole'a .

Formalnie,

Nazwa	Definicja
Funkcja prawdopodobieństwa	${\ Displaystyle P (l) = ({\ prod _ {(r, z, u) \ w l} P. (z=u)}))}$
Warunek wartości	${\ Displaystyle \ forall vP (v = V (K)) = \ suma _ {(v, l) \ w K}P(l)}$
Kompletny zestaw	${\ Displaystyle \ suma _ {(v, l) \ w K} P (l) = 1}$
Dozwolone wartości	${\ Displaystyle \ suma _ {(v, l) \ w K \ ziemia v \ w \ operatorname {gset} (V(K))}P(l)=1}$
Wykluczenie	${\ Displaystyle \ forall v_ {1} \ forall l_ {1} \ forall v_ {2} \ forall l_ {2} ((v_ {1}, l_ {1} )\w K\land (v_{2},l_{2})\in K\land (v_{1},l_{1})\neq (v_{2},l_{2}))\do P (C(l_{1})\kraina C(l_{2}))=0}$

Prawdopodobieństwa dla każdej wartości w zbiorze wartości można obliczyć z prawdopodobieństw w zbiorach wartości bazowych przy użyciu funkcji prawdopodobieństwa i warunku wartości. Zestawy wartości bazowych są przeznaczone dla pojedynczej wartości lub wielu zestawów wartości.

Prawdopodobieństwo dla pojedynczej wartości

Wartość ustawiona do reprezentowania pojedynczej wartości to,

{\ Displaystyle k = V (\ {(k, \ {\}) \})}

Kompletna reguła brzmi:

{\ Displaystyle \ suma _ {(v, l) \ w K} P (l)}

{\ Displaystyle = \ suma _ {(v, l) \ w \ {(k, \ {\}) \}} P (l)} = P ( { } ) {

{ \})}

{\ displaystyle = 1}

Co jest zgodne z aksjomatem.

Prawdopodobieństwa dla wielu wartości

Wartość ustawiona do reprezentowania wielu wartości to,

{\ Displaystyle \ forall x \ forall X (\ nazwa operatora { let} x\in X\nazwaoperatora {in} x)=V(\{(w,\{(\_,x,w)\}):w\in X\})}

Prawdopodobieństwo określa reguła dozwolonych wartości,

{\ Displaystyle \ suma _ {(v, l) \ w K \ ziemia v \ w \ operatorname {gset} (V(K))}P(l)=1}

co upraszcza,

{\ Displaystyle \ suma _ {v \ in \ operatorname {gset} (V (K))} P (x = v) = 1}

Jeśli podane są wcześniejsze oszacowania prawdopodobieństw dla wartości, to będą one proporcjonalne do prawdopodobieństw późniejszych, jeśli wartość jest w zbiorze wartości.

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

Jeśli wartość nie znajduje się w zestawie wartości, prawdopodobieństwa wyniosą zero,

{\ Displaystyle \ forall v \ nie \ w \ operatorname {gset} (V (K)), P (x = v) = 0}

Więc,

{\ Displaystyle \ suma _ {v \ in \ operatorname {gset} (V (K))} w * P_ {i} (x=v)=1}

{\ Displaystyle w = {\ Frac {1} {\ suma _ {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)}} {\ suma _ {v \ in \ operatorname {gset} (V (K))} P_ {i} (x = v)}}}

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

Jeśli wszystkie prawdopodobieństwa wcześniejsze są takie same, to prawdopodobieństwa są takie,

{\ Displaystyle \ forall v \ in \ operatorname {gset} (V (K)), P (x = v) = {\ Frac {1} {| \ operatorname {gset} (V (K)) |}}}

Prawdopodobieństwa ogólnych zbiorów wartości

Ogólny zestaw wartości jest tworzony z zastosowania podstawowych zestawów wartości. Regułę warunku wartości i funkcję prawdopodobieństwa można połączyć, aby dać,

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

Dostęp do zestawu wartości

Zawężanie umożliwia eliminację wartości, które nie spełniają ograniczeń zmiennej. Uważane za podstawę algorytmu rozwiązywania równań, to zawężenie daje zestaw wartości zgodnych z ograniczeniami nałożonymi na zmienną. Jednak w matematyce nie ma sposobu, aby uzyskać dostęp do tego zestawu wartości.

Jeśli jest wyrażeniem ograniczającym zmienną $E (x)$ , to zbiór wartości, które może przyjąć zmienna, to mi ( x ) {

{\ Displaystyle \ {z: E (z) \}}

Zdefiniuj gset x jako zbiór wartości, które spełniają ograniczenia na x . Rozważ zdefiniowanie gset jako,

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

Definicja ta polega na znajomości wyrażenia E , które jest warunkiem dającym wszystkie ograniczenia na x . W matematyce E nie można otrzymać z x . Tak więc nie ma funkcji matematycznej, którą można zastosować do zmiennej, aby zażądać zestawu wartości. Czy zatem gset można dodać do matematyki?

Definicja metamatematyki

Możliwa może być metamatematyczna definicja gset . Wyobraź sobie, że to, co znamy jako matematyka, jest w rzeczywistości realizowane przez metafunkcję o nazwie math . matematyka przyjmuje abstrakcyjne drzewo składniowe i nadaje znaczenie zmiennym i strukturom matematycznym oraz dodaje kwantyfikatory egzystencjalne dla zmiennych, które nie zostały jawnie skwantyfikowane.

math byłaby wyrażeniem w środowisku metamatematycznym z własnymi zmiennymi. Aby odróżnić te metazmienne od zmiennych matematycznych, przedstaw je wielkimi literami, a zmienne matematyczne małymi literami.

Załóżmy teraz, że istnieje rozszerzona implementacja matematyki zaimplementowana przez funkcję xmath , zdefiniowaną jako: