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).
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...
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...
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.
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) ##...
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...
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...
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...
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...
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...
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...
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...
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$...
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...
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...
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
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...
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.
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...
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.
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...
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...
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...
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...
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
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...
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...
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...
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...
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...
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...
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))...
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
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...
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...
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...
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 ``=''...
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...
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...
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...
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...
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...
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.
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...
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...
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...