Jump to content

Vector logic: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
Almadana (talk | contribs)
m Fixing typo raised by BracketBot, and page is no longer an orphan (tagged by Josve05a
Almadana (talk | contribs)
No edit summary
Line 1: Line 1:


'''Vector logic''' <ref> 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> 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 [[algebraic]] [[model]] of elementary [[logic]] based on [[Matrix (mathematics) | matrix algebra]]. Vector logic assumes that the [[truth value | truth values]] map on [[vectors]], and that the [[monadic]] and [[dyadic]] operations are executed by matrix operators.
'''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> 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 [[algebraic]] [[model]] of elementary [[logic]] based on [[Matrix (mathematics) | matrix algebra]]. Vector logic assumes that the [[truth value | truth values]] map on [[vectors]], and that the [[monadic]] and [[dyadic]] operations are executed by matrix operators.


== Overview ==
== Overview ==
Line 6: Line 6:
For instance, a two-dimensional 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:
For instance, a two-dimensional 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=s'' and ''f=n''
<math>t=s</math> and <math>f=n</math>


(where <math> q \geq 2</math> is an arbitrary natural number, and “normalized” means that the [[http://en.wikipedia.org/wiki/Norm_(mathematics)#Euclidean_norm | length]] of the vector is 1). This correspondence generates a space of vector truth-values: ''V<sub>2</sub>={s,n}''. The basic logical operations defined using this set of vectors lead to matrix operators.
(where <math> q \geq 2</math> is an arbitrary natural number, and “normalized” means that the [[http://en.wikipedia.org/wiki/Norm_(mathematics)#Euclidean_norm | length]] of the vector is 1). This correspondence generates a space of vector truth-values: ''V<sub>2</sub>={s,n}''. The basic logical operations defined using this set of vectors lead to matrix operators.
Line 39: Line 39:
::<math>C=s(s\otimes s^T) + n(s\otimes n^T) + n(n\otimes s^T) + n(n\otimes n^T) </math>
::<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
::and verifies


::<math>C(s\otimes s)=s</math>, and
::<math>C(s\otimes s)=s</math>, and
Line 47: Line 47:
* '''[[∨ | Disjunction]]'''. The disjunction is executed by the matrix
* '''[[∨ | Disjunction]]'''. The disjunction 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(s\otimes s^T)+s(s\otimes n^T)+s(n\otimes s^T)+n(n\otimes n^T)</math>, resulting in
::<math>C(s\otimes s)=C(s\otimes n)=C(n\otimes s)=s</math> and
::<math>D(s\otimes s)=D(s\otimes n)=D(n\otimes s)=s</math> and
::<math>C(n\otimes n)=n</math>.
::<math>D(n\otimes n)=n</math>.






* '''[[Logical implication | Implication]]'''. The implication corresponds in classical logic to the expression p→q≡¬p∨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
* '''[[Logical implication | Implication]]'''. The implication corresponds in classical logic to the expression p→q≡¬p∨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>,
::<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:
::and the properties of classical implication are satisfied:
::<math>C(s\otimes s)=C(n\otimes s)=C(n\otimes n)=s</math> and
::<math>L(s\otimes s)=L(n\otimes s)=L(n\otimes n)=s</math> and
::<math>C(s\otimes n)=n</math>.
::<math>L(s\otimes n)=n</math>.


* '''[[Logical equivalence | Equivalence]] and [[Exclusive or]]'''.
* '''[[Logical equivalence | Equivalence]] and [[Exclusive or]]'''.
Line 64: Line 64:
::<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(s\otimes s^T)+n(s\otimes n^T)+n(n\otimes s^T)+s(n\otimes n^T)</math> with


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


::<math>C(s\otimes n)=C(n\otimes s)=n</math>.
::<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
::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>,
::<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>C(s\otimes s)=C(n\otimes n)=n</math> and
::with <math>X(s\otimes s)=X(n\otimes n)=n</math> and

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


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


=== De Morgan Law ===
=== De Morgan Law ===
In the two-valued logic, the conjunction and the disjunction operations satisfy the [[De Morgan's Laws | De Morgan Law]]: p∧q≡¬(¬p∨¬q), and its dual: p∨q≡¬(¬p∧¬q)). For the two-dimensional vector logic this Law is also verified:
In the two-valued logic, the conjunction and the disjunction operations satisfy the [[De Morgan's Laws | De Morgan Law]]: p∧q≡¬(¬p∨¬q), and its dual: p∨q≡¬(¬p∧¬q)). For the two-dimensional 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.
::<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:
The Kronecker product implies the following factorization:
Line 86: Line 85:
::<math>C(u\otimes v)=ND(N\otimes N)(u\otimes v)</math>.
::<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 Law is a law involving operators, and not only a law concerning operations <ref>Mizraji, M. (1996) The operators of vector logic. Mathematical Logic Quarterly, 42, 27–39</ref>:
Then it can be proved that in the two–dimensional vector logic the De Morgan Law is a law involving operators, and not only a law concerning operations <ref>Mizraji, E. (1996) The operators of vector logic. Mathematical Logic Quarterly, 42, 27–39</ref>:


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


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



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





== Many-valued two-dimensional logic ==
== 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 (J. Lukasiewicz, Selected Works, L. Borkowski, ed., pp. 153–178. North-Holland,
[[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). In modern times, these extended logical systems have been adapted to the development of fuzzy logics and its applications (G. J. Klir, and B. Yuan. Fuzzy Sets and Fuzzy Logic. Prentice-Hall, New Jersey, 1995). 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 , with 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 (References Mizraji 1992).
Amsterdam, 1980</ref>. In modern times, these extended logical systems have been adapted to the development of fuzzy logics and its applications (G. J. Klir, and B. Yuan. Fuzzy Sets and Fuzzy Logic. Prentice-Hall, New Jersey, 1995). 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 , with 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 <ref name="miz92"/>.


===Scalar projections of vector outputs===
===Scalar projections of vector outputs===

Revision as of 02:26, 23 May 2013

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. For instance, a two-dimensional 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:

and

(where is an arbitrary natural number, and “normalized” means that the [| length] of the vector is 1). 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: : the orthonormality between vectors s and n implies that if , and if .

Monadic operators

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

  • Identity: A logical identity ID(p)is represented by matrix . This matrix operates as follows: Ip=p, p∈V2; due to the orthogonality of s respect to n, we have and conversely .
  • Negation: A logical negation ¬p is represented by matrix Consequently, Ns=n and Nn=s. The involutory behavior of the logical negation, namely that ¬(¬p) equals p, corresponds with the fact that N2=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 ; 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
  2. Distributive transpose The operation of transposition is distributive over the Kronecker product:

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: .This matrix reproduces the features of the classical conjunction truth-table in its formulation:
and verifies
, and
.
, resulting in
and
.


  • Implication. The implication corresponds in classical logic to the expression p→q≡¬p∨q. The vector logic version of this equivalence leads to a matrix that represents this implication in vector logic: . The explicit expression for this implication is:
,
and the properties of classical implication are satisfied:
and
.

In vector logic the equivalence p≡q is represented by the following matrix:

with
and
.
The Exclusive or is the negation of the equivalence, ¬(p≡q); it corresponds with the matrix given by
,
with and
.

De Morgan Law

In the two-valued logic, the conjunction and the disjunction operations satisfy the De Morgan Law: p∧q≡¬(¬p∨¬q), and its dual: p∨q≡¬(¬p∧¬q)). For the two-dimensional vector logic this Law is also verified:

, where u and v are two logic vectors.

The Kronecker product implies the following factorization:

.

Then it can be proved that in the two–dimensional vector logic the De Morgan Law is a law involving operators, and not only a law concerning operations [3]:

The matrices S=NC and P=ND, correspond to the Sheffer (NAND) and the Peirce (NOR) operations, respectively.

Law of Contraposition

In the classical propositional calculus, the [[Contraposition (traditional logic) | 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:

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 modern times, these extended logical systems have been adapted to the development of fuzzy logics and its applications (G. J. Klir, and B. Yuan. Fuzzy Sets and Fuzzy Logic. Prentice-Hall, New Jersey, 1995). 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 , with 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 (N. Rescher. Many-Valued Logic. McGraw-Hill, New York, 1969; R. Blanché, Introduction à la Logique Contemporaine, Armand Colin, Paris, 1968; G. J. Klir, and B. Yuan. Fuzzy Sets and Fuzzy Logic. Prentice-Hall, New Jersey, 1995). Given two vectors and and a dyadic logical matrix G, a scalar probabilistic logic is provided by the projection over vector s :

.

Here are the main results of these projections:




The associated negations are:



It is interesting that if the scalar values belong to the set {0, ½, 1} these many value scalar logic is for many of the operators almost identical to the 3-valued logic of Łukasiewitz (N. Rescher. Many-Valued Logic. McGraw-Hill, New York, 1969).

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 (E. Mizraji. The operators of vector logic. Mathematical Logic Quarterly, 42, 27–39, 1996).

History

The approach has been inspired in neural network models based on the use of high-dimensional matrices and vectors [6] [7]. Vector logic is a direct translation into a matrix-vector formalism of the classical Boolean polynomials [8]. This kind of formalism has been applied to develop a fuzzy logic in terms of complex numbers [9]. Other matrix and vector approaches to logical calculus have been developed in the framework of quantum physics, computer Science and optics [10] [11][12]. Early attempts to use liner algebra to represent logic operations can be referred to Peirce and Copilowich [13]. The Indian biophysicist G.N. Ramachandran developed a formalism using algebraic matrices and vectors to represent many operations of classical Indian Logic [14].

Boolean polynomials

George Boole established the development of logical operations as polynomials [8]. For the case of monadic operators ( identity, ¬ or negation, tautolog1y and contradiction), the Boolean polynomial looks as follows:

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:

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.


Extensions

  1. Vector logic can be extended to many dimensions, and large dimensional vector-spaces allows to create many truth values and the corresponding logical matrices (E. Mizraji, Vector logic: a natural algebraic representation of the fundamental logical gates. Journal of Logic and Computation 18, 97–121, 2008)
  1. Logical modalities can be fully represented in this context, with recursive process inspired in neural models proposed by McCulloch and Pitts (W. S. McCulloch, and W. Pitts. A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5, 115–133, 1943; E. Mizraji. Modalities in vector logic. Notre Dame Journal of Formal Logic, 35, 272–283, 1994; E. Mizraji, Vector logic: a natural algebraic representation of the fundamental logical gates. Journal of Logic and Computation 18, 97–121, 2008)
  1. Some cognitive problems about logical computations can be analyzed using this formalism, in particular recursive decisions (E. Mizraji, and J. Lin. The dynamics of logical decisions. Physica D, 168–169, 386–396, 2002; P. beim Graben, and R. Potthast. (2009). Inverse problems in dynamic cognitive modeling. Chaos, 19, 015103, 2009; P. beim Graben, D. Pinotsis, D. Saddyand R Potthast (2008a). Language processing with dynamic fields. Cogn. Neurodyn., 2, 79–88, 2008; P. beim Graben, S. Gerth, and S. Vasishth. Towards dynamical system models of language-related brain potentials. Cogn. Neurodyn., 2, 229–255, 2008; A. Binazzi. Cognizione logica e modelli mentali, Studi sulla formazione, 1-2012, pag. 69-84 © Firenze University Press-http://www.fupress.net/index.php/sf/article/view/11649).
  1. The computation via reversible operations as the Fredkin gate (E. Fredkin, and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21, 219–253, 1982; R. P. Feynman. Lectures on Computation, Perseus, Cambridge, 1999) 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 (E. Mizraji. The operators of vector logic. Mathematical Logic Quarterly, 42, 27–39, 1996; E. Mizraji, Vector logic: a natural algebraic representation of the fundamental logical gates. Journal of Logic and Computation 18, 97–121, 2008 ).
  1. Elementary Celular Automata (ECA) can be analyzing using the operator structure of this vector logic; this analysis lead to an spectral decomposition of the laws governing ECA (E. Mizraji, The parts and the whole: inquiring how the interaction of simple subsystems generates complexity. International Journal of General Systems, 35 , p. 395-415, 2006;.C. Arruti, E, Mizraji, Hidden potentialities. International Journal of General Systems, 35 , 461-469, 2006).

References

  1. ^ a b Mizraji, E. (1992). Vector logics: the matrix-vector representation of logical calculus. Fuzzy Sets and Systems, 50, 179–185, 1992
  2. ^ Mizraji, E. (2008) Vector logic: a natural algebraic representation of the fundamental logical gates. Journal of Logic and Computation, 18, 97–121, 2008
  3. ^ Mizraji, E. (1996) The operators of vector logic. Mathematical Logic Quarterly, 42, 27–39
  4. ^ 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. ^ Kohonen, T.(1977) [Associative Memory: A System-Theoretical Approach.] Springer-Verlag, New York
  7. ^ Mizraji,E. (1989) [Context-dependent associations in linear distributed memories]. Bulletin of Mathematical Biology, 50, 195–205
  8. ^ a b 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
  9. ^ Dick, S. (2005) Towards complex fuzzy logic. IEEE Transactions on Fuzzy Systems, 15,405–414, 2005
  10. ^ Mittelstaedt, P. (1968) Philosophische Probleme der Modernen Physik, Bibliographisches Institut, Mannheim
  11. ^ Stern, A. (1988) Matrix Logic: Theory and Applications. North-Holland, Amsterdam
  12. ^ Westphal, J., Hardy, J. (2005) Logic as a vector system. Journal of Logic and Computation, 15, 751–765
  13. ^ Copilovich, I.M. (1948) Matrix development of the calculus of relations. Journal of Symbolic Logic, 13, 193–203
  14. ^ Jain, M.K. (2001) Logic of evidence-based inference propositions, Current Science, 1663-1672, 100