Editing Artificial intelligence (section)

=== Logic ===
Formal [[logic]] is used for [[automatic reasoning|reasoning]] and [[knowledge representation]].<ref>[[Logic]]: {{Harvtxt|Russell|Norvig|2021|loc=chpts. 6–9}}, {{Harvtxt|Luger|Stubblefield|2004|pp=35–77}}, {{Harvtxt|Nilsson|1998|loc=chpt. 13–16}}</ref>
Formal logic comes in two main forms: [[propositional logic]] (which operates on statements that are true or false and uses [[logical connective]]s such as "and", "or", "not" and "implies")<ref>[[Propositional logic]]: {{Harvtxt|Russell|Norvig|2021|loc=chpt. 6}}, {{Harvtxt|Luger|Stubblefield|2004|pp=45–50}}, {{Harvtxt|Nilsson|1998|loc=chpt. 13}}</ref> and [[predicate logic]] (which also operates on objects, predicates and relations and uses [[Quantifier (logic)|quantifier]]s such as "''Every'' ''X'' is a ''Y''" and "There are ''some'' ''X''s that are ''Y''s").<ref>[[First-order logic]] and features such as [[Equality (mathematics)|equality]]: {{Harvtxt|Russell|Norvig|2021|loc=chpt. 7}}, {{Harvtxt|Poole|Mackworth|Goebel|1998|pp=268–275}}, {{Harvtxt|Luger|Stubblefield|2004|pp=50–62}}, {{Harvtxt|Nilsson|1998|loc=chpt. 15}}</ref>

[[Deductive reasoning]] in logic is the process of [[logical proof|proving]] a new statement ([[Logical consequence|conclusion]]) from other statements that are given and assumed to be true (the [[premise]]s).<ref>[[Logical inference]]: {{Harvtxt|Russell|Norvig|2021|loc=chpt. 10}}</ref> Proofs can be structured as proof [[tree structure|trees]], in which nodes are labelled by sentences, and children nodes are connected to parent nodes by [[inference rule]]s.

Given a problem and a set of premises, problem-solving reduces to searching for a proof tree whose root node is labelled by a solution of the problem and whose [[leaf nodes]] are labelled by premises or [[axiom]]s. In the case of [[Horn clause]]s, problem-solving search can be performed by reasoning [[Forward chaining|forwards]] from the premises or [[backward chaining|backwards]] from the problem.<ref>logical deduction as search: {{Harvtxt|Russell|Norvig|2021|loc=sects. 9.3, 9.4}}, {{Harvtxt|Poole|Mackworth|Goebel|1998|pp=~46–52}}, {{Harvtxt|Luger|Stubblefield|2004|pp=62–73}}, {{Harvtxt|Nilsson|1998|loc=chpt. 4.2, 7.2}}</ref> In the more general case of the clausal form of [[first-order logic]], [[resolution (logic)|resolution]] is a single, axiom-free rule of inference, in which a problem is solved by proving a contradiction from premises that include the negation of the problem to be solved.<ref>[[Resolution (logic)|Resolution]] and [[unification (computer science)|unification]]: {{Harvtxt|Russell|Norvig|2021|loc= sections 7.5.2, 9.2, 9.5}}</ref>

Inference in both Horn clause logic and first-order logic is [[Undecidable problem|undecidable]], and therefore [[Intractable problem|intractable]]. However, backward reasoning with Horn clauses, which underpins computation in the [[logic programming]] language [[Prolog]], is [[Turing complete]]. Moreover, its efficiency is competitive with computation in other [[symbolic programming]] languages.<ref>{{Cite journal |last1=Warren |first1=D.H. |last2=Pereira |first2=L.M. |last3=Pereira |first3=F. |date=1977 |title=Prolog-the language and its implementation compared with Lisp |journal=[[ACM SIGPLAN Notices]] |volume=12 |issue=8 |pages=109–115 |doi=10.1145/872734.806939}}</ref>

[[Fuzzy logic]] assigns a "degree of truth" between 0 and 1. It can therefore handle propositions that are vague and partially true.<ref>Fuzzy logic: {{Harvtxt|Russell|Norvig|2021|pp=214, 255, 459}}, {{Harvtxt|Scientific American|1999}}</ref>

[[Non-monotonic logic]]s, including logic programming with [[negation as failure]], are designed to handle [[default reasoning]].<ref name="Default reasoning"/> Other specialized versions of logic have been developed to describe many complex domains.