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
1
vote
1 answer

How to prove the expressiveness of first-order logic formulas with equality over the empty signature?

How can one prove that every first-order-logic formula with equality over the empty signature is equivalent to either False, or "there are exactly n elements in the domain", or "there are at least n elements in the domain"?
Udi
  • 11
1
vote
1 answer

Meaning of "If $X$ then $Y$ unless $Z$"

If $X$ then $Y$ unless $Z$ is represented by which of formula in propositional logic? I am getting confused between $X\rightarrow \left ( Y\wedge \sim Z \right )$ and $\left ( X \rightarrow Y\right )\wedge \sim Z$. Is it represented by any other…
Romy
  • 279
1
vote
2 answers

Decision procedure vs Proof system in Predicate Logic

I recently started reading Logic in Computer Science and in section 2.5 the authors talk about decision procedures. They state in Theorem 2.22, "The decision problem of validity in predicate logic is undecidable: no program exists which, given any…
Kona
  • 11
1
vote
1 answer

Proving that if $x^2+y^2+xy=x+y$, then $0\le x+y\le \frac 43$ for $x,y\in\mathbb R$.

So the question I've been trying to solve is : for $(x, y)$ in $R²$ $x^2 + y^2 + xy = x + y \Rightarrow 0 \le x + y \le \frac{4}{3}$ I've tried two things so far : I have put $t = (x+y)$ so the first equation becomes $t² -t -xy = 0$ this means…
enzo
  • 113
1
vote
0 answers

Predicate logic proof, can't get to the right solution

So I have tried to make a solution for a predicate logic proof, and would like if someone could give a hint to come to the correct proof. I already know that Line 11 is incorrect since it only holds in the assumption. And the same for line 9,…
Tjavsi
  • 11
1
vote
1 answer

Claiming truth value of predicate statements

For each of the following claims, state whether it is true or false. If an assertion is true, either give a carefully reasoned argument to show that it is true, or prove it formally. If an assertion is false, give an appropriate counterexample,…
Helpsun
  • 43
1
vote
1 answer

Solving truth value of predicate calculus statements(Just the approach)

Which of the following predicate calculus statements is/are valid? $$\forall x, P(x)\lor \forall x,Q(x) \Rightarrow \forall x, (P(x)\lor Q(x))$$ $$\exists x, P(x)\land \exists x, Q(x) \Rightarrow \exists x, (P(x)\land Q(x)) $$ $$\exists x,…
bandit_king28
  • 403
1
vote
1 answer

In predicate logic, all $x$ in set $X$ who have quality A also have quality B

How do I convert the premise that all $x$ in set $X$ for which $A$ is true $\implies B$ is also true the main part where I am having trouble finding examples is "all $x$ in set $X$ for which $A$ is true"...I can do there exists $x$ in $X$ for which…
Chris
  • 488
1
vote
1 answer

Predicate logic with negation "not"

I've really confused myself here: $$ P(x) = ``\text{x has a tail}" $$ How would I write: $$ ``\text{Not everything has a tail}" $$ would it: $$ ¬∀x P(x) $$ be correct?
Feath
  • 47
1
vote
1 answer

Using predicate logic to see if P(X) holds

Suppose We have a set called ${A}$ and we let it equal to $A = \{a \in \mathbb{Z} \mid a^2 = 3\}$ and we let ${P(x)}$ be the predicate ${x \in \mathbb{Z} }$ Problems: 1.) ${\forall x \in A }, P(x)$ 2.) ${\exists x \in A }, P(x)$ Reasoning: For both…
Deathslice
  • 261
1
vote
2 answers

Existential quantifier equivalent of a universal quantifier statement.

My question is this, for the following sentence: Every pet has an owner , when translated into predicate logic gives $\forall x\enspace(P(x) \rightarrow O(x))$, but what is the equivalent with a $\exists x$ instead of $\forall x$? Is there a general…
user4357505
  • 35
1
vote
1 answer

Can I define a predicate over a set and use it in the definition of another one?

Let's say I have two sets $A$ and $B$, and a relation $R \subseteq A \times B$. $R' \subset R$. Can I define a predicate $P(R) = \forall a \in A, \exists b \in B, (a,b) \not\in R$ And then define another set $X = \{ (a,b) | (a,b) \in R, P(R')\}$…
firas
  • 135
1
vote
1 answer

Valid logical statements

I was wondering if the following is a valid statement: $\forall x \exists y\ (y\neq x)\ P(x,y)$, where P(x) is 'x is the parent of y' and the domain of x and y is the set of all animals. I am specifically referring to the part '$(y\neq x)\ P(x,y)$'.
fast-and-last
  • 21
1
vote
1 answer

Convert English to logic

How to write the following sentence using propositional logic: Only monkeys properly appreciate the value of art. Is this good: Let $M(x)$ be '$x$ is a monkey' and $A(x)$ be '$x$ properly appreciates the value of art', where the domain of $x$ is the…
fast-and-last
  • 21
1
vote
1 answer

Use of symbols in predicate calculus

Consider the following quantified proposition: $$\exists x\ : R(x) \land T(x) $$ where $R(x)$ is 'x likes to paint in red,' $T(x)$ is 'x likes to live on a tree,' and $x$ is the domain of all monkeys. Is the following a valid restatement of the…
nightmarish
  • 617
1 2 3
…
22 23