Vector logic

Vector logic[1][2] is an algebraic model of elementary logic based on matrix algebra. Vector logic assumes that the truth values map on vectors, and that the monadic and dyadic operations are executed by matrix operators.

Overview

Classic 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 and the value 0 to 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:

t\mapsto s    and    f\mapsto n

(where  q \geq 2 is an arbitrary natural number, and “normalized” means that the length of the vector is 1; usually s and n are orthogonal vectors). This correspondence generates a space of vector truth-values: V2 = {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: u^Tv=\langle u,v\rangle: the orthonormality between vectors s and n implies that \langle u,v\rangle=1 if u = v, and \langle u,v\rangle=0 if u \ne v.

Monadic operators

The monadic operators result from the application Mon: V_2 \to V_2, and the associated matrices have q rows and q columns. The two basic monadic operators for this two-valued vector logic are the identity and the negation:

Dyadic operators

The 16 two-valued dyadic operators correspond to functions of the type Dyad: V_2 \otimes V_2\to V_2; the dyadic matrices have q rows and q2 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:

  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

     (A \otimes B)(C \otimes D) = AC \otimes BD
  2. Distributive transpose The operation of transposition is distributive over the Kronecker product:
    (A\otimes B)^T = A^T \otimes B^T.

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

C=s(s\otimes s)^T + n(s\otimes n)^T + n(n\otimes s)^T + n(n\otimes n)^T
and verifies
C(s\otimes s)=s, and
C(s\otimes n)=C(n\otimes s)=C(n\otimes n)=n.
D=s(s\otimes s)^T+s(s\otimes n)^T+s(n\otimes s)^T+n(n\otimes n)^T, resulting in
D(s\otimes s)=D(s\otimes n)=D(n\otimes s)=s and
D(n\otimes n)=n.
L=s(s\otimes s)^T+n(s\otimes n)^T+s(n\otimes s)^T+n(n\otimes n)^T,
and the properties of classical implication are satisfied:
L(s\otimes s)=L(n\otimes s)=L(n\otimes n)=s and
L(s\otimes n)=n.
E=s(s\otimes s)^T+n(s\otimes n)^T+n(n\otimes s)^T+s(n\otimes n)^T with
E(s\otimes s)=E(n\otimes n)=s and
E(s\otimes n)=E(n\otimes s)=n.
The Exclusive or is the negation of the equivalence, ¬(p≡q); it corresponds with the matrix X=NE given by
X=n(s\otimes s)^T+s(s\otimes n)^T+s(n\otimes s)^T+n(n\otimes n)^T,
with X(s\otimes s)=X(n\otimes n)=n and
X(s\otimes n)=X(n\otimes s)=s.

The matrices S and P correspond to the Sheffer (NAND) and the Peirce (NOR) operations, respectively:

S=NC
P=ND

De Morgan's law

In the two-valued logic, the conjunction and the disjunction operations satisfy the 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:

C(u\otimes v)=ND(Nu\otimes Nv), where u and v are two logic vectors.

The Kronecker product implies the following factorization:

C(u\otimes v)=ND(N\otimes N)(u\otimes v).

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:[3]

C=ND(N\otimes N)

Law of contraposition

In the classical propositional calculus, the Law of Contraposition p  q  ¬q  ¬p is proved because the equivalence holds for all the possible combinations of truth-values of p and q.[4] 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:

L(u\otimes v)=D(N\otimes I)(u\otimes v)=D(Nu\otimes v)=D(Nu\otimes NNv)=
 D(NNv\otimes Nu)=D(N\otimes I)(Nv\otimes Nu)=L(Nv\otimes Nu)

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.[5] 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 f=\epsilon s + \delta n, with \epsilon, \delta \in [0,1], \epsilon + \delta = 1 be this kind of “probabilistic” vectors. Here, the many-valued character of the logic is introduced a posteriori via the uncertainties introduced in the inputs.[1]

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.[6][7][8] Given two vectors u=\alpha s + \beta n and v=\alpha's + \beta'n and a dyadic logical matrix G, a scalar probabilistic logic is provided by the projection over vector s:

Val(\mathrm{scalars}) = s^TG(\mathrm{vectors})

Here are the main results of these projections:

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

The associated negations are:

NOR(\alpha,\alpha')=1-OR(\alpha,\alpha')
NAND(\alpha,\alpha')=1-AND(\alpha,\alpha')
EQUI(\alpha,\alpha')=1-XOR(\alpha,\alpha')

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.[3]

History

The approach has been inspired in neural network models based on the use of high-dimensional matrices and vectors.[9][10] Vector logic is a direct translation into a matrix-vector formalism of the classical Boolean polynomials.[11] This kind of formalism has been applied to develop a fuzzy logic in terms of complex numbers.[12] Other matrix and vector approaches to logical calculus have been developed in the framework of quantum physics, computer science and optics.[13][14][15] Early attempts to use linear algebra to represent logic operations can be referred to Peirce and Copilowish.[16] The Indian biophysicist G.N. Ramachandran developed a formalism using algebraic matrices and vectors to represent many operations of classical Jain Logic known as Syad and Saptbhangi. Indian logic.[17] It requires independent affirmative evidence for each assertion in a proposition, and does not make the assumption for binary complementation.

Boolean polynomials

George Boole established the development of logical operations as polynomials.[11] For the case of monadic operators (such as identity or negation), the Boolean polynomials look as follows:

f(x) = f(1)x + f(0)(1-x)

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

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)

The dyadic operations can be translated to this polynomial format when the coefficients f take the values indicated in the respective truth tables. For instance: the NAND operation requires that:

 f(1,1)=0 and f(1,0)=f(0,1)=f(0,0)=1.

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:

S=n(s\otimes s)^T + s[(s\otimes n)^T+(n\otimes s)^T+(n\otimes n)^T]

Extensions


See also

References

  1. 1 2 Mizraji, E. (1992). Vector logics: the matrix-vector representation of logical calculus. Fuzzy Sets and Systems, 50, 179–185, 1992
  2. 1 2 3 4 Mizraji, E. (2008) Vector logic: a natural algebraic representation of the fundamental logical gates. Journal of Logic and Computation, 18, 97–121, 2008
  3. 1 2 3 Mizraji, E. (1996) The operators of vector logic. Mathematical Logic Quarterly, 42, 27–39
  4. 1 2 Suppes, P. (1957) Introduction to Logic, Van Nostrand Reinhold, New York.
  5. Łukasiewicz, J. (1980) Selected Works. L. Borkowski, ed., pp. 153–178. North-Holland, Amsterdam, 1980
  6. Rescher, N. (1969) Many-Valued Logic. McGraw–Hill, New York
  7. Blanché, R. (1968) Introduction à la Logique Contemporaine, Armand Colin, Paris
  8. Klir, G.J., Yuan, G. (1995) Fuzzy Sets and Fuzzy Logic. Prentice–Hall, New Jersey
  9. Kohonen, T. (1977) Associative Memory: A System-Theoretical Approach. Springer-Verlag, New York
  10. Mizraji, E. (1989) Context-dependent associations in linear distributed memories. Bulletin of Mathematical Biology, 50, 195–205
  11. 1 2 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
  12. Dick, S. (2005) Towards complex fuzzy logic. IEEE Transactions on Fuzzy Systems, 15,405–414, 2005
  13. Mittelstaedt, P. (1968) Philosophische Probleme der Modernen Physik, Bibliographisches Institut, Mannheim
  14. Stern, A. (1988) Matrix Logic: Theory and Applications. North-Holland, Amsterdam
  15. Westphal, J., Hardy, J. (2005) Logic as a vector system. Journal of Logic and Computation, 15, 751–765
  16. Copilowish, I.M. (1948) Matrix development of the calculus of relations. Journal of Symbolic Logic, 13, 193–203
  17. Jain, M.K. (2011) Logic of evidence-based inference propositions, Current Science, 1663–1672, 100
  18. Mizraji, E. (1994) Modalities in vector logic. Notre Dame Journal of Formal Logic, 35, 272–283
  19. Mizraji, E., Lin, J. (2002) The dynamics of logical decisions. Physica D, 168–169, 386–396
  20. beim Graben, P., Potthast, R. (2009). Inverse problems in dynamic cognitive modeling. Chaos, 19, 015103
  21. beim Graben, P., Pinotsis, D., Saddy, D., Potthast, R. (2008). Language processing with dynamic fields. Cogn. Neurodyn., 2, 79–88
  22. beim Graben, P., Gerth, S., Vasishth, S.(2008) Towards dynamical system models of language-related brain potentials. Cogn. Neurodyn., 2, 229–255
  23. beim Graben, P., Gerth, S. (2012) Geometric representations for minimalist grammars. Journal of Logic, Language and Information, 21, 393-432 .
  24. Binazzi, A.(2012) Cognizione logica e modelli mentali. Studi sulla formazione, 1–2012, pag. 69–84
  25. 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.
  26. Arruti, C., Mizraji, E. (2006) Hidden potentialities. International Journal of General Systems, 35, 461–469.
  27. Mizraji, E. (2015) Differential and integral calculus for logical operations. A matrix–vector approach Journal of Logic and Computation 25, 613-638, 2015
This article is issued from Wikipedia - version of the Monday, November 02, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.