Editing Logic in computer science

{{short description|Academic discipline}}
{{for|the [[academic conference]] LICS|Symposium on Logic in Computer Science}}
[[File:Logic Gates.svg|thumbnail|right|Diagrammatic representation of computer [[logic gates]]]]
'''Logic in computer science''' covers the overlap between the field of [[logic]] and that of [[computer science]]. The topic can essentially be divided into three main areas:
* Theoretical foundations and analysis
* Use of computer technology to aid logicians
* Use of concepts from logic for computer applications

== Theoretical foundations and analysis ==
Logic plays a fundamental role in computer science.  Some of the key areas of logic that are particularly significant are [[computability theory]] (formerly called recursion theory), [[modal logic]] and [[category theory]]. The [[theory of computation]] is based on concepts defined by logicians and mathematicians such as [[Alonzo Church]] and [[Alan Turing]].<ref>{{cite book|last=Lewis|first=Harry R.|url=https://archive.org/details/elementsoftheory00lewi|title=Elements of the Theory of Computation|publisher=[[Prentice Hall]]|year=1981|author-link=Harry R. Lewis}}</ref><ref>{{cite book|last=Davis|first=Martin|title=The Universal Turing Machine|publisher=Springer Verlag|chapter-url=https://books.google.com/books?id=YafIDVd1Z68C&pg=PA290|editor=Rolf Herken|access-date=26 December 2013|chapter=Influences of Mathematical Logic on Computer Science|date=11 May 1995|isbn=9783211826379|author-link=Martin Davis (mathematician)}}</ref>  Church first showed the existence of [[Undecidable problem|algorithmically unsolvable problem]]s using his notion of lambda-definability.  Turing gave the first compelling analysis of what can be called a mechanical procedure and [[Kurt Gödel]] asserted that he found Turing's analysis "perfect.".<ref>{{cite book|last=Kennedy|first=Juliette|authorlink = Juliette Kennedy|title=Interpreting Godel|publisher=Cambridge University Press|url=https://books.google.com/books?id=ulw3BAAAQBAJ&q=Godel+convinced+by+Turing%27s+analysis&pg=PA118|access-date= 17 August 2015|isbn=9781107002661|date=2014-08-21}}</ref> In addition some other major areas of theoretical overlap between logic and computer science are:
*[[Gödel's incompleteness theorem]] proves that any logical system powerful enough to characterize [[Peano axioms#Peano arithmetic as first-order theory|arithmetic]] will contain statements that can neither be proved nor disproved within that system.  This has direct application to theoretical issues relating to the feasibility of proving the [[formal verification|completeness and correctness]] of software.<ref>{{cite book|last=Hofstadter|first=Douglas R.|title=Gödel, Escher, Bach: An Eternal Golden Braid|publisher=Basic Books|isbn=978-0465026562|author-link=Douglas Hofstadter|url=https://archive.org/details/gdelescherbachet00hofs|date=1999-02-05}}</ref>  
*The [[frame problem]] is a basic problem that must be overcome when using [[first-order logic]] to represent the goals of an [[artificial intelligence]] agent and the state of its environment.<ref>{{cite journal|last=McCarthy|first=John|author2=P.J. Hayes |title=Some philosophical problems from the standpoint of artificial intelligence|journal=Machine Intelligence|year=1969|volume=4|pages=463–502|author-link1=John McCarthy (computer scientist)|url=http://www-formal.stanford.edu/jmc/mcchay69.pdf}}</ref> 
<!-- *[[Category theory]] is the formal analysis and transformation of [[Graph theory|directed graphs]], an area with some applications in computer science, most notably programming languages and compilers.<ref>{{cite journal|last=DeLoach|first=Scott|author2=Thomas Hartrum |title=A Theory Based Representation for Object-Oriented Domain Models|journal=IEEE Transactions on Software Engineering|date=June 2000|volume=25|issue=6|doi=10.1109/32.852740|pages=500–517}}</ref> -->
*The [[Curry–Howard correspondence]] is a relation between logical systems and programming languages. This theory established a precise correspondence between [[formal proof|proof]]s and programs.  In particular it showed that terms in the [[simply typed lambda calculus]] correspond to proofs of [[intuitionistic logic|intuitionistic propositional logic]].
*[[Category theory]] represents a view of mathematics that emphasizes the relations between structures.  It is intimately tied to many aspects of computer science: [[type system]]s for programming languages, the theory of [[transition system]]s, models of programming languages and the theory of [[programming language semantics]].<ref>{{cite book|first=Michael|last=Barr|title=Category Theory for Computing Science|year=1998|author2=Charles Wells|url=https://www.math.mcgill.ca/barr/papers/ctcs.pdf|publisher=[[Centre de Recherches Mathématiques]]}}</ref>
*[[Logic programming]] is a [[programming paradigm|programming]], [[database]] and [[knowledge representation]] paradigm that is based on formal [[logic]]. A logic program is a set of sentences about some problem domain. Computation is performed by applying logical reasoning to solve problems in the domain.  Major logic programming language families include [[Prolog]], [[answer set programming|Answer Set Programming]] (ASP) and [[Datalog]].

== Computers to assist logicians ==
One of the first applications to use the term [[artificial intelligence]] was the [[Logic Theorist]] system developed by [[Allen Newell]], [[Cliff Shaw]], and [[Herbert A. Simon|Herbert Simon]] in 1956. One of the things that a logician does is to take a set of statements in logic and deduce the conclusions (additional statements) that must be true by the laws of logic. For example, if given the statements "All humans are mortal" and "Socrates is human" a valid conclusion is "Socrates is mortal".  Of course this is a trivial example. In actual logical systems the statements can be numerous and complex. It was realized early on that this kind of analysis could be significantly aided by the use of computers. [[Logic Theorist]] validated the theoretical work of [[Bertrand Russell]] and [[Alfred North Whitehead]] in their influential work on mathematical logic called ''[[Principia Mathematica]]''. In addition, subsequent systems have been utilized by logicians to validate and discover new mathematical theorems and proofs.<ref>{{cite book|last=Newell|first=Allen|title=Computers and Thought|chapter-url=https://archive.org/details/computersthought00feig|chapter-url-access=registration|year=1963|publisher=McGraw Hill|isbn=978-0262560924|pages=[https://archive.org/details/computersthought00feig/page/109 109–133] |author2=J.C. Shaw |author3=H.C. Simon|editor=Ed Feigenbaum|chapter=Empirical explorations with the logic theory machine}}</ref>

== Logic applications for computers ==
There has always been a strong influence from mathematical logic on the field of [[artificial intelligence]] (AI). From the beginning of the field it was realized that technology to automate logical inferences could have great potential to solve problems and draw conclusions from facts. [[Ronald J. Brachman|Ron Brachman]] has described [[first-order logic]] (FOL) as the metric by which all AI [[knowledge representation]] formalisms should be evaluated. First-order logic is a general and powerful method for describing and analyzing information. The reason FOL itself is simply not used as a computer language is that it is actually too [[expressive power (computer science)|expressive]], in the sense that FOL can easily express statements that no computer, no matter how powerful, could ever solve. For this reason every form of knowledge representation is in some sense a trade off between expressivity and [[computability]]. A widely held belief maintains that the more expressive the language is, the closer it is to FOL, the more likely it is to be slower and prone to an infinite loop.<ref>{{cite book|last=Levesque|first=Hector|title=Reading in Knowledge Representation|year=1985|publisher=Morgan Kaufmann|isbn=0-934613-01-X|page=[https://archive.org/details/readingsinknowle00brac/page/49 49]|author2=Ronald Brachman|editor=Ronald Brachman and Hector J. Levesque|chapter=A Fundamental Tradeoff in Knowledge Representation and Reasoning|quote=The good news in reducing KR service to theorem proving is that we now have a very clear, very specific notion of what the KR system should do; the bad new is that it is also clear that the services can not be provided... deciding whether or not a sentence in FOL is a theorem... is unsolvable.|chapter-url=https://archive.org/details/readingsinknowle00brac|url=https://archive.org/details/readingsinknowle00brac/page/49}}</ref> However, in a recent work<ref name=":0">{{Cite journal |last=Zhang |first=Heng |last2=Jiang |first2=Guifei |last3=Quan |first3=Donghui |date=2025-04-11 |title=A Theory of Formalisms for Representing Knowledge |url=https://ojs.aaai.org/index.php/AAAI/article/view/33674 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |language=en |volume=39 |issue=14 |pages=15257–15264 |doi=10.1609/aaai.v39i14.33674 |issn=2374-3468|arxiv=2412.11855 }}</ref> by Heng Zhang et al., this belief has been rigorously challenged. Their findings establish that all universal knowledge representation formalisms are recursively isomorphic. Furthermore, their proof demonstrates that FOL can be translated into a pure procedural knowledge representation formalism defined by Turing machines with computationally feasible overhead, specifically within deterministic polynomial time or even at lower complexity.<ref name=":0" />

For example, IF–THEN rules used in [[expert system]]s approximate to a very limited subset of FOL. Rather than arbitrary formulas with the full range of logical operators the starting point is simply what logicians refer to as [[modus ponens]]. As a result, [[rule-based system]]s can support high-performance computation, especially if they take advantage of optimization algorithms and compilation.<ref>{{cite journal|last=Forgy|first=Charles|authorlink  = Charles Forgy|title=Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem*|journal=[[Artificial Intelligence (journal)|Artificial Intelligence]]|year=1982|volume=19|pages=17–37|url=http://web.yonsei.ac.kr/yusong/lecture/data/BI/Materials/1.1.Rete%20-%20A%20Fast%20Algorithm%20for%20the%20Many%20Pattern,%20Many%20Object%20Pattern%20Match%20Problem.pdf|access-date=25 December 2013|doi=10.1016/0004-3702(82)90020-0|archive-url=https://web.archive.org/web/20131227044049/http://web.yonsei.ac.kr/yusong/lecture/data/BI/Materials/1.1.Rete%20-%20A%20Fast%20Algorithm%20for%20the%20Many%20Pattern,%20Many%20Object%20Pattern%20Match%20Problem.pdf|archive-date=2013-12-27|url-status=dead}}</ref>

On the other hand, [[logic programming]], which combines the [[Horn clause]] subset of first-order logic with a [[non-monotonic logic|non-monotonic]] form of [[negation as failure|negation]], has both high expressive power and  efficient [[Implementation#Computer science|implementation]]s. In particular, the logic programming language [[Prolog]] is a  [[Turing completeness|Turing complete]] programming language. [[Datalog]] extends the [[relational database]] model with recursive relations, while [[answer set programming]] is a form of logic programming oriented towards difficult (primarily [[NP-hard]]) [[search problem]]s.

Another major area of research for logical theory is [[software engineering]]. Research projects such as the [[Knowledge Based Software Assistant]] and Programmer's Apprentice programs have applied logical theory to validate the correctness of [[software specification]]s. They have also used logical tools to transform the specifications into efficient code on diverse platforms and to prove the equivalence between the implementation and the specification.<ref>{{cite journal|last=Rich|first=Charles|author2=Richard C. Waters |title=The Programmer's Apprentice Project: A Research Overview|journal=IEEE Expert |date=November 1987|url=ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1004.pdf|archive-url=https://web.archive.org/web/20170706115702/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1004.pdf|archive-date=2017-07-06|url-status=dead|access-date=26 December 2013}}</ref>  This formal transformation-driven approach is often far more effortful than traditional software development. However, in specific domains with appropriate formalisms and reusable templates the approach has proven viable for commercial products. The appropriate domains are usually those such as weapons systems, security systems, and real-time financial systems where failure of the system has excessively high human or financial cost. An example of such a domain is [[Very Large Scale Integration|Very Large Scale Integrated (VLSI)]] design—the process for designing the chips used for the CPUs and other critical components of digital devices. An error in a chip can be catastrophic. Unlike software, chips can't be patched or updated. As a result, there is commercial justification for using [[formal methods]] to prove that the implementation corresponds to the specification.<ref>{{cite book|last=Stavridou|first=Victoria|title=Formal Methods in Circuit Design|year=1993|publisher=Press Syndicate of the University of Cambridge|isbn=0-521-443369|url=https://books.google.com/books?id=Hf_AZfW2YWsC&q=VLSI+chip+design+formal+methods&pg=PA14|access-date=26 December 2013}}</ref>

Another important application of logic to computer technology has been in the area of [[frame language]]s and automatic classifiers. [[Frame language]]s such as [[KL-ONE]]  can be directly mapped to [[set theory]] and first-order logic. This allows specialized [[Theorem-prover|theorem prover]]s called classifiers to analyze the various declarations between [[set (mathematics)|set]]s, [[subset]]s, and [[relation (mathematics)|relation]]s in a given model. In this way the model can be validated and any inconsistent definitions flagged. The classifier can also infer new information, for example define new sets based on existing information and change the definition of existing sets based on new data. The level of flexibility is ideal for handling the ever changing world of the Internet. Classifier technology is built on top of languages such as the [[Web Ontology Language]] to allow a logical semantic level on top of the existing Internet. This layer is called the [[Semantic Web]].<ref>{{cite journal|last=MacGregor|first=Robert|title=Using a description classifier to enhance knowledge representation|journal=IEEE Expert|date=June 1991|volume=6|issue=3|doi=10.1109/64.87683|pages=41–46|s2cid=29575443}}</ref><ref>{{cite journal|last=Berners-Lee |first=Tim |author2=James Hendler |author3=Ora Lassila |title=The Semantic Web A new form of Web content that is meaningful to computers will unleash a revolution of new possibilities |journal=[[Scientific American]] |date=May 17, 2001 |url=http://www.cs.umd.edu/~golbeck/LBSC690/SemanticWeb.html |author-link=Tim Berners-Lee |doi=10.1038/scientificamerican0501-34 |volume=284 |pages=34–43 |url-status=dead |archive-url=https://web.archive.org/web/20130424071228/http://www.cs.umd.edu/~golbeck/LBSC690/SemanticWeb.html |archive-date=April 24, 2013 |url-access=subscription }}</ref>

[[Temporal logic]] is used for reasoning in [[concurrency (computing)|concurrent systems]].<ref>{{cite conference | author = Colin Stirling | year = 1992 | title = Modal and Temporal Logics |pages=477–563| 
book-title = Handbook of Logic in Computer Science |editor1=S. Abramsky |editor-link1 = Samson Abramsky|editor2=D. M. Gabbay |editor-link2 = Dov Gabbay|editor3=T. S. E. Maibaum |editor-link3 = Tom Maibaum| volume = II| publisher = Oxford University Press | isbn = 0-19-853761-1 }}</ref>

== See also ==
* [[Automated reasoning]]
* [[Computational logic]]
* [[Logic programming]]

== References ==
{{reflist}}

== Further reading ==
* {{cite book|url=https://www.weizmann.ac.il/sci-tea/benari/research-activities/mathematical-logic-computer-science-third-edition|title=Mathematical Logic for Computer Science|first1=Mordechai|last1=Ben-Ari|authorlink =Mordechai Ben-Ari |publisher=Springer-Verlag|edition=3rd|year=2012|isbn=978-1447141280}}
* {{cite book|url=https://www.cl.cam.ac.uk/~jrh13/atp/|title=Handbook of Practical Logic and Automated Reasoning|first1=John|last1=Harrison|publisher=Cambridge University Press|edition=1st|year=2009|isbn=978-0521899574}}
* {{cite book|url=http://www.cs.bham.ac.uk/research/lics/|title=Logic in Computer Science: Modelling and Reasoning about Systems|first1=Michael|last1=Huth|first2=Mark|last2=Ryan|publisher=Cambridge University Press|edition=2nd|year=2004|isbn=978-0521543101}}
* {{cite book|url=https://www.math.uwaterloo.ca/~snburris/htdocs/lmcs.html|title=Logic for Mathematics and Computer Science|first1=Stanley N.|last1=Burris|publisher=Prentice Hall|edition=1st|year=1997|isbn=978-0132859745}}

==External links==
*[http://plato.stanford.edu/entries/logic-ai/ Article on ''Logic and Artificial Intelligence''] at the ''[[Stanford Encyclopedia of Philosophy]]''.
*[https://web.archive.org/web/20051025052601/http://www.informatik.hu-berlin.de/lics/ IEEE Symposium on Logic in Computer Science] (LICS)
*Alwen Tiu, [http://videolectures.net/ssll09_tiu_intlo/ Introduction to logic] video recording of a lecture at ANU Logic Summer School '09 (aimed mostly at computer scientists)

{{logic}}
{{Digital electronics}}

[[Category:Logic in computer science| ]]
[[Category:Formal methods]]