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

learn more… | top users | synonyms

3
votes
2answers
43 views

Are the quantifiers interchangeable?

In other words, is it true that $\forall x \; \exists y\;\phi(x, y) \iff \exists y\;\forall x \; \phi(x, y) $?
0
votes
4answers
44 views

A tautology that contains quantifier and logical connective.

It might seem a stupid "question", but I need a logical explanation of it. If $p(x)$ is a predicate and $q$ is a statement, then $(\forall x:p(x))\wedge q\iff \forall x:(p(x)\wedge q)$, and ...
0
votes
1answer
47 views

Scope of Quantifier, bit puzzling

$\forall x(p(x) \rightarrow \exists xq(x))$ $p(x)$ : $x$ is a human. $q(x)$ : $x$ has a job Help me understand this in english please?
2
votes
3answers
56 views

Quantifier elimination over rationals.

My question is concerned with a statement in Marker's Model Theory. The statement is that for formula $\phi(a,b,c)=\exists x(ax^2+bx+c=0)$, we cannot have a quantifier free formula $\phi'$ such that ...
1
vote
2answers
41 views

Multiple Quantifier Proof

I am completely confused on how to go about proving this multiple quantifier expression. $$(\forall m\in\mathbb Z)(\exists N\in\mathbb Z)(\forall n\in\mathbb Z)(n\geq N\Rightarrow (n-1)^2 \geq m^2)$$ ...
1
vote
2answers
21 views

Is there a difference between these statements about natural numbers?

Can i say that $(\forall x \in \mathbb{N}:x^2=x) \vee(\forall x \in \mathbb{N}:x>1)$ is the same statement as:$\forall x \in \mathbb{N}:(x^2=x)\vee(x>1)$ ? If not, why? Thanks.
0
votes
1answer
40 views

First Order Logic Question

$\forall x\ \forall y\ P(x,y) \to \forall x\ \forall y\ P(y,x)$ Is this a tautology? Is there a set method that we can use to find whether a wff is a tautology?
2
votes
1answer
47 views

Basic First Order Logic Question

Which one of the following well formed formulae is a tautology? (A) $\forall x\exists yR(x,y)\iff\exists y\forall xR(x,y)$ (B) $[(\forall x\exists y(p(x,y)\Rightarrow R(x,y))]\Rightarrow ...
0
votes
0answers
10 views

Basic Predicate & Quantifier Doubt

Which one of the following well formed formulae is tautology? (A)∀x∃yR(x,y)<=>∃y∀xR(x,y) (B)(∀x[∃yR(x,y)=>S(x,y)])=>∀x∃yS(x,y) (C)[(∀x∃y(p(x,y)=>R(x,y))]=>[∀x∃y(¬p(x,y) V R(x,y)] ...
1
vote
2answers
30 views

Nested Quantifiers Doubt: “If $xy$ is equal to $x$ for all $y$, then $x=0$”

If $P(x,y,z)$ represents $xy=z$. Then represent the following statement using quantifiers,connectives etc. "If $xy$ is equal to $x$ for all $y$, then $x=0$". The answer given is $\forall x[ \forall ...
0
votes
1answer
28 views

Translate into a formula using quantifiers

Let B(x) be “x is a bird”, F(x) be “x has feathers”, and Y(x) be “x can fly”. Then translate into a formula using quantifiers: Some things that can fly are not birds.
2
votes
3answers
91 views

Determining if all integers of the polynomial form $n^2+21n+1$ are prime

Suppose I had a statement that said For all positive integers of n, ${n^2 + 21n + 1}$ is prime. Attempt: The first thing that I decided to do was to try and factor it. I immediately saw that it ...
2
votes
2answers
42 views

Difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$

Existential quantifier confusion: what is the difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$? What are the differences between those two ...
2
votes
1answer
52 views

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$. Given the above expression, For all of $x$ [ if $x$ is less than zero, then $x^2$ is greater than zero]. Is that a ...
2
votes
1answer
85 views

Quantifier-free induction and comparison with $\sqrt{2}$

I am trying to understand quantifier-free induction in the system called PRA - primitive recursive arithmetic which states the following: $$ \frac{ \varphi[0] \quad \varphi[n] \implies ...
1
vote
0answers
52 views

Translation of English statements to logical expression using nested quantifier and predicates.

I have come across few doubts solving Exercise of Propositional logic and predicates. Here are they, Doubt 1 ...
1
vote
1answer
25 views

using logical quantifiers to write that f approaching infinity DOES NOT tend to infinity

Is this the same as writing that the limit of f as f approaches $\infty$ is L? i.e.: $\forall \space \epsilon > 0 \space \exists \space c \space \forall \space x>c : |f(x) - L|< \epsilon$
1
vote
3answers
48 views

When does the negation of a universal quantifier require a disjunctive statement?

Here's a question I got wrong on a HW assignment recently, which asked students to negate the given statement and assign that negation a truth value. Q: There are exactly 3 points on every line. my ...
0
votes
1answer
55 views

Logical Equivalence: $\exists x((P(x) \land \lnot Q(x))\Leftrightarrow R(x)) \iff (\forall xP(x)\Rightarrow \exists y(Q(y) \lor R(y)))$

I am trying to show LHS equivalent to RHS however, but I am unsure on this specific example. Any help would be appreciated. $$\exists x((P(x) \land \lnot Q(x))\Rightarrow R(x)) \iff (\forall ...
1
vote
0answers
37 views

Truth value of a mathematical statement about circles?

Let $A$ be the set of circles in the plane with center $(0,0)$ and let $B$ be the set of circles in the plane with center $(-2,3)$. Furthermore, let $P(C_1,C_2)\colon C_1$ and $C_2$ have exactly one ...
1
vote
2answers
33 views

Find a logical predicate for some given conditions

I am trying to give an example of a predicate $P(x, y)$ such that $\exists x$ $\forall y$ $P(x, y)$ and $\forall y$ $\exists x$ $P(x, y)$ have different truth values. I am struggling to think of such ...
0
votes
1answer
29 views

Can First Order Logic identify that two variables are the same object?

Supposed I defined: $Px$ = $x$ is a person $Lxy$ = $x$ loves $y$ And I expressed that everyone loves someone: $$(∀x)(Px \implies (∃y)(Py ∧ Lxy))$$ However I want to formally exclude narcissists ...
3
votes
1answer
73 views

Does “Everyone loves all kittens” imply “Everyone loves a kitten”?

In my logic class, we explored whether various quantified statements implied others. We agreed that the statement "Everyone loves everyone" implies that "Everyone loves someone": $Px$ = $x$ is a ...
1
vote
1answer
35 views

Discrete Structures: Trying Correcting my Predicate Logic with the appropriate quantifiers

I am trying to correctly use predicate symbols and using the appropriate quantifiers were I have to write each English language statement in predicate logic and the domain is the whole word. $P(x)$ ...
0
votes
0answers
31 views

Adding Sentence Variables and Quantifiers to Formal Languages

I have been thinking about the following construction, and was contemplating investigating it for my undergraduate thesis: Let $L$ be a formal language, e.g. the set $\{x_1, x_2, \dots, \forall, ...
0
votes
0answers
15 views

How to use a predicate function when formalizing predicate propositions?

I've tried the following question from my maths assesment but not sure if I'm using the predicate, fool(p,t) correctly. Can anyone advise on if I'm using it ...
1
vote
2answers
60 views

for some or for all

The following text is from Velleman's How to Prove book from the reflexive closure section: According to the definition we gave in the last section, the ...
0
votes
0answers
22 views

Problems of Quantifiers

Translate the following natural language sentences to quantified statements. Then apply the negation on them so that no negation sign appears to the left of a quantifier. Then express the most ...
0
votes
2answers
29 views

Truth Value for Quantifier

What would be the truth value for the following two quantifiers if n and m are both integers? I have trouble proving each of these statements. I appreciate any help you can provide! a)   ...
3
votes
1answer
44 views

How to prove $(\forall x,y\in\mathbb{Z})(5\nmid xy\to(5\nmid x\land 5\nmid y))$

Question: Prove $x,y\in\mathbb{Z},\Bigl((5\nmid xy)\to(5\nmid x\land 5\nmid y)\Bigr)$ where $\forall a,b\in\mathbb{Z},\bigl((a\nmid b)\leftrightarrow(\forall k\in\mathbb{Z},b\neq ak)\bigr)$ and ...
0
votes
2answers
36 views

Order of logical quantifiers within a statement

I understand that the order of the quantifiers of a statement determine the truth value of statement. For example, $$\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\ \text{such that}\ ...
1
vote
1answer
42 views

Quantifiers for mutually distinct variables

Okay, this is freaking me out, I'm going nuts. In a first-order condition with formula $\phi$ containing $x, y$ such as $\forall x\forall y . \phi$ I need to ensure that the second variable bound ...
0
votes
0answers
24 views

quantization of a discrete probability source

The alphabet of a memory less source is $A=\{-5,-3, -1, 0, 1, 3, 5\}$ with corresponding probabilities $\{0.05, 0.1, 0.1, 0.15, 0.05, 0.25, 0.3\}$. If I know that the source can be quantized ...
2
votes
2answers
102 views

Quantifier for “there is at most one”?

As "there is at least one" and "there is exactly one" both have their symbols, I wonder what is the common notation for "there is at most one"? By "common" I mean the desired notation can be used ...
2
votes
1answer
37 views

Prenex normal form of $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$

I have the statement $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$ and I have to write it in prenex normal form. First I use the second De Morgan law $\neg \big(\forall x \ P(x) \vee ...
1
vote
0answers
18 views

Universal Instantiation

I'm a bit confused about how Universal Instantiation works. I read that you shouldn't really plug in any value "a" for x in "For all x P(x)" unless a choice for "a" pops up in the givens but in the ...
2
votes
2answers
67 views

How do I show that $\forall x \ P(x) \vee \forall x \ Q(x)$ and $\forall x (P(x) \vee Q(x))$ are NOT logically equivalent?

Show that $\forall x \ P(x) \vee \forall x \ Q(x)$ and $\forall x (P(x) \vee Q(x))$ are not logically equivalent. Can someone give a hint?
1
vote
1answer
96 views

$P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations.

Suppose that the domain of the propositional function $P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations. a) ...
2
votes
0answers
43 views

When does renaming bound variables require a fresh variable?

Suppose that $E_1$ and $E_2$ are two $\alpha$-equivalent first-order logic formulas (or $\lambda$-terms), and let $V$ be the set of all variables (free and bound) used in $E_1$ or $E_2$. Is it ...
0
votes
1answer
74 views

Prove DeMorgan's Theorem for indexed family of set using logic quantifiers

I need to prove both general union and intersection for indexed family sets using logic quantifiers, this is the prove i've written but i'm not sure if its correct: Thanks for help.
2
votes
2answers
68 views

Which variables are free in $\forall x (\exists y (x < y+z) \to \exists z (x < y+z))$?

anyone could explain for me, why $x,y,z$ is bound variable in this formula? $ \forall x [ \exists y (x < y+z) \to \exists z (x < y+z) ] $ I think $y,z$ is free variable.
3
votes
2answers
39 views

Have troubles with contradiction of a statement

"Suppose that there are 13 people in a room. Prove: "At least two of these people were born in the same month". Use the indirect method." The question I have is: Which of the following (if any) are ...
0
votes
1answer
11 views

Adding and subtracting variables which are part of an interval

I am following a paper proof which starts with the following constraint: $$\forall v \in [a,b], \forall \tilde{v} \in [a,b]$$ $$f_{i}(v) \geq f_{i}(\tilde{v}) + (v-\tilde{v})g_{i}(\tilde{v})$$ In ...
1
vote
1answer
29 views

For $p(x): x>0$, $q(x): \text{$x$ is even}$,$r(x): \text{$x$ is a perfect square},$ is $\forall x[r(x)\to p(x)]$ true?

Given $$p(x): x>0,$$ $$q(x): \text{$x$ is even},$$ $$r(x): \text{$x$ is a perfect square},$$ are the following statements true or false? a.) $\exists[p(x)\land q(x)].$ b.) $\forall x[r(x)\to ...
1
vote
3answers
59 views

Is $\exists x(P(x) \to Q(x)) \equiv (\exists xP(x) \to \exists xQ(x))$?

My intuition is that this statement is false and here is my proof. $\exists x(P(x) \to Q(x))$ $\exists x(\lnot P(x) \lor Q(x))$ using logical equivalence. $\exists x\lnot P(x) \lor \exists x Q(x)$ ...
1
vote
1answer
30 views

$(\forall (x,y) \in F\times G, \phi(x) \lor \psi(y) ) \Leftrightarrow (\forall x\in F, \phi(x)) \lor (\forall y\in G, \psi(y))$?

All the question is in the title: is the equivalency $$(\forall (x,y) \in F\times G, \phi(x) \lor \psi(y) ) \Leftrightarrow (\forall x\in F, \phi(x)) \lor (\forall y\in G, \psi(y))$$ true (where ...
0
votes
1answer
31 views

Prove the expression using deduction

$(\exists x)[A(x) \wedge B(x)] \rightarrow (\exists x)A(x) \wedge (\exists x)B(x)$ I realize that this is an equivalence but I am wondering how I might prove this. I feel like I would use ...
1
vote
2answers
49 views

Prove If $\forall x \in X((x,x) \in R)$ then $\forall x \in X \exists y \in X(x,y) \in R$

I have been solving one problem and at the end of the proof after performing some transformations, I have been left with this to prove: If $\forall x \in X((x,x) \in R)$ then $\forall x \in X \exists ...
1
vote
2answers
61 views

When existential quantifiers distribute over conjunction

I know that, generally: $$\exists x~~ (P(x) \land Q(x)) \implies \exists x~~P(x) \land \exists x~~Q(x)$$ But I wonder if is there any circumstances (by some restrictions of $P(x)$ and $Q(x)$) that ...
1
vote
2answers
48 views

Quantifiers for formal definition of a limit

I have a problem. I have to prove that $(\forall\,\epsilon > 0)(\exists\,\delta > 0)[0 < |x − a| < \delta \implies |f(x) − L| < \epsilon$ (formal definition of a limit) ...