View source for PSR J0348+0432

'''Vector logic'''<ref name="miz92">Mizraji, E. (1992). [http://www.sciencedirect.com/science/article/pii/016501149290216Q Vector logics: the matrix-vector representation of logical calculus.] Fuzzy Sets and Systems, 50, 179–185, 1992</ref><ref name="miz08">Mizraji, E. (2008) [http://logcom.oxfordjournals.org/content/18/1/97.full.pdf Vector logic: a natural algebraic representation of the fundamental logical gates.] Journal of Logic and Computation, 18, 97–121, 2008</ref> is an [[Algebra | algebraic]] [[Mathematical model | model]] of elementary [[logic]] based on [[Matrix (mathematics)|matrix algebra]]. Vector logic assumes that the [[truth value]]s map on [[Vector (mathematics and physics) | vectors]], and that the [[Monadic predicate calculus | monadic]] and [[Binary function | dyadic]] operations are executed by matrix operators.

== Overview ==
Classic [[Truth value#Classical logic | binary]] logic is represented by a small set of mathematical functions depending on one (monadic ) or two (dyadic) variables. In the binary set, the value 1 corresponds to ''[[True (logic)|true]]'' and the value 0 to ''[[False (logic) | false]]''. A two-valued vector logic requires a correspondence between the truth-values ''true'' (t)  and ''false'' (f), and two ''q''-dimensional normalized column vectors composed by real numbers ''s'' and ''n'', hence:

: <math>t\mapsto s</math>&nbsp;&nbsp;&nbsp; and &nbsp;&nbsp;&nbsp;<math>f\mapsto n</math>

(where <math> q \geq 2</math> is an arbitrary natural number, and “normalized” means that the [[Euclidean norm|length]] of the vector is 1; usually s and n are orthogonal vectors).  This correspondence generates a space of vector truth-values: ''V''<sub>2</sub>&nbsp;=&nbsp;{''s'',''n''}. The basic logical operations defined using this set of vectors lead to matrix operators.

The operations of vector logic are based on the scalar product between ''q''-dimensional column vectors: <math>u^Tv=\langle u,v\rangle</math>: the orthonormality between vectors ''s'' and ''n'' implies that <math>\langle u,v\rangle=1</math> if <math>u = v</math>, and <math>\langle u,v\rangle=0</math> if <math>u \ne v</math>.

===Monadic operators===
The monadic operators result from the application <math>Mon: V_2 \to V_2</math>, and the associated matrices have ''q'' rows and ''q'' columns. The two basic monadic operators for this two-valued vector logic are the [[Identity function|identity]] and the [[Logical negation|negation]]:

* '''Identity''': A logical identity ID(p)is represented by matrix <math>I=ss^T + nn^T</math>. This matrix operates as follows:  ''Ip''&nbsp;=&nbsp;''p'', ''p''&nbsp;∈&nbsp;''V''<sub>2</sub>; due to the orthogonality of ''s'' respect to ''n'', we have <math>Is=ss^Ts+nn^Ts=s\langle s,s\rangle+n\langle n,s\rangle=s</math>, &nbsp; and conversely <math>In=n</math>.

* '''Negation''': A logical negation ¬p is represented by matrix <math>N=ns^T + sn^T</math> Consequently, ''Ns''&nbsp;=&nbsp;''n''  and ''Nn''&nbsp;=&nbsp;''s''. The involutory behavior of the logical negation, namely that ¬(¬''p'') equals ''p'',  corresponds with the fact that ''N''<sup>2</sup>&nbsp;=&nbsp;''I''. Is important to note that this vector logic identity matrix is not generally an [[identity matrix]] in the sense of matrix algebra.

=== Dyadic operators ===
The 16 two-valued dyadic operators correspond to functions of the type <math>Dyad: V_2 \otimes V_2\to V_2</math>; the dyadic matrices have ''q'' rows and ''q''<sup>2</sup> columns.
The matrices that execute these dyadic operations are based on the properties of the [[Kronecker product]].

Two properties of this product are essential for the formalism of vector logic:
{{ordered list
|1= '''The mixed-product property'''
If '''A''', '''B''', '''C''' and '''D''' are matrices of such size that one can form the matrix products '''AC''' and '''BD''', then
:<math> (A \otimes B)(C \otimes D) = AC \otimes BD </math>
|2= '''Distributive transpose''' The operation of transposition is distributive over the Kronecker product:
:<math>(A\otimes B)^T = A^T \otimes B^T.</math>
}}

Using these properties, expressions for dyadic logic functions can be obtained:

* '''[[∧|Conjunction]]'''. The conjunction (p∧q) is executed by a matrix that acts on two vector truth-values: <math>C(u\otimes v)</math> .This matrix reproduces the features of the classical conjunction truth-table in its formulation:

::<math>C=s(s\otimes s)^T + n(s\otimes n)^T + n(n\otimes s)^T + n(n\otimes n)^T </math>

::and verifies

::<math>C(s\otimes s)=s,</math> and

::<math>C(s\otimes n)=C(n\otimes s)=C(n\otimes n)=n.</math>

* '''[[∨|Disjunction]]'''. The disjunction (p∨q) is executed by the matrix
::<math>D=s(s\otimes s)^T+s(s\otimes n)^T+s(n\otimes s)^T+n(n\otimes n)^T,</math> resulting in
::<math>D(s\otimes s)=D(s\otimes n)=D(n\otimes s)=s</math> and
::<math>D(n\otimes n)=n.</math>

* '''[[Logical implication|Implication]]'''. The implication corresponds in classical logic to the expression p&nbsp;→&nbsp;q&nbsp;≡&nbsp;¬p&nbsp;∨&nbsp;q. The vector logic version of this equivalence leads to a matrix that represents this implication in vector logic: <math>L=D(N\otimes I)</math>. The explicit expression for this implication is:

::<math>L=s(s\otimes s)^T+n(s\otimes n)^T+s(n\otimes s)^T+n(n\otimes n)^T,</math>

::and the properties of classical implication are satisfied:
::<math>L(s\otimes s)=L(n\otimes s)=L(n\otimes n)=s</math> and
::<math>L(s\otimes n)=n.</math>

* '''[[Logical equivalence|Equivalence]] and [[Exclusive or]]'''. In vector logic the equivalence p≡q is represented by the following matrix:
::<math>E=s(s\otimes s)^T+n(s\otimes n)^T+n(n\otimes s)^T+s(n\otimes n)^T</math> with

::<math>E(s\otimes s)=E(n\otimes n)=s</math> and

::<math>E(s\otimes n)=E(n\otimes s)=n.</math>

::The Exclusive or is the negation of the equivalence, ¬(p≡q); it corresponds with the matrix <math>X=NE</math> given by

::<math>X=n(s\otimes s)^T+s(s\otimes n)^T+s(n\otimes s)^T+n(n\otimes n)^T,</math>

::with <math>X(s\otimes s)=X(n\otimes n)=n</math> and

::<math>X(s\otimes n)=X(n\otimes s)=s.</math>

* '''[[Sheffer stroke|NAND]] and [[Peirce arrow|NOR]]'''
The matrices ''S'' and ''P'' correspond to the [[Sheffer stroke|Sheffer]] (NAND) and the [[Logical NOR|Peirce]] (NOR) operations, respectively:
::<math>S=NC</math>   
::<math>P=ND</math>

=== De Morgan's law ===
In the two-valued logic, the conjunction and the disjunction operations satisfy the [[De Morgan's Laws|De Morgan's law]]: p∧q≡¬(¬p∨¬q), and its dual: p∨q≡¬(¬p∧¬q)). For the two-valued vector logic this Law is also verified:

::<math>C(u\otimes v)=ND(Nu\otimes Nv)</math>, where ''u'' and ''v'' are two logic vectors.

The Kronecker product implies the following factorization:

::<math>C(u\otimes v)=ND(N\otimes N)(u\otimes v).</math>

Then it can be proved that in the two–dimensional vector logic the De Morgan's law is a law involving operators, and not only a law concerning operations:<ref name="miz96">Mizraji, E. (1996) The operators of vector logic. Mathematical Logic Quarterly, 42, 27–39</ref>

::<math>C=ND(N\otimes N)</math>

=== Law of contraposition ===
In the classical propositional calculus, the [[Contraposition (traditional logic)|Law of Contraposition]] ''p''&nbsp;→&nbsp;''q''&nbsp;≡&nbsp;¬''q''&nbsp;→&nbsp;¬''p'' is proved because the equivalence holds for all the possible combinations of truth-values of ''p'' and ''q''.<ref name="suppes">Suppes, P. (1957) Introduction to Logic, Van Nostrand Reinhold, New York.</ref> Instead, in vector logic, the law of contraposition emerges from a chain of equalities within the rules of matrix algebra and Kronecker products, as shown in what follows:

::<math>L(u\otimes v)=D(N\otimes I)(u\otimes v)=D(Nu\otimes v)=D(Nu\otimes NNv)=</math>
::<math> D(NNv\otimes Nu)=D(N\otimes I)(Nv\otimes Nu)=L(Nv\otimes Nu)</math>

This result is based in the fact that ''D'', the disjunction matrix, represents a commutative operation.

== Many-valued two-dimensional logic ==
[[Many-valued logic]] was developed by many researchers, particularly by [[Jan Łukasiewicz]] and allows extending logical operations to truth-values that include uncertainties.<ref>Łukasiewicz, J. (1980) Selected Works. L. Borkowski, ed., pp. 153–178. North-Holland,
Amsterdam, 1980</ref> In the case of two-valued vector logic, uncertainties in the truth values can be introduced using vectors with ''s'' and ''n'' weighted by probabilities.

Let <math>f=\epsilon s + \delta n</math>, with <math>\epsilon, \delta \in [0,1], \epsilon + \delta = 1</math> be this kind of “probabilistic” vectors. Here, the many-valued character of the logic is introduced [[A priori and a posteriori|''a posteriori'']] via the uncertainties introduced in the inputs.<ref name="miz92"/>

===Scalar projections of vector outputs===
The outputs of this many-valued logic can be projected on scalar functions and generate a particular class of probabilistic logic with similarities with the many-valued logic of Reichenbach.<ref>Rescher, N. (1969) Many-Valued Logic. McGraw–Hill, New York</ref><ref>Blanché, R. (1968) Introduction à la Logique Contemporaine, Armand Colin, Paris</ref><ref>Klir, G.J., Yuan, G. (1995) Fuzzy Sets and Fuzzy Logic. Prentice–Hall, New Jersey</ref>  Given two vectors <math>u=\alpha s + \beta n</math> and <math>v=\alpha's + \beta'n</math> and a dyadic logical matrix <math>G</math>, a scalar probabilistic logic is provided by the projection over vector&nbsp;''s'':

::<math>Val(\mathrm{scalars}) = s^TG(\mathrm{vectors})</math>

Here are the main results of these projections:

::<math>NOT(\alpha)=s^TNu=1-\alpha</math>
::<math>OR(\alpha,\alpha')=s^TD(u\otimes v)=\alpha + \alpha' - \alpha\alpha'</math>
::<math>AND(\alpha,\alpha')=s^TC(u\otimes v)=\alpha\alpha'</math>
::<math>IMPL(\alpha,\alpha')=s^TL(u\otimes v)=1-\alpha(1-\alpha')</math>
::<math>XOR(\alpha,\alpha')=s^TX(u\otimes v)=\alpha+\alpha'-2\alpha\alpha'</math>

The associated negations are:
::<math>NOR(\alpha,\alpha')=1-OR(\alpha,\alpha')</math>
::<math>NAND(\alpha,\alpha')=1-AND(\alpha,\alpha')</math>
::<math>EQUI(\alpha,\alpha')=1-XOR(\alpha,\alpha')</math>

If the scalar values belong to the set {0, ½, 1}, this many-valued scalar logic is for many of the operators almost identical to the 3-valued logic of Łukasiewicz. Also, it has been proved that when the monadic or dyadic operators act over probabilistic vectors belonging to this set, the output is also an element of this set.<ref name="miz96"/>

== History ==

The approach has been inspired in [[neural network]] models based on the use of high-dimensional matrices and vectors.<ref>Kohonen, T. (1977) Associative Memory: A System-Theoretical Approach. Springer-Verlag, New York</ref><ref>Mizraji, E. (1989) [http://link.springer.com/article/10.1007%2FBF02458441 Context-dependent associations in linear distributed memories]. Bulletin of Mathematical Biology, 50, 195–205</ref> Vector logic is a direct translation into a matrix-vector formalism of the classical [[Boolean algebra|Boolean polynomials]].<ref name="boole">Boole, G. (1854) An Investigation of the Laws of Thought, on which are Founded the Theories of Logic and Probabilities. Macmillan, London, 1854; Dover, New York Reedition, 1958</ref> This kind of formalism has been applied to develop a [[fuzzy logic]] in terms of [[complex numbers]].<ref>Dick, S. (2005) Towards complex fuzzy logic. IEEE Transactions on Fuzzy Systems, 15,405–414, 2005</ref> Other matrix and vector approaches to logical calculus have been developed in the framework of [[quantum physics]], [[computer science]] and [[optics]].<ref>Mittelstaedt, P. (1968) Philosophische Probleme der Modernen Physik, Bibliographisches Institut, Mannheim</ref><ref>Stern, A. (1988) Matrix Logic: Theory and Applications. North-Holland, Amsterdam</ref><ref>Westphal, J., Hardy, J. (2005) Logic as a vector system. Journal of Logic and Computation, 15, 751–765</ref> Early attempts to use linear algebra to represent logic operations can be referred to [[Charles Sanders Peirce|Peirce]] and [[Irving Copi|Copilowich]].<ref>Copilovich, I.M. (1948) Matrix development of the calculus of relations. Journal of Symbolic Logic, 13, 193–203</ref> The [[Indian people | Indian]] biophysicist [[G.N. Ramachandran]] developed a formalism using algebraic matrices and vectors to represent many operations of classical [[Indian logic]].<ref>Jain, M.K. (2011) Logic of evidence-based inference propositions, Current Science, 1663–1672, 100</ref>

== Boolean polynomials ==

[[George Boole]] established the development of logical operations as polynomials.<ref name="boole"/> For the case of monadic operators (such as [[Identity function|identity]] or
[[Logical negation|negation]]), the Boolean polynomials look as follows:

::<math>f(x) = f(1)x + f(0)(1-x) </math>

The four different monadic operations result from the different binary values for the coefficients. Identity operation requires ''f''(1)&nbsp;=&nbsp;1 and ''f''(0)&nbsp;=&nbsp;0, and negation occurs if ''f''(1)&nbsp;=&nbsp;0 and ''f''(0)&nbsp;=&nbsp;1.  For the 16 dyadic operators, the Boolean polynomials are of the form:

::<math>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)</math>

The dyadic operations can be translated to this polynomial format when the coefficients ''f'' take the values indicated in the respective [[truth table]]s. For instance: the [[Sheffer stroke|NAND]] operation requires that:
::<math> f(1,1)=0</math>    and    <math>f(1,0)=f(0,1)=f(0,0)=1</math>. 
These Boolean polynomials can be immediately extended to any number of variables, producing a large potential variety of logical operators.
In vector logic, the matrix-vector structure of logical operators is an exact translation to the format of liner algebra of these Boolean polynomials, where the ''x'' and ''1-x'' correspond to vectors ''s'' and ''n'' respectively (the same for ''y'' and ''1-y''). In the example of NAND, ''f(1,1)=n'' and ''f(1,0)=f(0,1)=f(0,0)=s'' and the matrix version becomes:

::<math>S=n(s\otimes s)^T + s[(s\otimes n)^T+(n\otimes s)^T+(n\otimes n)^T]</math>

==Extensions==

* Vector logic can be extended to include many truth values since large dimensional vector spaces allow to create many orthogonal truth values and the corresponding logical matrices.<ref name="miz08"/>
* Logical modalities can be fully represented in this context, with recursive process inspired in [[Artificial neuron|neural models]]<ref name="miz08"/><ref>Mizraji, E. (1994) [http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.ndjfl/1094061864&page=record Modalities in vector logic]. Notre Dame Journal of Formal Logic, 35, 272–283</ref>
* Some cognitive problems about logical computations can be analyzed using this formalism, in particular recursive decisions. Any logical expression of classical propositional calculus can be naturally represented by a [[tree structure]].<ref name="suppes"/> This fact is retained by vector logic, and has been partially used in neural models focused in the investigation of the branched structure of natural languages.<ref>Mizraji, E., Lin, J. (2002) The dynamics of logical decisions. Physica D, 168–169, 386–396</ref><ref>beim Graben, P., Potthast, R. (2009). Inverse problems in dynamic cognitive modeling. Chaos, 19, 015103</ref><ref>beim Graben, P., Pinotsis, D., Saddy, D., Potthast, R. (2008). Language processing with dynamic ﬁelds. Cogn. Neurodyn., 2, 79–88</ref><ref>beim Graben, P., Gerth, S., Vasishth, S.(2008) Towards dynamical system models of language-related brain potentials. Cogn. Neurodyn., 2, 229–255</ref><ref>beim Graben, P., Gerth, S. (2012) Geometric representations for minimalist grammars. Journal of Logic, Language and Information, 21, 393-432 .
</ref><ref>Binazzi, A.(2012) [http://www.fupress.net/index.php/sf/article/view/11649 Cognizione logica e modelli mentali.] Studi sulla formazione, 1–2012, pag. 69–84 </ref>
* The computation via reversible operations as the [[Fredkin gate]] can be implemented in vector logic. This implementations provides explicit expressions for matrix operators that produce the input format and the output filtering necessary for obtaining computations<ref name="miz08"/><ref name="miz96"/>
* [[Elementary cellular automaton|Elementary celular automata]] can be analyzed using the operator structure of vector logic; this analysis leads to a spectral decomposition of the laws governing the its dynamics<ref>Mizraji, E. (2006) The parts and the whole: inquiring how the interaction of simple subsystems generates complexity. International Journal of General Systems, 35, pp. 395–415.</ref><ref>Arruti, C., Mizraji, E. (2006) Hidden potentialities. International Journal of General Systems, 35, 461–469.</ref>

== See also ==
*[[Fuzzy logic]]
*[[Quantum logic]]
*[[Boolean algebra]]
*[[Propositional calculus]]
*[[George Boole]]
*[[Jan Łukasiewicz]]

== References ==

{{Reflist}}

[[Category:Logic]]
[[Category:Boolean algebra]]