# Tag Info

0

I would advise to start with everything in parentheses first, then go from there, but of course, this is not the only way to approach these problems. Is there any particular problem you have with drawing circuits? It really depends on the individual on how they would approach these problems. This website is pretty good for drawing logic circuits. If your ...

2

They don't cancel out in the way you write it, no. Don't forget, the rule in the form you cite is equivalent to: $$\neg\, \forall x \,\neg\, \varphi(x) \iff \exists x\, \varphi(x) \\ \,\neg \,\exists x \,\neg\, \varphi(x) \iff \forall x\, \varphi(x) \\$$ Even more concisely for all four equivalences, \begin{align} \neg \exists &= \forall \neg \\ \neg ... 1 Bounded quantification is saying "for all elements x \in X, it holds that ..." or "there exists an element x \in X such that ...". Unbounded quantification is saying "for all (sets) X, it holds that ..." or saying "there exists a set X such that ...". For some parts of mathematics, bounded quantifications entirely suffice. For instance, when talking ... 0 The reason "If P then Q" is considered to be true in the case when P is false is simple: It's a true statement because it's not false. Let me unpack that. What would it mean for "If P then Q" to be false? It would mean that P is true, but Q isn't. That's really the only way an implication can fail: If the hypothesis holds, but the ... 0(\forall x) [\beta \implies a(x)] \equiv \text{For all $x$, $\beta$ implies $a(x)$}\beta \implies (\forall x)[a(x)] \equiv \text{$\beta$ implies that for all $x$, $a(x)$ is true}$$You didn't specify the domain for x, so your statements already have a problem. Other than that, the two statements are equivalent. 0 Maybe it'll make a little more sense if you see the table knowing the following logical equivalence:$$(P \implies Q) \equiv (\neg P \lor Q)(Q \implies P) \equiv (\neg Q \lor P)$$i.e. "P implies Q" is logically equivalent to "either not P, or Q" Now that we know that this is the case, let's redraw the truth table using the right hand side of ... 1 Consider the implication "If it is raining, then it is cloudy."$$Raining\implies Cloudy$$In the mathematical sense of implication, this is not a claim of a causal relationship between rain and cloudiness: e.g. that cloudiness somehow causes rain, or that rain somehow causes cloudiness. This is also not a claim of any kind of historical pattern over ... 1 One of the "basic" pattern of inference is modus ponens (its latin name gives us a "flavour" about how old it is). Modus ponens formalize the inference step of the form : "if A then C, A; hence C. It is useful to define a conenctive "supporting" this basic move : the conditional. Suppose we claim "if A, then C. This means to rule out the ... 4 Here is why we say P \implies Q is true if P is false and Q is true: Let P be the statement "it's raining outside" and Q be the statement "the car is wet". In order for P \implies Q to be true, what needs to happen is: every time it rains outside, it better follow that the car is wet. That's all you need to check. So the only time P \implies ... 2 P \Rightarrow Q is logically equivalent to \sim P \vee Q (where \sim is '"not" and \vee is "or"), and \sim P \vee Q is true whenever P is false. Another thing to think about is providing counterexamples. P\Rightarrow Q can only be proved false if you give an example where P is true and Q is not true. Any example where P is false is not a ... 1$$((P \implies Q) \implies P) \implies P((\text{Pigs can fly} \implies 1+1=2) \implies \text{Pigs can fly}) \implies \text{Pigs can fly}((\text{False} \implies \text{True}) \implies \text{False}) \implies \text{False}(\text{True} \implies \text{False}) \implies \text{False}\text{False} \implies \text{False}\text{True}$$0 X={}“The result of the toss is head if and only if I am telling the truth.”$$ \begin{array}{|c|c|c|} \hline \text{type of person} & \text{coin outcome} & \text{Could say $X$?} \\ \hline \text{truth-teller} & \text{head} & \text{yes} \\ \text{truth-teller} & \text{tail} & \text{no} \\ \text{liar} & \text{head} & \text{yes} ...

0

They are generally less geometric than your examples, but Raymond Smullyan books have many logic problems. I particularly enjoy Satan, Cantor, and Infinity. He has many others.

0

The deleted answer by Henning Makholm had essentially the right idea, modulo a few details. Let me spell it out a bit more. Let $\Sigma^*$ consist of all consequences of $\Sigma$ which are either quantifier-free sentences or which have the form $\forall \overline{x}\,(\exists y\, \psi(\overline{x},y))\leftrightarrow \theta(\overline{x})$, where ...

2

The wikipedia article on Peirce's law remarks that "it can be thought of as the law of excluded middle written in a form that involves only one sort of connective, namely implication." This may make it a little obscure. It's instructive, then, to examine it from the perspective of constructive versus nonconstructive reasoning. Peirce's law seems to mainly ...

2

It is certainly possible for a Turing machine with alphabet $\{0,1\}$ to simulate a Turing machine with any finite alphabet. The idea is that if the larger alphabet has size less than $2^k$ then you can divide the tape into "chunks" of size $k$ and use each of these chunks to encode a single character from the larger alphabet. This requires a larger number ...

0

Before you can write formal proofs about numbers, you need rules of logic and some kind of set theory. The five essential properties of the set of natural numbers (see Peano's Axioms) can be expressed in the language of set theory. For the set $N$ of natural numbers, successor function $S$ and $0$ we have the following essential properties or axioms: $0\in ... 1 Your example seems to be about$(P\to Q)\to P$, which is not valid. Peirce's Law is more complicated and is valid; read it carefully. Peirce's Law says, in your example, that "pigs can fly" would be a consequence of the rather complicated hypothesis "If (if pigs can fly then$1+1=2$) then pigs can fly". But that hypothesis is, as you noticed, false, so it ... 1 It is a tautology : thus we can use the truth-functional definition of the conditional. When$P$is true, then the conditional$A \to P$is true, for$A$whatever (because$? \to T$is$T$); thus also when$A$is$(P→Q)→P$. When$P$is false, then$(P→Q)→P$is also false (because$F \to ?$is$T$), and thus$((P→Q)→P)→P$is true (because :$F \to F$is ... 0 The standard way to do it today is to begin with sets. We do this by taking for granted certain axioms of set theory, which serve to tell us more or less what properties sets have. From this, we use the language of set theory to actually define what a real number is. Taking a course in real analysis will hopefully help you, but the general steps to construct ... 0 If I remember my tableaus, you get$\forall x,y,zF(\ldots)$(the antecedent) and$\neg\forall x,y\exists z\ldots$(the negation the of consequent). You should have a rule that allows you to conclude $$¬∃z∀v∃uF(a,b,z,v,u)$$ for some$a,b$. To reduce$¬∃z$we need something to apply it to. The terms we have lying around are those involving$a,b,f,g$. To ... 0 $$w'x'+wx+w'y+yz'+x'z'$$ $$=(w'+z')x'+(w'+z')y+wx$$ $$=(w'+z')(x'+y)+wx$$ $$=(wz)'(xy')'+wx$$ Or $$...=(w'+z')(x'+y)+wx$$ $$=(w'+z'+wx)(x'+y+wx)$$ $$=(w'+x+z')(x'+w+y)$$ (I used$x+x'y=x+y$on the last line.) 0 If a liar says this, then the truth is the negation of the statement. In general, $$p\iff q\equiv (p\Leftarrow q)\wedge(q\Leftarrow p)\equiv(q\vee\neg p)\wedge(p\vee\neg q),$$ and so $$\neg(p\iff q)\equiv\neg(q\vee\neg p)\vee(p\vee\neg q)\equiv(p\wedge\neg q)\vee(q\wedge\neg p)$$ by DeMorgan's laws. In this particular situation, then, we let$p$be the ... 0 What I believe is the following: In case the person is telling a lie, either of the following statements must be true (i.e. the statement of the person is to be "negated"): $$\mathbb{The \ result \ of \ the \ toss \ is \ a \ head \ but \ the \ person \ is \ not \ telling \ the \ truth}$$ or$$\mathbb{The \ person \ is \ telling \ the \ truth \ but \ the \ ... 1 If$S$is any transitive relation such that$R \subseteq S$, then show that$R^n \subseteq S$, so$\cup_{n=1}^{\infty} R^n \subseteq S$. On the other hand, show directly that$\cup_{n=1}^{\infty} R^n$is indeed transitive. And it certainly contains$R$so... 0 The basic idea is to expand and simplify the formula to get an idea what the condition is saying,$\exists x ~ P(x) \land \forall y ~ \lnot Q(y)$and what the consequence is saying,$\exists z ~ \lnot P(z) \lor \exists w ~ Q(w)$. And since those are tautologically compatible, twice combine a term from the condition and a term from the consequence form an ... 1 Well a lot of people include those sorts of pedantic details and in fact it's often quite useful to do so. Ultimately what makes it into a paper or textbook is whatever communicates the point clearly to the reader. If you're just going to take a Cauchy principal value, or if the domain you were talking about was$x \in (10, 20),$then I wouldn't bat an eye ... 0 Let$\Delta$be the set of negations of sentences of$\Gamma$. We show that some conjunction of sentences of$\Delta$is inconsistent. For suppose to the contrary that every finite subset of$\Delta$is consistent. Then by Compactness there is a model of$\Delta$, that is, a structure$M$in which all the sentences of$\Delta$are true. Thus all sentences ... 1 First of all the distinction is not as important as one would think. When you use an informal formulation it can be considered a short hand description of how you would go about in creating the formal proof - just like a recipe for gingerbread is not a gingerbread, but it allows anyone to produce gingerbread if they're interested in doing so. Note that ... 0 The equivalence holds because the equivalence classes are infinite. If you have$(x_1,…,x_n)$such that the RHS holds, the set$\{x_j \mid j\in J\}$is finite. If it is nonempty, there is an element$y$such that$y\sim x_j$for$j\in J$and$y\neq x_j$. If the set is empty, the existence of$y$is implied by the fact that there are infinitely many ... 3 From your comment,$\simeq$in your question denotes isomorphism. This means that you have been given too much information: The two group structures are not isomorphic because$\Bbb{Z}^2$is not a cyclic group while$\Bbb{Z}$is. The two order structures are not isomorphic because with the lexicographic ordering there are elements$x, y \in \Bbb{Z}^2$... 1 Yes, that looks OK. You may want to be a little more specific about how you conclude$f(0)=(0,0)$, since$0$is not a symbol of the language. The two structures are so different that it is okay only to use part of them to conclude that they are not isomorphic. Conversely, you could also prove this looking only at$\le$and ignoring$+$, such as by observing ... 1 First of all, the structure on$\kappa^\alpha$that you describe is not a model of$\text{REI}_\alpha$. If you define$f E_\beta g$if and only if$f(\beta) = g(\beta)$, then the equivalence relations will be cross-cutting rather than refining. What you actually want to do is take$\kappa^{\alpha+1}$and for each$\beta\in \{-1\}\cup (\alpha+1)$, define$f ...

0

$(3)\Rightarrow (4)$, For every $\phi\in \mathcal{L}$, $M\models \phi$ or $M\models \neg \phi$, so for every $\phi\in \mathcal{L}$, $\phi\in C_n(T)$ or $\neg\phi\in C_n(T)$. By $(3)$ $T$ has model. If $M'\models T$, then $C_n(T)\subseteq Th(M')$. If $\phi\in Th(M')$, because $T$ has a model and for every $\phi\in \mathcal{L}$, $\phi\in C_n(T)$ or ...

1

Yes, $PA$ can prove that the "propositional busy beaver" is total. In fact, the bound you cite is provable in $PA$ - the standard proof doesn't use anything beyond $PA$!

2

Here is Doron Zeilberger's opinion bearing on this topic with a pointer to some feedback from me (which includes some remarks on Hagen's point about Principia Mathematica).

0

I would argue that the "right" relativization of a statement to (the degree of) a noncomputable set $B$ is the version where all the quantifiers range over the cone above $B$, $\{C: C\ge_T B\}$. On this cone, $\equiv_T$ and $\equiv_T^B$ coincide, so it doesn't matter which we use. If we look at the co-lower cone, $\{C: C\not<_TB\}$, instead, things are ...

1

I think that the idea of causation is the (or at least a) culprit here. In "most" implications in natural language, the implication is due to one thing causing another: If I eat thumbtacks, I will be unhappy. Unfortunately, this doesn't always line up with how the formal implication is interpreted. For instance, let's look at "I will only give you a ...

0

$p\to q$ , $\neg p \vee q$, $\neg q\to \neg p$, "$p$ is sufficient for $q$", "if $p$, then $q$", "$p$ only if $q$", "$q$ if $p$", "$q$ whenever $p$", "$q$ or not $p$", "$q$ is necessary for $p$", "not $p$ if not $q$", ... What's bugging me is why the first conversion from $p→q$ to $p$ only if $q$ doesn't make sense in everyday speech. Implication ...

1

Understanding numerical algorithms necessarily involves some arithmetic and algebra as well as just logic. I would strongly recommend you dip into Knuth's wonderful Art of Computer Programming. This is an encyclopaedic work but quite easy to use as a a very readable reference once you read the introductory sections. Volume 2 includes a discussion of the ...

0

Any such structure must be isomorphic to $(\Bbb{N}, 0, x \mapsto x + 1)$. To see this define $P(x)$ to hold iff for some $n \in \Bbb{N}$, $x = f^n(c)$. Then $P(c)$ and $\forall x (P(x) \to P(f(x))$ hold, so by $\psi$, $P(x)$ holds for all $x \in A$. So the function $g$ defined by $g(n) = f^n(c)$ maps $\Bbb{N}$ onto $A$. But then, if $A$ is infinite, $f$ must ...

2

The basic laws of equality (or identity) are : I.1 $∀x \ (x = x)$ I.2 $∀x∀y \ (x = y → y = x)$ I.3 $∀x∀y∀z \ (x = y ∧ y = z → x = z)$ I.4 $∀x_1 \ldots x_n y_1 \ldots y_n \ (x_1 = y_1 \land \ldots \land x_n = y_n → t(x_1, \ldots ,x_n) = t(y_1,\ldots, y_n))$, $\ \ \ \ \ ∀x_1 \ldots x_n y_1 \ldots y_n \ (x_1 = y_1 \land \ldots \land x_n ... 4 What you defined could be called a valid formal proof. A valid mathematical proof (or a proof accepted by the mathematical community) on the other hand might be described as an informal(!) arrangement of arguments that the reader finds convincing in the sense that he/she strongly believes that it is possible to write down a valid formal proof reflecting the ... 1 My personal opinion goes more along: A proof is valid if it convinces a significant number of experts in the field to declare it valid. A prime example was Andrew Wiles proof of FLT, a long and complicated proof, with initial flaws as well, in a subject only a few were deep into. A PhD student in algebra told me at that time that he would need two ... 0 We don't need to change, neither extend the idea of a mathematical proof just because many fields uses informal language. This is true that informal language might be more clear to the wide majority of people, but such a language can only be used for an explanation of the idea of the proof. On the other side the formal language is understood by a very small ... -2 Personally I've been having the same issues between the language aspect and the mathematical writing. from what I understand now: When it is "if and only if" would be the implies in both directions, whilst "only if" would be q only if p which is equivalent to p implies q. I agree that there is a problem between the boolean logic and the human language but ... 1 Here is an answer to the parts of your question: It is not possible to prove your statement by direct induction. I take this to mean the proof is only allowed use the induction hypothesis. Otherwise the question becomes incredibly vague. The reason why is given in the comments. An inductive hypothesis of$\sum\limits_{k=1}^n\frac{1}{k^2}<2$is too weak ... 4 HINT: prove that$\frac{1}{k^2}\le \frac{1}{k(k-1)}$for$k>1$1 1)$\big((P\rightarrow Q)\rightarrow P\big)$--- assumed [a] 2)$\lnot P$--- assumed [b] 3)$P$--- assumed [c] 4)$\bot$--- from 2) and 3) 5)$Q$--- from 4) by ex falso quodlibet (i.e. :$\bot \vdash \varphi$) or directly from 2) and 3) (skipping 4)) by negation elimination (i.e. :$\varphi, ¬ \varphi \vdash \psi$) 6)$P \to Q\$ --- from 3) and 5) ...

0

Assume the antecedent. Assume the negation of the consequent. Assume the antecedent of the antecedent of the antecedent. Assume the negation of the consequent of the antecedent of the antecedent. Derive a contradiction. Infer the negation of the negation of the consequent of the antecedent of the antecedent. Infer the consequent of the antecedent of ...

Top 50 recent answers are included