Tag Info

New answers tagged

1

See George Tourlakis, Mathematical Logic (2008), page 93 : 3.2.1 Metatheorem (Post's Tautology Theorem) : If $\Gamma \vDash_{TAUT} A$, then $\Gamma \vdash A$. Proof. It is most convenient to prove the contrapositive, namely, if $\Gamma \nvdash A$, , then $\Gamma \nvDash_{TAUT} A$ Some facts are needed : Claim One. There is an enumeration ...


2

There's no need to use distribution since $p \lor(\lnot q \lor r) \equiv p \lor \lnot q \lor r$ due to associativity of $\lor$, and by commutativity of $\lor$, that gives us $$\lnot q \lor p \lor r \equiv \lnot q \lor (p \lor r) \equiv q\rightarrow (p \lor r)$$ What is highly questionable in your proof is the second line of the following: $(q → p) ∨ (p∨r)$ ...


0

For Theorem L10: Suppose $( \sim B \implies \sim A)$ holds. We want to show $(A \implies B)$ is true. Since $\sim B \implies \sim A$ is true, then its negation, $\sim B \wedge A$, is false. But then, the negation of this statement, which is $B \vee \sim A$, is true. But $B \vee \sim A$ is equivalent to $\sim (\sim (B \vee \sim A)) \equiv \text{ }\sim ...


0

This is an application of the compactness theorem. If the theory $$\{\neg \varphi_i | i \in \mathbb{N} \} $$ is satisfied (has valuations for every finite subset) then it has a valuation for the entire set. This is the contrapositive of what you want to show.


0

No. I'll define "equivalence" as meaning that two propositions have the same truth-value. ↔ is defined by this table where $F$ indicates falsity, $T$ indicates truth, and $U$ indicates that the truth-value of a proposition takes on some other value than truth or falsity: ↔ F U T F T U F U U U U T F U T If $P$ has truth value of $U$, and so ...


0

Yes; this can be proved using the deduction theorem. TFAE. $(P \vdash Q) \wedge (Q \vdash P)$ $(\vdash P \rightarrow Q) \wedge (\vdash Q \rightarrow P)$ $\vdash (P \rightarrow Q) \wedge (Q \rightarrow P)$ $\vdash (P \leftrightarrow Q)$


3

Yes, that looks exactly right.


0

Now, you changed the question, first question is false yet because perhaps for each valuation $v$ only $v(\varphi_{n+1})=1$. But if you define $\Sigma=\{\varphi_1,\ldots,\varphi_n\}$ your proposition would be true. Even you defined $\Sigma=\{\varphi_1,\ldots,\varphi_n\}$ (and you must do it because $\varphi_1\vee\varphi_2\vee\ldots$ is meaningless) your ...


-1

I'll put up a resolution proof here. It probably doesn't help. assumption 1 ANac assumption 2 ANbc assumption 3 Aab R 1, 3 4 Abc R 2, 4 5 c


-1

I'll add my own loose answer here, and point out that we don't know exactly what your negation rule says. The only rule I will use is a resolution rule of inference R which can get described by saying "given two formulas $\phi$ and $\psi$ which only contain disjunction symbols and literals, if there exists a literal $\alpha$ in $\phi$ such that it is the ...


0

Note that, up to step 9 in your proof, you have not yet used the 3rd premise : $h \land \lnot (s \lor c) \Rightarrow p$, and we need it to complete the proof. We will start from step 9. $10 − \lnot c \lor \lnot n$ by De Morgan from 7 : $\lnot (c \land n)$ $11 - \lnot c$ by disjunctive syllogism from 10 and 5 [Note : disjunctive syllogism is a ...


0

"We know that: ((A∧B≡A≡B)≡(A∨B)) is true since it is an axiom(golden rule). But does this mean ((A∨B)≡(A∧B≡A≡B)) is a valid as a corollary since it is equivalent?" Yes. A quick way to verify this comes as to look at the truth table for ≡. ≡ False True False True False True False True Now suppose that (p≡q) is true and "p" is true also. ...


0

$ 1- c \wedge n \Rightarrow t$ $$ \equiv \sim (c \wedge n) \vee t \equiv \sim c \vee \sim n \vee t \equiv n \wedge \sim t \Rightarrow \sim c $$ $2- h \wedge \sim s$ $3- h \wedge \sim(s\wedge c) \Rightarrow p $ $$\equiv h \wedge (\sim s\vee \sim c) \Rightarrow p \equiv (h \wedge \sim s) \vee (h \wedge \sim c) \Rightarrow p \equiv \sim(h \wedge \sim s) ...


2

The so-called Golden Rule is "typical" of Equational Logic; thus I'll assume that your question must be "interpreted" in this context. I'll refer to the textbook by George Tourlakis, Mathematical Logic (2008), which is devoted to the exposition of mathematical logic according to the "equational" style. The axioms of the system are listed at page 42-43, and ...


4

The argument is not valid. One way to see why it is not valid, for example, is suppose $p = F$, $s = T,\;t = T,\; q = F$. Then we would have true premises, with a false conclusion. Hence the argument cannot be valid. What we can validly conclude, given the premises $p\rightarrow q$ and $s\rightarrow t,$ is that $(p \lor s) \rightarrow (q\lor t)$. Also, ...


3

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


2

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


5

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



Top 50 recent answers are included