What is Predicate logic: Definition and 46 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. shivajikobardan

    Comp Sci How to learn resolution in predicate logic?

    This is not really a homework question so don't bother answering them. It is more of a guidance problem. This is what I find the hardest out of all topics.. Unfortunately, this topic is a fixed 10 marks question in our 80 marks exam. Comes every time. The types of questions that I need to deal...
  2. shivajikobardan

    MHB How to learn resolution in predicate logic?

    This is not really a homework question so don't bother answering them. It is more of a guidance problem. This is what I find the hardest out of all topics.. Unfortunately, this topic is a fixed 10 marks question in our 80 marks exam. Comes every time. The types of questions that I need to deal...
  3. shivajikobardan

    Comp Sci Mistake while removing implications in first order predicate logic-:

    As you can see I am not getting correct result. What have I messed up? I want to learn it. https://slideplayer.com/slide/4942120/ Here is full slide in case anyone wants to refer to it.
  4. C

    Changing the Statement Combinatorial proofs & Contraposition

    I have a question regarding to combinatorial proofs and predicate logic. It seems to me that in some combinatorial proofs there is a use of contraposition ( although not explicitly stated in the books where I've read so far ), for example If we to prove that ## C(n,k) = C(n,n-k) ##...
  5. J

    MHB Predicate Logic: Semantics and Validity

    Hello, Given the domain as: D = {a,b}; ~Ba & Bb & Laa & ~Lab & Lba & ~Lbb Why is the interpretation false? (∀x)[Bx ⊃ (Lxx ⊃ Lxa)] I am having trouble understanding why that is the case because (Lxx ⊃ Lxa) evaluates to true in any case as long as Lxa is true in all cases, so the overall...
  6. Q

    I Predicate logic and modal logic

    I have a question about predicate logic and modal logic. Namely, do any of them overlap with one another? To give an example, does existential quantification apply to counterfactual statements? A counterfactual statement can be something like "A possible world where I won the lottery." I...
  7. B

    MHB Predicate logic with multiple quantifiers

    Hello everyone. This is my first post on this forum. Thank you for taking the time to help me with my question. I have no idea where to start. :( Question 1: Find an example of a predicate P(x,y) where the domain of x and y are D such that $\forall x \in D, \exists y \in D, P(x,y)$ is true but...
  8. 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...
  9. T

    MHB How to Translate 'There Exists Exactly One Happy Person' into Predicate Logic?

    How to translate "there exists exactly one happy person" into predicate logic? I came up with $$ \exists x : happy(x) \implies \forall y: happy(y) \land y = x$$. But this is incorrect. I also tried $$\exists x: happy(x) \land \forall y: happy(y) \land x = y$$. This is also incorrect. The...
  10. UsableThought

    Help with algebraic deduction steps in a proof by induction

    I'm in the 6th week of a well-known MOOC course created by Kevin Devlin, "Introduction to Mathematical Thinking." I enjoy the course & did well in the first weeks with conditionals and truth tables, etc.; however now that we are entering into proofs, I'm running into trouble with algebra...
  11. T

    I Problems with Existential Instantiation

    Why is it required to use a "fresh name/variable"? And because of that requirement, Existential instantiation always precedes universal instantiation. What I am thinking is, If we are picking elements at random from our universe of discourse then why can't universal instantiation pick that...
  12. M

    MHB Can Predicate Logic Capture Complex Human Reasoning?

    Hey! :o I want to formulate the following statements into formulas of predicate logic. If a bird cannot fly, then not all birds can fly. What Donald cannot do, can no one do. John likes everyone, that is older than $22$ years old and that doesn't like those who are younger than $22$...
  13. P

    How to Prove (∀x)(A→B) ≡ ((∃x)A) → B Using First-Order Logic

    Hello, I am having particular trouble with the below problem. We are using http://studygig.com/uploads/materials/math1090_mathematical_logi.pdf and we must prove this statement using Hilbert style or Equational style proof (first-order logic), but any proof of any type would point me in the...
  14. agent1594

    Symbolize propositions using predicate logic

    Homework Statement Suppose that predicates and individuals are dened as follows: S: should be shunned, U: is prone to unruly behaviour, P: is a friend of Peter's, M: is a friend of mine, a: Ann, d: David. Symbolize the following: i. Ann is a friend of Peter's and David is a friend of mine...
  15. N

    Translating sentence into symbols

    I'm having trouble with translating this english sentence into logic symbols. The sentence is The numbers four and five aren't both prime, but the numbers five and seven are. I was thinking ~(F&I)v(IvS) but I really don't know how to deal with the "but". Thanks
  16. S

    Predicate logic - true or false formulae

    Hello everyone, I can't seem to understand how to do this question. Determine whether the formula F: ∃x∀y(P(x) → x = y) is true or false under each of the following interpretations over the domain D = {a, b}. (i) both P(a) and P(b) are true; (ii) both P(a) and P(b) are false; (iii) P(a) is...
  17. Mathelogician

    MHB Question on substitution of variables in natural deduction of predicate logic.

    Hi all, I need Explanation on the attached image from Van Dalen's Logic and Structure; specially on how the red part follows from the lines before it! Regards.
  18. Mathelogician

    MHB Universal Quantifier Intro: Natural Deduction in Predicate Logic

    In Natural deduction in Predicate logic we have a rule which says [assume the set of hypotheses to be H) if H implies phi(x) then H implies [for all x phi(x)] such that x doesn't belong to FV(psi) for all psi in H [indeed such that x occurs free in no one of formulas in H] In other words, if...
  19. Mathelogician

    MHB A question on "Change of bound variables" Theorem (predicate logic)

    Hi all; I need some clarification in red part; in how it is deduced from the theorem 2.5.6! I know how the blue is deduced from the theorem but don't even know how to get blue form red in practice!(No algorithm is suggested...) Anyway, any explanation is thanked... Regards.
  20. Mathelogician

    MHB A question on substitution in predicate logic

    Hi everybody! I am confused about what is the role of the condition " xdoesn't belong to FV(phi)" in theorems like (i),(ii) or similarly in (iii) and (iv) . I know that the philosophy of the condition "the variable z's being free for x in phi" is to avoid the phenomenon that a free variable turn...
  21. B

    Predicate logic to prove equality of two formulas

    Hi All, I'm trying to write a program that will prove that a certain mathematical formula that is entered by a student is the same as the goal formula that I want. For example, if the goal formula is: 2 * X + Y then any of this student's answer can be considered correct: -> X + X + Y...
  22. N

    Difficult Predicate Logic Symbolization

    Homework Statement I do not know if this is the right forum or subforum for this kind of topic. So if it is not, I apologize in advance.Symbolize the following sentence: Given that some mean elf will bite and some friendly one will too, the mean ones will bite whether or not provoked but the...
  23. @

    Solve Predicate Logic Homework Equations

    Homework Statement 1) (∀xεℝ)((x≠0)→((∃yεℝ)(xy=1) 2) (∃yεℝ)(∀xεℝ)((x≠0)→(xy=1)) Homework Equations ∃ - there exists ∀ - for all → implication The Attempt at a Solution The brackets and implication are throwing me for a loop 1) for all real numbers, there exist...
  24. L

    Predicate logic and one point rule using Z notation

    Hello all, I'm in the process of simplifying the following equation using one-point rule and other predicate logic. But I’m a bit stuck with where to start or which inference rule to use first. Please help or any pointers would be much appreciated. Thanks
  25. S

    How to Translate and Prove a Complex Predicate Logic Statement?

    Homework Statement No matter what positive real number x we choose, there exists some positive real number y such that yz2 > xz + 10 for every positive integer z. Translate the above statement to predicate logic and prove it using a direct approach. Homework Equations I don't...
  26. A

    Predicate logic inference problem

    Homework Statement Consider the following question Adams is a boy who does not own a car. Mary dates only boys who own cars.Therefore Mary does not date Adams. Homework Equations The Attempt at a Solution My answer is like this... Let Bx=x is a boy. Ox=x owns car...
  27. B

    Inconsistency In Sentence Logic and in Predicate Logic

    Does anyone know/understand the different definitions for Inconsistency in Sentence Logic and in Predicate Logic? I know in Sentence Logic, that a sentence ( a Wff, actually) S is contradictory, if from S we can derive (using theorems of truth-functional logic ) a sentence of...
  28. M

    Predicate Logic Universal and Existential quantifiers

    Hi, I'm taking an intro logic class and though I'm comfortable with most propositional logic, predicate logic is confusing me. I joined the forum to ask this particular question that I've been stuck on for a while. Any help would be appreciated - I'm having trouble finding information on the web...
  29. A

    Can Predicate Logic Prove Some Customs Officials Were Drug Pushers?

    I need help with the following question on Resolution in FOL. The custom officials searched everyone who entered this country who was not a VIP. Some of the drug pushers entered this country and they were only searched by drug pushers. No drug pushers was a VIP. Let E(x) mean ”x entered...
  30. R

    Second Order Predicate Logic vs. First Order

    Hey, I'm studying Predicate Logic at the moment and I can't seem to wrap my head around the way that english sentences would convert into second order logic. What kind of sentence can be faithfully represented in PL2 but not in PL1? Sorry if this isn't the appropriate section; I'm actually in...
  31. G

    Predicate Logic: Are These Statements Logically Equivalent?

    Homework Statement Let p(n) and q(n) be predicates. For each pair of statements below, determine whether the two statements are logically equivalent. Justify your answers. a) (i) ∀n (p(n) ∧ q(n)) (ii) (∀n p(n)) ∧ (∀n q(n)) b) (i) ∃n st (p(n) ∧ q(n)) (ii) (∃n st p(n)) ∧ (∃n st q(n))...
  32. M

    Help me understand this predicate logic question

    Homework Statement I've completed the rest of this homework assignment, but I don't understand this question. Otherwise, the section consists of proofs using predicate logic. Could anyone shed some light on what this question means? The book (and the question) is available online, here
  33. M

    Translating english to predicate logic

    Homework Statement I've been given a problem: "C(x,y) is x and y have chatted over the internet. The domain is students in a class. Express there are two students who combined have chatted with all of the students in the class".2. The attempt at a solution I think this is the correct answer...
  34. O

    Can someone confirm these English to predicate logic problems for me?

    Homework Statement I actually have to problems I would just like someone to confirm for me. I have several other problems similar to these, and I don't want to waste time in case I do not understand the fundamentals. Anyway: a) Define suitable predicates and functions and then formalize...
  35. K

    Predicate Logic (family relationships problem)

    Homework Statement Formalize (in PL) the relations/predicates stated in (a)-(e) using just these relations/predicates: 1) Pxy: x is a parent of y 2) Fx: x is a female 3) Sxy: x is a sibling of y (a) x is an uncle of y (b) x is a great-aunt of y (c) x is an aunt (d) x is a great-uncle (e) x...
  36. K

    Predicate Logic and Relations on sets

    Homework Statement Here are a few questions from an exercise sheet that I need help on. I really don't have a clue on how to start them. Could anyone help me attempt at each a) for each question? 1. Use (nested) quantifiers (∀ and ∃) (and propositional junctors) and only equality ``=''...
  37. H

    Solving Predicate Logic Proof Problem with Resolution Refutation

    I have a question on my assignment that I'm having a great deal of trouble with. In this question we will consider a simplified model of the “People you may know” application in Facebook. The basic idea is that if two people have a common friend, then they may know each other. We will also...
  38. L

    Help with Translating English to Predicate Logic

    I have been asked to translate an argument from english into PL and show deductive validity through constructing a PL derivation. I have no problem constructing the derivation but this is the first time I have had to translate from English into PL. I am stuck and any help would be greatly...
  39. V

    Example exercises and answers for predicate logic inference (+ FOL in general)

    I'm battling with first order predicate logic (no identity, no extensions) and currently esp. inference using the so called "natural reasoning" rules for inference. Now, the textbook we use, is very ambiguously defined, even I have spotted several 'errors' in it, the lecturer even more. This...
  40. J

    Predicate logic implication and quantifiers

    Homework Statement C = (Ax)(EY) (p(X) -> p(Y)) D = (EX)(Ay) (p(X) -> p(Y)) Are C and D equivalent? Homework Equations Truth table for implication T T -> T T F -> F F T -> T F F -> T The Attempt at a Solution Well I believe C is true is all cases and is a tautology...
  41. R

    Is my Predicate Logic Solution Correct?

    I have the sentence: No American who hasn't met any Canadian's knows Canada. The teacher gave the correct answer as being: Vx-Ex((Ax ^ Cy ^ Mxy) -> -Kxc) Would this version also work?: -ExEy(Ax ^ Kxc ^ Cy ^ Mxy) or is it supposed to be: -ExEy(Ax ^ Kxc ^ Cy ^ -Mxy) After...
  42. M

    Consistency-related proof in predicate logic

    Could someone please help me with the proof of the following statement? Let L be language with n different constants and at least one predicate symbol. Prove that there exist 2 different maximal consistent sets formed of closed formulas of the language L.
  43. M

    Proof of Predicate Logic Statement: (A → B) → (∃x)(A → B)

    Hello, I don't know how to prove this: \vdash (A \rightarrow B) \rightarrow (\exists x)(A \rightarrow B) First I thought it is just an instantiation of the dual form of the axiom of specification, which says \vdash A_{x}[t] \rightarrow (\exists x) A but it probably...
  44. Y

    Get Help with Predicate Logic and Truth Values: Examples and Symbolization Tips

    Hey everyone, Just need some help on some truth values of a predicate logic interpretation. Here is the info. I will be using A(capital variable) to mean universal quantifier and EEX(capital variable) to mean existential quantifier. UD: Set of positive integers Bx: x is an even number...
  45. L

    Is This Predicate Logic Proof Correct?

    Hey, If anyone here likes working on these problems, I'm working on a couple more. I finished the first two. These go: 1. Vx Vy (Fxy ---> ~Fyx) |- -ExFxx (now my work - maybe wrong 2. Vy (Fay ---> ~Fya) 1,VE 3. (Faa ---> ~Faa) 2,VE 4. | Faa...
  46. A

    Homework help: predicate logic

    I am taking a logic class and we are getting into Predicate Logic and i have no idea how to do it can someone help me?