first-order logic
In plain wordsA precise formal language for statements about objects and their relations, using 'for all' and 'there exists', such as 'every person has a mother'. It is the standard logic of mathematics and of classic AI.
A formal logic whose sentences are built from constants, variables, function symbols and predicate symbols, combined with Boolean connectives (not, and, or, implies) and the quantifiers ∀ ('for all') and ∃ ('there exists'), where quantifiers range only over individuals, not over predicates or sets (which would make the logic second-order). A structure, or model, interprets the symbols over a domain of objects; a sentence is valid if it is true in every model. First-order logic is complete — every valid sentence has a finite proof (Gödel, 1929) — but only semi-decidable: no algorithm decides validity for all sentences (Church and Turing, 1936), although proof procedures such as resolutionresolution, n.: A mechanical step of logical reasoning: from 'A or B' and 'not A or C', conclude 'B or C'. Repeating it can demonstrate any conclusion that genuinely follows from what is known. find a proof whenever one exists. It underlies automated theorem provingautomated theorem proving, n.: Getting computers to prove mathematical or logical statements by themselves, by searching for a chain of valid steps that leads from basic assumptions to the statement., logic programminglogic programming, n.: A style of programming in which you write down facts and rules in logic and then ask questions; the computer works out the answers itself by logical deduction. and much of knowledge representationknowledge representation, n.: The study of how to record knowledge about objects, categories, rules and events in a precise format, so that a program can reason with it and reach conclusions nobody typed in., whose decidable fragments include description logicsdescription logic, n.: A family of precise logical languages for defining categories and how they relate, such as 'a parent is a person with at least one child', designed so that a computer's reasoning about them always finishes..
We encoded the access policy in first-order logic and asked the prover whether any user could reach the payroll table.
Origin
Gottlob Frege's Begriffsschrift (1879) introduced quantified logic, and Charles Sanders Peirce developed quantifiers independently in the 1880s. David Hilbert separated out the first-order fragment in lectures of 1917–18, and his 1928 textbook with Wilhelm Ackermann made it standard; Kurt Gödel proved its completeness in 1929. John McCarthy proposed it as AI's representation language in 1958–1959.
Usage note
Expressiveness has costs: first-order logic cannot pin down finiteness or the natural numbers up to isomorphism, which requires higher-order logic, but richer logics lose completeness. Most proof assistantsinteractive theorem proving, n.: Writing a proof in a precise computer language so that software checks every step: the person supplies the ideas, the computer fills in small steps and guarantees that nothing is wrong. therefore use higher-order logic or type theory, while automated proversautomated theorem proving, n.: Getting computers to prove mathematical or logical statements by themselves, by searching for a chain of valid steps that leads from basic assumptions to the statement. mostly stay first-order.
Related
- propositional logicpropositional logic, n.: The simplest formal logic: whole statements that are either true or false, joined by 'and', 'or', 'not' and 'if… then', with exact rules for working out whether the combination is true.
- automated theorem provingautomated theorem proving, n.: Getting computers to prove mathematical or logical statements by themselves, by searching for a chain of valid steps that leads from basic assumptions to the statement.
- resolutionresolution, n.: A mechanical step of logical reasoning: from 'A or B' and 'not A or C', conclude 'B or C'. Repeating it can demonstrate any conclusion that genuinely follows from what is known.
- unificationunification, n.: Finding values for the blanks in two logical patterns so that they become identical, for example matching 'parent(X, bob)' with 'parent(alice, Y)' by setting X to alice and Y to bob.
- description logicdescription logic, n.: A family of precise logical languages for defining categories and how they relate, such as 'a parent is a person with at least one child', designed so that a computer's reasoning about them always finishes.
- knowledge representationknowledge representation, n.: The study of how to record knowledge about objects, categories, rules and events in a precise format, so that a program can reason with it and reach conclusions nobody typed in.
- logic programminglogic programming, n.: A style of programming in which you write down facts and rules in logic and then ask questions; the computer works out the answers itself by logical deduction.
- propositional logicpropositional logic, n.: The simplest formal logic: whole statements that are either true or false, joined by 'and', 'or', 'not' and 'if… then', with exact rules for working out whether the combination is true.
Sources
- Hilbert, D. & Ackermann, W. (1928). Grundzüge der theoretischen Logik. Springer.
- Gödel, K. (1930). Die Vollständigkeit der Axiome des logischen Funktionenkalküls. Monatshefte für Mathematik und Physik 37.
Mentioned in
modelmodel, n.: A simplified working version of something. In AI it usually means the trained program, a big set of learned numbers, that takes an input and produces an answer, prediction or piece of content., automated theorem provingautomated theorem proving, n.: Getting computers to prove mathematical or logical statements by themselves, by searching for a chain of valid steps that leads from basic assumptions to the statement., deductive reasoningdeductive reasoning, n.: Reasoning in which true starting points guarantee a true conclusion: if every square is a rectangle and this shape is a square, then it must be a rectangle., interactive theorem provinginteractive theorem proving, n.: Writing a proof in a precise computer language so that software checks every step: the person supplies the ideas, the computer fills in small steps and guarantees that nothing is wrong., knowledge representationknowledge representation, n.: The study of how to record knowledge about objects, categories, rules and events in a precise format, so that a program can reason with it and reach conclusions nobody typed in., propositional logicpropositional logic, n.: The simplest formal logic: whole statements that are either true or false, joined by 'and', 'or', 'not' and 'if… then', with exact rules for working out whether the combination is true., closed-world assumptionclosed-world assumption, n.: The rule of treating whatever a system cannot confirm as false: if a library's catalog does not list a book, the library is assumed not to have it., description logicdescription logic, n.: A family of precise logical languages for defining categories and how they relate, such as 'a parent is a person with at least one child', designed so that a computer's reasoning about them always finishes., Douglas LenatDouglas Lenat, prop. n.: An American computer scientist who spent four decades building Cyc, a giant hand-written database of everyday common sense meant to let computers reason like people., Markov logic networkMarkov logic network, n.: A way of combining logical rules with probabilities, so that a rule like 'friends usually like the same music' can sometimes be broken, with each rule given a weight saying how strongly it holds., resolutionresolution, n.: A mechanical step of logical reasoning: from 'A or B' and 'not A or C', conclude 'B or C'. Repeating it can demonstrate any conclusion that genuinely follows from what is known., satisfiability modulo theoriessatisfiability modulo theories, n.: An extension of logic-puzzle solving that also understands arithmetic, arrays and other data types, so it can check whether conditions in software, such as 'x + y > 10 and x < 3', can ever be met., semantic parsingsemantic parsing, n.: Translating a sentence into a precise, machine-executable form — such as a database query or a logical formula — so that a computer can act on what was asked., situation calculussituation calculus, n.: A logical language for describing how the world changes as actions happen, so that a program can work out what will be true after any sequence of actions., temporal logictemporal logic, n.: A logic for statements about time — 'eventually the light turns green', 'the door is never open while the train moves' — used to specify and check how systems must behave over time., unificationunification, n.: Finding values for the blanks in two logical patterns so that they become identical, for example matching 'parent(X, bob)' with 'parent(alice, Y)' by setting X to alice and Y to bob.