# Tag Info

1

From what I've read, one usually says that $\;\oplus\;$ and $\;\iff\;$ are mutually associative. And since one is the negation of the other, in other words $$A \oplus B \;\iff\; \lnot (A \iff B)$$ therefore I much prefer to use the symbols $\;\not\equiv\;$ and $\;\equiv\;$ instead: that makes the relationship between these two symbols clearly visible. ...

2

I'll give you a solution equivalent to Tetori's one in Natural Deduction : 1) $B$ --- assumed [a] 2) $A \rightarrow B$ --- from 1) by $\rightarrow$I 3) $\lnot (A \rightarrow B)$ --- premise [1] 4) $\bot$ --- from 2)-3) by $\rightarrow$E 5) $\lnot B$ --- from 1) and 4) by $\rightarrow$I, discharging assumption [a] 6) $A$ --- assumed [b] 7) $\lnot A$ ...

3

I'll try to prove it in intuitionistic logic (that is, I'll try that without excluded middle.) Lemma. It is a theorem of intuitionistic logic: $$\lnot p\lor q\to (p\to q)$$ Proof of this lemms is not difficult: if $\lnot p$ holds, then $p\to q$ since $p\to \bot$ and $\bot \to q$ and if $q$ holds then $p\to q$ since $p,q\vdash q$ and deduction theorem. In ...

1

"First, in this language there are to be some unambiguously constituted sentences, whose internal structure we shall ignore (for our study of the propositional calculus) except for the purpose of identifying the sentences. We call these sentences prime formulas or atoms; and we denote them by capital Roman letters from late in the alphabet... [emphasis in ...

1

Still in process... The following will serve as a placeholder for the moment. I use condensed detachment notated by "D" in the proof analysis. Dx.y indicates that condensed detachment gets applied to formula x with form Cx y, and y has form x' such that x and x' have a most general unifier. So we want to prove ...

0

For an infinite $S$ we cannot stick to getting an equivalent and independent subset of $S$. An example that shows this is \begin{align} S =\{ & A_1 ,\\ & A_1 \land A_2 ,\\ & A_1 \land A_2 \land A_3 ,\\ & A_1 \land A_2 \land A_3 \land A_4 , \ldots \} \end{align} for propositional variables $A_i$. No set that contains two of these ...

0

The proof for any finite set of formulas is easy enough: Assume set of formulas $S$ is not itself an independent set (if it is, then clearly $S$ meets the condition of the theorem since $S$ is obviously equivalent to itself). Let the number of formulas in $S$ be $n_0$. Since $S$ is not an independent set, there is some proper subset $T_1 \subset S$ which ...

0

(1) The distributivity law As we know, the distributivity law, states that $\vDash (\phi \land \psi)\lor \sigma \equiv (\phi \lor \sigma)\land(\psi \lor \sigma)$ $\vDash (\phi \lor \psi)\land \sigma \equiv (\phi \land \sigma)\lor(\psi \land \sigma)$ where the former consists of its application on ∨ over ∧ and the latter on ∧ over ∨. (2) The question ...

0

I use Lukasiewicz/Polish notation. This answer will suppose that we have disjunction "A" is an abbreviation for "CN". Or that Apq is defined as CNpq. Thus, the axioms become: C CNrr r. C r CNrs. C CNrs CNsr. C Crs C CNrt CNst. We have a new axiom: Na. Now in axiom 2 let's substitute axiom 2 for "r". This yields: C CrCNrs CNCrCNrs s. ...

-2

It is not so easy to see! The only axiom we have is the original single axiom DDpDqrDDtDttDDsqDDpsDps, and our only rule of inference other than uniform substitution is {D$\alpha$D$\beta$$\gamma, \alpha} \vdash \gamma. This "if S⊢(A→B), then S∪{A}⊢B" involves \rightarrow. I'll rewrite that as: "if S\vdashCab, then S ∪ {a} \vdashb." Thus, ... 2 Let \langle\varphi_1,\varphi_2,\ldots,\varphi_n\rangle be a proof of (A\to B) from S: \varphi_n is (A\to B), and each \varphi_k with k<n either is in S, is an axiom, or follows from earlier statements in the list by one of your inference rules. Then \langle\varphi_1,\ldots,\varphi_n=(A\to B),A,B\rangle is a proof of B from ... 1 The statement S\vdash (A\to B) means that there is a formal proof using the assumptions in S (as well as standard axioms, and rules of inference including modus ponens) which ends with the line A\to B. Take this proof and append two more lines: A (assumption) B (modus ponens from the previous two lines). You now have a formal proof using ... 2 Assuming that the correct formula is : ∀x[∀y[¬A(y)∨B(x,y)]⇒[¬∀yB(y,x)]] --- (*) we have that p \Rightarrow q is equivalent to \lnot p \lor q; thus (*) is : ∀x[\lnot ∀y[¬A(y)∨B(x,y)] \lor [¬∀yB(y,x)]] i.e. : ∀x[\exists y \lnot (¬A(y)∨B(x,y)) \lor \exists z (\lnot B(z,x))] i.e. to : \forall x \exists y \exists z [\lnot ... 1 I can only give you a proof sketch since you did not tell us which axioms you have in your system. Lemma (Soundness) Γ \vdash ϕ ⇒ Γ \vDash ϕ Proof Sketch: Let Γ⊢ϕ. We need to show that Γ \vDash ϕ, that is, that for any truth assignment ν such that ν(ψ)=1 for all ψ∈Γ then ν(ϕ)=1. By definition of Γ⊢ϕ, there is a derivation D with ... 0 I prefer to write the rules with the symbol : \vdash for derivability always explicit. Thus, the above rule is :$$\frac{\Gamma, \varphi \vdash \psi }{\Gamma \vdash \varphi \rightarrow \psi} \quad (\rightarrow-i)$$They are the rules of Natural Deduction in "sequent calculus-style" and you can find them for example in Jan von Plato, Elements ... 1 A is the first to answer. Since he said no, that means B and C don't both have white hats. This leaves 6 possible cases (in order ABC). WWB WBW WBB BWB BBW BBB Now, WBW is easy to exclude. If B sees two whites, then he knows his must be black. Also we can exclude BBW. For, if A didn't know, but B sees black and white, he knows that he must be ... 2 I suspect that you have a rule of inference that allows you to infer \varphi from the pair of formulas \psi\to\varphi and \psi. If so, the final step of the proof is justified by the earlier appearance of \varphi_n and \psi_m in the proof. 1 Here are a few, probably in order of increasing difficulty: In every formula the total number of connectives (\neg and \to) is equal to the number of left (or right) parentheses. In every formula the number of (not necessarily distinct) propositional symbols is at least one more than the number of instance of \to. Every formula has the following ... 0 Ok, I decided to convert the comments into an answer. The sentence in English is "Anyone who has cats as pets will not have mice". This naturally translates as$$\forall x (\exists y(Cat(y) \land Have(x,y))\rightarrow \neg \exists z (Mouse(z) \land Have(x,z)))$$remove \rightarrow$$\forall x (\neg\exists y(Cat(y) \land Have(x,y))\lor \neg \exists z ... 0 Hints : Let P denotes an animal, and A denotes a person: (1):$P$is a wolf$\implies$P howl. (2):$A$has cats as pets$\implies $A don't have mice. (3):$A$is a light sleeper$\impliesA$don't live near anything that howls. (4): John has cats XOR John lives near wolves. [ this one can be expressed as : (John has cats AND ... 0 If a dog, then has 4 legs- true If a dog, then has no legs- false If not a dog(may be a cat), then has 4 legs- true If not a dog( a snake), then has no legs - true 1 Typically,$\vee$and$\wedge$are of equal precedence, and so parentheses are used to specify which must come first. For example,$(a\vee b)\wedge c$is not in general the same as$a\vee(b\wedge c).$Consequently,$a\vee b\wedge c$is ill-defined, under the standard rules of propositional calculus. I suspect, therefore, that your text has introduced ... 2$\lor$and$\land$have equal precedence, so we typically evaluate from left to right. Here, because of associativity of$\lor$, all disjuncts follwing the$\land$connective can be grouped together, as follows: $$(p \lor \lnot q) \land (\lnot p \lor q \lor p \lor \lnot r \lor \lnot q)$$ Having done this, we see that within the grouped disjunctions to ... 1 We can easily prove that :$(\lnot p \lor q) \rightarrow (p \rightarrow q)$holds intuitionistically with Natural Deduction. I'm quite unfamiliar with the intuitionistical version of tableau method; I've seen : Melvin Fitting, Intuitionistic logic Model theory and Forcing (1969), page 28 where the usual tableau rules are modified as follows : ... 1 I think you have the statement for unique readability written out right, but the problem is that the language is not uniquely readable. To see this, we can construct a=<>+<>+<#>, b=<>+<#>+<#>, c=<>+<>+<#>+<>+<#>+<#> Now, since a, b, and c are all in L*, <>+a+b+<#> and <>+c+<#> are also each in L*. But ... 2 The explanation is in the paragraph following Definition 1.1.4 of formation sequence. Examples. (a)$⊥, p_2, p_3, (⊥ \lor p_2), (¬(⊥ \lor p_2)), (¬p_3)$and$p_3, (¬p_3)$are both formation sequences of$(¬p_3)$. Note that formation sequences may contain ‘garbage’ [emphasis added]. As you noted [page 8] : "$\varphi$and$\psiare used as variables for ... 1 Why don't you do a Truth-False table? \begin{align*}&P&Q&&P&\iff Q&&\neg(P\iff Q)&P\rlap{\;\,\cdot}\vee Q\\ &T&T&&&T&&F&F\\ &T&F&&&F&&T&T\\ &F&T&&&F&&T&T\\ &F&F&&&T&&F&F\end{align*} assuming ... 4 Since you only have two variables, I'd suggest writing down it as a table: $$\begin{array}{lcr} \mbox{P} & \mbox{Q} & \mbox{P}\leftrightarrow \mbox{Q} & \neg (\mbox{P}\leftrightarrow \mbox{Q}) & \mbox{P}\oplus \mbox{Q}\\ T & T & T & F & F\\ T & F & F & T & T\\ F & T & F & T & T\\ F & F ... 1 I think this proof should help, in case you need any step explained: By DeMorgan's Law:$$\lnot(P\lor Q)\lor(\lnot P \lor Q)\iff(\lnot P \land \lnot Q) \lor (\lnot P \lor Q )$$By the commutative property:$$ \iff (\lnot P\lor Q)\lor(\lnot P\land\lnot Q)$$By the distribution property:$$ \iff ((\lnot P\lor Q)\lor\lnot P)\land((\lnot P\lor Q)\lor\lnot ... 2 Note that(A\land B)\lor B=B$, and then we have $$(\lnot P \land \lnot Q) \lor \lnot P \lor Q = \lnot P \lor Q.$$ 3 Hint: commute and associate:$P\wedge \neg Q\wedge P = (P\wedge P)\wedge \neg Q$. Now, what is$(P\wedge P) = \underline{\qquad}? 4 \begin{align} [\lnot p \land (p \lor q)] \rightarrow q & \equiv\lnot [\lnot p \land (p \lor q)] \lor q\\\\ & \equiv [p \lor \lnot (p \lor q)]\lor q\\\\ &\equiv [p \lor (\lnot p \land \lnot q)] \lor q\\\\ &\equiv [(p \lor \lnot p) \land (p \lor \lnot q)] \lor q\\\\ &\equiv [T \land (p \lor \lnot q)] \lor q\\\\ &\equiv p \lor \lnot ... 2 The exact details of the proof will differ, depending on your proof system. It will go something like this though: Suppose (\neg p \land (p\lor q)), therefore \neg p and (p\lor q). If p, then p and \neg p, a contradiction, hence q. Else, q, hence q. In either case of the disjunction, we have q. Therefore(\neg p \land(p\lor ... 0 A solution using just words and definitions of the connectives: Let $$\alpha = \big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r), \;\;\;\; \beta = p \lor q \lor r$$ Suppose\alpha $is true. Then either$ \big((p\rightarrow q) \lor (p \rightarrow r)\big) $is false, or$ \big((p\rightarrow q) \lor (p \rightarrow r)\big) is true ... 0 Your answer... \begin{equation*} \begin{split} (p\to q)\vee (p \to r)\to (q\vee r) & \equiv \neg [(\neg p\vee q)\vee (\neg p \vee r)]\vee (q\vee r) \quad \text{by implication rule}\\ &\equiv \neg[(\neg p\vee( q\vee r)]\vee (q\vee r) \quad \text{by associative rule}\\ & \equiv [( p\wedge \neg( q\vee r)]\vee (q\vee r) \quad\text{by De Morgan's ... 3 \begin{align}\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r) &\equiv \lnot\big((\lnot p \lor q) \lor (\lnot p \lor r)\big) \lor (q \lor r)\tag{1}\\ \\ &\equiv \big(\lnot(\lnot p \lor q) \land \lnot (\lnot p \lor r)\big) \lor (q\lor r)\tag{2}\\ \\ &\equiv \big((p \land\lnot q)\land (p \land \lnot r)\big) \lor (q \lor ... 2 What you mean is that \{ \neg, \to\} is a functionally complete set of connectives. We find such systems for example in Frege's famous Begriffsschrift (1879). Naturally: (a) (A_1∧A_2) \equiv \neg (A_1 \to \neg A_2) (b) (A_1∨A_2) \equiv \neg A_1 \to A_2 (c) (A_1 \leftrightarrow A_2) \equiv (A_1 \to A_2) \wedge (A_2 \to A_1) These equivalences can ... 2 Hint: Use the fact that A\to B is equivalent to \neg A \vee B. And, of course, deMorgan's rules. 0 Suppose \phi is a formula in \mathcal{P_0}. Then \phi is one and only one of these forms: (1) There is an n such that \phi =A_n. (2) There is a \psi in \mathcal{P_0} such that \phi = \neg\psi. (3) There are \psi_1 and \psi_2 in \mathcal{P_0} such that \phi = \to\psi_1\psi_2.Further, the \psi_i in (2) and (3) are uniquely determined. ... 1 HINT: Suppose that f is an automorphism, and f(0)=n, what can you tell about f(1) and about f(-1)? Show that f(0) decides completely all the values of f. Now find a compact and nice way to write f. 0 \Bbb Z=<1> or <-1>. So all the automorphisms can be created by sending 1 to 1 or -1. So, there are two automorphisms. So, Aut(\Bbb Z) \equiv \Bbb Z_2=<-1>. 0 I assume that you have a natural deduction system in mind: (1) Prove that B∧C,(B↔C)→(H∨G) \vdash G∨H Proof sketch: here we saw already that B∧C \to (B↔C). Now you can easily derive H \vee G by hypothetical syllogism. G \vee H follows from commutativity. (2) Prove that P→(Q→R) , Q→(R→S) \vdash P→(Q→S) Hint: What happens if you assume P ... 1 I assume you have a natural deduction system in mind: Goal: Derive B \leftrightarrow C from the set of premises \{B \wedge C\}, in symbols: B \wedge C \vdash B \leftrightarrow C For this issue, remember that for deriving a biconditional \phi \leftrightarrow \psi we first have to show that a conditional from both sides holds, that is, you ... -1 I use Lukasiewicz/Polish notation and condensed detachment. The axioms I will use are: CpCqp. CKpqp. CKpqq. CCpqCCqpEpq. Here we go: assumption 5 Kbc. D2.5 6 b. D1.6 7 Cqb. D3.5 8 c. D1.8 9 Cqc. D4.9 10 CCcqEqc. D10.7 11 Ebc. 1 HINT (first 2 lines): Suppose \neg[P\implies Q] \neg\neg[P\land \neg Q] (from 1) 1 HINT (first 3 lines): Suppose B\land C Suppose B C (from 1) 3 Apply the equivalence of implication twice, then commute and associate so that you can apply identity rules.\neg(p\to q)\to p \\= (p\to q) \vee p \\ = (\neg p \vee q)\vee p \\ \vdots$0 If you consult the book Introduction to Metamathematics by S. C. Kleene, you can find an algorithm for a distinct infix language which might give you some ideas here. In Polish notation there exist several known algorithms. One of them is the following... Assign -1 to each propositional symbol. Assign 0 to$\lnot$or "N". Assign 1 to$\rightarrow$or ... 0 For this we need to have a look at the definitions of conjunctive normal form, where recalling the definitions of finite disjunctions and conjunctions may be useful. From van Dalen Logic and Structure (2008), p.25: Definition 1.3.7 (Finite conjunctions/disjunctions): \begin{cases} \bigwedge_{i \leq 0} \varphi_i = \varphi_0\\ \bigwedge_{i \leq n+1} ... 1 We have to use as$\phi$the formula :$(A_1 \land A_2) \land (A_3 \lor \lnot A_3)$that is equivalent to :$(A_1 \land A_2) \land \top \equiv (A_1 \land A_2)$Condiser the "easy" part :$(A_3 \lor \lnot A_3)$; this is equivalent to :$A_3 \rightarrow A_3$. Now for :$(A_1 \land A_2)$that is equivalent to :$\lnot (A_1 \rightarrow \lnot A_2)\$. ...

Top 50 recent answers are included