Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [quantifiers]

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

0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
0answers
31 views

Rewriting statements in full detail with logical operators, but without quantifiers

I've been given the following question: Let P and Q be predicates on the set S, where S has two elements, say S={a, b}. Then the statement $\forall xP(x)$ can also be written in full detail as $P(a) \...
0
votes
1answer
38 views

How to translate the following predicates with quantifiers into English?

Q(x, z) = "x has z followers on Twitter" Universe of discourse for x, y = all students Universe of discourse for z = non-negative integers How would I properly write the following in English? $$\...
1
vote
1answer
29 views

Logical statements with multiple quantifiers - discrete math

So I have some questions below that I don't understand because I'm struggling with solving questions that involve multiple quantifiers. I was wondering if someone could walk me through how to do these?...
1
vote
1answer
22 views

How To Analyze Statements of Quantifiers

Having trouble figuring out how to interpret Universal Quantifiers, from my book there's two sets of statements. Assuming x,y and z are real numbers, determine the truth value of each statement (a): $...
0
votes
0answers
26 views

Universal quantifiers and Existential quantifiers in Normal English sentences.

I am learning about Discrete Math and I came to know about some sentences in English that are unclear about quantification. For example, the Textbook that I'm following says: "If you can solve any ...
3
votes
1answer
46 views

$\forall x (P(x) \wedge \neg Q(x)) \equiv \forall x P(x) \wedge \neg \exists x Q(x)$

I'm supposed to determine whether or not these equivalences are valid for all predicates P and Q. I've written my assumptions but I've never done anything like this so it almost seems too simple and I ...
0
votes
1answer
30 views

Discrete math - negate proposition using the quantifier negation

I'm asked to negate the following proposition using the quantifier negation rules. No negation operations are to appear before any of the quantifiers in the expression that is created. The issue is I'...
0
votes
0answers
21 views

Proving a sequence does not converge by the definition.

Question:Prove that this sequence does not converge for any $x \in \Bbb R.$ $x_n=(-1)^n(1-\frac{1}{n})$ Definition (Negation):$ \exists \varepsilon \forall N \in \Bbb N \exists n \in \Bbb N, n>N:...
1
vote
1answer
60 views

Syntactical proof of universal instantiation rule

First: I am not mathematician but philosopher. I understand why the universal instantiation rule is working. $\frac{\vdash\forall xA}{\vdash A^x_t}$ But is there actually a serious proof in a ...
0
votes
0answers
10 views

Symbolize using schemas, quantifiers and logical connective.

How can I symbolize the follow sentence: "not all integers numbers are positive" I tried to do this: if x∈ℤ and P(x)= x>0 (∃x)¬p(x) Thanks in advance.
0
votes
1answer
38 views

How can I deny the formula $(\exists x)(p(x)\vee(\forall y)h(y)) \leftrightarrow q $

Can anyone explain me how can I deny this propositional formula? $$(\exists x)(p(x)\vee(\forall y)h(y)) \;\leftrightarrow\; q $$ According to my textbook, the answer would be: $$(\forall x)(\sim p(x)...
1
vote
1answer
25 views

Infinitely many $x_0$s in a sequence, same thing as $\exists N\in \mathbb{N}$ s.t $\forall n \geq N, x_n=x_0$?

Let $\{x_n\}_{n=0}^{\infty}$ be a sequence in $\mathbb{R}$. Is the following implication correct? If so, why? $(x_n)$ contains infinitely many $x_0$s $\iff \exists N\in \mathbb{N}$ s.t $\forall n \...
1
vote
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 ...
0
votes
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 = {...
0
votes
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 → ...
-1
votes
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 ...
7
votes
0answers
189 views

Who was the first to use $\bigwedge$ and $\bigvee$ as universal and existential quantifiers?

It's not surprised that somebody uses $\bigwedge$ and $\bigvee$ as universal and existential quantifiers since $$ \bigwedge_{x\in A}\,\varphi(x)\Leftrightarrow \varphi(a_0)\wedge\varphi(a_1)\wedge\...
0
votes
1answer
33 views

First order logic without existential quantifier, does the position of the “forall” matter?

I am considering first order logic without existential quantification (i.e. with $\forall$ as the only quantifiers). Given an arbitrary formula, would moving all the $\forall$ to the "front" of the ...
0
votes
1answer
31 views

Prove the following by deduction rules for qualifiers and implication

I am having trouble with the following proof. First, some basic definitions: Def. Given two statements $\alpha$ and $\beta$, the statement \begin{equation}\alpha \implies \beta ,\end{equation} read ...
0
votes
1answer
14 views

Quantifiers- universal and existential

Let P(x) denote the statement “x is an accountant let Q(x) denote the statement “x owns a Porsche Someone who owns a Porsche is an accountant why is the answer ∃x (P(x) ^ Q(x)) and not ∃x (Q(x) -> P(...
0
votes
0answers
24 views

Question involving the truth value of two logic statements

Context: Previous multiple choice question from uni exam Statement 1: There exists a real number $x$ such that for all real numbers $y$, the sum of $x$ and $y$ is greater than or equal to $1$. ...
0
votes
1answer
28 views

Gentzen Natural Deduction Quantifier Problem!

I am having a problem with $$\exists x \ T(x),\quad \forall x \ (T(x) \to P(x)) \quad \text{leads to} \quad \exists y\ (T(y) \land P(y))... \tag 1$$ It is using $$\forall \text{intro,elim} \ \...
2
votes
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 ...
0
votes
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 ...
6
votes
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}$-...
2
votes
1answer
31 views

Understanding interpretation of a predicate

This exercise is confusing me. Let $S(x,y,z):= $ $z$ is the child of $x$ and $y$, where $x$ is the mother and $y$ is the father. Express the following sentence in predicate logic using the predicate $...
2
votes
2answers
44 views

How would I convert this discrete math statement from logic/equation to English?

Given that $B(x)$ means "$x$ is a bear", $F(x)$ means "$x$ is a fish", and $E(x,y)$ means "$x$ eats $y$", what is the best English translation of $\forall x[F(x)\rightarrow \forall y(E(y,x)\...
0
votes
1answer
24 views

Help with rewriting a simple statement using Logical Quantifiers.

The question was to rewrite the statement "The equation $x^2=-1$ has no real solution in $\def\Z{\Bbb Z}\Z$" using only logical quantifiers and the words "such that" My incorrectly marked answer was $...
2
votes
1answer
67 views

Can we specify in a first order formula that a variable depends not on all previous universal quantifiers

Let $\sigma$ be a first-order language (signature) and let $\mathcal{A}$ be a structure those signature is $\sigma$ and those domain is $A$. A subset $X\subset A$ is called definable in $\mathcal{A}$ ...
-4
votes
1answer
36 views

Direct Proof with Quantifiers [closed]

How can i use direct proof to prove that the function $n^2+5n+6$ is even when $n$ is odd and even, for all natural numbers?
0
votes
0answers
19 views

Predicate Logic Equivalences [duplicate]

It is from discrete mathematics notes. These are part of the biconditional tautologies. E29. (∀x)A(x) →B ⇔ (∃x)(A(x)→B) E30. (∃x)A(x) →B ⇔ (∀x)(A(x)→B) I don't understand how these formulas are ...
1
vote
3answers
93 views

Commutative quantifiers

If I have a proposition of the form $$(\forall x \in X) (\exists y \in Y) (\forall r \in R) \, P(x,y,r)$$ where at least any number of $X$, $Y$ and $R$ can be the same. Is that logically equivalent to ...
0
votes
1answer
61 views

Why are these terms not equivalent?

can can someone please explain me, why these terms are not equivalent when I apply alpha-conversion? ∀x p(x) ∧ q(y) != ∀y p(y) ∧ q(x) Thanks!
0
votes
0answers
31 views

First order logic formulae

Prove that $$((\forall x) ( a \Rightarrow b)) \Rightarrow [((\forall x)( a)) \Rightarrow ((\forall x) (b)) ]$$ is valid first order formula. Where ' a ' and 'b' are first order formulae. My attempt: $...
0
votes
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 ...
2
votes
1answer
87 views

Show that $∀x∃yRxy ⊢ ∃zRf(a)z$

I'm very logic noob. I'm having trouble deciphering what this means. What I've got is "For all $x$, there exists some $y$ such that $x$ Respects (R) $y$ ~something~ there exists some $z$ such that $...
1
vote
1answer
55 views

Is this a free variable? Something else?

I am struggling to understand the terminology behind free variables. If we have $\forall x \ P(x)$ I would believe $x$ is bound and not free. If we have $\forall x \ P(x, y)$ I believe $y$ is free, ...
1
vote
3answers
63 views

Quantifier order confusion [duplicate]

I wondered, if $\forall x\, \exists y\, R(x,y)$ is equivalent to $\exists y\, \forall x\, R(x,y)$. If $R(x, y) = (x < y)$ then the answer would appear to be no. In the first case, for all $x$, ...
1
vote
3answers
73 views

Need help understanding variable label/scoping rules for first order logic

I don't understand when we're allowed to use what label when we're writing a proof in first order logic. During $\forall$-intro we introduce a new variable $c$ and then close out with something in ...
0
votes
1answer
61 views

Prove whether ¬∃xP(x) logically implies ¬∀xP(x) or not.

So my logic is ¬∃xP(x)⟺ ∀x¬P(x) and if ∀x¬P(x) is taken to be true, then for all x P(x) is false and ¬∀xP(x)⟺ ∃x¬P(x) which means that for some $x$, $P(x)$ is false and if all $x$ is false, ...
0
votes
2answers
46 views

Quantifier Positioning

How does the positioning of a quantifier affect the meaning of the statement? For example, what is the difference between $\forall x : \forall y : (P(x) \land P(y))$ and $(\forall x: P(x)) \land (\...
4
votes
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. ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
3
votes
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)) \...
0
votes
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.” ...