What is First order logic: Definition and 24 Discussions

First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.
A theory about a topic is usually a first-order logic together with a specified domain of discourse (over which the quantified variables range), finitely many functions from that domain to itself, finitely many predicates defined on that domain, and a set of axioms believed to hold about them. Sometimes, "theory" is understood in a more formal sense, which is just a set of sentences in first-order logic.
The adjective "first-order" distinguishes first-order logic from higher-order logic, in which there are predicates having predicates or functions as arguments, or in which one or both of predicate quantifiers or function quantifiers are permitted. In first-order theories, predicates are often associated with sets. In interpreted higher-order theories, predicates may be interpreted as sets of sets.
There are many deductive systems for first-order logic which are both sound (i.e., all provable statements are true in all models) and complete (i.e. all statements which are true in all models are provable). Although the logical consequence relation is only semidecidable, much progress has been made in automated theorem proving in first-order logic. First-order logic also satisfies several metalogical theorems that make it amenable to analysis in proof theory, such as the Löwenheim–Skolem theorem and the compactness theorem.
First-order logic is the standard for the formalization of mathematics into axioms, and is studied in the foundations of mathematics.
Peano arithmetic and Zermelo–Fraenkel set theory are axiomatizations of number theory and set theory, respectively, into first-order logic.
No first-order theory, however, has the strength to uniquely describe a structure with an infinite domain, such as the natural numbers or the real line. Axiom systems that do fully describe these two structures (that is, categorical axiom systems) can be obtained in stronger logics such as second-order logic.
The foundations of first-order logic were developed independently by Gottlob Frege and Charles Sanders Peirce. For a history of first-order logic and how it came to dominate formal logic, see José Ferreirós (2001).

View More On Wikipedia.org
  1. V

    First Order Logic: ∀x,y a(x) ∧ a(y)

    An example we were given is as follows: {ua|u∈∑*} (where ∑* is set of all words over ∑) so we have ∀x. last(x) → a(x). I am given {awa|w∈∑*} to do, and I know that I have to express that a is the first letter and last letter in a word. Could I write it as: ∀x,y ( a(x) ∧ a(y) ∧ x<y → ∃z(x<z<y))...
  2. P

    MHB Proving First Order Logic in Machover's Text

    Trouble working through Set theory, Logic, and their Limitations by Maurice Machover. Particularly these 1. $\sigma \vDash \alpha \rightarrow \forall x\alpha$ where $x$ does not occur in a free $\alpha$ 2. $\sigma \vDash s_1 = t_1 \rightarrow ... \rightarrow s_n = t_n \rightarrow...
  3. J

    A First order logic and set theory: who comes first?

    Goldrei's Propositional and Predicate Calculus states, in page 13: "The countable union of countable sets is countable (...) This result is needed to prove our major result, the completeness theorem in Chapter 5. It depends on a principle called the axiom of choice." In other words: the most...
  4. Mr Davis 97

    Interpreting a statement in first order logic

    Homework Statement Rewrite the following statements in symbolic form: a) If ##a## and ##b## are real numbers with ##a \ne 0##, then ##ax+b=0## has a solution. b) If ##a## and ##b## are real numbers with ##a \ne 0##, then ##ax+b=0## has a unique solution. Homework EquationsThe Attempt at a...
  5. W

    A Transcription from SQL to FOL (First Order Logic)

    Hi All, When a query is made in SQL , it is transcribed into FOL in the back end , and, if the transcription is a wff , the models, if any, are returned as the answer to the query. I have an idea of how the transcription works for basic statements, but, does anyone know the actual "...
  6. radouani

    A First order logic : Predicates

    I have a small problem with the first order logic, in particular, predicate logic Let us take this sentence as an example: Each teacher has given a form to each student. From this sentence, can we have different reading? This is my try to solve such problem, I did not know if this is the...
  7. M

    Convert statements into first order logic

    Given are the following predicate symbols: Member(x) : x is a member of the bicycle club Chairman(x) : x is the chairman of the bicycle club Bicycle(x) : x is a bicycle Brand(x, y) : the brand of x is y Owns(x, y) : x is the owner of y a. Statement: every member of the bicycle club has the same...
  8. E

    I First order logic - help with translation algorithm between

    given a dictionary \Sigma = \left \{f(),g(),R(,),c_0,c_1,c_2 \right \} and a sentence \phi over \Sigma, I need to find an algorithm to translate \phi to \psi over \Sigma' where \Sigma' = \left \{Q(,,,), = \right \} (Q is a 4-place relation symbol), so that \psi is valid iff \phi is valid. I...
  9. T S Bailey

    Are formal systems of first order logic incomplete?

    Godels Incompleteness Theorem states that for any formal system with finitely recursive axioms we can construct a Godel sentence G that is unprovable within that system but is none the less true. Does this still apply to formal systems which, instead of creating Godel numbers for arithmetical...
  10. G

    Why in first order logic theories are not possible a demonstration with infinite steps?

    Why in first order logic theories are not possible a demonstration with infinite steps?
  11. U

    Convert sentences into First Order Logic

    (1) Anyone who is thin, tall and energetic will be good basketball player. (2) Some people are tall but not good basketball players. (3) Anyone who do exercise or eating healthy food will be energetic. (4) Saman is thin and tall person who do exercises. Write the above sentences in First Order...
  12. C

    Convert sentences into First Order Logic

    Hello there, I have 3 sentences. They are: 1) If someone is not in the class then that person is either ill or lazy. 2) Ill people do not go for shopping. 3) The class teacher noticed that James is not in the class but she has seen James come out of the Candy...
  13. S

    First order logic : definitions

    Hi all, Just a few question about FOL logic. What is the difference between terms and atoms, I read lot's of differents definitions, then when I think that I've understood, I find an exemple where both are used without any difference (for ordering by instance). An another question is : What...
  14. D

    Solving First-Order Logic Problem with Valuation Existence

    I have a problem I can't quite figure out: I have a first order system S, and an interpretation I of S. I have to show that a closed well formed formula B is true in I if and only if there exists a valuation in I which satisfies B. I've done one of the two implications, but I still have...
  15. K

    First order logic: definability

    Homework Statement What subsets of the real line R are definable in (R,<)? What subsets of the plane RxR are definable in (R,<)? Homework Equations A subset is definable if there is a formula in first order logic that is true only of the elements of that subset. For example, in the...
  16. A

    Solving First Order Logic w/ Huey, Dewey, Louie: Age, Color & Design

    Could anyone help me with this? Donald and Daisy Duck took their nephews, age 4, 5, and 6, on an outing. Each boy wore a tee-shirt with a different design on it and of a different color. You are also given the following information: ■ Huey is younger than the boy in the green tee-shirt. ■...
  17. Z

    Why is 2nd First Order Logic Statement of "Infinitely Many Primes" Wrong? | Help

    Homework Statement The following are two first order logic statements of the statement "There are infinitely many prime numbers" 1. http://uploadpie.com/3PZlO [Broken] 2. [PLAIN][PLAIN]http://uploadpie.com/PN5i8 [Broken] Can anyone explain why the second one is wrong? Thanks for help...
  18. T

    Correcting my first order logic translations

    Homework Statement Well the problem is: translate the following sentences in first order logic. I cannot verify whether they are correct or not. Maybe someone can point out my mistakes. 1. No barber shaves persons shaving themselves. (\neg \exists x)(Barber(x) \wedge (\forall...
  19. K

    First-Order Logic: Finite & Infinite Domains

    Let L = {f } be a first-order language containing a unary function symbol f , and no other non-logical symbols. 1.Write down a sentence χ of L which is satisfiable in some structure with an infinite domain but is false in every structure with a finite domain. What can you say about the size of...
  20. A

    Decidability of -1<1/0<1 using the ordered field axioms and first order logic

    Is the statement -1<1/0<1 decidable using the ordered field/real number axioms and first order logic? I have tried to prove that the statement is either true or false but have had no success since the axioms and theorems only make statements about objects that exist and do not give any clear way...
  21. J

    Deduction theorem for first order logic

    If I have P l- Q in FOL and P is closed, can I infer l- P -> Q. IIRC, this is valid as long as P is closed, but my memory is a little hazy. Is that how it works?
  22. J

    Understanding First Order Logic for "Two Purple Mushrooms

    hi, could someone explain to me why the sentence - There are exactly two purple mushrooms is represented in FOL like this: (Ex)(Ey) mushroom(x) ^ purple(x) ^ mushroom(y) ^ purple(y) ^ ~(x=y) ^ (Az) (mushroom(z) ^ purple(z)) => ((x=z) v (y=z)) especially the last part i have problem with...
  23. A

    First order logic: Soundness, Completeness, Decidability

    So I'm a bit confused about these metatheorems about first order logic, partly because I haven't read any of the real proofs, but I just want to know the results for right now. Here is what I understand: Soundness means that any derivation from the axioms and inference rules is still valid...
  24. quantumdude

    Propositional and First Order Logic

    Is total formalization possible? If not, why not? The following is a first course in formal mathematical logic. http://www.trentu.ca/academic/math/sb/pcml/pcml-i-15.pdf Looking through the book, I do not see any that the author presupposes any mathematical knowledge. Volume II...