Tag Info

New answers tagged

4

This is a logic "confused" problem ... We approach it "by steps". Question 1 Assuming that you are meaning : for a valuation $v$ there is some $n$ for which : $v(\varphi_n)=1$. Is so, due to the fact that : $v(\varphi_1 \lor \ldots \lor \varphi_n) = max_i \{ v(\varphi_i) \}$, we have that for the valuation $v$ : $v(\varphi_1 \lor \ldots \lor ...


0

The convention in play is that in the main part of the table (after recording the truth-values of atoms -- if we bother to that again, since that's just copying across the values assigned at the beginning of the line) we write the truth-value under the main connective of the (sub)formula we are evaluating at that step. So it is indeed wffs that are being ...


2

Presumably one is only interested in $1$s in the output. There are $8$ where $p_4$ is true. Or else we want the antecedent of $p_4$ false, forcing $p_3$ false, and $p_1\longrightarrow p_2$ true. The count of cases where $p_1\longrightarrow p_2$ is true, and the rest false is easy. One uses a similar analysis in producing a "quick" disjunctive normal ...


1

I'll use Enderton's system (see Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001)). We start with : $\forall x \exists y \varphi(x,y) \rightarrow \lnot \exists x \psi(x)$; the first step is to change the second bound $x$ to $z$, in order to avoid problems with "clashing" quantifiers : $\forall x \exists y \varphi(x,y) \rightarrow ...


0

Both are correct given that you have "0" as allowable in expressions since (p→0) is logically equivalent to ¬p. ¬φ is logically equivalent to (p→(q→r)). ¬(p∧q→r) is logically equivalent to ¬(¬(p→¬q)→r) which is logically equivalent ¬(¬(p→(q→0))→r) which is logically equivalent to ¬(((p→(q→0))→0)→r) which is logically equivalent to ...


0

You are looking at it wrong. It may be easier to understand if stated more precisely; "Either 1) it is true that White can force a win, or else 2) it is true that Black can force a win, or else 3) neither White nor Black can force the other to accept a loss." That is, the theorem sets out the possiblities. It does not say which of those three possiblities ...


1

I know this has an accepted answer. Just to add for the sake of being helpful. If you look here: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap01.pdf In the readings there is a section on predicates. The explanation I found most helpful is on page 14 & ...


0

In general $$A \rightarrow B = \lnot A \lor B$$ Also, notice that $$\lnot(\lnot A \lor B) = A \land \lnot B ~\text{(De Morgan theorem)}$$ In your case, you have: $$\varphi = \lnot((p \land q) \rightarrow r) = p \land q \land \lnot r $$ and $$\lnot\varphi = (p \land q) \rightarrow r = \lnot p \lor \lnot q \lor r ~\text{(De Morgan theorem)}$$ In the ...


3

$$\begin{align}\lnot \varphi & \equiv \lnot \Big(\lnot((p\land q)\rightarrow r)\Big) \\ & \equiv (p \land q)\rightarrow r\\ & \equiv p\rightarrow(q\rightarrow r) \end{align}$$


0

Hint: $$x\lor y \equiv \lnot x\to y \\ x\land y \equiv \lnot(\lnot x \lor \lnot y) $$


0

p->q If I have chocolate, then I am happy. T T -> T If I have chocolate, then I am happy. As initially stated. T F -> F If I have chocolate, then I cannot be not happy, by the initial statement...............That's why this is false. F T -> T If I do not have chocolate, I could still be happy .............. (perhaps because I ...


2

I have once played around with this stuff myself and obtained this example of such a sentence. The long thing at the end of that page (there are in fact two long things, just minor variants if I recall it correctly).


2

You statment needs a little additional specification : in second-order logic it is possible to define equality by Leibniz's law : $∀x∀y[x=y→∀P(Px↔Py)]$. In Second-order Logic we interpret the universally quantified predicate variables as meaning “for every property of objects (in the universe of discourse)”. The semantics for second-order ...


0

Though I do not understand the question description compeltely (and forgive my wrong use of terminology, it is not really my field), the title compelled me to think about this. Under the assumption that a game only ends if a draw is claimed, I believe that chess can be used to represent any brainfuck code. And, as brainfuck is turing complete, I would say ...


0

This answer address the "unsolved" problem regarding the proof of the "propositional part" of the question, using an Hilbert-style proof system (with Natural Deduction, the proof is quite easy, and has been already provided). The list at page 13 of M.J.Cresswell & G.E.Hughes, A New Introduction to Modal Logic (1966) is significantly called a "list ...


-2

As chess is played on a finite board with finite many pieces, the number of which can not grow but decline during the game, chess is a game with finite many states and thus never Touring-complete. Though the number of states grows exponentally with the size of the board chess only represents a finite state machine and will be won by computers at some time in ...


0

We assume that your system is the usual first-order logic with equality. For $n\ge 2$, let $S_n$ be the sentence that says $\forall x\exists y_1\exists y_2\cdots \exists y_n\phi(x,y_1,y_2,\dots, y_n)$. Here $\phi$ is the conjunction of (i) formulas $R(x,y_i)$, where $i$ ranges over the integers from $1$ to $n$ and (ii) formulas of the shape ...


5

Here's an intuitive definition for what a "winning strategy" is. We define recursively what it means to "have a winning strategy" for any given state of the game. If at a particular game state, it's your turn, and there is a move you can make that'll win you the game (right away), you have a winning strategy for that state. If it's the opponent's turn, ...


1

In the statement, there are three disjoint sets: A) White can win. B) Black can win. C) Either White or Black (or both) can force a draw. (We won't go into the subsets of this, since the outcome is the same--a draw.) The union of these three sets A U B U C is just the whole space of possible outcomes.


18

Answering to a comment which seems to be closer to the core of the issue here: In every game, if people play a perfect game they win and they lose otherwise. What is the utility of the theorem then, please? The theorem allows you to classify games. Assuming all players play perfectly, there are games where the beginning perfect player will always win, ...


71

The theorem is about perfect players. Assume you were able to enumerate and evaluate all the gazillion chess positions. Then the following can happen: You find out that you can force a win as white, no matter how well black plays You find out that even with your best play, you cannot force a win as white if black plays well enough You find out that you ...


3

People lose because nobody know how to force a draw. It is possible, but no one know how and this is what keeps chess interesting. On the other hand, you can force a draw in tic tac toe, and since it is really easy to learn a strategy that ensures that, games of tic tac toe are not that interesting.


0

The halting set $K = \{e \mid \varphi_{e}(e) \downarrow\} \subset \mathbb{N}$ is not many-one reducible to its complement. For if it were, that is if there were a total computable $f\colon \mathbb{N} \to \mathbb{N}$ such that $x \in K \Leftrightarrow f(x) \notin K$, then we could decide if $e \in K$ by simultaneously watching $\varphi_{e}(e)$ and ...


1

This breaks down to four statements: White can force a win Black can force a wim White can force a draw Black can force a draw The rules of chess ensure that at least one of these outcomes happens. Also notice that it's one player causing the outcome to happen. Now, regarding your statement: "And why do people lose in chess then, if they can force a ...


2

You actually need modifications in your translation: The connectives in each existential (or negation of existence) need to be $\land$, not $\rightarrow$. I'll use $S(x)$ to mean "is a showman", and $H(x)$ to mean "x is sincere (honest)". Then what follows is the correct translation of the statement “If all politicians are showmen and no showman is sincere ...


1

The first step is to create a formula that states whether a given natural number is a prime number or not. The definition of a prime number $p$ is that the only divisors of $p$ are 1 and $p$, and where $p\neq 1$. Thus, we could write this as $$\varphi(p):= (1<p)\wedge \forall q(q|p \rightarrow (q=1 \vee q=p))$$ Then we can produce the formula ...


0

I am guessing at the interpretation to this question. if predicate H(x) become false when a program with code r(x) halt on input l(x), then H be a computable predicate Suppose the range of $l(x)$ is all programs. Suppose $r(x)$ is a simulator. Suppose $H(x)$ is the predicate "$l(x)$ runs forever without stopping." When $r$ stops the simulation of ...


0

You can prove it in Sequent Calculus as described in the pdf mentioned in the comments (http://zll22.user.srcf.net/talks/2011-12-01-CategoricalLogic.pdf ) 1 A |- A Identity 2 B |- B Identity 3 C |- C ...


1

Just prove that (for all $x$) $$(2x+1)\in (A\oplus B)\oplus C \Longleftrightarrow (4x+3)\in A \oplus (B\oplus C)$$ $$(4x+2)\in (A\oplus B)\oplus C \Longleftrightarrow (4x+1)\in A \oplus (B\oplus C)$$ $$(4x)\in (A\oplus B)\oplus C \Longleftrightarrow (2x)\in A \oplus (B\oplus C)$$ Hence, (see 1-reduction) $$(A\oplus B)\oplus C \equiv_1 A \oplus (B\oplus ...


0

Logicians also prove the consistency of a formal system relative to each other. For instance, if ZFC is consistent, then PA (Peano arithmetic) is consistent. So in that sense ZFC is stronger than PA. Fermat's last theorem was proved in a system stronger that PA. In that sense, it might be the case that the proof is inconsistent (we'll likely never know) ...


1

The truth tables here with "0" as falsity and "1" as truth are (in Polish notation) are p q Np Nq CNpNq Cpq 0 0 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 So, yes if p=0, and q=0, then it holds that if CNpNq, then Cpq. In other words, for some instance (or in other words some valuation of the ...


2

Knowing only that $x^2=y^2$ isn't enough to conclude that $x=y,$ so you can't draw your final conclusion. Rather, the following are equivalent among integers $x,y$: $$x^2=y^2$$ $$x^2-y^2=0$$ $$(x+y)(x-y)=0$$ $$x+y=0\text{ or }x-y=0$$ $$x=-y\text{ or }x=y$$ Furthermore, you cannot get from the statement $$\forall x\in\Bbb Z,\forall y\in\Bbb ...


0

Assuming I understand it correctly, computer science (denotational semantics?) deals with this by using total functions to represent partial functions. We define a distinguished element $\bot$ meaning undefined (usually pronounced "bottom"). Given a partial function $f:A \nrightarrow B$ we can represent it with a total function $f^{\prime}:A \rightarrow ...


1

No, that doesn't tell us anything relevant about sets. Since $x\notin S$ is just an abbreviation for $\neg(x\in S)$, we can abbreviate your property $$ \forall x. \; (x\in S \lor \neg(x\in S))\land \neg(x\in S\land \neg(x\in S)) $$ as $$ \forall x. \; (A\lor \neg A)\land \neg(A\land \neg A) $$ where $A$ is the proposition $x\in S$. And this is a logical ...


0

We construct a model for 1). The (underlying set of) the structure $M$ has one element $a$. The interpretation $C_M$ of the predicate symbol $C$ is false at $(a,a,a)$. Then the sentence 1) is true in $M$. Similarly, we can construct models for 2) and for 4). In 4), let $M$ have two elements, $0$ and $1$. The interpretation of the predicate symbol $B$ is ...


1

If you consider the universe is $\mathbb{R-0}$ and the language is $(.,>,0)$, statements 1 and 3 translate to: $$\forall a(a^2>0)$$ And 3 is the universe that this formula is true on it


0

I think that part of the problem is in the terminology used: thus, I'll prefer to avoid to speak of "proof by contradiction". Consider the standard natural deduction rules for propositional logic ; see Dirk van Dalen, Logic and Structure (5th ed - 2013), page 30. The rules for $\bot$ are : ($\bot$) $$\frac {\bot} \varphi$$ and : (RAA) $$\frac ...


0

I can't comment so I'll give answer. I suggest you to use the "Truth Table". When the result is all true then the equivalence held. Here is my try: Hope this helps


0

Note that the expression on the left-hand side is simply equivalent to $\neg Q$, and so is the expression on the right-hand side. $(\neg Q \land \neg R)\lor (\neg Q\land R)\iff \neg Q\land(R\lor \neg R)\iff \neg Q\iff \neg Q\lor (\neg Q \land P)$, where the last equivalence follows from the absorption law (I'm assuming you can use this).


0

How about using a truth table? You go through the four possibilities $P$ and $Q$ are both true $P$ is true and $Q$ is false $P$ is false and $Q$ is true $P$ and $Q$ are both true This will prove the equivalence, as required. For instance, for 1. (both are true), you get [(¬Q ∧ P ) ∨ ¬Q] ⇔ [(¬Q ∧ ¬R) ∨ (¬Q ∧ R)] [(¬t ∧ t ) ∨ ¬t] ⇔ [(¬t ∧ ¬t) ∨ (¬t ∧ ...


0

Now I give an answer without using provable equivalences on Enderton, page 121 and page 130. Main formula is equivalent to $$(\neg\exists x\varphi(x))\vee(\forall x\exists y\psi(x,y))$$ and this is also equivalent to $$(\forall x\neg\varphi(x))\vee(\forall x\exists y\psi(x,y))$$ but we have: $$\forall x\exists y\psi(x,y))\leftrightarrow\forall z\exists ...


0

A proof by contradiction is not $\{T\ \cup \ \neg p\}\vdash p$. It is $\{T\ \cup \ \neg p\}\vdash \neg q$, where $q$ is a proposition such that $T \vdash q$. For example, a proof by contradiction may terminates by $0=1$ or $0>1$ or anything else "obviously" (for the point of view of the theory $T$) false. This is why proof by contradiction is also ...


0

The two expressions "abcd" and "abcdefg" are compatible because you can talke the former and add "efg" to the right side, and it turns into the latter. THe expressions "abcd" and "abd" are not compatible, since no matter what you put on the right side of any of them, they won't become the same expressions. In your case, the letters $a, b, c$ and $d$ are ...


2

$\Rightarrow:\;\;(1)$ Distribute. $\;\;(2) A\lor A \equiv A\land A \equiv A$. (Simplification.) $\;\;(3)\land$-Elimination. $$A\lor (A\land B) \overset{(1)}{\iff} (A \lor A)\land (A\lor B) \overset{(2)}\iff A \land (A\lor B) \overset{(3)}\implies A$$ $\Leftarrow:\;\;$ We use disjunction-Introduction. $$A \implies A\lor (\text{anything}.)\;\;\text{So,}\; ...


1

I assume "commutative algebraic theory" means that the language should have one commutative binary operation, plus constants? Do you also require associativity? Anyway, here's an associative counterexample: Let $L = \{\cdot, c\}$, and consider the theory axiomatized by $T$: $(x\cdot y)\cdot z = x\cdot (y\cdot z)$ $x\cdot y = y\cdot x$ $x\cdot x = c$ ...


1

The point is that one can use a lot of coding to reduce a great deal of fancy mathematics to Peano arithmetic, and even weaker theories. But to really get things going, you would want to use second-order arithmetic, or at least a subsystem of it. Have a look at the work on Reverse Mathematics, where such things are studied systematically. In essence, ...


5

There is (up to isomorphism) only one standard model of PA. And there are sentences true in the natural numbers that are not theorems of PA.


3

My favorate example is the theory of torsion free divisible abelian groups. All of these are first order properties, but with infinitely many axioms. A little reflection leads one to see that such a group is in fact a vector space over the rationals, and thus its isomorphism type is determined by its dimension. For dimensions $1,2,\ldots \aleph_0$ the ...


5

Let $T$ be the theory whose axioms are all sentences true in the integers. Here the language has symbols for $0$, $1$, and for addition and multiplication. This theory has a countable non-standard model. It is obtained in the usual way, by adding a constant symbol $a$ and axioms that say $a$ is different from $0$, $\pm 1$, and so on. Now use Compactness ...


1

You use soundness: Let $L$ be a language and let $T$ be an $L$-theory. Now let $\theta$ be an $L$ sentence. Then; $T\vdash{\theta}\rightarrow{\forall{M},(M\models{T}\implies{M\models{\theta}})}$ We use this idea: If you trace through the example I gave here Can a statement in FOL be equivalent to two separate independent statements?; you can see these ...



Top 50 recent answers are included