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

learn more… | top users | synonyms

1
vote
1answer
29 views

Negation of a Statement with Quantifiers — If Then?

I need to find the negation of a statement on my homework, specifically problem 19 of secton 3.2 in Discrete Mathematics with Applications by Susanna Epp. The problem is as follows: \begin{align} ...
1
vote
1answer
35 views

Order of quantifiers

I was reading about quantifiers from this book. I decided to jot down all implications due to different orders of quantifiers. While talking about the orders of the quantifiers the author states ...
1
vote
1answer
34 views

Convert universal quantification to existential quantification

I came across following problem "Every intelligent student is not honest." And I have to convert this in quantifiers. Straight conversion will be: ∀x [(S(x)∧I(x)) → ¬H(x)] ...(i) However the ...
1
vote
1answer
24 views

Using quantifier get truth value

In each case below say whether the given statement is true for whcih universe $(0,1)={{(x\in R: 0<x<1})}$ $[0,1]={{(x\in R: 0\le x \le1})}$ $\exists y(\forall x( x>y)$ This means there ...
0
votes
1answer
20 views

Show every boolean combination of $\mathcal{L}$-formula is equivalent one with quantifiers.

This is part 2 of a question I asked here: Prove this claim about language and structures. The setting is that suppose $\phi_1,\ldots,\phi_n$ are $\mathcal{L}$-formulas and $\psi$ is a Boolean ...
0
votes
1answer
36 views

Why are conjunctions used with existentially quantified sentences? [closed]

Why can we not use implication with existentially quantified sentences? Why can we only use conjunction?
5
votes
4answers
189 views

How can we say two algebraic expressions are “equal” if one is undefined at certain points and the other isn't?

I'm trying to understand why it is that we can say $\frac{x^2-1}{x-1} = \frac{(x-1)(x+1)}{(x-1)} = x+1$ but then have it also be the case that the two functions $f(x) = \frac{x^2-1}{x-1}$ and ...
1
vote
1answer
26 views

Question about equivalencies when using the existential quantifier

I'm currently in a boolean algebra class, and we are asked if the statement: $$ \exists xM(x) \wedge \exists xD(x) $$ is a proposition. Although I know that it is a proposition, I was wondering if ...
1
vote
3answers
43 views

Quantified Statement - Is this true and why/why not?

$\left(\forall x\in\mathbb R\right)\left(x^2+6x+5\geq 0\right)$. I originally was thinking false because when you factor this quadratic equation, it equals zero when $x$ is $-1$ and $x$ is $-5$. ...
0
votes
0answers
16 views

Will this predicate be true over all of the domain, as specified by quantifier?

This is a problem from Discrete Mathematics and its Applications My question is about 27a. I know what the nested quantifier is saying - for every integer n, there exists an integer m that is ...
1
vote
2answers
32 views

How to iterate through all the possibilities in with this quantifier?

This is a problem from Discrete Mathematics and its Applications My question is on 9g. Here is my work so far I am struggling with the exactly one person part. The one person whom everybody loves ...
1
vote
3answers
82 views

What’s wrong with this proof that $5$ is prime?

I’m reading How To Prove It and I’m confused as to how the proof of “$x$ is prime” is correct. I've written proof given below and also my conclusion after substituting in values for $x$, $y$ and $z$: ...
2
votes
1answer
40 views

More than one quantifiers for one variable: $\forall x\exists x P(x)$

I couldn't find any definiton about this: $\forall x\exists x P(x)$ Is here the for all or the there exists stronger? Cheers
0
votes
1answer
29 views

How to express exact quantifier in this situation?

This is a problem from Discrete Mathematics and its Applications My question is on 10g. Here is my work so far. My logic behind this is to first iterate over all peoples in the world, for each ...
1
vote
1answer
33 views

Would including the outside quantifier make more sense/be logically correct?

This is a question from Discrete Mathematics and Its Applications. My focus/question is 1b. What I got was for this question was (English translation) There is a student in your class who has sent ...
0
votes
1answer
24 views

Is my inference based on previous assumptions correct?

This is to check my work on a problem from Discrete Math and Its Applications. Here is the problem. My question is on part d. I would say that c does not follow from a and b because it is true that ...
0
votes
1answer
47 views

Negation of quantifiers

Prove the following statement on negation of quantifiers: Statement: To negate a statement of the form $$ Q_1x_1 Q_2x_2 \ldots Q_nx_n\; P(x_1,x_2,\ldots,x_n), $$ where $Q_i$ is $\forall$ or ...
0
votes
1answer
43 views

Predicates and Quantifiers in discrete math

Let P(x,y) be "x is waiting for y", where the universe of discourse is the set of all people in the world. Use quantifiers to express the following statement. (i)There is no one who is waiting for ...
5
votes
1answer
44 views

Is there a syntax for type quantification in higher order logic?

I'm trying to understand higher order logic deduction, and I sort of understand how after going to third order logic and higher you have a type explosion; predicates and functions can have a large ...
2
votes
1answer
55 views

Does order of qualifiers matter in FOL formula?

In preparing for an exam, I'm working through old exam questions and am now trying to figure out if the following first-order formula is valid. FYI, $m$ is a binary predicate. $$(\forall x \,\exists ...
3
votes
1answer
70 views

Re-writing “Everybody loves somebody” and variants in symbolic logic.

Right now I'm working on a set of questions and I came across a two-parter that confused me a bit with the way it was asked. The question is simply put as such: ...
3
votes
1answer
67 views

Would this be an acceptable translation of the English statement as well?

This is an except from my textbook (Discrete Mathematics and Its Applications 7th Edition) This was my initial stab at the problem (with domain of both variables being all real numbers) Would it ...
1
vote
1answer
28 views

Would these two statements be logically equivalent?

This is an excerpt from my textbook(Discrete Mathematics and Its Applications 7th edition) When I tried doing this example on my own, my answer was "There is a student x in this class and that ...
1
vote
2answers
37 views

Can we ignore predicates in a statement if they aren't used?

Prove/disprove: $$\forall a>0:a\in\mathbb R: \exists N\in\mathbb R:\forall x\in \mathbb R:\exists z\in\mathbb R:\forall n\in \mathbb N:|n-99|<N\Rightarrow n>10 \vee \frac {n^2} 4 \le 25$$ ...
1
vote
2answers
85 views

Clarification regarding Drinker's paradox [duplicate]

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
50 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
41 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
42 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
24 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
28 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
44 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
74 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
18 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
75 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
45 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
41 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 ...
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
38 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
20 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
48 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
27 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
72 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 ???
1
vote
1answer
55 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
44 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
30 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
16 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
61 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 ...