Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [predicate-logic]

Questions concerning predicate calculus, i.e. the logic of quantifiers.

Some well-known formal systems covered by this term are

  • first-order logic, containing the quantifiers $\forall$ and $\exists$
  • second-order logic
  • many-sorted logic
  • infinitary logic
4144 questions
3
votes
2 answers

Predict Logic Exercise

I have a question regarding Resolution and Substitution We are Given the following rules ∀x∀y(p(x,y)=>∃z q(x,y,z)) ∃x∀y∀z(r(y,z) <=> q(x,y,z)) ∀x∃y (¬p(x,y) => ∀z q(x,y,z)) The question is, Can we prove this Rule ∃w ∃x ∃y ∃z ( r(x,y) ∧…
YAMI
  • 33
3
votes
2 answers

Proving that it is not the case that a one-place predicate is not derivable from an infinite set

I'm trying to prove that it's not the case that $\Sigma \vdash \bigwedge_x F_x$, where $\Sigma= \{FA_1, FA_2, FA_3, \ldots , FA_n,\ldots\}$ I started to prove by contradiction. So assume that $\bigwedge_x F_x$ is derivable. Then by the soundness…
Jon Harris
  • 31
3
votes
1 answer

On translating "Everyone admires someone who works hard"

I think that the English sentence Everyone admires someone who works hard. ...has two plausible, but non-equivalent, translations into predicate logic. Here they are: $$ \forall x \, \forall y \, (Wy \rightarrow Axy )$$ $$ \forall x \, \exists y…
kjo
  • 14,334
3
votes
0 answers

Predicate logic: scope of quantifiers and bound variable

I'm having a little trouble understanding the below predicate formula: $$\exists x P(x, y) \rightarrow Q(x) $$ So if I understand it correctly, the scope of the existential quantifier is $P(x,y)$. Anything variable that is within the scope of a…
Shiny_and_Chrome
  • 363
3
votes
2 answers

Please help me translate these english sentence into Predicate calculus. I have hard time doing it.

Everything is greater than or equa to itself; For evert number n, the resut of adding n to 9 is greater than or equal to 9; Everything has something greater than it. This is for my semantics homework, I tried to first question, but I think I got…
Karen
  • 31
2
votes
1 answer

Predicate logic, linear relation

I've got a question about linear relations in predicate logic. I've got the follow definition where R is a relation of x has a Relation to y. $$\forall x \forall y(Rxy \vee x = y \vee Ryx)$$ How do I read this? Are there 3 formulas? Or just 2? Also,…
Byebye
  • 277
2
votes
2 answers

Give an equational proof $ \vdash (\forall x)(A \rightarrow B) \equiv ((\exists x) A) \rightarrow B$

Give an equational proof of $ \vdash (\forall x)(A \rightarrow B) \equiv ((\exists x) A) \rightarrow B$ I tried and used ping pong theorem to split it into two implications to prove $$ \vdash (\forall x)(A \rightarrow B) \rightarrow (((\exists x)A)…
Out Of Bounds
  • 1,531
2
votes
1 answer

Is the formula an absolute theorem schema?

Is $ (\forall x)(A \rightarrow B) \vdash (\forall x)A \rightarrow (\forall x)B $ an absolute theorem schema ? If you think yes, then give a proof. If you think no, construct a counter model or prove the invalid strong generalization from it. How…
Out Of Bounds
  • 1,531
2
votes
2 answers

Is this predicate logic true?

∃ x ∈ R, ∀ y ∈ R x ≥ y Write the statement in English. A complete answer will not use any mathematical notation, nor the symbols x and y. Write down the truth value of the statement. Write down the negation of the statement in symbols and in…
logicunix
  • 21
  • 3
2
votes
2 answers

predicate logic truth value

I have a structure of predicate logic given by taking the set of natural numbers, 0,1,2... as the domain of discourse ∃X · ∀Y · X < Y Do you read this as there exists an X such that for all Y X is less than Y? Is the domain of discourse the…
Anand
  • 23
2
votes
0 answers

How many "gaps" is needed in a predicate?

So, this actually builds on an earlier post where I asked which of the two expression of PL best express the sentence "Stockholm is the largest city in Sweden": Is it: $$Cab \space\ \wedge \forall x((\neg x=a \wedge Cxb) \rightarrow Lax)$$ with…
tom tronbone
  • 423
2
votes
3 answers

Predicate Logic: Factoring of Quantifiers (Clarification of Concept)

Suppose we have, $\exists x\, P(x) \rightarrow \exists x\,Q(x)$ I know this is logically equivalent to $\exists x\, P(x) \rightarrow \exists y\,Q(y)$ Now, suppose we factor the quantifiers: $\forall x (P(x) \rightarrow \exists y\,Q(y))$ $\exists \,…
EggHead
  • 667
2
votes
3 answers

The difference between $\forall x[R(x) \rightarrow P(x)]$ and $\forall x[R(x)\wedge P(x)]$.

Apparently, it is a common mistake to write $\forall x[R(x) \rightarrow P(x)]$ instead of $\forall x[R(x)\wedge P(x)]$ in some cases, however I can't seem to find the difference between the two. I did some research in ProofWiki and a Discrete…
borg123
  • 275
2
votes
2 answers

Representing $\forall x\exists y:\lnot P(x,y)$ by an English statement

Please help me solve this in an easy way: Write an English statement representing $$\forall x\exists y:\lnot P(x,y).$$ Define all your terms first. Define $P$ and $x$ and $y$ first. Answer: The answer then as I understanded will be : x is a…
MathDisease
  • 307
2
votes
1 answer

How can I write one-to-one and onto in predicate logic?

How can I write one-to-one and onto in predicate logic? $\forall a \forall b(a\in X \land b\in Y, a \implies b)$ This seems very wrong, but I don't know any other way to do it.
KKendall
  • 869
1
2
3
…
22 23