# Questions tagged [quantifiers]

The quantifiers $\forall$ ("for all") and $\exists$ ("there exists") are what distinguishes predicate calculus from propositional logic.

1,172 questions
1answer
27 views

### First order logic question about whether variables in the same sentence are bound

Is my intuition right that $$((\exists x)Px \land (\exists x)Gx)$$ is equivalent to $$((\exists x)Px \land (\exists y)Gy)$$ or is it actually equivalent to $$(\exists x)(Px \land Gx)$$ Any help ...
2answers
48 views

### $\lnot\exists x(S(x) \Rightarrow R(x))$ VS $\forall x(S(x) \Rightarrow R(x))$ Without Using De Morgan's Law

I was doing logic exercises the other day and I encountered the following: Write this statement symbolically and verify your answer using De Morgan's Law: No squares are rectangles My ...
2answers
49 views

### Usage of (x, 1) (1) in natural deduction

When neither one of premises and conclusion includes a number like "1", like the following, I could at least proceed to some extent (although I don't know how to connect Q(y) of the first premise and ...
0answers
31 views

1answer
27 views

### Nested Quantifiers: Domain of subjects shared?

I have been trying to find some similar questions but couldn't find one. My question is the following predicate: $\forall$x$\forall$yP(x,y). Suppose P(x, y):x has written an email to y, my question ...
1answer
31 views

### Predicate logic & quantifiers question to write in symbolic form

I'm practising for my math finals... Question: Using D(x, y) to mean "x uses y". Write the following sentence in symbolic form. Make sure to specify the domain of all variables used. Let c = {...
2answers
54 views

### Bracketing and multiple negated quantifiers in predicate logic

Do bracketing and placement affect quantifiers in predicate logic? I.e., are the following two propositions equivalent (where x and y are variables and P and T predicates) ¬∃x (¬∃y Pxy → (∀z ¬(Pzx → ...
4answers
83 views

### Why $\forall$ is not a predicate [closed]

There is a reason why existence can not be a predicate, namely: Let's prove that unicorns exist. It is sufficient to prove that there is an existing unicorn. There are two possibilities: either an ...
0answers
189 views

1answer
40 views

### First order logic: Difference between sentences

My task is to translate the following 2 sentences to first-order logic. I can't figure if my proposed solution is also correct even though it doesn't match the professor's solution. $1$. No student ...
0answers
21 views

### Solving a certain universal claim in natural deduction for predicate logic. [duplicate]

I am having a lot of trouble coming up with a solution for the following predicate Logic Natural Deduction question: $$⊢P(a) → ∀x(P(x) ∨ ¬(x = a))$$ I have spent almost all day working on it and ...
2answers
259 views

### Why is quantifier elimination desirable for a given theory?

We say that a given theory $T$ admits QE in a language $\mathcal{L}$ if for every $\mathcal{L}$-formula, there is an equivalent quantifier free $\mathcal{L}$-formula. That is for every $\mathcal{L}$-...
1answer
31 views

1answer
24 views

1answer
36 views

### Express each of these sentences in terms of Q(x, y), quantifiers, and logical connectives [closed]

Let Q(x, y) be the statement “student x has been a contestant on quiz show y.” Express each of these sentences in terms of Q(x, y), quantifiers, and logical connectives, where the domain for x ...
1answer
87 views

3answers
93 views

### Are quantifiers only required because of infinite proposition chains?

Quantifiers such as $\forall x \ P(x)$ and $\exists x \ P(x)$ are in some ways equivalent to a long conjunction chain being true versus at least one statement being true in a long disjunction chain. ...
2answers
83 views

### prove whether ∃x∀yP(x, y) logically implies ∀y∃xP(x, y) or not.

logical implication in this sense really trips me up, and I don't understand it. What I know of this problem so far is, for some x all y are true in P(x,y) and then I have to show whether that ...
1answer
35 views

### Translating set syntax in FOL

Even though the formal syntax rules for first order logic talk about $\forall x$ or $\exists x$ without necessarily including any kind of $\in Y$ part for some domain/set $Y$, sometimes we'll see ...
1answer
115 views

### Can anyone clarify the rules for $\forall$ intro and elimination, and $\exists$ intro and elimination?

I am trying to better understand the introduction and elimination rules for quantifiers and in particular the syntax / proof system aspect. I'm currently using Fitch-style proofs. I asked a recent ...
1answer
67 views

### Is there a proof of $\lnot \forall x, P(x) \iff \exists x, \lnot P(x)$

I am interested in how one would formally prove: $\lnot \forall x, P(x) \iff \exists x, \lnot P(x)$ I realize that it's basically saying that: \$\lnot(P(x_0) \land P(x_1) \land ... \land P(x_n)) \...
1answer
26 views

### Does each variable in a premises undergoing Universal Instantiation have to change?

I'm currently working on this problem: “All movies produced by John Sayles are wonderful. John Sayles produced a movie about coal miners. Therefore, there is a wonderful movie about coal miners.” ...