# Tag Info

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

8

Differently from Mauro Allegranza and Graham Kemp, I think that your proof is formally correct, even if it is unnecessarily tricky, inelegant and non-efficient. I formalized your argument in natural deduction (see below), so this proves that your proof is correct. Let $\pi_0$ be the derivation of $\lnot c \to \lnot a$ from $\{a \to c\}$ (this correspond to ...

1

Proof by contradiction aims at assuming something and then arriving at a contradiction. Once you arrive at a statement that is contradictory, you are thus done (I know you are not talking about the efficiency). To answer your question, you could view your arguments as: Assume $\neg c$, arrive at some statement (line 5) of which you are not sure it is ...

3

my teacher says even in the case of a proof by contradiction non of the steps should be a contradiction (except the last one when the proof ends ) !? More precisely, once you've obtained a contradiction the proof has ended, because that's exactly what you were required to show.   Nothing more is needed. $$\dfrac{\neg c, \Sigma \vdash \bot}{\Sigma ... 1 First Skolemize. In other words, replace all existential quantified statements with appropriate terms. In your example, this means you just replace variables with constants and drop all existential quantifiers. You can also drop all universal quantifiers once you've Skolemized since you'll have them implicitly. Second, apply the INDO method. In other ... 1 Not exactly... I think that, due to the fact that the assumption \varphi has not been "crossed away", it is correct to consider it undischarged. But \psi is not listed explicitly as an assumption; thus, I think that the correct answer is : \{ \varphi \} \vdash (\varphi \to (\psi \to \varphi)). The following :$$\dfrac{ \varphi }{ \psi \to ...

0

In general, in propositional classical logic (which is the logic where truth tables make sense), a standard way to prove that a formula is a tautology without using truth table is: to derive the formula in some derivation system for propositional classical logic, such as sequent calculus, natural deduction, Hilbert system. This is sufficient since, ...

0

It is correct that : if $\alpha \vDash (\beta ∨ \gamma)$, then $α⊨β$ or $α⊨γ$ ? No, it is not. Consider as $α$ the formula $p∨¬p$ and $p$ in place of $β$ and $¬p$ as $γ$.

0

I use Polish notation. The formation rules go: All lower case letters of the Latin alphabet qualify as significant expressions. If $\alpha$ and $\beta$ qualify as significant expressions, then so do N$\alpha$, C$\alpha$$\beta, A\alpha$$\beta$, and K\alpha$$\beta. The significant expression CApqCCpqq can get proved in intuitionistic logic from the ... 1 Consider : (B∨C)∧(B→A)∧(C→A) and rewrite it as : (B \lor C)∧(\lnot B \lor A)∧(\lnot C \lor A) that is : (B \lor C)∧[(\lnot B ∧ \lnot C) \lor A] by Distributivity. By Distributivity again, we get : [(B \lor C)∧(\lnot B ∧ \lnot C)] \lor [(B \lor C) \land A] that is equivalent to (B \lor C) \land A, because the left disjunct ... 4 Your answer is correct. First note that \text{student}(y)\rightarrow \text{likes}(y,x) is equivalent to \neg\text{student}(y)\vee \text{likes}(y,x). With that the statements mean the following in plain english: For every teacher there exists a person who is either not a student or likes the teacher. Every teacher is liked by some student. There is ... 0 Additionally to Henning's answer: Usually you have at least some expression in your logic expressing "contradiction", for example 0=1 in Heyting Arithmetic. Then you immediately get all of intuitionistic logic by setting \neg a :\equiv a \Rightarrow (0 = 1), so removing \neg usually does not change anything. If you don't have contradiction already, ... 4 Classical and intuitionistic propositional logic do not prove the same formulas, even in the purely implicational fragment. Most famously, Peirce's Law ((P\to Q)\to P)\to P is a classical tautology, but is not intuitionistically valid. (That is, classical logic proves it, but intuitionistic logic doesn't). The two logics are equivalent for the ... 2$$\neg p \wedge q \rightarrow r =$$First we know that A\rightarrow B is equivalent with \neg A\vee B thus.$$\neg(\neg p \wedge q) \vee r =$$Now use de morgan:$$ (p \vee \neg q) \vee r =$$Switch place between r and (p \vee \neg q) and notice that r is equivalent with \neg \neg r.$$\neg \neg r \vee (p \vee \neg q) =$$Now again use that ... 2 The contrapositive of the first one is \lnot r\to\lnot(\lnot p\land q), which equals the second expression. 0 It can't actually be done, except in the most schematic way which discards the structure. In the first case, the three sentences can be represented as follows, using the predicate Fool(x,y,t) to mean "x can fool y at time t":$$\begin{align} (\forall x)(\exists y)(\forall t)\,Fool(x,y,t) \tag{1a} \\ (\forall x)(\forall y)(\exists t)\,Fool(x,y,t) ... 0 As the question starts with "Any person", the whole statement regards this 'person' and this can not be translated into propositional logic in any good way (i.e. we can not do the quantification needed). The whole statement will be just one propositional variable, sayA$. Same thing here, we cant quantify over the children, and we can not express a ... 3 Both have their uses, and neither easier to convert to. DNF gives you the truth table of a formula: it shows you exactly which assignments of truth values to atomic formulas make the entire formula true. Converting a formula to CNF, and converting to DNF, are both NP-hard. One reason why CNF gets more attention: the method of resolution, used in automated ... 0 Although you didn't say so in the question, your title indicates that you want a formula in propositional logic. So I'd express "each pigeon is in a hole" as $$\bigwedge_{i=1}^{n+1}\bigvee_{j=1}^n p[i,j],$$ and I'd express "some hole contains two distinct pigeons" as $$\bigvee_{j=1}^n\bigvee_{1\leq i<k\leq n+1}(p[i,j]\land p[k,j]).$$ Finally, I'd ... 0 Note:$x \land y$being true means both$x$and$ y$are true. So let$x = P \lor Q$and$ (P \lor Q) \land y $being true means$(P \lor Q)$is true no matter what the **** P, Q, y are. 1 Yes, your truth table proves the claim. We can also observe:$P \vee Q$is equivalent to$\neg P \implies Q$. With$Q \implies R$, that gives$\neg P \implies R$, which is equivalent to$P \vee R$. ETA: Regarding your last question, in the first case, a true value of$P$"conceals"$\neg (Q \implies R)$, and in the second case, a true value of$R... 1 What you need to do is to prove $$((P∨Q)∧(Q⟹R))⟹(P∨R)\tag1$$ is a tautology. You'd better do it by Boolean algebra rather than truth table. \begin{align} (1)&\iff(\neg((P∨Q)∧(\neg Q∨R))∨(P∨R)) \\ &\iff((\neg(P∨Q)∨\neg(\neg Q∨R))∨(P∨R)) \\ &\iff((\neg P∧\neg Q)∨(Q∧\neg R))∨(P∨R)) \\ &\iff(\neg P∧\neg Q)∨((Q∨P∨R)∧(\neg R∨P∨R)) \\ ... 1 It almost proves your claim — it provides all the evidence you need. What you're trying to show is that the following formula is a tautology, true for all values ofP,Q,R$: $$((P \lor Q) \land (Q \!\implies\! R)) \implies (P \lor R).\tag{*}$$ You can either add another column to your truth table for this formula, and confirm that every value is$1$, or ... 0 Let's walk through this, making each step more explicit:$\neg\forall y\exists x\exists z[(Bxy\wedge Rzy)\vee(Bxy\wedge Gzy)\vee(Rxy\wedge Gzy)]$When you have a negated quantifier, you may remove the negation, change the quantifier to the other type of quantifier, and negate the formula quantified over:$=\exists y\neg\exists x\exists z[(Bxy\wedge ...

2

You probably want $\varphi_i$ to be sentences (or at least for them to have disjoint sets of free variables). No, you're doing it backwards: you don't need to show that for every valuation you can find a structure which gives you the valuation. Indeed, it may not be possible for given $\varphi_i$ (say, when $\varphi_0=\forall x (x=x)$). You need to go the ...

0

We need the following tautology : $A(c) \to (\lnot A(c) \to (B \land \lnot B))$; due to the fact that the contradiction $B \land \lnot B$ is always false, the formula is always true (check it with truth table...). Thus, if $A(c)$ is true (valid, according to Cohen's), then we can "detach" the consequent of the previous tautology by modus ponens, ...

0

The $X$ in the consequent $\exists Z\,q(X,Z)$ is free. The $X$ quantifier in the antecedent $\forall X\,p(X,Y)$ does not bind it. That free $X$ has nothing to do with the bound $X$ in $\forall X\,p(X,Y)$. It's just a coincidence (an unfortunate one) that they're the same variable. However, in your third step, you move $\exists X$ to the outside without ...

0

Oky, maybe there is some kind of good learning materials. I have to understand the things I can do to prove something. The basic strategies if any. For example, I am looking to this one and just don't know the things i can do. (Xv!X)->(X->Z)v(Z->X). I usually try to create some basic hypothesis and try to find some good axiom scheme, but it works for ...

2

Let's say that your premises are $A$, $A \vee B \Rightarrow X$. Now you can use a rule of inference called addition and infer that $A \vee B$ is true. (This is not a hypothesis). Now using Modus Ponens, you can infer that $X$ is true. The formal proof would look like this: Premises 1)$\quad A$ 2)$\quad A\vee B \Rightarrow X$ Proof 3)$\quad A \vee ... 1 The other direction: Suppose that$v(\phi) = 1$. Write$\phi$in conjunctive normal form, so it's a conjunction of clauses, each of which is a disjunction of propositional variables or their negations. Let$p_1, \dotsc, p_m$be all the propositional variables appearing in$\phi$. The resulting formula$\phi_{cnf}$is $$\phi_{cnf} = \bigwedge_{i=1}^n ... 4 \lnot \lnot (A \lor B) \to (\lnot \lnot A \lor \lnot \lnot B) is not intuitionistically acceptable. One way of seeing this is by considering the Heyting algebra whose elements are the open subsets of the unit interval [0, 1] \subseteq \Bbb{R}, with A \lor B = A \cup B, A \to B = \mathsf{int}(A^c\cup B) and \bot = \emptyset (see ... 1 I use Polish notation. The formation rules run: All lower case letters of the Latin alphabet qualify as wffs. If \alpha and \beta qualify as wffs, so do N\alpha, and C\alpha$$\beta$. The axioms in Polish notation run: CpCqp CCpCqrCCpqCpr CCNpNqCCNpqp And the problem goes: CbCcd $\vdash$ CcCbd. Neither CbCcd nor CcCbd consists of a ...

0

If we have $\Gamma = \{ \gamma_1, \ldots, \gamma_k \}$ and $p_1, \ldots, p_n$ are the atoms occurring into some $\gamma_i$ or $\varphi$, we have to build the truth table with $2^n$ rows : one for each possible interpretation of the atoms $p_1,\ldots, p_n$ and $k+1$ rows : one for each formula. Then we have to define : $\Gamma \vdash \varphi$ iff, for ...

0

Fill in the blanks \begin{align} (p\to r)\wedge (q\to r) \iff & (\neg p\vee r)\wedge (q\to r) & \textsf{Implication Equivalence} \\[1ex] \iff & (\neg p\vee r)\wedge (\neg q\vee r) &\textsf{Implication Equivalence} \\[1ex] \iff & ~ & \textsf{Distribution} \\[1ex] \iff & ~ & \textsf{Association & Commutation} \\[1ex] ... 1 (p → r) ∨ ( q → r)=(¬p ∨ r) ∨ (¬q ∨ r)=¬p ∨ r ∨ ¬q ∨ r=(¬p ∨ ¬q) ∨ r=¬(p∧q)∨r=(p∧q) → r 1 Here is a derivation: (k\to (k\to k)) \to (\neg(k\to k) \to \neg k) by Ax.2, with X = k, Y = (k\to k). k\to(k\to k) by Ax.1, with X=k, Y=k. (\neg(k\to k) \to \neg k) by 1. and 2. via MP. (\neg(k\to k) \to \neg k) \to [((\neg k\to k)\to k) \to (\neg(k\to k) \to \neg k)] Ax.1 with X = (\neg(k\to k) \to \neg k) = 3., Y = ((\neg k\to k)\to ... 3 With the axioms you gave, the formula is not provable. I've used Mace to find a counter-model, which consists in interpreting "\neg" as an operator that always outputs F, irrespective of the input truth value. The arrow "\rightarrow" is to be interpreted standardly (since A1 and A2 indeed are axioms that capture the material conditional). Along these ... 3 You're correct, you do have to check two things, in any case. But you have two choices about which two things to check. p\iff q is equivalent to (p \land q) \lor (\neg p \land \neg q). The two disjuncts are the two things you checked: (p \land q), and (\neg p \land \neg q). The two formulas on either side of \!\iff\! have to have the same truth ... 0 I use Polish notation. The formation rules run: All lower case letters of the Latin alphabet, and 0 qualify as well-formed formulas (wffs). If \alpha and \beta qualify as wffs, then so do N\alpha, C\alpha\beta$, K$\alpha$$\beta, and A\alpha$$\beta$. The axiom schemes are: CAppp a law of Clavius CpKpp a law of K-tautology introduction CpApq ... 0 I recommend Logic as Algebra (Dolciani Mathematical Expositions) by Paul Halmos and Steven Givant. Here is an introduction to modern logic that differs from others by treating logic from an algebraic perspective. What this means is that notions and results from logic become much easier to understand when seen from a familiar standpoint of algebra. The ... 2 You can prove $$\psi\land \chi \to \psi\land\chi$$ by going through$(\psi\land\chi)\land(\psi\land\chi)$. Now apply rule 10 to get $$\psi \to (\chi\to\psi\land\chi)$$ Then your assumed derivations of$\psi$and$\chi$, plus modus ponens twice concludes$\psi\land \chi$. 0 Your approach is overcomplicating the task at hand. Instead, just show that$M_{a(\Sigma')}\vDash \sigma'$for each$\sigma' \in\Sigma'$separately. Such a$\sigma'$will either be something that is true in$M_R$, and therefore also in every$M_a$, or it will assert that$0<b<c_r$for some$c_r$where the interpretation of$c_r$is by construction ... 2 The proof goes as follow:$p\lor q$[premise]$p$2.1.$\neg p$[premise] 2.2$\bot$[$\rightarrow_e$2 and 2.1] 2.3.$q$[absurdity rule 2.2]$q$3.1.$q$[copy 3]$q$[$\lor_e$2 - 3.1] I hope it is clear what I meant. Any further questions/comments? 0 Natural deduction? If you have the choice between p and q, probably both but p is not allowed then q remain to be chosen. That is the natural argument which can be formalized:$[p\vee q]\wedge \neg p\equiv [p\wedge\neg p]\vee [\neg p\wedge q]$. There it is. 0 thanks for the help so far but I'm still having trouble understanding using the proof system you use. The first line, why have you put P and ¬Q as assumptions? I usually write it out like this... 1. P v Q Premise {1} 2. ¬P Premise {2} 3. |¬Q Hypothesis {3} ... etc 1 $$A \lor (B\land \lnot A) = (A \lor B) \land (A\lor \lnot A) = A \lor B$$ and $$\lnot B \lor (B \land \lnot A) = (\lnot B \lor B) \land (\lnot B \lor \lnot A) = \lnot B \lor \lnot A$$ 0 I use Polish notation. The formation rules go: All lower case letters of the Latin alphabet stand as well-formed formulas. If$\alpha$and$\beta$qualify as formulas, so do A$\alpha$$\beta, C\alpha$$\beta$, and N$\alpha$. assumption 1 Apq assumption 2 Np hypothesis 3 | p hypothesis ... 1 You can show that$P\Rightarrow Q$with those assumptions. You just assume$P$and note that$\neg Q\Rightarrow P$and$\neg Q\Rightarrow\neg P$(via implication introduction via the assuming$\neg Q$) and conclude that$Q$. Then you have by the implication introduction that the asssuming$P$and that$Q$is amoung your assumption that$P\implies Q\$. But as ...

1

\begin{align} LHS&\equiv((p∧ ¬q)\to(¬p ∧ q)) \land ((¬p ∧ q)\to(p∧ ¬q)) \\ &\equiv ((\neg p\lor q)\lor(¬p ∧ q)) \land ((p \lor \neg q)\lor(p∧ ¬q)) \\ &\equiv (((\neg p\lor q)\lor¬p)\land ((\neg p\lor q)\lor q)) \land (((p \lor \neg q)\lor p)\land ((p \lor \neg q)\lor ¬q)) \\ &\equiv ((\neg p\lor q)\land (\neg p\lor q)) \land ((p \lor \neg ...

Top 50 recent answers are included