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

AND, OR operators inside implications

$$A \lor B \implies C$$ To prove this, is it sufficient to show that A implies C OR that B implies C? This would seem most intuitive to me, but my lecture class today said that I would be required to show that A implies C AND that B implies C.
Wishiknew
  • 15
  • 3
1
vote
1 answer

Are these two predicates equivalent (and correctly formed)?

For all x there exists a y where if x is prime, it is less than or equal to y and y is prime. $\forall x \exists y\space (prime(x) \implies x \leq y \land prime(y))$ There exists a y for all x where if x is prime, it is less than or equal to y…
user12501923
  • 13
1
vote
1 answer

How do I write the following mathematical statement as a predicate logic formula?

The mathematical statement that I has to write as a predicate logic formula in the language L = {<, =, f}, where f is unary function, is the following: "Strictly increasing function doesn't have a maximum." I have an idea but I am not sure if it is…
TKN
  • 757
1
vote
1 answer

Please check my predicate logic answer

I have a been working on a predicate logic question and wondered if someone could check my answer and possibly point me in the correct direction should it be wrong. question: Let A be the set of DM students, B the set of BA students and S all…
prinve228
  • 11
  • 3
1
vote
1 answer

Predicate logic using sets instead of predicate functions

Let $\mathit{L}$ be the set of Lions, $\mathit{M}$ the set of Mammals and $\mathit{A}$ the set of all Animals. Use rules of inference with quantifiers to formalize the following statement: $\mathit{S}$: "If an animal is a Lion, then, they must also…
デリエゴくん
  • 11
1
vote
1 answer

Interpretation of negation when translating a sentence to propositional logic (outside bracket vs. applied to each proposition inside bracket)

Assume we have the following propositions: John was victorious: J Robert was victorious: R Dan was victorious: D Now we are given the sentence "If John was defeated, Robert and Dan suffered the same fate". What would be the correct way of…
MikeKatz45
  • 167
  • 11
1
vote
1 answer

Is this a correct predicate logic question?

There are three robots: two good robots and one bad robot. One of the good robot is rich and the other is poor. Each of the two good robots only makes statements which are true and the bad robot only make statements which are false. Write…
Majid Persian
  • 13
1
vote
0 answers

Trying to figure out a logically equivalent statement to the left associative implication chain

The material implication operator $\to$ is not associative, i.e. $$((((A \to B) \to C) \to \cdots )\to X) \neq (A \to (B \to (C \to (\cdots \to X)))$$ I am trying to understand their difference. What I can prove is that $$(A \to (B \to (C \to…
Secret
  • 2,390
1
vote
2 answers

Negating ∃x∀z∃y(S(x,y) ∧ C(y,z))

Negating ∃x∀z∃y(S(x,y) ∧ C(y,z)) would be logically equivalent to ¬∃x∀z∃y(S(x,y) ∧ C(y,z)) however would ∀x∃z∀y¬(S(x,y) ∧ C(y,z)) also be logically equivalent?
Andrew Ryan
  • 233
1
vote
2 answers

Translate English statements into propositions of predicate logic...

So I tried to solve a few logic problems but I'm not sure that I translated these statements correctly... $B(x)$: $x$ breathes fire, $D(x)$: $x$ is a dragon, $F(x)$: $x$ can fly, $R(x; y)$: $x$ frightens $y$ (or $y$ is frightened by…
CodeLearner
  • 15
1
vote
1 answer

What is the complement of exactly one?

L = $\{\langle M \rangle \mid$ $M$ and $Y$ are TMs and $M(x) = Y(x)$ for exactly one $x \in \{1,2,\dots, k\}, k \in \mathbb N \}$ I want the complement for "$M(x) = Y(x)$ for exactly one $x \in \{1,2,\dots, k\}, k \in \mathbb N$" this part
Tree Garen
  • 709
  • 5
  • 15
1
vote
0 answers

Predicate logic: Definition of prime numbers

I have come up with this definition: n is prime iff $$(n>1)\ \wedge \ \left[ \forall x.\ \ (\exists k. n=kx) \implies (x=1 \vee x=n) \right] $$ Is this definition correct?
FizzleDizzle
  • 397
1
vote
3 answers

Show $\vdash P(a) \to \forall x(P(x) \lor \lnot(x=a))$ using natural deduction

Can somebody help me with this question? The question is to show $$\vdash P(a) \to \forall x(P(x) \lor \lnot(x=a))$$ using natural deduction. Here is my attempt: I think I am going half-way through the question but I can't reach the…
Waliy Ismail
  • 21
1
vote
0 answers

Translation Sentence with Four Predicates

Not sure if I am to continue asking questions in my old question thread or post a new one since I'm new here so please forgive any perceived spamming on my part. Given the following predicates and letting the domain for $F$, $G$, and $H$ be all…
Daniel Cazares
  • 715
1
vote
1 answer

Translation of sentence into predicate logic. "Greeks who fear Romans, fear only romans.".

I am trying to figure out how to translate this sentence into predicate logic: "Greeks who fear Romans, fear only Romans". R_ _ : _ Fear _ x: Greeks y: Romans z: Others This is my crack at it, and I am almost certain that it is wrong. $ (Rxy…
Mats Hagen
  • 13
1 2 3
…
22 23