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

learn more… | top users | synonyms

1
vote
0answers
27 views

Given an open statement determine if their quantification is true

The Question My Work/Question My book says for part a, iv is true. I disagree. To show an existential statement is false we have to show that for all x that statement is untrue. There are no ...
-2
votes
1answer
27 views

a formal logic proposition about real numbers

I have the following informal statement about real numbers: Every real number except zero has a multiplicative inverse. Can this be expressed as: $$ \forall x \exists y(x\neq 0 \implies xy=1) ...
0
votes
0answers
19 views

Formalize: “Every mail message larger then one megabyte will be compressed” [duplicate]

Formalize: Every mail message larger then one megabyte will be compressed
1
vote
1answer
36 views

Prove a predicate formula in the constructive logic

Using the constructive logic (the axiom $A\lor\lnot A$ cannot be used), using quantifier axioms and Modus Ponens, and Generalization, prove the following: $\exists x(B(x) \to C(x)) \to (\forall xB(x) ...
1
vote
1answer
17 views

determining free and bounded variable occurrences in a WFF

show all variable occurrences that are free and ones that are bounded and indicate the quantifier that binds them ∀a[∃b(P(a,b,c,d)) ∧ ∀c(∃a(R(b,a,c,d)))] my ...
1
vote
1answer
43 views

Is this quantifier is true?

"Every mail message larger than one megabyte will be compressed". Let $M(x) = x$ mail message $L(x) = x$ larger than one megabyte will be compressed $ \forall x \space (M(x) \rightarrow L(x))$
1
vote
2answers
24 views

Is there an implicit quantifier, or is it always an error when one isn't specified?

I have an exercise book from my university which doesn't specify a quantifier. It uses expressions like "here $A$,$B$,$C$ are sets", or "if $x \notin A$ then ..." (it uses $x$ before it is even ...
-1
votes
1answer
71 views

Is this question is true? [closed]

The negation of There is an x whose square is equal to 2 is for every x whose square is equal to 2 ???
0
votes
1answer
42 views

Double check my quantifier logic? $(\exists x~:~P(x) \rightarrow \exists y~:~Q(y)) \equiv (\exists z~:~P(z) \rightarrow Q(z))$

I was looking at some random math problem and needed to resolve $$\bigg( \exists x ~:~ P(x) \bigg) \rightarrow \bigg(\exists y ~:~ Q(y) \bigg) \tag 1$$ by rewriting as an equivalent statement. I ...
1
vote
1answer
48 views

is $P(x) \to \forall x P(x)$ satisfiable

I need to prove that this formula $P(x) \to \forall x P(x)$ is satisfiable. Can I say for example that x is even number ?
0
votes
1answer
31 views

Is this quantifier negation correct?

I would like to know, if this negation is correct, and if not, an explanation on what is wrong. Any help would be appreciated :) Original: $$ \forall \epsilon > 0 \exists \delta > 0 \forall ...
1
vote
1answer
36 views

Prove equivalence in predicate logic

I have to prove that these formulas are equivalent: $$\begin{align} \exists x \forall y P(x,y) \equiv \forall y \exists x P(x,y) \\ \end{align}$$ Can I say that $$\begin{align} \forall y \exists x ...
1
vote
1answer
26 views

Expressing given statements using quantifiers examples

I'm new on this subject and I have answered some questions which I found. Since there are no answers for them; I couldn't be sure that my answers are true. Could you help me verify the answers or ...
-1
votes
1answer
47 views

Is $\exists x \forall y \exists z P(x,y,z)$ satisfiable? [closed]

I have this formula: $$\begin{align} \exists x \forall y \exists z P(x,y,z) \\ \end{align}$$ How to check whether it is satisfiable? I know that I have to find a structure in which it is true.
0
votes
1answer
15 views

Predicate formula to propositional formula

I have: $$\begin{align} \exists x \forall y P(x,y) \\ \end{align}$$ where $$\begin{align} M=\{a,b\} \\ \end{align}$$ I need to convert this formula to propositional logic. I know that if ...
1
vote
3answers
50 views

Where to put the “such that”, given multiple quantifier

Personally, I would put the "such that" (i.e. the symbol $:$ or $|$) behind any quantification. That is given an assertion $A(x,y)$, I'd write $$ \forall x\in X\exists y\in Y:A(x,y)\\ \exists x\in ...
2
votes
2answers
46 views

Syntax of an epsilon delta proof/why is this version incorrect [duplicate]

So we have the regular $\delta$-$\epsilon$ definition of continuity as: (1) For all $\epsilon>0$, there exists a $\delta>0$ such that, if $|x-a|<\delta$, then $|f(x)-f(a)|<\epsilon$. My ...
0
votes
1answer
43 views

Problem in solving a logical Equivalence

Prove or disprove the following equivalence: $$ ∀x Px \wedge ∀x Qx \Leftrightarrow ∀x ∃y ( Px \vee Qy ) $$ I've tried it, but I do not know how to solve logical equivalences involving quantifiers.
2
votes
3answers
30 views

Question About Notation Nested Quantifiers.

It's a pretty simple question on nested quantifiers but I didn't see anything about it on my Textbook or on Google so I wanted to give this a shot. So let's say you have $P(x)$ and $P(y)$ and you ...
0
votes
1answer
33 views

Find the free variables in the given sentences. [closed]

How to find free variables? 1)$(\forall x)$$(\forall y)$$x+y=2$ 2)$x+y<x$$\vee $$(\forall z)$$z<0$ 3)$((\forall y)(y<x))$$\vee $$((\forall x)(x<y))$ please guide me?
1
vote
1answer
29 views

Why is Skolem normal form equisatisfiable while the second order form equivalent?

I asked in another question when is it appropriate to de-Skolemize a statement. The answer, I'm not sure I'm satisfied with yet, relies on a second order logical equivelance, but Skolem normal form ...
0
votes
1answer
44 views

Universe of discourse in $A \subseteq B$

In the following logical analysis: $A \subseteq B $ $\forall x(x \in A \implies x \in B)$ Is the universe of discourse for the above logical form is A since the ...
0
votes
2answers
65 views

Showing that ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x)

Q(x, y) := “Student x did exercise y in the book” R(x) := “Student x gets an A in the class” So my goal is to show that the following equivalency holds: ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S ...
0
votes
1answer
33 views

Clarification regarding bound variables and quantifiers

I have been working on one of the problem like this: $ x \in \wp(A \cap B) $ $ x \subseteq (A \cap B) $ $ \forall y (y \in x \implies y \in (A \cap B)) $ $ \forall y (y \in x \implies y \in A ...
4
votes
2answers
51 views

When is de-Skolemizing statements appropriate?

In first order logic we often convert prenex normal form statements to Skolem normal form statements to eliminate the existential quantifier: $\exists$x$\forall$y$\exists$z$\phi$(x,y,z) becomes ...
1
vote
1answer
41 views

Second order universal quantifier elimination restriction

Dirk van Dalen in his Logic and Structure gives following universal elimination rule: from $\forall_{X^n} \phi$ infer $\phi^*$ where $\phi^*$ is $\phi$ in which every occurence of $X^n(t_1, ..., ...
0
votes
4answers
53 views

Solving $\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$

I have been solving this problem from Velleman's How to prove book: $\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$ This is my ...
0
votes
1answer
32 views

Set of all perfect squares

I have been going through Velleman's How to prove book and they have explained the set of all perfect squares using this set: $S = \{ n^2 | n \in N\}$ Then it is ...
0
votes
1answer
25 views

Bounded quantifier and it's meaning

It's explained in Velleman's how to prove book that $\exists x \in AP(x)$ means that there is at least one value of x in the set A such that P(x) is true. Then ...
1
vote
2answers
32 views

Proving the Truth Value of Quantified Statements

I would like to know an efficient way of disproving existential quantifier ∃ to show that "for every value of a P(a) is false." ? Also, proving universal quantifier ∀ to show that "for every a, P(a) ...
1
vote
2answers
26 views

Statements to Predicates and Quantifiers

"There is a student in this class who has taken every course offered by one of the departments in this school." I need to express this is predicates and quantifiers. Can someone check my answer? I ...
0
votes
1answer
22 views

Simple Question on Quantifier Logic [closed]

is this a valid implication: $(\forall\epsilon>0.\exists x\in A.x>a-\epsilon)\implies(\forall\beta\epsilon>0.\exists \beta x\in \beta A.\beta x>\beta a-\beta\epsilon) $ $,\beta>0$
0
votes
1answer
52 views

Analyzing logical form of ∀x∀yM(x, y)

I have been going through Velleman's How to prove book and in one of their sample problems they have used ∀x∀yM(x, y) for ...
-1
votes
2answers
64 views

find a universe for variables x, y, and z for which this statement is true and another universe in which it is false

Im solving a practice quesitons on quantifiers and I'm stuck with this questions im trying to solve this question for few hours now and I really don't have a clue what to do... The question is ...
0
votes
2answers
77 views

Determine the truth value of each of these statements if the universe of each variable consists of following [closed]

hello im working on practice questions and Im stuck with this 2 question The question is Determine the truth value of each of these statements if the universe of each variable consists of 1)all real ...
1
vote
1answer
72 views

Find a universe for variables x, y, and z for which the statement is true and another universe in which it is false.

Find a universe for variables $x, y$, and $z$ for which the statement $∀x∀y((x ≠ y) → ∀z((z = x) ∨ (z = y)))$ is true and another universe in which it is false. Is there a more ...
1
vote
2answers
41 views

How are $ \exists x (P(x) ⊕ Q(x)) $ and $(\exists x P(x)) ⊕ (\exists x Q(x))$ not logically equivalent?

I want to know how these two statements are not logically equivalent. From what I have done I am getting them as logically equivalent. I have started as letting $P(x) = x$ is even and $Q(y) = y$ is ...
0
votes
1answer
39 views

Determine the truth value of the statement if the universe of each variable consists of (i) all real numbers, (ii) all integers.

∀x (x > 0 → ∃y ((√x)/y = 3)) I've learned about different types of proofs, and I'm thinking here that I would first negate the statement to then prove the negation. Would the negation be: ∃x(x ≯ 0 → ...
1
vote
1answer
81 views

Use predicates and quantifiers to express this statement.

“Some students in this class grew up in the same town as exactly one other student in this class." I'm thinking there is a relation T(x,y) where the student x grew up the same town as student y. And ...
1
vote
1answer
51 views

How do I interpret z in this equation?

The sentence this corresponds with is "Some students in this class grew up in the same town as exactly one other student in this class." It seems that x and y are the same student from the same town ...
0
votes
2answers
53 views

Trying to understand negation of quantifiers

Trying to understand the negation of the following: For this: ∀x~P(x) I have this as negation: ~∃xP(x) For this: ~∃x(∀yP(y) Λ Q(x)) I have this: ∀x(~∃yP(y) V ~Q(x)) Are these correct? If not please ...
1
vote
1answer
98 views

Proof using existential quantifier [closed]

Prove: $$\begin{align} \exists x ~:~ \bigg(p(x) &\rightarrow q(x)\bigg) \ How do I go about proving this? Can I distribute the existential quantifier in the first term?
0
votes
0answers
39 views

Existential quantifier with implication/conjunction as a Venn diagram?

I'm having trouble visualizing the following statements in a Venn diagram: $$\exists x\in D, Q(x) \implies P(x) $$ $$\exists x\in D, Q(x) \wedge P(x) $$ For the first statement, does it look like ...
0
votes
1answer
50 views

Proving property for all predicates in first order logic

Let's consider language with predicate $P$ and following derivation $${{{[P[a/x]]^1} \over {P[a/x] \rightarrow P[a/x]}}\rightarrow I^1 \over {\forall_x (P(x) \rightarrow P(x))}}\forall I$$ Doesn't ...
0
votes
4answers
92 views

Translate these statements into English

Translate the following statements into English, where $C(x)$ means '$x$ is a comedian', $F(x)$ means '$x$ is funny' and the domain consists of all people: a) ∀x(C(x) → F(x)) b) ∀x(C(x) ∧ F(x)) c) ...
0
votes
2answers
58 views

How to prove that for all $x$ there exists some $y$ where $ (x^2 + y^2 \geq 0)$?

How can I prove that $\forall \,\,x\,\,\exists y\,\,,(x^2 + y^2 \geq 0)$?
2
votes
1answer
78 views

Predicate logic proof problem

Where the domain of the variables are Real Numbers, determine the truth value for the following: $$ \forall x \exists y(y^2-x<200) $$ I don't understand how to formally prove this problem. Since ...
1
vote
2answers
60 views

How to prove that we can switch two $\forall$?

This is true? See a simple proof (High-school level) Thanks e.g: $$\forall x, \forall y\;P\;\text{is true}. \iff \forall y,\forall x\;\text{P is true}$$
0
votes
1answer
34 views

Understanding triple mixed quantifiers

I'm having a hard time understanding mixed quantifiers of this form: $$\forall x\exists y\forall z(...)$$ and similarly $$\exists x\forall y\exists z(...)$$ It really hurts my head to think about ...
0
votes
0answers
7 views

Meaning of a statement implying a value in a set?

There is this statement: There exists $T>0$ such that $f(x+T)=f(x) \implies x\in(-\infty,\infty)$. What does it mean? Is that the same as saying: There exists $T>0$ such that $f(x+T)=f(x)$ ...