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

learn more… | top users | synonyms

1
vote
2answers
20 views

Universal Instantiation and Proof of: if $x$ and $y$ are odd integers, then $xy$ is odd.

I have a question about the first part of the proof for the statement "If $x$ and $y$ are odd integers, then $xy$ is odd" if we are using a direct proof. Now i've gotten the proof roughly correct but ...
0
votes
1answer
21 views

finding a DNF with an expression that contains quantifiers

I am supposed to use equivalencies to find the prenex DNF for the wff: $\exists xp(x) \land \exists xq(x) \rightarrow \exists x(p(x) \land q(x))$ It's been awhile since I've done something like this ...
0
votes
2answers
24 views

Changing (enlarging) the domain in a Quantified statement

I would like to ask the following. If we have the proposition $$\forall x\in\mathbb{R}^{+}(x^2>0)$$ and we wish to use as a domain the $$\mathbb{R}$$ instead. Is it correct that it will translate ...
2
votes
1answer
12 views

Nested Quantification of exactly one.

Suppose my domain is "All students in the class" and P(x, y):= x has emailed y. So, how do i define: Every student has emailed exactly one student. Exactly one student has emailed every one. A ...
1
vote
0answers
18 views

Symmetric and transitive relation definition problem

Mathematical definitions and notation really confuse me. For example, a definition similar to the following can be found in many textbooks and online: In mathematics, a binary relation R over a ...
1
vote
1answer
22 views

Translating Mathematical (Universal/Existential Quantifier) Statements into English?

Can anyone confirm if I have these correct? Or if not, where I am going wrong? Translate these statements into English, where $K(x)$ is '$x$ is a Kangaroo' and $H(x)$ is '$x$ hops' and the domain ...
0
votes
2answers
51 views

Quantifier notation: $\forall n \implies \cdot$ versus $\forall n, \cdot$

I'm not sure which of the following two notations is the correct one (or, are both correct?). I've seen both being used by different professors. $\forall \varepsilon > 0\ \exists \bar n \colon ...
0
votes
0answers
109 views

Is the establishment of the validity of this argument correct?

I am trying to show that the following argument is valid. There is an email that is sent but it is not saved in the inbox. All emails are saved in the inbox or the inbox is full. If the inbox is ...
2
votes
2answers
42 views

nested quantifiers (exactly one questions)

Express this statement using quantifiers, without using the uniqueness quantifier."There is exactly one student in this class who has taken exactly one mathematics class at this school" T (x, ...
0
votes
3answers
21 views

Statements involving quantifiers

I am confused regarding the following; If we have a statement, for example, $$\exists_{x} \in X, \forall_{y} \in Y, x + y = 0.$$ Now, I'm wondering if you could just choose $x$ as $-y$, or do you ...
1
vote
1answer
25 views

Shifting bounded quantifiers

The universe of the following variables are the natural numbers $\mathbb{N}$. I found in the literature the following logic equivalence: $\forall n < k \exists m \ \varphi(m,n) \leftrightarrow ...
0
votes
1answer
18 views

Restricting universal quantifiers with conditions?

I want to express "For every $x\in\mathbb R$ that has (at least) one $p\in\mathbb Z$ and $q\in\mathbb N$, such that $x=\frac pq$, $x\in\mathbb Q$ is true" with logical quantifiers, just like this ...
1
vote
1answer
22 views

$∀x(N(x)→∃y∃x(N(y) ∧ x ≥ y))$ - bounded variables

Using this formula I am trying to see which variables are bounded by which quantifiers. $∀x$ universal quantifier bounds all the $x$'s in the formula as they are all within its bracket. However, does ...
2
votes
2answers
30 views

Express statement “not every student in this class will pass the Discrete Mathematics”

I have a bit of a problem with this question: Express the following statement using predicate function(s), existential or universal quantifier, and/or negation. “not every student in this ...
1
vote
1answer
60 views

Is there a definition of the existential quantifier which does not imply the axiom of choice?

The definition of the existential quantifer given in Bourbaki's Theory of Sets is $$(\exists x)R \iff (\tau_x(R)\mid x)R.$$ Here $x$ is a letter, $R$ is a relation, and $(\tau_x(R)\mid x)R$ means ...
1
vote
0answers
41 views

Relations between statements involving universal quantifier, conditional and biconditional

If we consider two predicates: $b(x)$: x is a boy $c(x)$: x is clever Then, there are four statements involving $∀, b(x), c(x), →$ and $↔$ . These are below along with my interpretation of their ...
2
votes
1answer
66 views

Rules of distribution of quantifiers over conditional and biconditional

Which of the following propositional logic statements are true and why? $(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x)))$ $(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x)))$ $(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))$ ...
2
votes
2answers
44 views

Naive Question About Quantifiers: for all, for some, where, and given…

I was bumped into a question related to quantifiers: and was wondering if anyone can give me a further explanation for the following four statements: Let $f: \mathbb{R} \to \mathbb{R}$ be a function, ...
0
votes
1answer
37 views

Conversion To prenex normal form with ∃xα ∨ ∀x(β)

The algorithm I use is the one on this page But does this algorithm actually handle the following 6 cases? ∀x(α) ∧ ∀x(β) ∀x(α) ∨ ∀x(β) ∃x(α) ∧ ∃x(β) ∃x(α) ∨ ∃x(β) ∀x(α) ∧ ∃x(β) ∀x(α) ∨ ∃x(β) If ...
5
votes
3answers
112 views

A proof of $(\forall x P(x)) \to A) \Rightarrow \exists x (P(x) \to A)$

I recently asked this question. In that question I presented a hand-waving proof as part of the question. There was some confusion as to the validity of my hand-waving proof. So I wanted to make it ...
1
vote
1answer
36 views

Where to make a conjunction instead of an implication?

We have this statement in natural language: Benjamin hates all politicians. I suggested this formula: $$ \forall X ( politician(X) \Rightarrow hate(benjamin,X)) $$ But our teacher has written ...
0
votes
1answer
18 views

Logic formalization for Perfect Graph Matching problem

A matching $M$ in a undirected graph $G(V,E)$ is a subset of the edges of $E$ such that no two edges in $M$ are incident to a common vertex. A perfect matching ${M}'$ is one in which every vertex is ...
0
votes
1answer
17 views

Translating from predicate formula into English

$\left ( \forall x \right )\left [ P_{x}\Leftrightarrow \left ( \forall y \right ) \left [ Q_{xy}\Leftrightarrow \sim Q_{yy} \right ] \right]\Rightarrow \left ( \forall x \right )\left [ \sim P_{x} ...
0
votes
0answers
48 views

Quantificational Logic: “For every number a, the equation $ax^2 + 4x -2 = 0$ has at least one solution if and only if $a \ge -2$.”

This is a solution check for my quantified representation of the following statement. "For every number a, the equation $ax^2 + 4x -2 = 0$ has at least one solution if and only if $a \ge -2$." ...
12
votes
6answers
836 views

Quantifier: “For all sets”

I've seen the following statement a few times: "Let $A$ be a set, then $\emptyset\subseteq A$". Or, written 'more formally': $$ \forall A\,\, \emptyset\subseteq A $$ My doubt is: I've ...
0
votes
0answers
26 views

Model-finding: negated quantifiers

I want to find a model and a countermodel for the following formula: $¬∀a¬∃b((P(a)∧P(f(b)))→Q(f(f(b))))$ I tried: Model 1: $A = \{x, y\}, P^M = \{x,y\}, Q^M = \{x\}, f(b) = b$ which satisfies the ...
1
vote
1answer
33 views

Negation of existential quantifiers, functions in first order logic

I know the following rule: $\lnot \forall a (P(a)$ means $\exists a \lnot P(a)$ and $\lnot \exists a (P(a)$ means $\forall a \lnot P(a)$ But what if the problem is something like: $\lnot \forall ...
0
votes
1answer
23 views

Does the two first order formula interprets to same meaning?

[∀x,β → α(x)] [β → (∀x,α(x))] Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable.
1
vote
1answer
296 views

proving the validity

I need to prove the validity of the formula: $Q= \forall x \forall y \forall v \ F(x,y,f(x,y),v, g(x,y,v)) \rightarrow \forall x \forall y \exists z \forall v \exists u \ F(x,y,z,v,u)$ I thought the ...
1
vote
0answers
42 views

Existential and Universal Equivalence Proof

Taking ¬∀x:X.r≡∃x:X.¬r Is there a way of actually formally proving this? Not implementing it but proving how to go from a negated universal quantifier to a an existential with a negated element... ...
2
votes
1answer
68 views

Stack semantics for the layman

I am trying to read bits and pieces of Ingo Blechschmidt's notes on using the internal language of toposes in algebraic geometry. I have not studied the internal language. I only have a bare bones ...
0
votes
2answers
25 views

Logical equivalences with the universal quantifier

I am required to show that $\forall(x \in A)P(x) \lor \forall(x \in A)Q(x)$ is logically equivalent to $\forall(x \in A)\forall(y \in A)(P(x) \lor Q(y))$. I'm not quite sure how to proceed, mostly ...
-1
votes
1answer
44 views

Decide whether logical formula is a tautology [duplicate]

How do we decide whether the formula in predicate logic is a tautology? Is there some universal way to decide and prove it? Let's have an example: $$ \forall x \forall z \exists y\,(P(x,y) \lor ...
0
votes
0answers
81 views

Which of the following statements is always TRUE?

Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE? $\left(\left(\forall x \left(P\left(x\right) \vee Q\left(x\right)\right)\right)\right) \implies ...
3
votes
3answers
88 views

Why the ordering of the quantifiers matters here?

$\newcommand{\fool}{\operatorname{fool}}$I want to transfer the statement You can fool all the people some of the time into predicate logic. Now I am using fool(X,T) to mean that I fool person ...
0
votes
3answers
44 views

what is the difference between ∀x∈ℝ, ∀ε>0, (|x|≤ε ⇒ x=0) and ∀x∈ℝ, ((∀ε>0, |x|≤ε) ⇒ x=0)

I am supposed to Prove or disprove: ∀x∈ℝ, ∀ε>0, (|x|≤ε ⇒ x=0) and: ∀x∈ℝ, ((∀ε>0,|x|≤ε) ⇒ x=0) I think I understand how to prove the second one (by contradiction) but I don't understand what makes it ...
0
votes
3answers
43 views

translating logical quantifiers

Let a = “A is working,” b = “B is working,” and c = “C is working.” Write the three status reports in terms of a, b, and c, using the symbols of formal logic. Processor A reports that Processor B is ...
-1
votes
1answer
51 views

Distributive Property of Quantifiers

I know that given $$ \forall x \;\; P(x) \wedge \forall x \;\; Q(x) $$ can be simplified to $$ \forall x \;\; (P(x) \vee Q(x)) $$ but does the same apply if its $ \neg \forall x P(x) \wedge ...
0
votes
0answers
48 views

Converting to Clauses

Convert the following into clauses. Show all of your steps. (a) ∃x ∀y L(x,y) (b) ∀x ∃y L(y,x) (c) ∀x ∀y ((H(x,y) ∧ F(y)) ⇒ (¬∃z (H(x,z) ∧ S(z)))) (d) ∀z {Q(z) ⇒ {¬∀x ∃y[P(y) ⇒ P(g(z,x)) ] }} I've ...
1
vote
1answer
20 views

Existential quantificator vs conjunction in intuitionistic logic.

It's well-know that in classical logic the following equivalence hols: $$\exists x(P\wedge Q(x))\iff P\wedge\exists xQ(x)$$ where $x$ is not free in $P$. I ask if the same equivalence holds in ...
0
votes
1answer
19 views

Symmetry of Predicate and Universal Quantifiers

$$ \forall x \forall y P(x,y) \implies \forall x \forall y P(x,y) \land P(y,x) $$ I guess the above statement is valid but no idea how to formally prove it, any idea?
2
votes
2answers
94 views

Natural deduction proof for $\exists x(\exists y A(y) \rightarrow A(x))$

I spent a long time trying to find a natural deduction derivation for the formula $\exists x(\exists y A(y) \rightarrow A(x))$, but I always got stuck at some point with free variables in the leaves. ...
0
votes
0answers
48 views

Sentences and Quantifier Rank

Suppose we have a (first-order) sentence, having quantifier rank $q$. How can we prove that it is equivalent or not equivalent to a logical sentence of rank $p$, with $p \lt q$? Say for example: $$ ...
0
votes
1answer
14 views

Translate Quantified FOL Statement into English

I am busy having a war with Tarski's world but I'm obviously not winning right now. I have the following sentence ∀x ∀y ∀z [(Cube(x) ∧ Cube(y) ∧ Cube(z)) → (x=y ∨ x=z ∨ y=z)] On my world I have ...
0
votes
1answer
45 views

Understanding Scope of Quantifiers

I have a set of questions below that I'm trying to logically work my way through. I have ideas about each but I'm not sure if I'm correct. Any advice would be most welcome! Thanks so much! 1) I know ...
0
votes
1answer
45 views

How does Universal/Existential instantiation work with multiple statements?

So, say you're given ∃x P(x) and ∀x Q(x)-->˜P(x). I want to use this given statements in a formal proof. To manipulate them in the way I want to, I believe I need to use instantiation to remove the ...
1
vote
2answers
29 views

Find a model for the given WFF

Find a model for the given WFF: $\exists xp(x) \rightarrow \forall xp(x)$ I'm interpreting this as saying "There exists an x in the function p(x) which implies For all X in p(x)? So my solution ...
1
vote
2answers
65 views

$\forall x[P(x) \vee Q(x)]$ is not $\equiv (\forall xP(x) \vee ∀xQ(x))$

I have a question from a discrete math text, Determine whether $\forall x[P(x) \vee Q(x)]$ and $\forall xP(x) \to \forall xQ(x)$ have the same truth value. Thus far using the definitions from my ...
1
vote
2answers
49 views

order of quantifiers and effect on the strength of logic statement

I was looking at the following question: which is the stronger logic statement The original poster provides two statements with the only difference being the order of the quantifiers as follows: ...
0
votes
1answer
33 views

Quantification Using Biconditional

The question I am trying to reason about is as follows: let L(x,y) be the statement "x loves y" ...