Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [predicate-logic]

Questions concerning predicate calculus, i.e. the logic of quantifiers.

Some well-known formal systems covered by this term are

  • first-order logic, containing the quantifiers $\forall$ and $\exists$
  • second-order logic
  • many-sorted logic
  • infinitary logic
4144 questions
0
votes
3 answers

Nested Quantifiers true or false

I have a concern with nested quantifiers. I have: $$ \forall x \exists y \forall z(x^2-y+z=0) $$ such that $$ x,y,z \in \Bbb Z^+$$ My first question, can it be read like this: $$ \forall x \forall z \exists y(x^2-y+z=0) $$ The way I did it, is I…
Dimitri
  • 1,287
0
votes
0 answers

Is it correct to use variables that are not not quantified in my statement?

I want to find the truth value of this statement given that the domain of discourse is $\mathbb Z$: $$∃m∃n (2x+5y=y ∧ x+5y=3).$$ I am a bit confused whether the statement is correct or not since $x$ and $y$ are not quantified (we did not say $∃x$ or…
joumana
  • 1
0
votes
1 answer

Describe the union for some sets

Let's describe the union for the following sets using operations with predicates: $A=\{2n~| ~n\in\mathbb{N}\}$ , $B=\{2n+1~|~ n\in\mathbb{N}\}$ $A=\{x~|~ x\in\mathbb{R}, x>0\}$, $B=\{x~|~ x\in\mathbb{R}, x^2>0\}$ $A=\{4k ~|~ k\in\mathbb{Z}\}$,…
marinaaaa
  • 183
0
votes
2 answers

The converse of Euclid lemma : counter example?

Converse of Euclid lemma : if (p|ab implies p|a or p|b), then p is prime, where p,a,b are integers. But counter example that I have, 4|8*2 and 4|8 and 4∤2, then 4 should be a prime number, but it is a composite number. Please let me know, if it is…
Shivam Maurya 1729
  • 21
0
votes
0 answers

Prove $(\forall x (P(x) \to \exists y Q(x, y))) \to (\exists x P(x) \to \exists y Q(x, y))$

What I did was to first assume $$ \forall x (P(x) \to \exists y Q(x, y))$$ Assume a free variable $x_0$ then doing a universal quantifier elimination $$P(x_0) \to \exists y Q(x_0, y)$$ Now assuming $P(x_0)$ Using implication elimination $$ \exists y…
Aditya
  • 6,191
0
votes
0 answers

Prove the sequent $\exists x A(x) \to \forall x B(x) \vdash \forall x (A(x) \to B(x))$

I am unable to start the natural deduction process because I don't know how to parse the two different quantifiers on the LHS. A hint would be really helpful
Aditya
  • 6,191
0
votes
1 answer

Existential generalization of a statement function.

( x )( Ax —> Bx) Ay —> By ( ∃x )(Ax —> Bx) Line 1 is the premise, line 2 is obtained through universal instantiation of line 1 and line 3 is obtained through existential generalization of line 2. Is the inference at line 3 valid? I read in my…
Ahmad Eldesokey
  • 57
0
votes
1 answer

Predicate logic - Symbolize the sentence

I am a little confused about this sentence. How can I symbolize it? Let P(x), L(x), R(x,y,z), and E(x,y) represent "x is a point," "x is a line," "z passes through x and y," and "x = y," respectively. Translate the following: For every two…
Maktavish
  • 1
0
votes
1 answer

How can the definition of an Indexed Set be explained in terms of predicate logic?

I'm learning about indexed sets and came across the definition of an indexed set to be, "...any set,such that for $i \in I$, we have a set $A_i$ ...how would this definition be written using quantifiers? Please let me know if this definition is…
NotBadG
  • 19
0
votes
1 answer

How to express "at most 2" or "more than 1" in predicate logic?

There is another question about expressing "at most one", but it extremely specific and doesn't seem applicable to other cases. For example, "for all smurfs, at most 2 of them are angry." How would you express such a statement in predicate logic?…
Curulian
  • 337
  • 1
  • 6
0
votes
0 answers

Formulate a graph with no cycles in predicate logic

Let $G$ be a graph, which must have at least one node, i.e. the set of nodes and edges cannot be empty. Let $R$ be a symmetric and irreflexive relation for $G$ and each vertex. I would like to build a formula, such that if a graph $G$ with $n \geq…
kklaw
  • 301
  • 1
  • 9
0
votes
1 answer

Math logic versus Semantic Web use of predicate

When I see any sort of mathematical logic treatment of a predicate, it typically says something like $G(x)$ where $G$ stands for, e.g. "is the color blue" and the $x$ will be the subject or variable that, when evaluated, becomes a proposition either…
147pm
  • 920
0
votes
1 answer

Converting Predicate Logic Statement to Negation in English

I'm working on some Predicate Logic and want to express a proposition in English into the negation. The statement is: "Everyone who has not read a book is dumb" My question is: Is the negation of this statement - "Some people who have read a book…
LiteralJumpingAddition
  • 5
  • 1
0
votes
1 answer

Prove $\vdash\forall x(\alpha\rightarrow\beta)\rightarrow(\alpha\rightarrow\forall x\beta)$ in Enderton's system

$\vdash\forall x(\alpha\rightarrow\beta)\rightarrow(\alpha\rightarrow\forall x\beta)$ According to Enderton p.121, it suffices to show that: $\{\forall x(\alpha\rightarrow\beta),\alpha\}\vdash\beta$ For then, Enderton suggests, we can derive the…
beachtrees
  • 209
0
votes
1 answer

Prove whether a non-numeric predicate statement is true or false while giving reasons?

I am studying discrete math at university. However, the materials don't seem to explain non-numeric predicate statements in much detail. I am asked to prove that a predicate statement is false using nested quantifiers and give reasons. The statement…
Arnel Jan Sarmiento
  • 13
1 2 3
…
22 23