Four-valued logic

Last updated

In logic, a four-valued logic is any logic with four truth values. Several types of four-valued logic have been advanced.

Contents

Belnap

Nuel Belnap considered the challenge of question answering by computer in 1975. Noting human fallibility, he was concerned with the case where two contradictory facts were loaded into memory, and then a query was made. "We all know about the fecundity of contradictions in two-valued logic: contradictions are never isolated, infecting as they do the whole system." [1] Belnap proposed a four-valued logic as a means of containing contradiction. [2] [3]

He called the table of values A4: Its possible values are true, false, both (true and false), and neither (true nor false). Belnap's logic is designed to cope with multiple information sources such that if only true is found then true is assigned, if only false is found then false is assigned, if some sources say true and others say false then both is assigned, and if no information is given by any information source then neither is assigned. These four values correspond to the elements of the power set based on {T, F}.

T is the supremum and F the infimum in the logical lattice where None and Both are in the wings. Belnap has this interpretation: "The worst thing is to be told something is false simpliciter. You are better off (it is one of your hopes) in either being told nothing about it, or being told both that it is true and also that it is false; while of course best of all is to be told that it is true." Belnap notes that "paradoxes of implication" (A&~A)→B and A→(B∨~B) are avoided in his 4-valued system.

Logical connectives

Belnap addressed the challenge of extending logical connectives to A4. Since it is the power set on {T, F}, the elements of A4 are ordered by inclusion making it a lattice with Both at the supremum and None at the infimum, and T and F on the wings. Referring to Dana Scott, he assumes the connectives are Scott-continuous or monotonic functions. First he expands negation by deducing that ¬Both = Both and ¬None = None. To expand And and Or the monotonicity goes only so far. Belnap uses equivalence (a&b = a iff avb = b) to fill out the tables for these connectives. He finds None & Both = F while None v Both = T.

&NFTB
NNFNF
FFFFF
TNFTB
BFFBB
vNFTB
NNNTT
FNFTB
TTTTT
BTBTB

The result is a second lattice L4 called the "logical lattice", where A4 is the "approximation lattice" determining Scott continuity.

Implementation using two bits

Let one bit be assigned for each truth value: 01=T and 10=F with 00=N and 11=B. [4]

Then the subset relation in the power set on {T, F} corresponds to order ab<cd iff a<c and b<d in two-bit representation. Belnap calls the lattice associated with this order the "approximation lattice".

The logic associated with two-bit variables can be incorporated into computer hardware. [5]

Matrix transitions

As a discrete system, the four-valued logic illustrates a set of states subject to transitions by logical matrices to form a transition system. An input of two bits transitions to an output of two bits through matrix multiplication.

There are sixteen logical matrices that are 2x2, and four logical vectors that act as inputs and outputs of the matrix transitions:

X = {A, B, C, D } = {(0,1), (1, 0), (0, 0), (1, 1) }.

When C is input, the output is always C. Four of the sixteen have zero in one corner only, so the output of vector-matrix multiplication with Boolean arithmetic is always D, except for C input.

Nine further logical matrices need description to fill out the labelled transition system where the matrices label the transitions. Excluding C, inputs A, B, and D are considered in order and the output in X expressed as a triple, for example ABD for commonly known as the identity matrix.

The asymmetric matrices differ in their action on row versus column vectors. The row convention is used here:

has code BBB, code AAA
has code CDB, code DCA.

The remaining operations on X are expressed with matrices with three zeros, so outputs include C for a third of the inputs. The codes are CAA, BCA, ACA, and CBB in these cases.

Applications

A four-valued logic was established by IEEE with the standard IEEE 1364: It models signal values in digital circuits. The four values are 1, 0, Z and X. 1 and 0 stand for Boolean true and false, Z stands for high impedance or open circuit and X stands for don't care (e.g., the value has no effect). This logic is itself a subset of the 9-valued logic standard called IEEE 1164 and implemented in Very High Speed Integrated Circuit Hardware Description Language, VHDL's std_logic.

One should not confuse four-valued mathematical logic (using operators, truth tables, syllogisms, propositional calculus, theorems and so on) with communication protocols built using binary logic and displaying responses with four possible states implemented with Boolean-like type of values : for instance, the SAE J1939 standard, used for CAN data transmission in heavy road vehicles, which has four logical (Boolean) values: False, True, Error Condition, and Not installed (represented by values 0–3). Error Condition means there is a technical problem obstructing data acquisition. The logics for that is for example True and Error Condition=Error Condition. Not installed is used for a feature that does not exist in this vehicle, and should be disregarded for logical calculation. On CAN, usually fixed data messages are sent containing many signal values each, so a signal representing a not-installed feature will be sent anyway.

Split bit proposed gate

Creation of carbon nanotubes for logical gates has used carbon nanotube field-effect transistors (CNFETs). An anticipated demand for data storage in the Internet of Things (IoT) provides a motivation. A proposal has been made for 32 nm process application using a split bit-gate: "By using CNFET technology in 32 nm node by the proposed SQI gate, two split bit-lines QSRAM architectures have been suggested to address the issue of increasing demand for storage capacity in IoT/IoVT applications. Peripheral circuits such as a novel quaternary to binary decoder for QSRAM have been offered." [6]

Related Research Articles

<span class="mw-page-title-main">Boolean algebra (structure)</span> Algebraic structure modeling logical operations

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra.

<span class="mw-page-title-main">Logical disjunction</span> Logical connective OR

In logic, disjunction, also known as logical disjunction or logical or or logical addition or inclusive disjunction, is a logical connective typically notated as and read aloud as "or". For instance, the English language sentence "it is sunny or it is warm" can be represented in logic using the disjunctive formula , assuming that abbreviates "it is sunny" and abbreviates "it is warm".

<span class="mw-page-title-main">Logical conjunction</span> Logical connective AND

In logic, mathematics and linguistics, and is the truth-functional operator of conjunction or logical conjunction. The logical connective of this operator is typically represented as or or (prefix) or or in which is the most modern and widely used.

Many-valued logic is a propositional calculus in which there are more than two truth values. Traditionally, in Aristotle's logical calculus, there were only two possible values for any proposition. Classical two-valued logic may be extended to n-valued logic for n greater than 2. Those most popular in the literature are three-valued, four-valued, nine-valued, the finite-valued with more than three values, and the infinite-valued (infinitely-many-valued), such as fuzzy logic and probability logic.

<span class="mw-page-title-main">Inverter (logic gate)</span> Logic gate implementing negation

In digital logic, an inverter or NOT gate is a logic gate which implements logical negation. It outputs a bit opposite of the bit that is put into it. The bits are typically implemented as two differing voltage levels.

<span class="mw-page-title-main">Exclusive or</span> True when either but not both inputs are true

Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ. With multiple inputs, XOR is true if and only if the number of true inputs is odd.

An adder, or summer, is a digital circuit that performs addition of numbers. In many computers and other kinds of processors, adders are used in the arithmetic logic units (ALUs). They are also used in other parts of the processor, where they are used to calculate addresses, table indices, increment and decrement operators and similar operations.

In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: the input and output of a truth function are all truth values; a truth function will always output exactly one truth value, and inputting the same truth value(s) will always output the same truth value. The typical example is in propositional logic, wherein a compound statement is constructed using individual statements connected by logical connectives; if the truth value of the compound statement is entirely determined by the truth value(s) of the constituent statement(s), the compound statement is called a truth function, and any logical connectives used are said to be truth functional.

<span class="mw-page-title-main">Boolean function</span> Function returning one of only two values

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set. Alternative names are switching function, used especially in older computer science literature, and truth function, used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form (CDNF), minterm canonical form, or Sum of Products as a disjunction (OR) of minterms. The De Morgan dual is the canonical conjunctive normal form (CCNF), maxterm canonical form, or Product of Sums which is a conjunction (AND) of maxterms. These forms can be useful for the simplification of Boolean functions, which is of great importance in the optimization of Boolean formulas in general and digital circuits in particular.

The OR gate is a digital logic gate that implements logical disjunction. The OR gate outputs "true" if any of its inputs is "true"; otherwise it outputs "false". The input and output states are normally represented by different voltage levels.

XOR gate is a digital logic gate that gives a true output when the number of true inputs is odd. An XOR gate implements an exclusive or from mathematical logic; that is, a true output results if one, and only one, of the inputs to the gate is true. If both inputs are false (0/LOW) or both are true, a false output results. XOR represents the inequality function, i.e., the output is true if the inputs are not alike otherwise the output is false. A way to remember XOR is "must have one or the other but not both".

The XNOR gate is a digital logic gate whose function is the logical complement of the Exclusive OR (XOR) gate. It is equivalent to the logical connective from mathematical logic, also known as the material biconditional. The two-input version implements logical equality, behaving according to the truth table to the right, and hence the gate is sometimes called an "equivalence gate". A high output (1) results if both of the inputs to the gate are the same. If one but not both inputs are high (1), a low output (0) results.

A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in combinatorial mathematics and theoretical computer science.

<span class="mw-page-title-main">Karnaugh map</span> Graphical method to simplify Boolean expressions

A Karnaugh map is a diagram that can be used to simplify a Boolean algebra expression. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which itself was a rediscovery of Allan Marquand's 1881 logical diagram. It is also useful for understanding logic circuits. Karnaugh maps are also known as Marquand–Veitch diagrams, Svoboda charts -(albeit only rarely)- and Karnaugh–Veitch maps.

Zhegalkinpolynomials, also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927, they are the polynomial ring over the integers modulo 2. The resulting degeneracies of modular arithmetic result in Zhegalkin polynomials being simpler than ordinary polynomials, requiring neither coefficients nor exponents. Coefficients are redundant because 1 is the only nonzero coefficient. Exponents are redundant because in arithmetic mod 2, x2 = x. Hence a polynomial such as 3x2y5z is congruent to, and can therefore be rewritten as, xyz.

<span class="mw-page-title-main">Dedekind number</span> Combinatorial sequence of numbers

In mathematics, the Dedekind numbers are a rapidly growing sequence of integers named after Richard Dedekind, who defined them in 1897. The Dedekind number M(n) is the number of monotone Boolean functions of n variables. Equivalently, it is the number of antichains of subsets of an n-element set, the number of elements in a free distributive lattice with n generators, and one more than the number of abstract simplicial complexes on a set with n elements.

In mathematics, a semigroup with two elements is a semigroup for which the cardinality of the underlying set is two. There are exactly five nonisomorphic semigroups having two elements:

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arguments, that is, for each combination of values taken by their logical variables. In particular, truth tables can be used to show whether a propositional expression is true for all legitimate input values, that is, logically valid.

In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false, usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction (and) denoted as , disjunction (or) denoted as , and negation (not) denoted as ¬. Elementary algebra, on the other hand, uses arithmetic operators such as addition, multiplication, subtraction, and division. Boolean algebra is therefore a formal way of describing logical operations in the same way that elementary algebra describes numerical operations.

References

  1. This feature of two-valued logic has been termed the principle of explosion.
  2. N. Belnap (1975) "How Computers Should Think", pages 30 to 56 in Contemporary Aspects of Philosophy, Gilbert Ryle editor, Oriel Press ISBN   0-85362-161-6
  3. N. Belnap (1977) A Useful Four-Valued Logic, in Modern Uses of Multiple-Valued Logic, edited by J. Michael Dunn and George Epstein, Springer books
  4. Greniewski, Henryk; Bochenek, Krystyn; Marczyński, Romuald (1955). "Application of bi-elemental boolean algebra to electronic circuits". Studia Logica. 2: 7–75. doi:10.1007/BF02124765. S2CID   122166200.
  5. Ben Choi (2013) "Advancing from two to four valued logic circuits", International Conference on Industrial Technology, IEEE, doi : 10.1109/ICIT.2013.6505818
  6. Ghasemian1, Arsalan; Abiri1, Ebrahim; Hassanli1, Kourosh; Darabi1, Abdolreza (11 January 2022). "HF-QSRAM: Half-Select Free Quaternary SRAM Design with Required Peripheral Circuits for IoT/IoVT Applications". ECS Journal of Solid State Science and Technology. 11 (1). IOP. 011002. Bibcode:2022JSSST..11a1002G. doi:10.1149/2162-8777/ac4798. S2CID   245689866.{{cite journal}}: CS1 maint: numeric names: authors list (link)

See also

Further reading