Get Our Extension

Many-valued logic

From Wikipedia, in a visual modern way

Many-valued logic (also multi- or multiple-valued logic) refers to a propositional calculus in which there are more than two truth values. Traditionally, in Aristotle's logical calculus, there were only two possible values (i.e., "true" and "false") 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 (e.g., Łukasiewicz's and Kleene's, which accept the values "true", "false", and "unknown"), four-valued, nine-valued, the finite-valued (finitely-many valued) with more than three values, and the infinite-valued (infinitely-many-valued), such as fuzzy logic and probability logic.

Discover more about Many-valued logic related topics

Propositional calculus

Propositional calculus

Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives. Propositions that contain no logical connectives are called atomic propositions.

Aristotle

Aristotle

Aristotle was a Greek philosopher and polymath during the Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatetic school of philosophy within the Lyceum and the wider Aristotelian tradition. His writings cover many subjects including physics, biology, zoology, metaphysics, logic, ethics, aesthetics, poetry, theatre, music, rhetoric, psychology, linguistics, economics, politics, meteorology, geology, and government. Aristotle provided a complex synthesis of the various philosophies existing prior to him. It was above all from his teachings that the West inherited its intellectual lexicon, as well as problems and methods of inquiry. As a result, his philosophy has exerted a unique influence on almost every form of knowledge in the West and it continues to be a subject of contemporary philosophical discussion.

Term logic

Term logic

In philosophy, term logic, also known as traditional logic, syllogistic logic or Aristotelian logic, is a loose name for an approach to formal logic that began with Aristotle and was developed further in ancient history mostly by his followers, the peripatetics. It was revived after the third century CE by Porphyry's Isagoge.

Proposition

Proposition

In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, "meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the non-linguistic bearer of truth or falsity which makes any sentence that expresses it either true or false.

Three-valued logic

Three-valued logic

In logic, a three-valued logic is any of several many-valued logic systems in which there are three truth values indicating true, false and some indeterminate third value. This is contrasted with the more commonly known bivalent logics which provide only for true and false.

Jan Łukasiewicz

Jan Łukasiewicz

Jan Łukasiewicz was a Polish logician and philosopher who is best known for Polish notation and Łukasiewicz logic His work centred on philosophical logic, mathematical logic and history of logic. He thought innovatively about traditional propositional logic, the principle of non-contradiction and the law of excluded middle, offering one of the earliest systems of many-valued logic. Contemporary research on Aristotelian logic also builds on innovative works by Łukasiewicz, which applied methods from modern logic to the formalization of Aristotle's syllogistic.

Stephen Cole Kleene

Stephen Cole Kleene

Stephen Cole Kleene was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of mathematical logic known as recursion theory, which subsequently helped to provide the foundations of theoretical computer science. Kleene's work grounds the study of computable functions. A number of mathematical concepts are named after him: Kleene hierarchy, Kleene algebra, the Kleene star, Kleene's recursion theorem and the Kleene fixed-point theorem. He also invented regular expressions in 1951 to describe McCulloch-Pitts neural networks, and made significant contributions to the foundations of mathematical intuitionism.

Four-valued logic

Four-valued logic

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

Finite-valued logic

Finite-valued logic

In logic, a finite-valued logic is a propositional calculus in which truth values are discrete. Traditionally, in Aristotle's logic, the bivalent logic, also known as binary logic was the norm, as the law of the excluded middle precluded more than two possible values for any proposition. Modern three-valued logic allows for an additional possible truth value.

Infinite-valued logic

Infinite-valued logic

In logic, an infinite-valued logic is a many-valued logic in which truth values comprise a continuous range. Traditionally, in Aristotle's logic, logic other than bivalent logic was abnormal, as the law of the excluded middle precluded more than two possible values for any proposition. Modern three-valued logic allows for an additional possible truth value and is an example of finite-valued logic in which truth values are discrete, rather than continuous. Infinite-valued logic comprises continuous fuzzy logic, though fuzzy logic in some of its forms can further encompass finite-valued logic. For example, finite-valued logic can be applied in Boolean-valued modeling, description logics, and defuzzification of fuzzy logic.

Fuzzy logic

Fuzzy logic

Fuzzy logic is a form of many-valued logic in which the truth value of variables may be any real number between 0 and 1. It is employed to handle the concept of partial truth, where the truth value may range between completely true and completely false. By contrast, in Boolean logic, the truth values of variables may only be the integer values 0 or 1.

Probabilistic logic

Probabilistic logic

Probabilistic logic involves the use of probability and logic to deal with uncertain situations. Probabilistic logic extends traditional logic truth tables with probabilistic expressions. A difficulty of probabilistic logics is their tendency to multiply the computational complexities of their probabilistic and logical components. Other difficulties include the possibility of counter-intuitive results, such as in case of belief fusion in Dempster–Shafer theory. Source trust and epistemic uncertainty about the probabilities they provide, such as defined in subjective logic, are additional elements to consider. The need to deal with a broad variety of contexts and issues has led to many different proposals.

History

It is wrong that the first known classical logician who did not fully accept the law of excluded middle was Aristotle (who, ironically, is also generally considered to be the first classical logician and the "father of [two-valued] logic"[1]). In fact, Aristotle did not contest the universality of the law of excluded middle, but the universality of the bivalence principle: he admitted that this principle did not all apply to future events (De Interpretatione, ch. IX),[2] but he didn't create a system of multi-valued logic to explain this isolated remark. Until the coming of the 20th century, later logicians followed Aristotelian logic, which includes or assumes the law of the excluded middle.

The 20th century brought back the idea of multi-valued logic. The Polish logician and philosopher Jan Łukasiewicz began to create systems of many-valued logic in 1920, using a third value, "possible", to deal with Aristotle's paradox of the sea battle. Meanwhile, the American mathematician, Emil L. Post (1921), also introduced the formulation of additional truth degrees with n ≥ 2, where n are the truth values. Later, Jan Łukasiewicz and Alfred Tarski together formulated a logic on n truth values where n ≥ 2. In 1932, Hans Reichenbach formulated a logic of many truth values where n→∞. Kurt Gödel in 1932 showed that intuitionistic logic is not a finitely-many valued logic, and defined a system of Gödel logics intermediate between classical and intuitionistic logic; such logics are known as intermediate logics.

Discover more about History related topics

Law of excluded middle

Law of excluded middle

In logic, the law of excluded middle states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncontradiction, and the law of identity. However, no system of logic is built on just these laws, and none of these laws provides inference rules, such as modus ponens or De Morgan's laws.

Aristotle

Aristotle

Aristotle was a Greek philosopher and polymath during the Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatetic school of philosophy within the Lyceum and the wider Aristotelian tradition. His writings cover many subjects including physics, biology, zoology, metaphysics, logic, ethics, aesthetics, poetry, theatre, music, rhetoric, psychology, linguistics, economics, politics, meteorology, geology, and government. Aristotle provided a complex synthesis of the various philosophies existing prior to him. It was above all from his teachings that the West inherited its intellectual lexicon, as well as problems and methods of inquiry. As a result, his philosophy has exerted a unique influence on almost every form of knowledge in the West and it continues to be a subject of contemporary philosophical discussion.

Jan Łukasiewicz

Jan Łukasiewicz

Jan Łukasiewicz was a Polish logician and philosopher who is best known for Polish notation and Łukasiewicz logic His work centred on philosophical logic, mathematical logic and history of logic. He thought innovatively about traditional propositional logic, the principle of non-contradiction and the law of excluded middle, offering one of the earliest systems of many-valued logic. Contemporary research on Aristotelian logic also builds on innovative works by Łukasiewicz, which applied methods from modern logic to the formalization of Aristotle's syllogistic.

Problem of future contingents

Problem of future contingents

Future contingent propositions are statements about states of affairs in the future that are contingent: neither necessarily true nor necessarily false.

Alfred Tarski

Alfred Tarski

Alfred Tarski was a Polish-American logician and mathematician. A prolific author best known for his work on model theory, metamathematics, and algebraic logic, he also contributed to abstract algebra, topology, geometry, measure theory, mathematical logic, set theory, and analytic philosophy.

Hans Reichenbach

Hans Reichenbach

Hans Reichenbach was a leading philosopher of science, educator, and proponent of logical empiricism. He was influential in the areas of science, education, and of logical empiricism. He founded the Gesellschaft für empirische Philosophie in Berlin in 1928, also known as the “Berlin Circle”. Carl Gustav Hempel, Richard von Mises, David Hilbert and Kurt Grelling all became members of the Berlin Circle.

Kurt Gödel

Kurt Gödel

Kurt Friedrich Gödel was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an immense effect upon scientific and philosophical thinking in the 20th century, a time when others such as Bertrand Russell, Alfred North Whitehead, and David Hilbert were using logic and set theory to investigate the foundations of mathematics, building on earlier work by the likes of Richard Dedekind, Georg Cantor and Frege.

Intuitionistic logic

Intuitionistic logic

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not include the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.

Gödel logic

Gödel logic

In mathematical logic, a first-order Gödel logic is a member of a family of finite- or infinite-valued logics in which the sets of truth values V are closed subsets of the interval [0,1] containing both 0 and 1. Different such sets V in general determine different Gödel logics. The concept is named after Kurt Gödel.

Classical logic

Classical logic

Classical logic is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.

Examples

Kleene (strong) K3 and Priest logic P3

Kleene's "(strong) logic of indeterminacy" K3 (sometimes ) and Priest's "logic of paradox" add a third "undefined" or "indeterminate" truth value I. The truth functions for negation (¬), conjunction (∧), disjunction (∨), implication (K), and biconditional (K) are given by:[3]

¬  
T F
I I
F T
T I F
T T I F
I I I F
F F F F
T I F
T T T T
I T I I
F T I F
K T I F
T T I F
I T I I
F T T T
K T I F
T T I F
I I I I
F F I T

The difference between the two logics lies in how tautologies are defined. In K3 only T is a designated truth value, while in P3 both T and I are (a logical formula is considered a tautology if it evaluates to a designated truth value). In Kleene's logic I can be interpreted as being "underdetermined", being neither true nor false, while in Priest's logic I can be interpreted as being "overdetermined", being both true and false. K3 does not have any tautologies, while P3 has the same tautologies as classical two-valued logic.[4]

Bochvar's internal three-valued logic

Another logic is Dmitry Bochvar's "internal" three-valued logic , also called Kleene's weak three-valued logic. Except for negation and biconditional, its truth tables are all different from the above.[5]

+ T I F
T T I F
I I I I
F F I F
+ T I F
T T I T
I I I I
F T I F
+ T I F
T T I F
I I I I
F T I T

The intermediate truth value in Bochvar's "internal" logic can be described as "contagious" because it propagates in a formula regardless of the value of any other variable.[5]

Belnap logic (B4)

Belnap's logic B4 combines K3 and P3. The overdetermined truth value is here denoted as B and the underdetermined truth value as N.

f¬  
T F
B B
N N
F T
f T B N F
T T B N F
B B B F F
N N F N F
F F F F F
f T B N F
T T T T T
B T B T B
N T T N N
F T B N F

Gödel logics Gk and G

In 1932 Gödel defined[6] a family of many-valued logics, with finitely many truth values , for example has the truth values and has . In a similar manner he defined a logic with infinitely many truth values, , in which the truth values are all the real numbers in the interval . The designated truth value in these logics is 1.

The conjunction and the disjunction are defined respectively as the minimum and maximum of the operands:

Negation and implication are defined as follows:

Gödel logics are completely axiomatisable, that is to say it is possible to define a logical calculus in which all tautologies are provable. The implication above is the unique heyting implication defined by the fact that the suprema and minima operations form a complete lattice with an infinite distributive law, which defines a unique complete heyting algebra structure on the lattice.

Łukasiewicz logics Lv and L

Implication and negation were defined by Jan Łukasiewicz through the following functions:

At first Łukasiewicz used these definitions in 1920 for his three-valued logic , with truth values . In 1922 he developed a logic with infinitely many values , in which the truth values spanned the real numbers in the interval . In both cases the designated truth value was 1.[7]

By adopting truth values defined in the same way as for Gödel logics , it is possible to create a finitely-valued family of logics , the abovementioned and the logic , in which the truth values are given by the rational numbers in the interval . The set of tautologies in and is identical.

Product logic Π

In product logic we have truth values in the interval , a conjunction and an implication , defined as follows[8]

Additionally there is a negative designated value that denotes the concept of false. Through this value it is possible to define a negation and an additional conjunction as follows:

and then .

Post logics Pm

In 1921 Post defined a family of logics with (as in and ) the truth values . Negation and conjunction and disjunction are defined as follows:

Rose logics

In 1951, Alan Rose defined another family of logics for systems whose truth-values form lattices.[9]

Discover more about Examples related topics

Four-valued logic

Four-valued logic

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

Stephen Cole Kleene

Stephen Cole Kleene

Stephen Cole Kleene was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of mathematical logic known as recursion theory, which subsequently helped to provide the foundations of theoretical computer science. Kleene's work grounds the study of computable functions. A number of mathematical concepts are named after him: Kleene hierarchy, Kleene algebra, the Kleene star, Kleene's recursion theorem and the Kleene fixed-point theorem. He also invented regular expressions in 1951 to describe McCulloch-Pitts neural networks, and made significant contributions to the foundations of mathematical intuitionism.

Graham Priest

Graham Priest

Graham Priest is Distinguished Professor of Philosophy at the CUNY Graduate Center, as well as a regular visitor at the University of Melbourne, where he was Boyce Gibson Professor of Philosophy and also at the University of St Andrews.

Negation

Negation

In logic, negation, also called the logical complement, is an operation that takes a proposition to another proposition "not ", written , or . It is interpreted intuitively as being true when is false, and false when is true. Negation is thus a unary logical connective. It may be applied as an operation on notions, propositions, truth values, or semantic values more generally. In classical logic, negation is normally identified with the truth function that takes truth to falsity. In intuitionistic logic, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition is the proposition whose proofs are the refutations of .

Logical conjunction

Logical conjunction

In logic, mathematics and linguistics, And is the truth-functional operator of logical conjunction; the and of a set of operands is true if and only if all of its operands are true. The logical connective that represents this operator is typically written as or ⋅ .

Material conditional

Material conditional

The material conditional is an operation commonly used in logic. When the conditional symbol is interpreted as material implication, a formula is true unless is true and is false. Material implication can also be characterized inferentially by modus ponens, modus tollens, conditional proof, and classical reductio ad absurdum.

Tautology (logic)

Tautology (logic)

In mathematical logic, a tautology is a formula or assertion that is true in every possible interpretation. An example is "x=y or x≠y". Similarly, "either the ball is green, or the ball is not green" is always true, regardless of the colour of the ball.

Nuel Belnap

Nuel Belnap

Nuel Dinsmore Belnap Jr. is an American logician and philosopher who has made contributions to the philosophy of logic, temporal logic, and structural proof theory. He taught at the University of Pittsburgh from 1963 until his retirement in 2011.

Kurt Gödel

Kurt Gödel

Kurt Friedrich Gödel was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an immense effect upon scientific and philosophical thinking in the 20th century, a time when others such as Bertrand Russell, Alfred North Whitehead, and David Hilbert were using logic and set theory to investigate the foundations of mathematics, building on earlier work by the likes of Richard Dedekind, Georg Cantor and Frege.

Real number

Real number

In mathematics, a real number is a number that can be used to measure a continuous one-dimensional quantity such as a distance, duration or temperature. Here, continuous means that values can have arbitrarily small variations. Every real number can be almost uniquely represented by an infinite decimal expansion.

Jan Łukasiewicz

Jan Łukasiewicz

Jan Łukasiewicz was a Polish logician and philosopher who is best known for Polish notation and Łukasiewicz logic His work centred on philosophical logic, mathematical logic and history of logic. He thought innovatively about traditional propositional logic, the principle of non-contradiction and the law of excluded middle, offering one of the earliest systems of many-valued logic. Contemporary research on Aristotelian logic also builds on innovative works by Łukasiewicz, which applied methods from modern logic to the formalization of Aristotle's syllogistic.

Rational number

Rational number

In mathematics, a rational number is a number that can be expressed as the quotient or fraction p/q of two integers, a numerator p and a non-zero denominator q. For example, −3/7 is a rational number, as is every integer. The set of all rational numbers, also referred to as "the rationals", the field of rationals or the field of rational numbers is usually denoted by boldface Q, or blackboard bold

Relation to classical logic

Logics are usually systems intended to codify rules for preserving some semantic property of propositions across transformations. In classical logic, this property is "truth." In a valid argument, the truth of the derived proposition is guaranteed if the premises are jointly true, because the application of valid steps preserves the property. However, that property doesn't have to be that of "truth"; instead, it can be some other concept.

Multi-valued logics are intended to preserve the property of designationhood (or being designated). Since there are more than two truth values, rules of inference may be intended to preserve more than just whichever corresponds (in the relevant sense) to truth. For example, in a three-valued logic, sometimes the two greatest truth-values (when they are represented as e.g. positive integers) are designated and the rules of inference preserve these values. Precisely, a valid argument will be such that the value of the premises taken jointly will always be less than or equal to the conclusion.

For example, the preserved property could be justification, the foundational concept of intuitionistic logic. Thus, a proposition is not true or false; instead, it is justified or flawed. A key difference between justification and truth, in this case, is that the law of excluded middle doesn't hold: a proposition that is not flawed is not necessarily justified; instead, it's only not proven that it's flawed. The key difference is the determinacy of the preserved property: One may prove that P is justified, that P is flawed, or be unable to prove either. A valid argument preserves justification across transformations, so a proposition derived from justified propositions is still justified. However, there are proofs in classical logic that depend upon the law of excluded middle; since that law is not usable under this scheme, there are propositions that cannot be proven that way.

Suszko's thesis

Discover more about Relation to classical logic related topics

Logic

Logic

Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises in a topic-neutral way. When used as a countable noun, the term "a logic" refers to a logical formal system that articulates a proof system. Formal logic contrasts with informal logic, which is associated with informal fallacies, critical thinking, and argumentation theory. While there is no general agreement on how formal and informal logic are to be distinguished, one prominent approach associates their difference with whether the studied arguments are expressed in formal or informal languages. Logic plays a central role in multiple fields, such as philosophy, mathematics, computer science, and linguistics.

Intuitionistic logic

Intuitionistic logic

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not include the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.

Law of excluded middle

Law of excluded middle

In logic, the law of excluded middle states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncontradiction, and the law of identity. However, no system of logic is built on just these laws, and none of these laws provides inference rules, such as modus ponens or De Morgan's laws.

Functional completeness of many-valued logics

Functional completeness is a term used to describe a special property of finite logics and algebras. A logic's set of connectives is said to be functionally complete or adequate if and only if its set of connectives can be used to construct a formula corresponding to every possible truth function.[10] An adequate algebra is one in which every finite mapping of variables can be expressed by some composition of its operations.[11]

Classical logic: CL = ({0,1}, ¬, →, ∨, ∧, ↔) is functionally complete, whereas no Łukasiewicz logic or infinitely many-valued logics has this property.[11][12]

We can define a finitely many-valued logic as being Ln ({1, 2, ..., n} ƒ1, ..., ƒm) where n ≥ 2 is a given natural number. Post (1921) proves that assuming a logic is able to produce a function of any mth order model, there is some corresponding combination of connectives in an adequate logic Ln that can produce a model of order m+1.[13]

Discover more about Functional completeness of many-valued logics related topics

Functional completeness

Functional completeness

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete.

Truth function

Truth function

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.

Łukasiewicz logic

Łukasiewicz logic

In mathematics and philosophy, Łukasiewicz logic is a non-classical, many-valued logic. It was originally defined in the early 20th century by Jan Łukasiewicz as a three-valued modal logic; it was later generalized to n-valued as well as infinitely-many-valued (ℵ0-valued) variants, both propositional and first order. The ℵ0-valued version was published in 1930 by Łukasiewicz and Alfred Tarski; consequently it is sometimes called the Łukasiewicz–Tarski logic. It belongs to the classes of t-norm fuzzy logics and substructural logics.

Emil Leon Post

Emil Leon Post

Emil Leon Post was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.

Applications

Known applications of many-valued logic can be roughly classified into two groups.[14] The first group uses many-valued logic to solve binary problems more efficiently. For example, a well-known approach to represent a multiple-output Boolean function is to treat its output part as a single many-valued variable and convert it to a single-output characteristic function (specifically, the indicator function). Other applications of many-valued logic include design of programmable logic arrays (PLAs) with input decoders, optimization of finite state machines, testing, and verification.

The second group targets the design of electronic circuits that employ more than two discrete levels of signals, such as many-valued memories, arithmetic circuits, and field programmable gate arrays (FPGAs). Many-valued circuits have a number of theoretical advantages over standard binary circuits. For example, the interconnect on and off chip can be reduced if signals in the circuit assume four or more levels rather than only two. In memory design, storing two instead of one bit of information per memory cell doubles the density of the memory in the same die size. Applications using arithmetic circuits often benefit from using alternatives to binary number systems. For example, residue and redundant number systems[15] can reduce or eliminate the ripple-through carries that are involved in normal binary addition or subtraction, resulting in high-speed arithmetic operations. These number systems have a natural implementation using many-valued circuits. However, the practicality of these potential advantages heavily depends on the availability of circuit realizations, which must be compatible or competitive with present-day standard technologies. In addition to aiding in the design of electronic circuits, many-valued logic is used extensively to test circuits for faults and defects. Basically all known automatic test pattern generation (ATG) algorithms used for digital circuit testing require a simulator that can resolve 5-valued logic (0, 1, x, D, D').[16] The additional values—x, D, and D'—represent (1) unknown/uninitialized, (2) a 0 instead of a 1, and (3) a 1 instead of a 0.

Discover more about Applications related topics

Characteristic function

Characteristic function

In mathematics, the term "characteristic function" can refer to any of several distinct concepts:The indicator function of a subset, that is the function which for a given subset A of X, has value 1 at points of A and 0 at points of X − A.There is an indicator function for affine varieties over a finite field: given a finite set of functions let be their vanishing locus. Then, the function acts as an indicator function for . If then , otherwise, for some , we have , which implies that , hence . The characteristic function in convex analysis, closely related to the indicator function of a set: In probability theory, the characteristic function of any probability distribution on the real line is given by the following formula, where X is any random variable with the distribution in question: where denotes expected value. For multivariate distributions, the product tX is replaced by a scalar product of vectors. The characteristic function of a cooperative game in game theory. The characteristic polynomial in linear algebra. The characteristic state function in statistical mechanics. The Euler characteristic, a topological invariant. The receiver operating characteristic in statistical decision theory. The point characteristic function in statistics.

Indicator function

Indicator function

In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if A is a subset of some set X, one has if and otherwise, where is a common notation for the indicator function. Other common notations are and

Programmable logic array

Programmable logic array

A programmable logic array (PLA) is a kind of programmable logic device used to implement combinational logic circuits. The PLA has a set of programmable AND gate planes, which link to a set of programmable OR gate planes, which can then be conditionally complemented to produce an output. It has 2N AND gates for N input variables, and for M outputs from PLA, there should be M OR gates, each with programmable inputs from all of the AND gates. This layout allows for many logic functions to be synthesized in the sum of products canonical forms.

Die (integrated circuit)

Die (integrated circuit)

A die, in the context of integrated circuits, is a small block of semiconducting material on which a given functional circuit is fabricated. Typically, integrated circuits are produced in large batches on a single wafer of electronic-grade silicon (EGS) or other semiconductor through processes such as photolithography. The wafer is cut (diced) into many pieces, each containing one copy of the circuit. Each of these pieces is called a die.

Residue number system

Residue number system

A residue numeral system (RNS) is a numeral system representing integers by their values modulo several pairwise coprime integers called the moduli. This representation is allowed by the Chinese remainder theorem, which asserts that, if M is the product of the moduli, there is, in an interval of length M, exactly one integer having any given set of modular values. The arithmetic of a residue numeral system is also called multi-modular arithmetic.

Redundant binary representation

Redundant binary representation

A redundant binary representation (RBR) is a numeral system that uses more bits than needed to represent a single binary digit so that most numbers have several representations. An RBR is unlike usual binary numeral systems, including two's complement, which use a single bit for each digit. Many of an RBR's properties differ from those of regular binary representation systems. Most importantly, an RBR allows addition without using a typical carry. When compared to non-redundant representation, an RBR makes bitwise logical operation slower, but arithmetic operations are faster when a greater bit width is used. Usually, each digit has its own sign that is not necessarily the same as the sign of the number represented. When digits have signs, that RBR is also a signed-digit representation.

Automatic test pattern generation

Automatic test pattern generation

ATPG is an electronic design automation method/technology used to find an input sequence that, when applied to a digital circuit, enables automatic test equipment to distinguish between the correct circuit behavior and the faulty circuit behavior caused by defects. The generated patterns are used to test semiconductor devices after manufacture, or to assist with determining the cause of failure. The effectiveness of ATPG is measured by the number of modeled defects, or fault models, detectable and by the number of generated patterns. These metrics generally indicate test quality and test application time. ATPG efficiency is another important consideration that is influenced by the fault model under consideration, the type of circuit under test, the level of abstraction used to represent the circuit under test, and the required test quality.

Research venues

An IEEE International Symposium on Multiple-Valued Logic (ISMVL) has been held annually since 1970. It mostly caters to applications in digital design and verification.[17] There is also a Journal of Multiple-Valued Logic and Soft Computing.[18]

Source: "Many-valued logic", Wikipedia, Wikimedia Foundation, (2022, November 25th), https://en.wikipedia.org/wiki/Many-valued_logic.

Enjoying Wikiz?

Enjoying Wikiz?

Get our FREE extension now!

See also
Mathematical logic
Philosophical logic
Digital logic
References
  1. ^ Hurley, Patrick. A Concise Introduction to Logic, 9th edition. (2006).
  2. ^ Jules Vuillemin, Necessity or Contingency, CSLI Lecture Notes, N°56, Stanford, 1996, pp. 133-167
  3. ^ (Gottwald 2005, p. 19)
  4. ^ Humberstone, Lloyd (2011). The Connectives. Cambridge, Massachusetts: The MIT Press. pp. 201. ISBN 978-0-262-01654-4.
  5. ^ a b (Bergmann 2008, p. 80)
  6. ^ Gödel, Kurt (1932). "Zum intuitionistischen Aussagenkalkül". Anzeiger der Akademie der Wissenschaften in Wien (69): 65f.
  7. ^ Kreiser, Lothar; Gottwald, Siegfried; Stelzner, Werner (1990). Nichtklassische Logik. Eine Einführung. Berlin: Akademie-Verlag. pp. 41ff–45ff. ISBN 978-3-05-000274-3.
  8. ^ Hajek, Petr: Fuzzy Logic. In: Edward N. Zalta: The Stanford Encyclopedia of Philosophy, Spring 2009. ([1])
  9. ^ Rose, Alan (December 1951). "Systems of logic whose truth-values form lattices". Mathematische Annalen. 123: 152–165. doi:10.1007/BF02054946. S2CID 119735870.
  10. ^ Smith, Nicholas (2012). Logic: The Laws of Truth. Princeton University Press. p. 124.
  11. ^ a b Malinowski, Grzegorz (1993). Many-Valued Logics. Clarendon Press. pp. 26–27.
  12. ^ Church, Alonzo (1996). Introduction to Mathematical Logic. Princeton University Press. ISBN 978-0-691-02906-1.
  13. ^ Post, Emil L. (1921). "Introduction to a General Theory of Elementary Propositions". American Journal of Mathematics. 43 (3): 163–185. doi:10.2307/2370324. hdl:2027/uiuo.ark:/13960/t9j450f7q. ISSN 0002-9327. JSTOR 2370324.
  14. ^ Dubrova, Elena (2002). Multiple-Valued Logic Synthesis and Optimization, in Hassoun S. and Sasao T., editors, Logic Synthesis and Verification, Kluwer Academic Publishers, pp. 89-114
  15. ^ Meher, Pramod Kumar; Valls, Javier; Juang, Tso-Bing; Sridharan, K.; Maharatna, Koushik (August 22, 2008). "50 Years of CORDIC: Algorithms, Architectures and Applications" (PDF). IEEE Transactions on Circuits & Systems I: Regular Papers (published September 9, 2009). 56 (9): 1893–1907. doi:10.1109/TCSI.2009.2025803. S2CID 5465045. Archived (PDF) from the original on October 9, 2022. Retrieved January 3, 2016.
  16. ^ Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1994). Digital Systems Testing and Testable Design. New York: Computer Science Press. p. 183. ISBN 978-0-7803-1062-9.
  17. ^ "IEEE International Symposium on Multiple-Valued Logic (ISMVL)". www.informatik.uni-trier.de/~ley.
  18. ^ "MVLSC home". Archived from the original on March 15, 2014. Retrieved August 12, 2011.
Further reading

General

  • Augusto, Luis M. (2017). Many-valued logics: A mathematical and computational introduction. London: College Publications. 340 pages. ISBN 978-1-84890-250-3. Webpage
  • Béziau J.-Y. (1997), What is many-valued logic ? Proceedings of the 27th International Symposium on Multiple-Valued Logic, IEEE Computer Society, Los Alamitos, pp. 117–121.
  • Malinowski, Gregorz, (2001), Many-Valued Logics, in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic. Blackwell.
  • Bergmann, Merrie (2008), An introduction to many-valued and fuzzy logic: semantics, algebras, and derivation systems, Cambridge University Press, ISBN 978-0-521-88128-9
  • Cignoli, R. L. O., D'Ottaviano, I, M. L., Mundici, D., (2000). Algebraic Foundations of Many-valued Reasoning. Kluwer.
  • Malinowski, Grzegorz (1993). Many-valued logics. Clarendon Press. ISBN 978-0-19-853787-8.
  • S. Gottwald, A Treatise on Many-Valued Logics. Studies in Logic and Computation, vol. 9, Research Studies Press: Baldock, Hertfordshire, England, 2001.
  • Gottwald, Siegfried (2005). "Many-Valued Logics" (PDF). Archived from the original on March 3, 2016. {{cite journal}}: Cite journal requires |journal= (help)CS1 maint: bot: original URL status unknown (link)
  • Miller, D. Michael; Thornton, Mitchell A. (2008). Multiple valued logic: concepts and representations. Synthesis lectures on digital circuits and systems. Vol. 12. Morgan & Claypool Publishers. ISBN 978-1-59829-190-2.
  • Hájek P., (1998), Metamathematics of fuzzy logic. Kluwer. (Fuzzy logic understood as many-valued logic sui generis.)

Specific

  • Alexandre Zinoviev, Philosophical Problems of Many-Valued Logic, D. Reidel Publishing Company, 169p., 1963.
  • Prior A. 1957, Time and Modality. Oxford University Press, based on his 1956 John Locke lectures
  • Goguen J.A. 1968/69, The logic of inexact concepts, Synthese, 19, 325–373.
  • Chang C.C. and Keisler H. J. 1966. Continuous Model Theory, Princeton, Princeton University Press.
  • Gerla G. 2001, Fuzzy logic: Mathematical Tools for Approximate Reasoning, Kluwer Academic Publishers, Dordrecht.
  • Pavelka J. 1979, On fuzzy logic I: Many-valued rules of inference, Zeitschr. f. math. Logik und Grundlagen d. Math., 25, 45–52.
  • Metcalfe, George; Olivetti, Nicola; Dov M. Gabbay (2008). Proof Theory for Fuzzy Logics. Springer. ISBN 978-1-4020-9408-8. Covers proof theory of many-valued logics as well, in the tradition of Hájek.
  • Hähnle, Reiner (1993). Automated deduction in multiple-valued logics. Clarendon Press. ISBN 978-0-19-853989-6.
  • Azevedo, Francisco (2003). Constraint solving over multi-valued logics: application to digital circuits. IOS Press. ISBN 978-1-58603-304-0.
  • Bolc, Leonard; Borowik, Piotr (2003). Many-valued Logics 2: Automated reasoning and practical applications. Springer. ISBN 978-3-540-64507-8.
  • Stanković, Radomir S.; Astola, Jaakko T.; Moraga, Claudio (2012). Representation of Multiple-Valued Logic Functions. Morgan & Claypool Publishers. doi:10.2200/S00420ED1V01Y201205DCS037. ISBN 978-1-60845-942-1.
  • Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1994). Digital Systems Testing and Testable Design. New York: Computer Science Press. ISBN 978-0-7803-1062-9.
External links

The content of this page is based on the Wikipedia article written by contributors..
The text is available under the Creative Commons Attribution-ShareAlike Licence & the media files are available under their respective licenses; additional terms may apply.
By using this site, you agree to the Terms of Use & Privacy Policy.
Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization & is not affiliated to WikiZ.com.