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

Translating proposition to predicates only and others

How can be translated to predicates the following two sentences: Every person has someone who defends him/her against attacks of others. Some people are only defended by pacific people. It's not clear for me: 1 - how to deal with the "others" in…
user232560
  • 85
1
vote
3 answers

Is this true? $\forall x,\forall y, \forall z, [(x\leqslant y)\land(y\leqslant z)\Rightarrow(x\leqslant z)]$

I think the following expression is false for the order relation on the real line. I do know the transitive relation exists on the real line. I don't see how the expression states this. $$\forall x,\forall y, \forall z, [(x\leqslant…
ralph
  • 51
1
vote
3 answers

Is $(\forall a)( a\in A \implies f(a)=b )$ abuse of notation?

I have two ways to write down a certain formula, but I am not sure if both have correct syntax. Given $f:A\rightarrow B$ and $b\in B$. One could write $(\forall a\in A)( f(a)=b )$, but is it also allowed to write the following? $(\forall a)( a\in A…
Constant
  • 134
1
vote
1 answer

Show that $F$ is a Tautology using equivalence transformations

I want to show that $((\lnot \forall v_0 Q v_0 \land \forall v_0 (\lnot Q v_0 \to P v_0)\land \forall v_0(Qv_0 \leftrightarrow \lnot Rv_0)) \to \exists v_0(Rv_0 \land P v_0))$ is a tautology using equivalence transformations. Now, I have tried so…
kklaw
  • 301
  • 1
  • 9
1
vote
0 answers

Show that $(\exists v_0 \varphi \to \psi) \vdash \forall v_0 (\varphi \to \psi)$

The proposition in the title should be proven with the following axioms: Any $L$-Tautologies $\forall$-Axiom $(\forall v_i \varphi \to \varphi \frac{\tau}{v_i})$ $v_i$ is free for $\tau$ in $\varphi$ Modus Ponens $\forall$-Introduction if $T…
kklaw
  • 301
  • 1
  • 9
1
vote
1 answer

Moving the universal quantifier when some statement is independent of the corresponding variable

If $P(x)$ is a predicate about $x$, while $Q$ is a statement, independent of $x$, is the following true? $(\forall x P(x))\iff Q\equiv \forall x(P(x)\iff Q)$ Please note, I have a very low knowledge about mathematical logic, so I might need some…
UnknownW
  • 2,008
1
vote
0 answers

Do these constants stay not zero when taking the negation of the consequent in the contraposition?

I was told to prove that if $v_{1},...,v_{k}$ is a linearly independent list of vectors in $V$, then $c_{1}v_{1},...,c_{n}v_{n}$ are linearly dependent, with $c_{i}\not=0$ for all $i\in\{1,...,k\}$. I was planning on proving it by contraposition;…
Alex D
  • 1,214
1
vote
1 answer

What rule of inference has been used here?

Hi I'm struggling with this exercise Exercise 3.4.10. Suppose that I and J are two sets, and for all α ∈ I ∪ J let Aα be a set. If I and J are non-empty, show that (⋂α∈I Aα) ∩ (⋂α∈J Aα) = ⋂α∈I∪J Aα. I know how to show that two sets are equal. first…
ju so
  • 287
1
vote
1 answer

How to deduce $\forall x \forall y \exists z(Gxz \land Gzy)$

The task is to deduce this: $\forall x \forall y \exists z(Gxz \land Gzy)$ From this: $ \forall x (Gxx) $ And this: $ \forall x \forall y ( x \neq y \to \exists z(Gxz \land Gzy) $ Using this instance of the Law of Indiscernibility of Identicals: $…
beachtrees
  • 209
1
vote
1 answer

Predicate Logic translation from English to formula

I am studying for an exam and I have these exercises I practiced. Let: Monkey(x) = "x is a monkey" Intelligent(x) = "x is an intelligent being" Likes(x, y) = "x likes y" No monkey likes a tiger. let Tigers(x) = "x is a tiger" ∀x(Tiger(x) =>…
Kinfol
  • 15
1
vote
3 answers

Can a function contain a variable?

For example: f is function x is a variable john is a constant Would $ f(x, john) $ be well formed? Or can a function only map constants to an object in a domain?
0implies0
  • 542
1
vote
2 answers

What interpretation shows that $\forall y \;\exists x(Fxy)$ does not imply $\exists x \;\exists y(Fxy \wedge Fyx)$?

So far, I have used the domain, $\{1, 2, 3\}$, and have tried to determine an interpretation for $F$ in which $\forall y\; \exists x(Fxy)$ is true and $∃x\;∃y(Fxy ∧ Fyx)$ is false. I began by trying to make $∃x\;∃y(Fxy ∧ Fyx)$ false. I reasoned that…
beachtrees
  • 209
1
vote
0 answers

How to use proper quantifier in following statement?

From the book: Discrete Mathematics and its application by Kenneth Rosen Page 54 and Exercise no. 28 Need to convert it to predicate calculus formula: "Nothing is in the correct place and is in excellent condition." My answer: $\neg∃x (C(x)…
Ubi.B
  • 340
1
vote
1 answer

translating informal language to predicate logic; existential vs universal quantifier

I am analysing some problems in the Hurley Logic Text book (12th edition) and I confused about a couple of answers he gives. Here are two related statements that he translates differently (taken from Hurly p. 505). The first with a universal…
Jeff
  • 129
  • 4
1
vote
2 answers

Show that the following inference is not correct

Show that the following inference is not correct: Suppose every day that is not rainy is not windy, and some day is windy. Then every day is rainy. $$\forall x (\lnot R(x)\rightarrow \lnot W(x)) \land \exists x W(x)$$ is how I would write it. I'm…
user63764
  • 165
1 2 3
…
22 23