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

learn more… | top users | synonyms

0
votes
0answers
19 views

Can First Order Logic identify that two variables are the same object?

Supposed I defined: $Px$ = $x$ is a person $Lxy$ = $x$ loves $y$ And I expressed that everyone loves someone: $$(∀x)(Px \implies (∃y)(Py ∧ Lxy))$$ However I want to formally exclude narcissists ...
3
votes
1answer
67 views

Does “Everyone loves all kittens” imply “Everyone loves a kitten”?

In my logic class, we explored whether various quantified statements implied others. We agreed that the statement "Everyone loves everyone" implies that "Everyone loves someone": $Px$ = $x$ is a ...
1
vote
1answer
20 views

Discrete Structures: Trying Correcting my Predicate Logic with the appropriate quantifiers

I am trying to correctly use predicate symbols and using the appropriate quantifiers were I have to write each English language statement in predicate logic and the domain is the whole word. $P(x)$ ...
0
votes
0answers
28 views

Adding Sentence Variables and Quantifiers to Formal Languages

I have been thinking about the following construction, and was contemplating investigating it for my undergraduate thesis: Let $L$ be a formal language, e.g. the set $\{x_1, x_2, \dots, \forall, ...
0
votes
0answers
10 views

How to use a predicate function when formalizing predicate propositions?

I've tried the following question from my maths assesment but not sure if I'm using the predicate, fool(p,t) correctly. Can anyone advise on if I'm using it ...
1
vote
2answers
52 views

for some or for all

The following text is from Velleman's How to Prove book from the reflexive closure section: According to the definition we gave in the last section, the ...
0
votes
0answers
14 views

Problems of Quantifiers

Translate the following natural language sentences to quantified statements. Then apply the negation on them so that no negation sign appears to the left of a quantifier. Then express the most ...
0
votes
2answers
27 views

Truth Value for Quantifier

What would be the truth value for the following two quantifiers if n and m are both integers? I have trouble proving each of these statements. I appreciate any help you can provide! a)   ...
3
votes
1answer
43 views

How to prove $(\forall x,y\in\mathbb{Z})(5\nmid xy\to(5\nmid x\land 5\nmid y))$

Question: Prove $x,y\in\mathbb{Z},\Bigl((5\nmid xy)\to(5\nmid x\land 5\nmid y)\Bigr)$ where $\forall a,b\in\mathbb{Z},\bigl((a\nmid b)\leftrightarrow(\forall k\in\mathbb{Z},b\neq ak)\bigr)$ and ...
0
votes
2answers
32 views

Order of logical quantifiers within a statement

I understand that the order of the quantifiers of a statement determine the truth value of statement. For example, $$\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\ \text{such that}\ ...
1
vote
1answer
35 views

Quantifiers for mutually distinct variables

Okay, this is freaking me out, I'm going nuts. In a first-order condition with formula $\phi$ containing $x, y$ such as $\forall x\forall y . \phi$ I need to ensure that the second variable bound ...
0
votes
0answers
21 views

quantization of a discrete probability source

The alphabet of a memory less source is $A=\{-5,-3, -1, 0, 1, 3, 5\}$ with corresponding probabilities $\{0.05, 0.1, 0.1, 0.15, 0.05, 0.25, 0.3\}$. If I know that the source can be quantized ...
2
votes
2answers
90 views

Quantifier for “there is at most one”?

As "there is at least one" and "there is exactly one" both have their symbols, I wonder what is the common notation for "there is at most one"? By "common" I mean the desired notation can be used ...
2
votes
0answers
24 views

Prenex normal form of $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$

I have the statement $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$ and I have to write it in prenex normal form. First I use the second De Morgan law $\neg \big(\forall x \ P(x) \vee ...
0
votes
2answers
61 views

What is the truth value of $\exists ! x \ (x=x+1)$? [closed]

What is the truth value of this statement? $\exists ! x \ (x=x+1)$
1
vote
0answers
17 views

Universal Instantiation

I'm a bit confused about how Universal Instantiation works. I read that you shouldn't really plug in any value "a" for x in "For all x P(x)" unless a choice for "a" pops up in the givens but in the ...
2
votes
2answers
50 views

How do I show that $\forall x \ P(x) \vee \forall x \ Q(x)$ and $\forall x (P(x) \vee Q(x))$ are NOT logically equivalent?

Show that $\forall x \ P(x) \vee \forall x \ Q(x)$ and $\forall x (P(x) \vee Q(x))$ are not logically equivalent. Can someone give a hint?
1
vote
1answer
41 views

$P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations.

Suppose that the domain of the propositional function $P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations. a) ...
2
votes
0answers
27 views

When does renaming bound variables require a fresh variable?

Suppose that $E_1$ and $E_2$ are two $\alpha$-equivalent first-order logic formulas (or $\lambda$-terms), and let $V$ be the set of all variables (free and bound) used in $E_1$ or $E_2$. Is it ...
0
votes
1answer
56 views

Prove DeMorgan's Theorem for indexed family of set using logic quantifiers

I need to prove both general union and intersection for indexed family sets using logic quantifiers, this is the prove i've written but i'm not sure if its correct: Thanks for help.
2
votes
2answers
67 views

Which variables are free in $\forall x (\exists y (x < y+z) \to \exists z (x < y+z))$?

anyone could explain for me, why $x,y,z$ is bound variable in this formula? $ \forall x [ \exists y (x < y+z) \to \exists z (x < y+z) ] $ I think $y,z$ is free variable.
2
votes
2answers
36 views

Have troubles with contradiction of a statement

"Suppose that there are 13 people in a room. Prove: "At least two of these people were born in the same month". Use the indirect method." The question I have is: Which of the following (if any) are ...
0
votes
1answer
11 views

Adding and subtracting variables which are part of an interval

I am following a paper proof which starts with the following constraint: $$\forall v \in [a,b], \forall \tilde{v} \in [a,b]$$ $$f_{i}(v) \geq f_{i}(\tilde{v}) + (v-\tilde{v})g_{i}(\tilde{v})$$ In ...
1
vote
1answer
27 views

For $p(x): x>0$, $q(x): \text{$x$ is even}$,$r(x): \text{$x$ is a perfect square},$ is $\forall x[r(x)\to p(x)]$ true?

Given $$p(x): x>0,$$ $$q(x): \text{$x$ is even},$$ $$r(x): \text{$x$ is a perfect square},$$ are the following statements true or false? a.) $\exists[p(x)\land q(x)].$ b.) $\forall x[r(x)\to ...
1
vote
3answers
53 views

Is $\exists x(P(x) \to Q(x)) \equiv (\exists xP(x) \to \exists xQ(x))$?

My intuition is that this statement is false and here is my proof. $\exists x(P(x) \to Q(x))$ $\exists x(\lnot P(x) \lor Q(x))$ using logical equivalence. $\exists x\lnot P(x) \lor \exists x Q(x)$ ...
1
vote
1answer
28 views

$(\forall (x,y) \in F\times G, \phi(x) \lor \psi(y) ) \Leftrightarrow (\forall x\in F, \phi(x)) \lor (\forall y\in G, \psi(y))$?

All the question is in the title: is the equivalency $$(\forall (x,y) \in F\times G, \phi(x) \lor \psi(y) ) \Leftrightarrow (\forall x\in F, \phi(x)) \lor (\forall y\in G, \psi(y))$$ true (where ...
0
votes
1answer
27 views

Prove the expression using deduction

$(\exists x)[A(x) \wedge B(x)] \rightarrow (\exists x)A(x) \wedge (\exists x)B(x)$ I realize that this is an equivalence but I am wondering how I might prove this. I feel like I would use ...
1
vote
2answers
42 views

Prove If $\forall x \in X((x,x) \in R)$ then $\forall x \in X \exists y \in X(x,y) \in R$

I have been solving one problem and at the end of the proof after performing some transformations, I have been left with this to prove: If $\forall x \in X((x,x) \in R)$ then $\forall x \in X \exists ...
1
vote
2answers
54 views

When existential quantifiers distribute over conjunction

I know that, generally: $$\exists x~~ (P(x) \land Q(x)) \implies \exists x~~P(x) \land \exists x~~Q(x)$$ But I wonder if is there any circumstances (by some restrictions of $P(x)$ and $Q(x)$) that ...
1
vote
2answers
39 views

Quantifiers for formal definition of a limit

I have a problem. I have to prove that $(\forall\,\epsilon > 0)(\exists\,\delta > 0)[0 < |x − a| < \delta \implies |f(x) − L| < \epsilon$ (formal definition of a limit) ...
0
votes
2answers
33 views

Difference between two statements/quantifiers?

1) $\forall \varepsilon > 0$, if $a + \varepsilon > b$, then $a > b$. 2) If $\forall \varepsilon > 0, a + \varepsilon > b$, then $a > b$. When I read these two statements, they ...
2
votes
2answers
43 views

How to define new constants in Tableaux Method of predicate logic

As you all know, in predicate logic when using Tableaux Method the quantifiers must be removed and their variables must be replaced with constants inside the relations and functions. The problem is I ...
0
votes
1answer
39 views

Translating a nested quantifier to plain English

Let Q(x,y) denote "x + y = 0". What are the truth values of the quantifications ∃y∀xQ(x,y) and ∀x∃yQ(x,y), where the domain for all variables consists of all real numbers? So from this ...
3
votes
1answer
75 views

$\exists x P(x)\land\exists x Q(x)$ is not logically equivalent to $\exists x(P(x)\land Q(x) )$

The textbook states that the solution is: Let P(x) be "x is positive" and Q(x) is "x is negative". The domain is integers. This shows $\exists x P(x)\land\exists x Q(x)$ is True and shows ...
-1
votes
3answers
35 views

Unique Existential Quantifier

The Unique Existential Quantifier states that there exists a unique $x$ which holds for a $P(x)$. I came up with $$\exists x\;p(x)\land\neg\exists y\;p(y)\land x\ne y\;.$$ How is this different ...
1
vote
4answers
59 views

Predicate Logic Negation Confusion

I have a question in my discrete math class that I was having some confusion with. If: N(x): x is a non-negative integer E(x): x is even O(x): x is odd P(x): x is prime Negate each sentence and ...
1
vote
1answer
30 views

Proof a quantified predicate logic statement

I am having trouble really understanding how to prove this $$(S(y) \to T(y)) \land S(x) \to (∃x)T(x).$$ My solution so far is: $S(y) \to T(y)$ --- Hypothesis $S(x)$ --- Hypothesis $T(y)$ --- ...
0
votes
0answers
44 views

Is ∃x in A||P(x) the same as ∃x||x in A=>P(x)?

If we wish to convert a statement of the form ∃x in A||P(x) into the form of an implication, would the correct conversion be ∃x||x in A=>P(x) Thanks
2
votes
2answers
45 views

Denotation of existence of $n$ distinct $x$ such that $P(x)$?

I have that $\exists!x:P(x)$ means that there exists exactly one $x$ where $P(x)$ holds; this is a more specific version of existential quantification with $\exists$. My problem stands like this. I ...
1
vote
0answers
55 views

Show if theory T is ∀∃-axiomatizable, then T has an existentially closed model.

Setting Definition $\mathcal{M} \models T$ is existentially closed if whenever $\mathcal{N} \models T$, $\mathcal{N} \supseteq \mathcal{M}$, and $\mathcal{N}\models \exists \bar{v} ...
1
vote
0answers
28 views

Order of Existential/Universal Quantifiers

I just wanted to check my answers for this because I'm still not that comfortable with it. Which of the following statements are true? (i) $(\forall x \in \mathbb R)$ $x+1>x$ (ii) $(\forall ...
5
votes
4answers
118 views

Interpreting the statement

Just started quantifiers, and I'm having some trouble with interpreting this. Here's what I understand: For every Epsilon $> 0$, there exists a Delta $> 0$ for all $x$ in $\mathbb{R}$. The ...
0
votes
1answer
34 views

Notation and Quantifiers

I was wondering what is a natural way to write certain formal expressions, without make them look too cumbersome. In particular, what I learned from various books is that, when we deal with the ...
3
votes
3answers
1k views

What is the meaning of ∀x(∃y(A(x)))

At first English is not my native language if something is not perfectly formulated or described I'm sorry. Could somebody please tell me what the generally valid statement of this is? $$ \forall ...
1
vote
2answers
39 views

Translating a sentence to predicate logic

I have the following sentence: "Everyone who has a tail is a dog" and its translation to predicate logic is: $$\neg\exists x \, ( \neg\text{dog}(x) \land \text{hasTail}(x))$$ I don't ...
0
votes
3answers
54 views

Universal quantifier distributes over implication

Is $\forall x \forall y: P(x) \to Q(y)$ the same thing as $(\forall x P(x)) \to (\forall y:Q(y))$ ? If not can someone give an example as to why it isn't? I'm not getting the whole ...
1
vote
1answer
37 views

How to formally express predicate statements?

I'm revising for an upcoming maths assessment for a theory of algorithms module, but I'm not entirely sure if my solutions to the below questions are correct. My main confusion with the questions is ...
4
votes
1answer
57 views

Express the quantified logical statements using the predicates

I just started learning predicates and quantifiers. I am pretty confused so I was wondering if someone can help me. Using the predicates $P(x)$ to denote “x is a pro baseball player”, $R(x)$ to ...
1
vote
1answer
56 views

Rewriting quantified statements using logical operators, but without using quantifiers.

I just need help verifying my answers cause I'm still not 100% what I'm doing at the moment! Let P and Q be predicates on the set S, where S has two elements, say,$ S = {a, b} $. Then the statement ...
0
votes
2answers
23 views

Translating a statement into a logical expression for two different domains.

I am given a statement like the following: Everyone in your class has a cellular phone I need to represent this twice, once for a domain of ...