Tag Info

New answers tagged

1

I will show that 1 is true and therefore 2 is false. Note that since $\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}$, we have that $\Sigma\equiv\{\neg p_1\to \neg p_2, \neg p_2\to \neg p_3,\, \dots\,\}$. In particular, we have $\Sigma \equiv \bigcup_{1 \leq n<\omega}\{\neg p_n \to \neg p_{n+1}\}$. (1) Claim: for all $n<\omega$ such that $\Sigma \cup ...


0

Both of them are false, this is due to exact definition: 1.for a formula $\psi$ we say $\vDash\psi$ if for all valuations $w$, $w(\psi)=1$ not for just a valuation $v$. 2.We say a set is consistent if we could find a valuation $v$ such that for all formula $\psi$ in it $v(\psi)=1$. But as you said formula $\varphi_1$ could be a contradiction.


4

This is a logic "confused" problem ... We approach it "by steps". Question 1 We assume that the meaning of the first part of the question is : 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$ : ...


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

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

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 ...


4

$$\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

I'd say this proof is more easily understood if you generalize it by replacing $\bot$ with an arbitrary proposition $C$: $$\left((A\Rightarrow C)\land (B\Rightarrow C)\right)\Rightarrow \left((A\lor B)\Rightarrow C\right)$$ But this is just the elimination rule for $\lor$ in disguise in natural deduction: $$\underline{\Gamma\vdash A\lor B \quad ...


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

$(p\to q) \wedge (q\to b)$ implies $p\to b$, but not the other way around. Hence those two justifications are false as written. Fortunately, you only need them in one direction, the one that is true.


1

I'll give you a hint. Recall that for $f : A\rightarrow B$ $$f^{-1}(C) = \{x\in A : f(x)\in C\}$$ Therefore $$\begin{align}x\in f^{-1}(B\setminus Y)&\Leftrightarrow x\in A\ \text{and}\ f(x)\in B\setminus Y \\ &\Leftrightarrow x\in A\ \text{and}\ f(x)\in B\ \text{and}\ f(x)\not\in Y \end{align}$$ From here, there are just two small steps left: can ...


0

Hint 1: $B\setminus Y = B \cap Y^c$. Hint 2: \begin{align*} f^{-1}(B\setminus Y) &= f^{-1}(B\cap Y^c)\\ &= \{a \in A : f(a) \in B \cap Y^c)\} \\ &= \{a \in A : f(a) \in B \text{ and } f(a) \notin Y\} \end{align*} Hint 3: To show that the two sets are equal, you must take $a \in f^{-1}(B\setminus Y)$ and show it is in $f^{-1}(B)\setminus ...


1

Whenever you want to show that two sets are equal, try element chasing. That means, assume your element is in the set on the left, $f^{-1}(B \setminus Y)$, and then show that it must be in the set on the right, $f^{-1}(B) \setminus f^{-1}(Y)$. That's half of the proof. Chase an element in the other direction, and you've done both halves. First assume $x\in ...


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

For some general remarks on how to prove that sets of connectives are/are not complete, see How to prove that a set of logical connectives is functionally complete(incomplete)? In this particular case, it is fairly easy to figure out how to build $\vee$ and $\neg$ out of $\{\$,\top,\bot\}$, once you see that $\$(p,q,r)$ equals $q$ if $p$ is true and $r$ ...


4

I think you are looking for an example of statements here. That is $\phi, \psi, \chi$ s.t. these properties hold. Let $L=\{\cdot\}$. Let $T=\text{group axioms}\cup \text{there are only twelve distinct elements}$. Now Let $\phi$ say that "I'm is abelian and I'm not is not cyclic" (i.e. $\forall a,b, a\cdot b = b\cdot a$ and a fairly long sentence that says ...


1

If ¬ (ψ → ϕ), then ψ, and ¬ϕ. If ¬ (χ → ϕ), then χ, and ¬ϕ. If ψ, and χ, then (ψ ∧ χ). If (ψ ∧ χ), and ¬ϕ, then ¬[(ψ ∧ χ)→ϕ]. If [ϕ ⟷ (ψ ∧ χ)], then [(ψ ∧ χ)→ϕ]. Thus, ϕ ⟷ (ψ ∧ χ), ¬ (ψ → ϕ), and ¬ (χ → ϕ) do not simultaneously hold true.


1

We have that : $\lnot (ψ \rightarrow ϕ)$ is equivalent to : $\lnot (\lnot ψ \lor ϕ)$ i.e. to : $ψ \land \lnot ϕ$. And $\lnot (χ \rightarrow ϕ)$ is equivalent to : $χ \land \lnot ϕ$. Thus, there is no way to satisfy both formuale together with : $ϕ \leftrightarrow (ψ \land χ)$. Comment The "problem" in your argument is the ...


2

As mentioned in the comment, the translation here is indeed crucial. The use of 'but' does not seem to fit in there (but I have to say that I'm also not a native English speaker). In any case, spoken languages can hardly cover the subtleties of logic (except for Lojban...). There are several interpretations or conventions for natural languages that are not ...


1

After chugging away on this for a while, I do think that the difficulty comes in keeping any “in-scope assumptions” available in each of the cases. The proof I outlined in the question does this by making the codomain of the coproduct arrow an exponential. That is, in trying to show $C$ from the assumptions $A \lor B$, $A \lif C$, and $B \lif C$, I ended ...


3

$\;\lnot (r \land t)\lor u,\;$ (premise) $\;r\land t,\;$ (premise) $\lnot \lnot (r \land t)$ from $(2),\;$ (double negation) $\therefore \;u\;$ (disjunctive syllogism)


1

It is all done with sentences and connectives: A sentence is usually denoted by Capital letters like $A,B$, etc., the connectives are or:=$ \lor$; and:=$\land$, and if-then:= $ \rightarrow$, and negation connective is $\lnot$ so that, e.g., If I go, then I will see a movie is transcribed as : say $A$ is " If I go" , and $B$ is , "I will see a movie" is ...


1

Using OTTER [1], I've found a 7 step, level 4 proof. axiom 4 CxCyx level 0 axiom 5 CCxyCCyzCxz 0 axiom 6 CCCxyxx 0 D4.4 8 CxCyCzy 1 S5.5 9 CCxyCCCxzuCCyzu 1 D5.8 31 CCCxCyxzCuz 2 D9.6 ...


0

Combining the subformula strategy, weighting of the axioms, the assumptions, and the goal, and a (partial) level saturation search, I've found a 20 step (excluding the axioms and assumptions), level 6 proof using OTTER [1] (OTTER treats "p" and "q" here as nullary functions or in other words, constants). axiom 4 CxCyx. level 0 ...


0

Yes, all of those systems have single axioms. Rezus's paper On a Theorem of Tarski makes this clear.


1

Combining the subformula strategy, weighting of the axioms and the goal, and a (partial) level saturation search, I've found a 15 step (excluding the axioms), level 5 proof using OTTER [1]. Actually, instead of proving CCCp0Cq0CCCp0qp. OTTER proved the more general CCCpqCr0CCCpqrp. (we can substitute q/0, r/q in CCCpqCr0CCCpqrp to get CCCp0Cq0CCCp0qp, ...


3

Let's assume the following axiom: Negatives Reverse Inequalities: If $x < y$ and $z < 0$, then $xz > yz$. Now suppose that $a < b < 0$. Then since $a < b$ and $a < 0$, it follows from the above axiom that $a^2 > ab$. Likewise, since $a < b$ and $b < 0$, it follows from the above axiom that $ab > b^2$. Combining ...


3

We have $$\begin{align} \neg(a < b < 0) &\iff \neg(\,(a < b) \,\&\, (b < 0)\,) \\&\iff (\,\neg(a < b)\,) \vee (\,\neg(b < 0)\,) \\&\iff (a \geq b) \vee (b \geq 0) \,\,. \end{align}$$


1

You are right. Your second example is [page 28] : Example 2.7.1 :We prove the sequent $(¬(¬(φ ∨ (¬φ))))$. See the final comment : [...] At first sight it looks as if the two ¬ signs at the beginning of the conclusion have made extra work for us. This is not so. The sequent $(φ ∨ (¬φ))$ is certainly valid, but it is just as hard to prove; in fact ...


2

When it comes to showing that logical statements are independent of certain variables I like to cycle through them and show it this way. Notice that you've shown that your statement is independent of the truth or falsity of $R$ so I'll take that approach here. Let's suppose $R = T$, then $$\neg Q\vee(\neg Q\wedge R) = \neg Q\vee(\neg Q\wedge T) = \neg ...


6

\begin{align*} \neg Q \vee (\neg Q\wedge R) &= (\neg Q\wedge 1) \vee (\neg Q\wedge R) \\ &= \neg Q \wedge (1\vee R) \\ &= \neg Q \wedge 1 \\ &= \neg Q \end{align*}


1

If you don't mind using order theory, you can show it without any reference to true or false. Let $\leq$ be an order with $A \vee B \geq A$ and $A \wedge B \leq A$. Then, $\neg Q \vee (\neg Q \wedge R) \geq \neg Q$ and $\neg Q \wedge (\neg Q \wedge R) \leq \neg Q$. If the two expressions are equal, you can see that they must equal $\neg Q$.


1

Assume that Q is true. Then it follows that $\lnot$Q is false, and ($\lnot$Q$\land$R) is false also. So, ¬Q∨(¬Q∧R) is false. Assume that Q is false. Then $\lnot$Q is true, and thus so is ¬Q∨(¬Q∧R). Since Q is either true or false, and since in either case the equality here ¬Q∨(¬Q∧R)=¬Q, it follows that ¬Q∨(¬Q∧R)=¬Q in all cases.


1

$Q\implies\lnot Q \wedge R\implies\lnot Q$ Contradiction!


1

One might argue that $\lnot$I corresponds to the formula (($\phi$$\rightarrow$0)$\rightarrow$$\lnot$$\phi$). This can get thought of as one-half of the definition of $\lnot$. On the other hand, RAA similarly corresponds to the formula (($\lnot$$\phi$$\rightarrow$0)$\rightarrow$$\phi$). This doesn't correspond to any definition quite so easily.


2

Well, Chiswell and Hodges in the exercises immediately following the quoted remarks in their book explicitly give some examples of sequents whose proofs in their system depend essentially on RAA, including $$\vdash \neg(\phi \to \psi) \to \phi$$ $$\vdash \phi \to (\neg\phi \to \psi)$$ So: If a conditional is false, its antecedent has to be true(?). A ...


1

Yes. You have to follow a "typical" proof of "equivalence" between Natural Deduction and Hilbert-style. See : Sara Negri & Jan von Plato, Structural Proof Theory (2001), page 41-on. An alternative approach is through soundness and completeness. Both proof systems are sound and complete regarding valid formulae; thus, a formula unprovable in ND, ...


1

Also in the Case 3, i.e. $\mathbf A \equiv \mathbf B \land \mathbf C$, we have to apply the Induction Hypotheses. We have that, by IH both $\mathbf B$ and $\mathbf C$ satisfy the theorem, i.e. : $\mathbf B \equiv (B_1 \lor \ldots \lor B_n)$ and $\mathbf C \equiv (C_1 \lor \ldots \lor C_k)$ where the RHS are DNF (disjunctions of conjuncts of ...


2

See Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001), page 23 : take the special case in which $\Sigma$ is the empty set $\emptyset$. Observe that it is vacuously true that any truth assignment satisfies every member of $\emptyset$. (How could this fail? Only if there was some unsatisfied member of $\emptyset$, which is absurd.) ...


0

You cannot prove $P \leftrightarrow Q$ "alone", and you cannot prove $P \rightarrow Q$ alone. There must be some other assumption missing ! This is the reason why (in this you are right !) you cannot understand the claim that : "not-Q contradicts a given P". Referring to your attachment, I assume that you are interested to the following proof : ...


3

The only way to prove that proposition $a\to b$ is false is if $a$ is true and $b$ is false. Hence, you must have $p$ true and $r$ false, by the conditions of the task you were set. If $q$ were true, then $r$ would be true (by the second hypothesis), so we must have $q$ false. Now verify that $\{p$ true, $q,r$ false$\}$ satisfy both hypothesis and ...



Top 50 recent answers are included