# Tag Info

## New answers tagged predicate-logic

2

Yes. You can keep pushing the negation in: $\neg \exists x \forall z \exists y (S(x,y) ∧ C(y,z)) \Leftrightarrow$ $\forall x \neg \forall z \exists y (S(x,y) ∧ C(y,z)) \Leftrightarrow$ $\forall x \exists z \neg \exists y (S(x,y) ∧ C(y,z)) \Leftrightarrow$ $\forall x \exists z \forall y \neg (S(x,y) ∧ C(y,z))$

2

The final answer will use De Morgan's law to get $$(\forall x )\;\;(\exists z) \;\; :$$ $$\;\; (\forall y ) \;\;\lnot S(x,y) \; \vee \lnot C(y,z).$$

1

1) There are at least two people who everyone knows. Domain = {People} My take in this.... for the 1) part is it valid to do something like this ∃𝒙∃𝒚∀z𝑷(𝒙, 𝒚,z). Where in my words i could be totally wrong.. there exist a pair (x,y) who everyone (z) knows. You must say: "There are some $x$ and some $y$ who are not the same people and every $z$ ...

4

To simplify notation, use a two-sorted logic where lowercase letters are person variables and uppercase letters are car variables. Let $x\mathrm{T}y$ be the relation of $x$ and $y$ living together and $x\mathrm{D}A$ be the relation that $x$ drives $A$. "All people who live together drive the same car." is equivalent to "For each person, there is a car that ...

0

For 1, try $$\forall x,y(((\operatorname{Person}(x)\land \operatorname{Person}(y))\land\operatorname{LivesTogether}(x,y))\to(\exists z\operatorname{Car}(z)\land(\operatorname{Drives}(x,z)\land\operatorname{Drives}(y,z)))$$ and for 2, try $$\lnot\exists n\forall m(n>m),$$ where the domain for the second one is understood to mean all (real) numbers.

1

I'd translate the first sentence like this: \begin{align}&\forall x\forall y \text{Person}(x)\wedge\text{Person}(y)\\ &\to\Big[(\exists h \wedge \text{Home}(h)\wedge\text{Live}(h,x)\wedge\text{Live}(h,y)) \\&\to\forall c\forall d\Big(\big(\text{Car}(c)\wedge\text{Car}(d)\big)\to[(\text{Drive}(c,x) \longleftrightarrow\text{Drive}(c,y))\\ &\... 2 Statement 1 is true and statement 2 is false, because the order of quantifiers matter. As the existence quantifier in statement 1 comes after the "for all" quantifers, it claims existence after assignments have been made to the variables named in those. Contrary to that the existence quantifer in statement 2 comes first, and therefore claims existence of ... 5 In order to evaluate the truth value of ∃x \ ∀y \ ∀z \ P(x,y,z), it is useful to "read" it : "there is a positive real x such that, for every (positive reals) y and z it is true that xyz=1. The reasoning is : assume that x > 0 exists such that .... From xyz=1 we get yz= \dfrac 1 x (we can do it because we have x > 0) for every y,... 2 All tigers are liked by some lion. My answer: ∀x, ∃y: Tiger(x) \land Lion(y)\implies Likes(x, y) Wrong. The original sentence, "All tigers are liked by some lion", would be false in a world where no lions existed. Your formulation of the sentence would also be true in a world where no lions existed, since Tiger(x)\land Lion(y) would always be false. ... 1 \exists !x~(\phi(x)\wedge\psi(x)) is equivalent to \exists x~((\phi(x)\wedge\psi(x)\wedge(\forall y~(\phi(y)\wedge\psi(y)\to y=x)). This says "there is only one entity which satisfies \psi and \phi". This assertion does not deny the existence of entities that satisfy \phi yet not \psi. \exists x~(\phi(x)\wedge\forall y~(\phi(y)\to ... 0 \def\Blue{\operatorname{\textsf{Blue}}}\def\Circle{\operatorname{\textsf{Circle}}}\exists x~(\Blue(x)\wedge\Circle(x)) specifies that something simultaneously satisfies both Blue and Circle predicates. \exists x~\Blue(x)\wedge\exists x~\Circle(x) specifies that something satisfies the Blue predicate, and something satisfies the Circle predicate, but it ... 0 Hint Assume not, i.e. that A \land B is True and C is False. C False means that P(a,b) and P(b,a) both hold, for some a,b. Thus, from B : P(a,b) ∧ P(b,a) \to P(a,a) we get : P(a,a). 0 Imagine P(x, y) is a checkerboard, where if P(x,y) is true then the square at (x, y) is red and when P(x, y) is false then the square at (x, y) is black. \exists x \exists y ~P(x, y) is the same as saying "there is at least one red square". \forall x \exists y ~P(x, y) is the same as saying "every column has at least one red square". Work ... 8 The natural "general" form of universal quantification breaks down when we try to apply it to terms more complicated than constant symbols. A more limited form of it is admissible, but we generally don't present it due to the potential for misuse. Incidentally, this is a great example of how semantic analyses make everything much easier. First, let me ... 2 I assume you meant \forall x(P(x) \land S(x)) (with S(x) inside the scope of the quantifier \forall x), not \forall x(P(x)) \land S(x). If you say \forall x(P(x) \land S(x)), this means "For all entities in the domain, P holds and S holds". This statement is false in the domain \{1,2,3\}, since neither P nor S hold of 3. If you want ... 3 would the first proposition indicate that there is an x that is both Blue(x) and a Circle"(x) or could the x of Blue(x) be distinct of the x that satisfies Circle(x)?" The first proposition says that there is an x such that both Blue(x) and Circle (x) holds simultaneously. The second proposition says that there is an x such that Bed(x) holds AND ... 3 I think of interpretation as a two-stage process. First, translate the symbols into "mathematical language" without referencing the quantified terms, and then coax it into natural language. For instance,\forall x\ E(T,x)$$is "for everything, Tom eats it", which I revise to "Tom eats everything." But if it's something where x is referenced in both ... 1 One could use this tree proof generator to determine if these formulas are true or false. If a tree is generated then the formula is true. If a countermodel is generated then it is false. These are simple enough that they will reach a conclusion quickly. Here is the first one with a countermodel showing that it is false: https://www.umsu.de/trees/#%E2%88%... 1 Your best bet is to come up with interpretations of P that will let you think about whether the implications are true. For instance, in the first problem, you could let P(x,y) be the statement |x|+|y|=0 where x and y are real numbers. Then it is true that \exists x\exists y P(x,y). Is it also true that \forall x \exists y P(x,y)? Then try ... 1 "Can two different objects be identical?" No. Just no. At least according to your book. With definition 1 you could have two different objects, one named 'a' and one named 'b', but with the exact same properties so that they are identical I don't blame you for thinking that is what the definition seems like. But it clear from context that according ... 4 One of the properties of a is the object to which it refers. That is, if both a and b have all the same properties, then they refer to the same object. We can relax this and talk about equivalence classes of objects, but the logical identity is as strict as one can make. If there is any property that discriminates between the two of them, they aren'... 3 There are tons of consequences of \sigma; indeed, T is a complete theory, so for every sentence \varphi, either \varphi or \neg\varphi is in T. For instance, one very meaningful universal statement in T is \forall x\forall y(x=y). Or, for any formula \varphi(x), \forall x\forall y(\varphi(x)\leftrightarrow \varphi(y)) is in T. The ... 5 I'm sorry to disappoint your expectations, but the widely used notation to say that two propositions p and q are consistent with each other is p,q \not\vdash \bot or \text{Con}(\{p,q\}). This is the same notation used more in general to say that a set \Gamma of propositions is consistent (\Gamma \not\vdash \bot or \text{Con}(\Gamma)). As far ... 2 However, this seems somewhat off to me. To me it looks like I just have to provide an example of \neg A, given that \neg B, but that doesn't seem right. Why doesn't it seem right? Take, for example, the statement If all walls of this room are red, then this is a red room. In this statement, A is "wall x is red", and B is "this room is red". ... 1 Indeed, what you have to prove is that \neg B \implies \exists x \, \neg A. So, consider the assertion, concerning \mathbb R^n,$$\forall x\,x.y=0\implies y=0.$$You wish to prove that if y\neq0, then there is some y such that x.y\neq0. Indeed this is true: just take y=x, and you're done. 0 To say A\vee B\vee B'\vee C is invalid, is to claim that we are able to evaluate it as false for some interpretation. Thus you need to construct a counterexample where \neg A\wedge\neg B\wedge\neg B'\wedge\neg C holds. But I can't understand how to implement '∀' Universal notation into formula. The negation of a universal is an existential. So \... 1 Hint To show that the formula is not valid, you have to find an interpretation such that the complex formula is False. Being a disjunction, this means that the sought interpretation must falsifies every disjunct. We can try with a simple interpretation \mathcal I with domain I = \{ 0,1,2,3 \}. Try with P^{\mathcal I} = \{ (0,0), (0,1), (0,2), (1,0), ... 4 Ok, several ways to do this: Probably the most straightforward way is to say that there are three distinct orange apples and no more: \exists x \exists y \exists z (A(x) \land O(x) \land A(y) \land O(y) \land A(z) \land O(z) \land x \neq y \land x \neq z \land y \neq z\land \neg \exists w (A(w) \land O(w) \land w \neq x \land w \neq y \land w \neq z)) ... 0 This is the arithmetic hierarchy, and the relevant notation (\Pi^0_n, \Sigma^0_n,\Delta^0_n) is quite snappy so I'll use it. There is a tight connection between syntactic complexity and computational complexity. Specifically: A set X\subseteq\mathbb{N} has a \Sigma^0_n definition if and only if X is many-one reducible to {\bf 0^{(n)}} (for \Pi^... 5 You can certainly get away with only using relation symbols. This is because each function is "equivalent," in a precise sense (see below), to its graph$$Graph(f)=\{(a_1,...,a_n, b): f(a_1,..., a_n)=b\}. That said, there are definitely situations where we actually are interested in functions in particular; we can always use the language of relations ...

1

If the question explicitly asks you to say that Adam is not taller than himself, than the answer in the book did indeed forget to add the $\neg Taa$ statement. So, your second answer is better than the book's. And, your first answer also implies that Adam cannot be taller than himself. So, good for you. But, as Graham Kemp points out, none of the answers ...

0

In the given question the last point is the valid first order formula: We can prove this by using law of contradiction and Rule of Inference (Modus Ponens specifically). The TT or boolean alzebra methods will be a bit difficult to apply in case of Predicate Logic, therefore your method of taking α as 0 = 0, β as 0 = 1 would be a little herculean. Proof: ...

1

A) No. $\exists dD(d)$ B) No. $\forall x(Dx\to Wx)\land \exists y(Dy\land\lnot Fy)$ C) Correct. D) No. $\exists x (Dx\land \forall y\lnot Ryx)$ E) No. $\forall x(Dx\to \exists y (Dy\land Ryx))$ F) Correct.

3

Hint: This is a very nice start. C and F are completely correct at the moment. Here are a few things in general to think about. All of your variables need a quantifier. When you have both $x$ and $y$ in an equation, both need to be quantified. Make sure that every statement that talks about dragons has a $D(\cdot)$ predicate in it. Otherwise, try ...

0

Here is a formal proof using Fitch natural deduction: The proof idea is similar to the one provided by Luiz Codeiro, but if we assume a rule system with a full set of elimination and introduction rules for all of the connectives, we don't need to make use of the deduction theorem: Instead we can show the derivability of the implication directly in one ...

2

You need to think of proofs in natural language. $P$ and $Q$ are properties about elements in your universe of discourse. The statement says that "If both $P$ and $Q$ are valid for every $x$, then $P$ is valid for every $x$, and $Q$ is valid for every $x$". So to prove it, in natural language and in a very pedantic manner, would be something like ...

1

You could use the method of analytic tableaux, like so The tree was generated by this site: https://www.umsu.de/trees/.

0

The formula $\forall i<A.F(i)=B\implies H(i)=C$ states that for every instance of $i<A$, if $F(i)=B$ then $H(i)=C$. It is not sufficient to check only the least $i$ such that $F(i)=B$. Unless $F$ is stated to be a bijection, it may be the case that for the least $i<A$ such that $F(i)=B$, $H(i)=C$, and yet for some $i<j<A$, $F(j)=B$ and $H(j)\... 0 Here is a natural deduction proof for the first one: For an example consider a basket of apples that are all red and round. The left side says "all of the apples are both red and round". The right side says "all of the apples are red and all of the apples are round". Here is a natural deduction proof for the second one: For an example consider a basket ... 2 Because the theorem says : for every$a,b,c$(real numbers) the equation$ax^2+bx+c=0$has exactly two real solutions iff$b^2 > 4ac$. Thus, an instance of the above equation will be obtained instantiating the leading universal quantifiers with three individual real numbers, says :$a=1, b=3, c=2$. The result will be the individual equation :$x^2+...

0

It is almost correct. You forgot to add that $x_1\neq x_2$.

0

Using Adrian Keister's symbolization of the third premise, here is a formal proof: Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

1

$\newcommand{\strc}{\mathfrak{A}}$ You can not use truth tables for predicate logic. This method is simply not appicable for this langauge. To prove the validity ($\vDash$) of a formula in predicate logic, either you provide an informal (meta-linguistic) semantic proof in which you argue why the formula must be true in all structures (something along ...

1

A quick way to approach deciding whether these are valid or not is to use a tree proof generator. It is like using a truth table generator for propositional logic, but it works for first order logic as well. Here is a tree proof for I: In a tree proof the desired result is negated as you can see from the first line. The branches (if more than one) expand ...

0

Prove that $∃y∀xf(x,y)⇒∀x∃yf(x,y)$ Assume the opposite: $∃y∀xf(x,y)⇒\neg ∀x∃yf(x,y)$ Nope. That is neither the direction needed, nor what the opposite actually is. The negation of the conditional: is $∃y∀xf(x,y)\wedge\neg ∀x∃yf(x,y)$. However, assuming that for a proof by contradiction will lead to a rather inellegant proof. All you need to do is ...

0

Here is a proof of the quantifier shift using a Fitch-style proof checker. Rather than starting with the negation of the statement to be derived, I started with the negation of an equivalent statement represented as a conjunction. After reaching a contradiction, I derived the desired conditional. Kevin Klement's JavaScript/PHP Fitch-style natural ...

0

One way to get a countermodel is to use a tree proof generator. Here is one countermodel: This model has a domain with two members. Only for the member $1$ is $P$ true. There is no member that makes $Q$ true. With that assignment, $\exists x Qx$ is false since $Q$ is false for both members of the domain. This makes the consequent false, but the antecedent ...

0

If what you are trying to derive from the premise $\forall x(Ax\to Cx)$ is $\neg\exists x \neg Cx$, this tree proof generator provides the following countermodel: A domain containing one element, $0$, which does not make either $A$ or $C$ true would make the conclusion false since there does exist $x=0$ for which $\neg C$ is true. However, the antecedent, a ...

0

It's been a while since I've read the book and I don't have it with me, so I'm not sure exactly where the overlines go. I'll just skip them entirely; they aren't all that important to the question. (It's very good that you're careful with them though!) In the case you discuss, $s(x|s(t))(u) = s(u)$ because $u \neq x$, by the first clause of the definition ...

-1

Here is a proof using a Fitch-style proof checker: Note that I used universal elimination twice from the same line 3. This allowed me to ultimately derive a contradiction on line 13 from the two disjuncts on line 9. Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

Top 50 recent answers are included