Editing Many-valued logic (section)

== 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]].<ref>{{cite book|last1=Smith|first1=Nicholas|title=Logic: The Laws of Truth|date=2012|publisher=Princeton University Press|page=124}}</ref> An adequate algebra is one in which every finite mapping of variables can be expressed by some composition of its operations.<ref name=":02">{{cite book|last1=Malinowski|first1=Grzegorz|title=Many-Valued Logics|date=1993|publisher=Clarendon Press|pages=26–27}}</ref>

Classical logic: CL = ({0,1}, '''¬''', →, ∨, ∧, ↔) is functionally complete, whereas no [[Łukasiewicz logic]] or infinitely many-valued logics has this property.<ref name=":02" /><ref>{{Cite book|last=Church|first=Alonzo|url=https://books.google.com/books?id=JDLQOMKbdScC&pg=PA162|title=Introduction to Mathematical Logic|date=1996|publisher=Princeton University Press|isbn=978-0-691-02906-1|language=en}}</ref>

We can define a finitely many-valued logic as being L''<sub>n</sub>'' ({1, 2, ..., ''n''} ƒ<sub>1</sub>, ..., ƒ''<sub>m</sub>'') where ''n'' ≥ 2 is a given natural number. [[Emil Leon Post|Post]] (1921) proves that assuming a logic is able to produce a function of any ''m''<sup>th</sup> order model, there is some corresponding combination of connectives in an adequate logic  L''<sub>n</sub>''  that can produce a model of order ''m+1''.<ref>{{Cite journal|last=Post|first=Emil L.|date=1921|title=Introduction to a General Theory of Elementary Propositions|journal=American Journal of Mathematics|volume=43|issue=3|pages=163–185|doi=10.2307/2370324|jstor=2370324|hdl=2027/uiuo.ark:/13960/t9j450f7q|issn=0002-9327|hdl-access=free}}</ref>