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

learn more… | top users | synonyms

2
votes
4answers
27 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
31 views

Find the free variables in the given sentences.

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
23 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
43 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
62 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
27 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
48 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
37 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
27 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
24 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
26 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
24 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
19 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
51 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
60 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
68 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
71 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
34 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
37 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
67 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
49 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
86 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
28 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
44 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
88 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
71 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
59 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
30 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)$ ...
0
votes
1answer
35 views

What is the difference between these two logical expressions?

I'm reading our lecturers recitations, and the lecturer remarked some comment that confuses me. Consider the expression $\exists !x:P(x)$, where $P$ is some predicate. This expresses the existence ...
1
vote
2answers
32 views

Order of parameters in quantified predicates

I'm studying up for my midterm in Discrete Math and I've been looking at sample questions and their solutions. There is one I don't really understand and I was hoping someone could help me out. ...
1
vote
1answer
27 views

Equivalence of Quantified Predicates

I'm in Discrete Math and I copied down some rules in my notes. Unfortunately I'm not sure if I made a typo or not, let me show you what I mean. Equivalence of Quantified Predicates Symmetry of 'All' ...
0
votes
1answer
25 views

How to formulate this logic formula

The problem setting is very simple. Suppose we have three variables x, y and z and a constraints C/3 predicate that is satisfied by the three variables C(x,y,z), but C/3 might not be the only ...
2
votes
1answer
65 views

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$. My Solution: For all $n$ that is an element of Natural number there is ...
0
votes
4answers
53 views

express in words without using the symbol N

Express $$\forall\ n\in\mathbb N\ \exists\ m \in\mathbb N: \ n^4 = m^2$$ in words without using the symbol $\mathbb N$.
1
vote
1answer
48 views

Is ∃xP(x) ∨ ∃xQ(x) the same as ∃xP(x) ∨ ∃yQ(y)?

Very simple question: is ∃xP(x) ∨ ∃xQ(x)the same as ∃xP(x) ∨ ∃yQ(y) Thank you.
1
vote
2answers
26 views

Logic question is it true

Exercise: $$\begin{align} (\forall x>2) &~:~ |x|<3 \tag{P1}\\ (\forall x\in\mathbb{R})(\exists\varepsilon > 0) &~:~-\varepsilon <x<\varepsilon \tag{P2}\\ (\forall ...
1
vote
1answer
40 views

How do you negate the following sentence?

$ ∀x ∈ R,∃n ∈ Z ,x^{n}>0 $ How do you negate it so that the ¬ symbol does not arise to the left of any quantifier? Is the negated statement is true?
0
votes
1answer
24 views

How to approach conversions of statements using predicates, quantifiers, and logical connectives.

I have an example problem where I must use predicates, quantifiers, and logical connectives to convert the statements. The statement is... ...
1
vote
3answers
75 views

Prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ using natural deduction

I want to prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ where $x \notin FV(\psi)$ using natural deduction method. I was able to prove implication from left to ...
0
votes
0answers
35 views

How can I represent these discrete math statements with predicates and quantifiers?

Use the predicate $A(x, y)$ that denotes ("$x$ loves $y$") Someone loves a person who loves everyone. Everyone loves someone who is loved by someone. I know I need to use nested universal and ...
4
votes
3answers
115 views

quantification domain of set theory formulas

Let ZFC set theory, what is the domain of quantification of a formula like $\forall x\phi(x)$? If the domain is the whole Von Neumann Hierarchy $V$ why it is not a problem that it doesn't form a set?
1
vote
1answer
38 views

Analyzing Set of all Perfect squares

I have been reading Velleman's How to Prove book and the following statement in the book confuses me: For example, suppose we wanted to define S to be the set of ...
1
vote
0answers
40 views

Interpreting logical forms involving quantifiers

I have been trying to translate these two logical form into English statements without using any quantifier laws: (a) ∃x∀y ¬L(x,y) (b) ¬(∃x∀y L(x,y)) where ...
0
votes
2answers
119 views

Expressing statements in positive way

I have been working on this problem from Velleman's How to prove book: Negate these statements and then reexpress the results as equivalent positive ...
0
votes
2answers
60 views

Why does the author define these “logical notations” for set logic with “if then” and &?

In Section 1.1 of "Set Theory for Computer Science", the author defines $ \forall x \in X. P(x) $ and $ \exists x \in X.P(x) $ as shorthand for $ \forall x.(x \in X \Rightarrow P(x)) $ and $ \exists ...
2
votes
1answer
58 views

Deciding between implication and conjunction

This is one of the solved problems in Velleman's How to prove book: Analyze the logical forms of the following statements: 1) John likes exactly one person. ...