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
1
vote
3 answers

If $F$ is a function symbol with arity $2$, then is $F(x,F(x,F(x,x)))$ a term?

Here $F$ is a function symbol with arity $2$. The solutions say it is but I am not sure. If $F$ has arity $2$, but the first $F$ on the outside contains three arguments: $x$, $F(x)$ and $F(x,x)$.
user99865
1
vote
2 answers

Is $F(x,y)=x$ an atomic formula?

$F$ is a function symbol with arity $2$. Is $F(x,y)=x$ an atomic formula? My teachers solutions say it is but I thought that atomic formula had to be a predicate name followed by a variable and if a $F$ is a function variable than it is not an…
user99865
0
votes
1 answer

Variables bound by two quantifiers and quantifers binding non-existent variables

Just wondering if these formulae are valid in classical logic: $\forall x \exists x (Px) \leftrightarrow \exists x (Px)$ $\exists x \forall x (Px) \leftrightarrow \forall x (Px)$ $\forall x (Py) \leftrightarrow Py$ $\exists x (Py) \leftrightarrow…
Stranger
  • 299
0
votes
3 answers

Negation of this statement

Having some trouble negating this expression \begin{align} \forall x \in N, x^2 \in N \text { and } (1 / 2x) \notin N \end{align} "Indicate whether the negated statement is true." When I read it out loud it makes sense to me. "For all x in the…
MarsIsPrettyClose
  • 47
0
votes
2 answers

Predicate Logic - How to define uniqueness

"Every positive real number has a unique positive real square root." \begin{align} \forall x ( (x\in\mathbb R\text{ ^ } x > 0) = > \exists y (y\in\mathbb R\text{ ^ } y > 0 \text{ ^ } y = \sqrt x )) \end{align} Sorry for the terrible formatting, new…
MarsIsPrettyClose
  • 47
0
votes
2 answers

Express the following statements in predicate logic.

Let the predicate $ E(x,y) $ represent the statement "Person x eats food y". Let the predicate $ M(y) $ represent the statement "Food y is a meat product". (a) Express the following statement in predicate logic: "Someone is a vegetarian". (b)…
Out Of Bounds
  • 1,531
0
votes
1 answer

Meaning of this- $\forall x \in S, \exists y \in S, p(x,y) \implies \exists y \in S, p(y,y)$

The problem was to prove or disprove the following $ S\neq \varnothing,\, \forall x \in S, \exists y \in S, p(x,y) \implies \exists y \in S, p(y,y)$
S.Dan
  • 1,115
0
votes
1 answer

How to prove that a predicate is decidable?

Prove the following predicates are decidable knowing that $A$ and $B$ are decidable predicates: $$\lnot A$$ $$A \lor B$$ I am supposed to prove this by writing a program or using some other way that a predicate is decidable but I am not sure how to…
user141418
0
votes
2 answers

Prove that ∀Z · ∃Q · (p(Q) → p(Z)) ⊨ ∀Z · (∃Q · p(Q)) → p(Z) does not hold by giving a suitable structure

Prove that ∀Z · ∃Q · (p(Q) → p(Z)) ⊨ ∀Z · (∃Q · p(Q)) → p(Z) does not hold by giving a suitable structure I am working on this problem but am frankly stumped. I read this as "for All Z such that there exists a Q such that if p(Q) then p(Z) has…
Anand
  • 23
0
votes
3 answers

Question about axiomatic scheme of predicate logic

I'm reading a chapter on axiomatic theories for predicate logic, which has three axiomatic schemes. One of them is: $\forall x \varphi \rightarrow [t/x]\varphi$ (in which the term t is free for x in $\varphi$) What does this mean, and can I see an…
Garth Marenghi
  • 1,115
0
votes
2 answers

Predicates and Quantifiers about Show Precedence of Quantifiers

Predicates and Quantifiers Questions for all x P(x) /\ for all x Q(x) for all x(P(x) /\ Q(x)) why is not logically equivalent?
user3225992
0
votes
2 answers

Predicate Logic: Proof of Validity, Satisfiability of Sentences

Suppose we are given a sentence (i.e. it has no free variables) of the form: $\forall x$ $(P(x) \rightarrow Q(x))$ and asked to determine whether it is a tautology, satisfiable or unsatisfiable. My questions are: 1) Is the sentence, saying that…
EggHead
  • 667
0
votes
2 answers

Does the position of ∃ matter?

Everyone who makes an A aces some final exam Is this ∀x,∃y: makes(x, A) => aces(x, y) the same as ∀x: makes(x, A) => ∃y: aces(x, y) where x represents everyone and y represents exams. Does the position of ∃ matter?
Buksy
  • 191
0
votes
1 answer

Predicate logic and validity

I have the following task: "Show that Pa V Pb -> Ex Px is valid" where E stands for the existential quantifier. I have done the following: - Let M denote a model with domain D, and assume that M |= Pa V Pb - It suffices then to show that M |= Ex…
aprilrocks92
  • 213
0
votes
1 answer

Predicate Logic formula

I came across this problem and found it quite challenging to solve in predicate logic. Here is the signature of the logic: $$\sigma=\{a,P/1,Q/2\}$$ where $a$ represents 10, $P(x)$ represents "$x$ is prime," and $Q(x,y)$ denotes $x
Pavan K
  • 39
1 2 3
…
22 23