New answers tagged

1

To prove 6) from 1)-5), by Resolution, we have to add to 1)-5) its negation: 6') $D(A, B)$. Then we need Unification. Performing the following substitution: $A \to v, \ B \to z,\ C \to u, x, \ f(A) \to t, y$ we get: $1) \neg E(f(A), C) \lor E(C, f(A))$ $2) \neg D(A, w) \lor E(f(A), w)$ $3) \neg E(C, f(A)) \lor \neg E(f(A), B) \lor E(C, B)$ $...


3

"No food is liked by all person" must be simbolized as: $\lnot \exists x \ (\text{food}(x) \land \forall t \ \text{likes}(x,t))$. Then we put into Prenex normal form to get: $\lnot \exists x \ \forall t \ (\text{food}(x) \land \text{likes}(x,t))$ and "moving inside" the negation sign: $\forall x \ \exists t \ \lnot \ (\text{food}(x) \land \...


0

"$A$ precisely when $B$" is defined as: when $B$ is true, then so is $A$, and when $B$ is not, neither is $A$.   So the truth state of $A$ and $B$ are equivalent; hence it is equivalent to: "$A$ if and only if $B$". "The light is on precisely when the switch is on." "The light is on if and only if the switch is on."


2

I'm taking this as a question about mathematical terminology. Using "when" as a synonym for "if" is common mathematical English jargon that adds a cosy temporal flavour to what are really static assertions about mathematical objects. E.g., "$tu$ vanishes when $t = 0$" sounds more lively than "$tu = 0$ if $t = 0$" (I've thrown in the cosy term "$x$ vanishes" ...


0

The following line of reasoning may help: \begin{align} (p\to q)\to(\neg q\to\neg p)&\equiv\neg(\neg p\lor q)\lor(q\lor\neg p)\tag{material implication}\\[1em] &\equiv\neg(\neg p\lor q)\lor(\neg p\lor q)\tag{commutativity}\\[1em] &\equiv \neg M\lor M\tag{$M:\neg p\lor q$}\\[1em] &\equiv \mathbf{T}.\tag{negation law} \end{align} Is the above ...


0

It depends on the logical inferences you have available. One way is to note that $$ (p\rightarrow q)\equiv(\neg q\rightarrow\neg p)\qquad\text{(contrapositive)} $$ so your original expression is equivalent to $$ (p\rightarrow q)\rightarrow(p\rightarrow q) $$ and if we let $r=(p\rightarrow q)$ we have $r\rightarrow r$, which we either know is true or if you ...


0

Intuitively speaking, I think of both statements as having an implicit "over all possibilities" universal quantification. Let me explain: If I say "if $A$ then $B$", I mean that for all possibilities in which $A$ is true, $B$ is true. So let's say $A = p \land q$, $B = p \lor q$. Then "if $A$ then $B$" means for all possibilities of $p$ and $q$ that make $...


1

"$A$ is true if $B$ is true" means that when $B$ is true, then also $A$ is; but we do not know about the truth of $A$ when $B$ is false. But then we add that "$A$ is true only if $B$ is true", that means that we cannot have $B$ false and $A$ true. Conclusion: $A$ and $B$ must both be true "together" or false together.


0

They're indeed equivalent (implication goes both ways). In fact $$ p\Rightarrow q \equiv \neg(p \land \neg q) $$ and $$ \neg q \Rightarrow \neg p \equiv \neg (\neg q \land \neg \neg p)\equiv \neg (p \land \neg q) $$ So the two are equal, and therefore one implies the other.


0

The schema in question is the following. If P then –P. To see that this is not contradictory notice that it is implied by its own consequent –P, which of course is not contradictory. No non-contradictory sentence implies a contradictory sentence. It is useful to be aware of the fact that every conditional follows from its own consequent. Moreover it implies ...


4

Natural Deduction refers to several deductive systems in first-order logic, and so without additional information it isn't clear which specific system is intended. Written in tree form, and not writing out sequents, one possible derivation would look something like this (the MathJax formatting is not ideal, but it conveys the idea): $$ \begin{array}{cc} \...


1

I don't know why I wrote the above axioms when I didn't really care if they had the form CδCxyδz or CδzδCxy, but I suppose the forms I used might provide for a more instructive proof. Section 2. part I. of Meredith's paper gave me enough hints, along with some previous experience working with this sort of system, to construct a proof. As a special case of ...


1

Hint: What is the antecedent of the assumption? Can you prove that antecedent?


0

Not exactly sure what you mean by natural deduction, I'm gonna assume you want a proof witouth using formalities at all: $H$ has only two possible states, $T$ or $F$. Therefore $H \implies H$ can only be $(T \implies T) \equiv T$, or $(F \implies F) \equiv T$. So now we have $T \implies G$. Since this statement is a premise, we are to take it as True, ...


1

Use the meaning $\lnot a \vee b$ where ever an $a\implies b$ appears: $$ (H\implies H) \implies G \\ (\lnot H\vee H) \implies G \\ \lnot((\lnot H\vee H)) \vee G \\ (H \wedge \lnot H)) \vee G \\ \mbox{false } \vee G \\ G $$


0

A sequence $(x_n) $ of real numbers does not converge to a real number $ x $ iff $\exists \epsilon \in \mathbb{R}: [\epsilon > 0 \land \forall n_0 \in \mathbb{N}: \exists n\in \mathbb{N}:[n \ge n_0 \land |x_n-x|\ge\epsilon]]$


0

The completeness of ${\mathbb R}$ allows to formulate this negation in a way that avoids the cumbersome "for all $x$ we don't have convergence to $x\,$". It is sufficient to formulate that the sequence in question violates the Cauchy condition, as follows: There is an $\epsilon_0>0$ such that for any $n_0$ we can find $m$, $n>n_0$ with $|x_m-x_n|\geq\...


2

$\forall \varepsilon > 0 \ \exists n_0 \in \mathbb{N}$ $\forall n$, if $ n \ge n_0$ then $ \ |x_n-x| < \varepsilon$. Let $p: n\ge n_0$ and $q:\ |x_n-x| < \varepsilon$. Then, $\forall \varepsilon > 0 \ \exists n_0 \in \mathbb{N} $$\forall n$, $p\implies q$. Note that $\lnot(p\implies q)=\lnot(\lnot p\lor q)=p\wedge\lnot q$ and $\lnot\...


6

In ordinary language: For any real number $x$, there are terms $x_n$ in the sequence with arbitrarily high rank which will remain (at least) at a minimal distance from $x$. Formally, as there's really an implication in the definition of convergence: $$\exists x\,\forall\varepsilon\,\exists n_0\,\forall n,\enspace\bigl((n\ge n_0 )\implies(\lvert x_n-x\...


4

You can write the definition of $(x_n) \to x$ as $$\forall \varepsilon > 0 \ \exists n_0 \in \mathbb{N} \ \forall n \ge n_0 \ |x_n-x| < \varepsilon$$ When you negate such a statement, the front-loaded quantifiers flip (so the $\forall \exists \forall$ becomes $\exists \forall \exists$, and the quantified proposition is negated (so the $|x_n-x|<\...


1

The question is asking you to use the rules of deduction you have been given to show that the two sides of the equivalence are exactly the same as each other - so in this case, show that "((for all x: P(x) is true) or (A is true))" is logically equivalent to "for all x: (P(x) is true or A is true)". "x does not occur as a free variable in A" means that you ...


0

The first proposition in the first question says: Any $x$ in the universe of discourse that has property $P$ also has property $Q$. The second says: If every $x$ in the universe of discourse has property $P$, then every $x$ in the universe of discourse has property $Q$. To see whether two propositions are equivalent, it’s often helpful to ask ...


1

In almost every context you will encounter $a \implies b \implies c$ it means $$a \implies (b \implies c)$$ This is so common in constructive logic that it is effectively a universal standard. The fake reason for it is that $$a_0 \implies (a_1 \implies (a_2 \implies (\dots \implies b)))$$ is propositionally equivalent to $$(a_0 \land a_1 \land a_2 \...


2

Edit: As pointed out in the comments, a self contained proof would have been better than just finishing what Ferengi Godfried started and pointing out that the last part can be done in the same way. So here is a full, self-contained proof. Answer: We have to prove by induction that for a formula $q$ in propositional logic which consists only of atoms, ...


0

You can't actually accomplish this, but the question still has some merit to it, as I hope I'll make clear in the second paragraph. You can't actually accomplish this, because formal Boolean Algebras, logically speaking, qualify as first-order theories with an equality predicate with all variables quantified. The operations on Boolean Algebras are also not ...


1

Firstly, your statement of the pumping lemma is wrong! The last quantifier should be universal. Secondly, both of you are wrong! Next time don't write in that messy inconsistent form; either use brackets or "$:$" or "$.$" consistently. Push the negation in from the front, and systematically use De Morgan's: $\neg \forall x \in S\ ( \cdots ) \...


-1

Hint: Prove that, in Polish notation, $\vdash$CpCNpq. More fully: axiom 1 CpCqp axiom 2 CCpCqrCCpqCpr axiom 3 CCpqCCpNqNp axiom 4 CNNpp 2 r/p 5 CCpCqpCCpqCpp 5, 1 6 CCpqCpp 6 q/Cqp 7 CCpCqpCpp 7, 1 8 Cpp hypothesis 9 | p hypothesis 10 || Np 1 q/Nq 11 || CpCNqp 1 q/Nq p/Np 12 || CNpCNqNp 11, 9 13 || CNqp 12, 10 14 || CNqNp 3 p/Nq, q/p ...


1

If you can prove $\Gamma \vdash ¬(\alpha \rightarrow \alpha)$, you can say $$\Gamma,\lnot \beta \vdash ¬(\alpha \rightarrow \alpha) \\ \Gamma \vdash (\lnot \beta \implies¬(\alpha \rightarrow \alpha)) \\ \Gamma \vdash \beta$$


0

Hint You have to use the axioms; in addition, some preliminary results, easily provable with axioms Ax.1 and Ax.2, may be useful: Lemma 1 : $⊢α→α$ (Derived rule of) Syllogism : $α→β, β→γ ⊢ α→γ$ Deduction Theorem : if $\Gamma, \alpha \vdash \beta$, then $\Gamma \vdash \alpha \to \beta$. Easy example: : $⊢β∨α→α∨β$ 1) $\vdash \alpha \to (\alpha \lor \...


1

This depends on convention, just like the precedence between different operators like $\neg, \land, \lor$ etc. I think that usually, the connective is interpreted right-associative, i.e. $a \to b \to c \Leftrightarrow a \to (b \to c)$ but that depends on what the author specified.


1

In first order logics, true and false are not values that are taken on by bound or free variables. If you have a background in software this may be confusing since you can store true/false into variables just as easily as storing integers or strings. So if you have an expression like $$\forall x ~ P(x)$$ then $P$ holds for every object in the domain of ...


3

No. Consider the case where $A$ and $B$ are false, and $C$ is true. The first statement is true (since "false implies $X$" is always true), but the second is false (since both implications are true).


1

We're missing two, so using your table: $$\begin{align*}&(P\rightarrow Q)\wedge\neg Q\\&\;\;\;\;\;\;\;\;\;\;F\\&\;\;\;\;\;\;\;\;\;\;T\\&\;\;\;\;\;\;\;\;\;\;F\\&\;\;\;\;\;\;\;\;\;\;T\end{align*}$$ and finally $$\begin{align*}&\left[(P\rightarrow Q)\wedge\neg Q\right]\rightarrow\neg P\\&\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;T\\&...


0

"Combine" your tables for ${P}\rightarrow {Q}$ and $\neg{Q}$ using "and". The result must be the same to $\neg P$.


0

Your confusion lies in the interpretation of sentenses. The original text says: " The main benefit of structured proofs is that they allow us to prove things that cannot be proved using only ordinary rules of inference. " What author means is that since the structured proofs allows us to introduce assumptions, we can now get rid of those Mendelson's 3 ...


0

Using Polish notation, can you manage to show from your premises that C$\alpha$$\gamma$ and C$\gamma$$\alpha$ are both tautologies?


1

Take any formulae $α,β,γ$ such that $α \equiv β \equiv γ$. Given any interpretation of atomic propositions:   If $α$ is true, what can you say about $β$?   If $β$ is true, what can you say about $γ$?   Similarly in the reverse direction. Therefore can you conclude that $α \equiv γ$?


0

Use the deduction theorem repeatedly to get an equivalence between the chain of implications and the ability to prove the final consequent from the set of antecedents. Then use the $\land$ rules to get an equivalence between provability from a finite set and provability from the conjunction of the set. Finally use the deduction theorem once to get between ...


-1

$(A→C)\land (C→\overline{B})\land B→\overline{A}$ $=(A→C)\land (C→\overline{B})$ Using Hypothetical syllogism : $=(A→\overline{B})\land B$ Using Modus tollens : $=\overline{A}$ Alternative way: $(A→C)\land (C→\overline{B})\land B→\overline{A}$ $=\overline{((\overline{A}\lor C)\land (\overline{C}\lor\overline{B})\land B)}\lor\overline{A}$ $=...


1

Indeed it is perfectly correct logical reasoning to prove your desired tautology. To be completely self-contained, you might want to add a final line stating that the desired implication is true since you have derived the consequent from the antecedent. However, do take note that if you're required to work in some specific framework, such as natural ...


0

$(P \Rightarrow Q)$ $\land$ $(Q \Rightarrow P) $ $\equiv$ $(\lnot P \lor Q)$ $\land$ $(\lnot Q \lor P)$ The distributive law gives you (note that two of those four expressions that you get simply vanish because they represent contradictions) ($\lnot P$ $\land$ $\lnot Q)$ $\lor$ ($P \land Q)$ $\equiv$ $\lnot (P \lor Q)$ $\lor$ $(P \land Q)$ $\equiv$ $(P \...


0

I chose this way : $(p \rightarrow q) \land (q \rightarrow p ) \equiv (p \lor q) \rightarrow (p \land q) \equiv (\lnot p \lor q) \land (\lnot q \lor p) \equiv ((\lnot p \lor q) \land \lnot q) \lor (\lnot p \lor q) \land p)$ $\equiv ((\lnot p \land \lnot q) \lor (q \land \lnot q)) \lor ((p \land \lnot p) \lor (p \land q)) \equiv (\lnot p \land \lnot q) \lor(p ...


2

A simple atomic proposition can qualify as a tautology, if the constant true proposition '1', also denoted 'T', belongs to the vocabulary of the language. A simple atomic proposition cannot qualify as a tautology if '1' is not part of the vocabulary of the language.


3

However, suppose I proved $p$ to be true. I am tempted to write $p \iff \top$, but this means "$p$ is a tautology". No it doesn't. $p \Leftrightarrow \top$ is just another formula, one that happens to be true in exactly the same structures as $p$ is. It also happens that $p \Leftrightarrow \top$ is a tautology exactly if $p$ itself is a tautology. So if ...


0

the error is the application $ ax \in n \mathbb{Z}+\{ay\} \rightarrow x \in n \mathbb{Z}+ \{y\}$ is not true ; it is true only if $a$ invertible modulo $n$, that is only if $gcd(a,n)=1$


2

Think on these lines. $(1)$ All humans die. Equivalent form : For every $x$, if $x$ is human, then $x$ must die. (An implication) $(2)$. Some animals are color blind. Equivalent form: There exists some $x$ such that, $x$ is an animal and $x$ is color blind. (A conjunction)


1

To show that the formula: $(p→q)→((p∨r)→(q∨r))$ is valid with Resolution, we have to consider its negation and show that this is unsatisfiable. Thus, we have to consider: $\lnot [\lnot (\lnot p ∨ q) ∨ (\lnot (p∨r) ∨ (q∨r))]$ i.e. $(\lnot p ∨ q) \land (p∨r) \land \lnot q \land \lnot r)$. Thus, we have the set of clauses: $\{ \{ ¬p,...


1

Let us look at the specific case of two mathmajors. There are the following three possibilities: $\{m,f\},\{m,m\},\{f,f\}$ Of these, only the one outcome would make the phrase "All math majors are male" true, namely where it was $\{m,m\}$. On the other hand, both of the phrases $\{m,f\}$ and $\{f,f\}$ would make the phrase "All math majors are male" ...


1

The negation of a statement $\varphi$, semantically, is a statement $\neg\varphi$ which is true iff $\varphi$ is false. Now in your case, if "all mathematicans are male" is true then "all mathematicans are female" is false. However is in not the case that if "all mathematicians are male" is false, then, all mathematicians are female. Indeed the statement ...


1

"All majors are female" is (one of) the opposite of "All majors are male" The negation of a sentence is another proposition that makes your sentence "look like" false. The way to go is to replace the universal quantifier "All" with its negation "There exist one", and the solutions your professor gave are indeed correct. Think at the sentence "All swans ...



Top 50 recent answers are included