Logika wektorowa

Logika wektorowa to algebraiczny model logiki elementarnej oparty na algebrze macierzowej . Logika wektorowa zakłada, że ​​wartości prawdy odwzorowują się na wektorach , a operacje monadyczne i diadyczne są wykonywane przez operatorów macierzowych. „Logiki wektorowej” używano również w odniesieniu do reprezentacji klasycznej logiki zdań jako przestrzeni wektorowej , w której wektory jednostkowe są zmiennymi zdań . Logika predykatów $orzeczeń$$,$ w której osie reprezentują litery i . W przestrzeni wektorowej dla logiki zdań początek reprezentuje fałsz, F, a nieskończone obrzeża reprezentują prawdę, T, podczas gdy w przestrzeni dla logiki predykatów początek reprezentuje „nic”, a obrzeże reprezentuje ucieczkę od niczego lub „coś”. ".

Przegląd

Klasyczna logika binarna jest reprezentowana przez mały zestaw funkcji matematycznych zależnych od jednej (monadycznej) lub dwóch (diadycznych) zmiennych. W zestawie binarnym wartość 1 odpowiada true , a wartość 0 false . Dwuwartościowa logika wektorowa wymaga zgodności między wartościami prawdy prawdziwymi (t) i fałszywymi (f) oraz dwoma q -wymiarowymi znormalizowanymi wektorami kolumnowymi o wartościach rzeczywistych s i n , stąd:

${\ Displaystyle t \ mapsto s}$ i ${\ Displaystyle f \ mapsto n}$

(gdzie jest $znormalizowany$ ” oznacza, że ​​​​długość 1; zwykle s i n są wektorami ortogonalnymi). Ta zgodność generuje przestrzeń wektorowych wartości logicznych: V ₂ = { s , n }. Podstawowe operacje logiczne zdefiniowane za pomocą tego zestawu wektorów prowadzą do operatorów macierzowych.

Operacje logiki wektorowej są oparte na iloczynie skalarnym między q -wymiarowymi wektorami kolumnowymi: ${\ Displaystyle u ^ {T} v = \ langle u, v \ rangle}$ : ortonormalność między wektorami s i n oznaczają, że ${\ Displaystyle \ langle u, v \ rangle = 1}$ i ${\ displaystyle u = v$ } ${\ Displaystyle \ langle u, v \ rangle = 0}$ jeśli ${\ Displaystyle u \ neq v}$ , gdzie ${\ Displaystyle u, v \ in \{s,n\}}$ .

Operatory monadyczne

Operatory $z$ a powiązane q i kolumn Dwa podstawowe operatory monadyczne dla tej dwuwartościowej logiki wektorowej to tożsamość i negacja :

• Tożsamość : logiczny identyfikator tożsamości ( p ) jest reprezentowany przez macierz. $displaystyle I = ss ^ {T} + nn ^ {T}}$ \ Macierz ta działa następująco: Ip = p , p ∈ V ₂ ; względu na ortogonalność s względem n mamy s ${\ Displaystyle Is = ss ^ {T} s + nn ^ {T} s = s \ langle s, s \ rangle + n \ langle n, s \ rangle = s}$ i podobnie ${\ displaystyle In = n}$ . Należy zauważyć, że ta macierz identyczności logiki wektorowej nie jest generalnie macierzą tożsamości w sensie algebry macierzy.
• Negacja : logiczna negacja ¬ p jest reprezentowana przez macierz ${\ Displaystyle N = ns ^ {T} + sn ^ {T}}$ W konsekwencji Ns = n i Nn = s . Inwolucyjne zachowanie negacji logicznej, a mianowicie, że ¬(¬ p ) równa się p , odpowiada temu, że N ² = I .

Operatory diadyczne

16 dwuwartościowych operatorów diadycznych odpowiada funkcjom typu $\ Displaystyle Dyad: V_ {2} \ czasami V_ {2} \ do V_ {2}}$ ; macierze diadyczne mają q ² rzędy i q kolumn. Macierze, które wykonują te operacje diadyczne, są oparte na właściwościach produktu Kroneckera . Dwie właściwości tego iloczynu są istotne dla formalizmu logiki wektorowej:

1. Właściwość produktów mieszanych

   Jeśli A , B , C i D są macierzami o takiej wielkości, że można utworzyć iloczyn macierzowy AC i BD , to

   $\ Displaystyle (A \ otimes B) (C \ otimes D) = AC \ otimes BD}$

2. Transpozycja dystrybucyjna Operacja transpozycji jest dystrybutywna względem iloczynu Kroneckera:
   ${\ Displaystyle (A \ otimes B) ^ {T} = A ^ {T} \ otimes B ^ {T}.}$

Korzystając z tych właściwości, można uzyskać wyrażenia dla diadycznych funkcji logicznych:

• spójnik . Koniunkcja ( p ∧ q ) jest wykonywana przez macierz, która działa na dwóch wektorowych wartościach prawdy: ${\ Displaystyle C (u \ otimes v)} Ta$ macierz odtwarza cechy klasycznej koniunkcji prawda- tabela w swoim sformułowaniu:

${\ Displaystyle C = s (s \ czasami s) ^ {T} + n (s \ czasami n) ^ {T} + n (n \ czasami s) ^ {T} + n (n \ otimes n) ^ {T}}$

i weryfikuje

${\ Displaystyle C (s \ otimes s) = s,}$ i

${\ Displaystyle C (s \ otimes n) = C (n \ otimes s) = C (n \ otimes n) = n.}$

• Rozłączenie . Alternatywa ( p ∨ q ) jest realizowana przez macierz

${\ Displaystyle D = s (s \ czasami s) ^ {T} + s (s \ czasami n) ^ {T} + s (n \ czasami s) ^ {T} + n (n \ czasami n) ^ { T},}$ w wyniku

${\ Displaystyle D (s \ czasami s) = D (s \ czasami n) = D (n \otimes s)=s}$ i

${\ Displaystyle D (n \ otimes n) = n.}$

• Implikacja . Implikacja odpowiada w logice klasycznej wyrażeniu p → q ≡ ¬ p ∨ q . Wersja logiki wektorowej tej równoważności prowadzi do macierzy reprezentującej tę implikację w logice wektorowej: ${\ Displaystyle L = D (N \ czasami I)}$ . Jawnym wyrażeniem dla tej implikacji jest:

${\ Displaystyle L = s (s \ czasami s) ^ {T} + n (s \ czasami n) ^ {T} + s (n\otimes s)^{T}+s(n\otimes n)^{T},} i$

spełnione są własności implikacji klasycznej:

${\ Displaystyle L (s \ otimes s) = L (n \ otimes s) = L (n \ otimes n) = s}$ i

${\ Displaystyle L (s \ otimes n) = n.}$

• Równoważność i wyłączność lub . W logice wektorowej równoważność p ≡ q jest reprezentowana przez następującą macierz:

${\ Displaystyle E = s (s \ czasami s) ^ {T} + n (s \ czasami n) ^ {T} + n (n \ czasami s) ^ {T} + s (n \ czasami n) ^ {T}}$ z

${\ Displaystyle E (s \ czasami s) = E (n \ czasami n)=s}$ i

${\ Displaystyle E (s \ otimes n) = E (n \ otimes s) = n.}$

Wyłączność lub jest zaprzeczeniem równoważności, ¬ ( p ≡ q ); odpowiada $określonej$ przez

${\ Displaystyle X = n (s \ czasami s) ^ {T} + s (s \ czasami n) ^ {T} + s (n \ czasami s) ^ {T} + n (n \ czasami n) ^ {T}}$

z ${\ Displaystyle X (s \ czasami s) = X (n \ czasami n )=n}$ i

${\ Displaystyle X (s \ otimes n) = X (n \ otimes s) = s.}$

• NAND i NOR

Macierze S i P odpowiadają odpowiednio operacjom Sheffera (NAND) i Peirce'a (NOR):

${\ Displaystyle S = NC}$

${\ Displaystyle P = ND}$

Przykłady liczbowe

Oto numeryczne przykłady niektórych podstawowych bramek logicznych zaimplementowanych jako macierze dla dwóch różnych zestawów dwuwymiarowych wektorów ortonormalnych dla s i n .

Zestaw 1 :

$${\ Displaystyle s = {\ rozpocząć {bmatrix} 1 \\ 0 \ koniec {bmatrix}} \ quad n = {\ rozpocząć {bmatrix} 0 \\1 \ koniec {bmatrix} }}$$

W tym przypadku operatorami tożsamości i negacji są macierze identyczności i antydiagonalne tożsamości :,

$${\ Displaystyle I = {\ rozpocząć {bmatrix} 1 i 0 \\ 0 i 1 \ koniec {bmatrix}} \ quad N = {\ rozpocząć {bmatrix} 0 i 1 \\ 1 i 0 \ koniec{bmacierz}}}$$

a macierze koniunkcji, alternatywy i implikacji to

$${\ Displaystyle C = {\ rozpocząć {bmatrix} 1 i 0 i 0 i 0 \\ 0 i 1 i 1 i 1 \ koniec {bmatrix}} \ quad D={\begin{bmatrix}1&1&1&0\\0&0&0&1\end{bmatrix}},\quad L={\begin{bmatrix}1&0&1&1\\0&1&0&0\end{bmatrix}}}$$

odpowiednio.

Zestaw 2 :

$${\ Displaystyle s = {\ Frac {1} {\ sqrt {2}}} {\ rozpocząć {bmatrix} 1 \\ 1 \ koniec {bmatrix }}\quad n={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1\\-1\end{bmatrix}}}$$

Tutaj operator tożsamości jest macierzą tożsamości, ale operator negacji nie jest już antydiagonalną macierzą tożsamości:

$${\ Displaystyle I = {\ rozpocząć {bmatrix} 1 i 0 \\ 0 i 1 \ koniec {bmatrix}} \ quad N = {\ rozpocząć {bmatrix} 1 & 0 \\ 0& -1\end{bmacierz}}}$$

Otrzymane macierze koniunkcji, alternatywy i implikacji to:

$${\ Displaystyle C = {\ Frac {1} {\ sqrt {2}}} {\ rozpocząć {bmatrix} 2 i 0 i 0 i 0 \\ -1 i 1 i 1 i 1 \ koniec {bmatrix}}, \ quad D = {\ frac {1} {\ sqrt {2}}}{\begin{bmatrix}2&0&0&0\\1&1&1&-1\end{bmatrix}},\quad L={\begin{bmatrix}2&0&0&0\\1&1&-1&1\end{bmatrix}}}$$

odpowiednio.

Prawo De Morgana

W logice dwuwartościowej operacje koniunkcji i alternatywy spełniają prawo De Morgana : p ∧ q ≡¬(¬ p ∨¬ q ) i jego podwójne: p ∨ q ≡¬(¬ p ∧¬ q )). Dla dwuwartościowej logiki wektorowej sprawdzane jest również to prawo:

${\ Displaystyle C (u \ otimes v) = ND (Nu \ otimes Nv)}$ , gdzie u i v to dwa wektory logiczne.

Produkt Kroneckera implikuje następującą faktoryzację:

${\ Displaystyle C (u \ otimes v) = ND (N \ otimes N) (u \ otimes v).}$

Wtedy można udowodnić, że w dwuwymiarowej logice wektorowej prawo De Morgana jest prawem dotyczącym operatorów, a nie tylko prawem dotyczącym operacji:

${\ Displaystyle C = ND (N \ czasami N)}$

Prawo kontrapozycji

W klasycznym rachunku zdań prawo kontrapozycji p → q ≡ ¬ q → ¬ p jest udowodnione, ponieważ równoważność zachodzi dla wszystkich możliwych kombinacji wartości logicznych p i q . Zamiast tego w logice wektorowej prawo kontrapozycji wyłania się z łańcucha równości w ramach reguł algebry macierzowej i produktów Kroneckera, jak pokazano poniżej:

${\ Displaystyle L (u \ otimes v) = D ( N\orazy I)(u\orazy v)=D(Nu\orazy v)=D(Nu\orazy NNv)=}$

${\ Displaystyle D (NNv \ otimes Nu) = D (N \ otimes ja) (Nv \ otimes Nu) = L ( Nv\czasami Nu)}$

Wynik ten opiera się na fakcie, że D , macierz dysjunkcji, reprezentuje operację przemienną.

Wielowartościowa logika dwuwymiarowa

Logika wielowartościowa została rozwinięta przez wielu badaczy, zwłaszcza przez Jana Łukasiewicza i umożliwia rozszerzenie operacji logicznych na wartości prawdziwościowe zawierające niepewności. W przypadku dwuwartościowej logiki wektorowej niepewności co do wartości prawdy można wprowadzić za pomocą wektorów, w których s i n ważone są prawdopodobieństwem.

Niech ${\ Displaystyle f = \ epsilon s + \ delta n}$ , gdzie ${\ Displaystyle \ epsilon, \ delta \ w [0,1 ],\epsilon +\delta =1}$ będą tego rodzaju „probabilistycznymi” wektorami. Tutaj wielowartościowy charakter logiki jest wprowadzany a posteriori poprzez niepewności wprowadzane na wejściach.

Skalarne projekcje wyjść wektorowych

Wyniki tej wielowartościowej logiki można rzutować na funkcje skalarne i generować określoną klasę logiki probabilistycznej , która jest podobna do wielowartościowej logiki Reichenbacha. Biorąc pod uwagę dwa wektory ${\ Displaystyle u = \ alfa s + \ beta n}$ i ${\ Displaystyle v = \ alfa 's + \ beta 'n}$ i diadyczny logiczny macierz ${\ Displaystyle G}$ , skalarną logikę probabilistyczną zapewnia rzutowanie na wektor s :

$\ Displaystyle Val (\ operatorname {skalary}) = s ^ {T} G (\ operatorname {wektory}) }$

Oto główne wyniki tych prognoz:

${\ Displaystyle NIE (\ alfa) = s ^ {T} Nu = 1- \ alfa}$

${\ Displaystyle LUB (\ alfa, \ alfa ') = s ^ {T} D (u \ otimes v) = \ alfa + \ alfa '- \ alfa \ alfa '}$

${\ Displaystyle I (\ alfa, \ alfa ') = s ^ {T} C (u \ otimes v) = \ alfa \ alfa '}$

${\ Displaystyle IMPL (\ alfa, \ alfa ') = s ^ {T} L (u \ otimes v) = 1 - \ alfa (1- \ alfa ') )}$

${\ Displaystyle XOR (\ alfa, \ alfa ') = s ^ {T} X (u \ otimes v) = \ alfa + \ alfa '-2 \ alfa \ alfa '}$

Powiązane negacje to:

${\ Displaystyle NOR (\ alfa, \ alfa ') = 1-LUB (\ alfa, \ alfa ')}$

${\ Displaystyle NAND (\ alfa, \ alfa ') = 1-AND (\ alfa, \ alfa ')}$

${\ Displaystyle EQUI(\alpha ,\alpha ')=1-XOR(\alpha ,\alpha ')}$

Jeśli wartości skalarne należą do zbioru {0, ½, 1}, to ta wielowartościowa logika skalarna jest dla wielu operatorów niemal identyczna z trójwartościową logiką Łukasiewicza. Udowodniono również, że gdy operatory monadyczne lub diadyczne działają na wektorach probabilistycznych należących do tego zbioru, wyjście jest również elementem tego zbioru.

Pierwiastek kwadratowy z NIE

Ten operator został pierwotnie zdefiniowany dla kubitów w ramach obliczeń kwantowych . W logice wektorowej operator ten można rozszerzyć na dowolne ortonormalne wartości prawdy. W rzeczywistości istnieją dwa pierwiastki kwadratowe z NOT:

${\ Displaystyle A = ({\ sqrt {N}}) _ {1} = {\ Frac {1} 2}}(1+i)I+{\frac {1}{2}}(1-i)N}$ i

${\ Displaystyle B = ({\ sqrt {N}}) _ {2} = {\ Frac {1} {2}} (1-i) ja + {\ Frac {1} {2}} (1 +i)N}$ ,

z ${\ Displaystyle i = {\ sqrt {-1}}}$ . ${\ Displaystyle A}$ i ${\ displaystyle B}$ są złożonymi koniugatami: ${\ Displaystyle B = A ^ {*}}$ i zauważ, że ${\ Displaystyle A ^ {2 } = B ^ {2} = N}$ i $\ Displaystyle AB = BA = I}$ . Innym interesującym punktem jest analogia z dwoma pierwiastkami kwadratowymi z -1. + ${\ sqrt {-1}})}$${\ Displaystyle ({\ sqrt {N}}) _ {1} = IA }$ odpowiada , a ujemny pierwiastek $_$ ( ${2 }=NIE dotyczy}$ ; w konsekwencji ${\ displaystyle NA = B}$ .

Historia

Wczesne próby użycia algebry liniowej do przedstawienia operacji logicznych można odnieść do Peirce'a i Copilowisha , zwłaszcza w przypadku użycia macierzy logicznych do interpretacji rachunku różniczkowego .

Podejście to zostało zainspirowane modelami sieci neuronowych opartymi na wykorzystaniu wielowymiarowych macierzy i wektorów. Logika wektorowa jest bezpośrednim tłumaczeniem na formalizm macierzowo-wektorowy klasycznych wielomianów Boole'a . Ten rodzaj formalizmu został zastosowany do opracowania logiki rozmytej w kategoriach liczb zespolonych . Inne macierzowe i wektorowe podejścia do rachunku logicznego zostały opracowane w ramach fizyki kwantowej , informatyki i optyki .

Indyjski biofizyk GN Ramachandran opracował formalizm wykorzystujący macierze algebraiczne i wektory do reprezentowania wielu operacji klasycznej logiki Jain , znanych jako Syad i Saptbhangi; zobacz logikę indyjską . Wymaga niezależnego potwierdzającego dowodu dla każdego twierdzenia w zdaniu i nie zakłada binarnego uzupełnienia.

Wielomiany Boole'a

George Boole ustalił rozwój operacji logicznych jako wielomianów. W przypadku operatorów monadycznych (takich jak tożsamość lub negacja ) wielomiany Boole'a wyglądają następująco:

${\ Displaystyle f (x) = f (1) x + f (0) (1-x)}$

Cztery różne operacje monadyczne wynikają z różnych wartości binarnych współczynników. Operacja tożsamości wymaga f (1) = 1 i f (0) = 0, a negacja występuje, jeśli f (1) = 0 i f (0) = 1. Dla 16 operatorów diadycznych wielomiany Boole'a mają postać:

${\ Displaystyle f (x, y) = f (1,1) xy + f (1,0) x (1-y) + f (0,1) (1-x) y + f (0,0 )(1-x)(1-y)}$

Operacje diadyczne można przetłumaczyć na ten format wielomianowy, gdy współczynniki f przyjmą wartości wskazane w odpowiednich tablicach prawdy . Na przykład: NAND wymaga, aby:

${\ Displaystyle f (1,1) = 0}$ i ${\ Displaystyle f (1,0) = f ( 0,1)=f(0,0)=1}$ .

Te wielomiany Boole'a można natychmiast rozszerzyć na dowolną liczbę zmiennych, tworząc dużą potencjalną różnorodność operatorów logicznych. W logice wektorowej struktura macierzowo-wektorowa operatorów logicznych jest dokładną translacją do formatu algebry liniowej tych wielomianów boolowskich, gdzie x i 1− x odpowiadają odpowiednio wektorom s i n (takie same dla y i 1− y ). W przykładzie NAND f (1,1)= n i f (1,0)= f (0,1)= f (0,0)= s a wersja macierzy przyjmuje postać:

${\ Displaystyle S = n (s \ czasami s) ^ {T} + s[(s\czasami n)^{T}+(n\czasami s)^{T}+(n\czasami n)^{T}]}$

Rozszerzenia

• Logikę wektorową można rozszerzyć, aby obejmowała wiele wartości logicznych, ponieważ wielkowymiarowe przestrzenie wektorowe umożliwiają tworzenie wielu ortogonalnych wartości prawdy i odpowiednich macierzy logicznych.
• Modalności logiczne mogą być w pełni reprezentowane w tym kontekście, z procesem rekurencyjnym inspirowanym modelami neuronowymi .
• Niektóre problemy poznawcze dotyczące obliczeń logicznych można analizować za pomocą tego formalizmu, w szczególności decyzje rekurencyjne. Każde logiczne wyrażenie klasycznego rachunku zdań może być naturalnie reprezentowane przez strukturę drzewiastą . Fakt ten jest zachowywany przez logikę wektorową i został częściowo wykorzystany w modelach neuronowych skupionych na badaniu rozgałęzionej struktury języków naturalnych.
• Obliczenia za pomocą operacji odwracalnych, takich jak bramka Fredkina, można zaimplementować w logice wektorowej. Taka implementacja zapewnia jawne wyrażenia dla operatorów macierzowych, które tworzą format wejściowy i filtrowanie wyjściowe niezbędne do uzyskania obliczeń.
• Elementarne automaty komórkowe można analizować za pomocą struktury operatorów logiki wektorowej; analiza ta prowadzi do spektralnej dekompozycji praw rządzących jej dynamiką.
• Ponadto, w oparciu o ten formalizm, opracowano dyskretny rachunek różniczkowy i całkowy .

Zobacz też

• Logika algebraiczna
• Algebra Boole'a
• Rachunek zdań
• Logika kwantowa
• Jonathana Westphala