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

learn more… | top users | synonyms

0
votes
1answer
45 views

Clarification regarding Drinker's paradox

This is the informal proof of Drinker's paradox The proof begins by recognising it is true that either everyone in the pub is drinking (in this particular round of drinks), or at least one ...
2
votes
1answer
43 views

Flattening quantification over relations

I already asked this question in stack overflow here and somebody suggested to post it here. I repeat the question again: I have a Relation f defined as $f: A \to B × C$. I would like to write a ...
2
votes
3answers
37 views

Proving if $A \subseteq B$ and $A \nsubseteq C$ then $B \nsubseteq C$

This is one of the problem I have been solving in Velleman's How to prove book: Prove that if $A \subseteq B$ and $A \nsubseteq C$ then $B \nsubseteq C$ This is my solution: Suppose $A ...
0
votes
1answer
38 views

two place predicate logic

Im trying to prove following,as lecturer did not have time to go through the proof on the lecture, I wonder how to solve at least the first statement $$(\forall x)(\forall y)L(x, y) ≡ (\forall ...
1
vote
1answer
22 views

Existential Quantifiers translated into categorical statements?

I've been recently trying to translate the categorical statements into the quantifiers ($\forall$ and $\exists$). Attempts I believe I can make the E statement as $$\nexists s:p,$$the A statement ...
1
vote
2answers
23 views

Pre-nex normal form. Correct way to distribute negations among quantifiers

Start point: $$(¬∀x P(x) ∨ ¬∀y Q(y)) → ¬∃x G(x)$$ Implication to Disjunction (DeMorgans Laws): $$¬(¬∀x P(x) ∨ ¬∀y Q(y)) ∨ ¬∃x G(x)$$ Now I am at the point where I need to move in the negations to ...
2
votes
3answers
43 views

Is the order of four quantifiers in a predicate formula relevant?

Is the formula: $$\forall x \exists y \forall z \exists u (F(x) \lor G(y) \to F(z) \lor G(u))$$ Equivalent to formula: $$\forall z \exists u \forall x \exists y (F(x) \lor G(y) \to F(z) \lor ...
4
votes
1answer
69 views

Rules for translating quantifiers to set operations?

I had this excercise in measure theory where I had to show that certain sets are measurable and I realized there was some mechanical procedure going on. Here is the question: Let $f_n:X\to ...
0
votes
1answer
10 views

Use quantifier to express each of the following statements symbolically

Let F(x,y) be the statement x can fool y, where the domain of discourse for both x and y is all people. Use quantifier to express each of the following statements symbolically. Then write the negation ...
1
vote
1answer
74 views

Is $\lnot\forall x\;\lnot\forall y\;A$ the same as $\forall x\;\forall y\;A$?

Is $\lnot\forall x\;\lnot\forall y\;A$ the same as $\forall x\;\forall y\;A$? And if so, by what rule? I am trying to find a rule where the above would apply. I am currently using Hilbert deduction ...
1
vote
0answers
38 views

Predicate Logic and Negation Assistance

I just want to make sure I'm on the right path with these: Using the predicate symbols shown and appropriate quantifiers, write each English language statement in predicate logic. (The domain is ...
1
vote
1answer
38 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
28 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
20 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
37 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
45 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
25 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
45 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
51 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
40 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
28 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
48 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
54 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
48 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
45 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
31 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 ...
1
vote
1answer
41 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
45 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
66 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
35 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
57 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
42 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
37 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
26 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
36 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
29 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
24 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
85 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
42 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
85 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 ...