Tag Info

New answers tagged

0

Another way to look at it: Suppose $A$ is true. Then we can obtain the contradiction $B\land\neg B$ from the two implications. So, $A$ must be false, i.e. we have $\neg A$.


2

$$ \begin{align} (A \rightarrow B)\wedge (A\rightarrow \lnot B) & \equiv (\lnot A\lor B)\land (\lnot A \lor \lnot B)\tag{Implication}\\ &\equiv \lnot A \lor (B \land \lnot B)\tag{Distribution}\\ & \equiv\lnot A \lor 0\\ &\equiv \lnot A \end{align}$$ $$\begin{align} A\rightarrow (B\rightarrow C) &\equiv \lnot A \lor (\lnot B \lor C) ...


1

As Brian M Scott have brilliantly answered above, the trick of the solution is to note that $(¬M∨I)∧(M∨L) \Rightarrow I \vee L$ Recall that logical reasoning is all about entailment, and if certain sentence, say, $\alpha$, entails other, say, $\beta$, it does not follow that both sentences are logically equivalent, although it can happens to be the ...


3

It’s true that either ... or often means exclusive or, but that is by no means always the case. Consider the following sentence: If John is either a veteran or over the age of 65, he is entitled to a discount at XYZ Market. The normal reading of this sentence is that John is entitled as long as he meets at least one of the qualifications: he’s a ...


-1

The problem is easily solved from the text version. If the unicorn is mythical, then it is immortal. If the unicorn is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned. From (1+2) it follows that the unicorn is either immortal or a mortal mammal. ...


0

Is John sick ONLY when it rains? Or might he also be sick in other circumstances? The statement "If it rains, John is sick" means only that it is never the case that it is both raining and John is not sick. $P\implies Q \equiv \neg[P\land \neg Q]$ From "It is not raining," we cannot infer the John is not sick. Neither can we infer that he is sick.


1

My problem was insisting on the above translation. Although I was aware that other translations are also possible, I didn't think it will have such a dramatic effect on the proof stages. This was important since, as I mentioned above, even a seemingly trivial proof - using only the axioms - can be painful. Another problem I had is that it didn't occur to me ...


2

To use equivalences to find the solution, we will profit from the equivalence scheme: $$\phi\implies(\psi\implies\chi) \quad\equiv\quad \neg\phi\lor\neg\psi\lor\chi$$ for arbitrary formulas $\phi,\psi,\chi$. This can be obtained by applying the rule of material implication $\phi \implies \psi \equiv \neg\phi \lor \psi$ twice. Applying it to the three ...


2

For every proposition $P$, the deduction that $P\land\lnot P\to\bot$, that is, that $\lnot(P\land\lnot P)$, is simply applying modus ponens, therefore intuitionistically valid; this is because $\lnot P$ just means $P\to\bot$. Apply this for $P=\lnot\alpha$.


0

Hint: Assume $\neg\alpha \wedge \neg\neg \alpha$, derive a contradiction. Does the resulting proof requires some use of the double negation elimation rule?


7

This statement can be proved in minimal logic. When you rewrite the negations as implications in the usual way, the statement is $$ ((\alpha \to \bot) \land ((\alpha \to \bot) \to \bot) \to \bot $$ which is really of the form $$ (X \land X \to Y) \to Y $$ which is just a form of modus ponens. The provability of the statement has nothing to do with negation, ...


-3

Classical logic, Yes definitely, please just take double negative out. Intuitive logic not quite so sure how is obvious, but I would say so, think of using double negative in sentence https://www.google.com/?q=double%20negative You have said as much yourself. Given lemmas one and two this should be trivial.


2

Consider just two propositional variables, say $p$ and $q$, and let's see what truth-functions of these we can express using $\neg$ and $G$. Using just $\neg$, we have $p,q,\neg p,\neg q$. Now let's apply $G$ to any triple of these, say $G(x,y,z)$. If two of $x,y,z$ are the same, the $G$ just produces that same one of $p,q,\neg p,\neg q$ as its output. So ...


0

excuse my unfamiliarity with the formal expression of propositional calculus, but i hope the following reasoning may be of assistance suppose the proposition false. then we have: $$ (A \to (B \to C)) \land ¬ ((A \to (C \to D) \to (A \to (B \to D))) = \\ (A \to (B \to C)) \land ((A \to (C \to D)) \land ¬(A \to (B \to D)) = \\ (A \to ((B \to C) \land (C \to ...


0

(If anyone wants a proof by the deduction theorem) Suppose $(A\implies (B\implies C))$. Then not $A$ or $(B \implies C)$. Case 1: If not $A$, then $(A⟹(B⟹D))$. So $((A⟹(C⟹D))⟹(A⟹(B⟹D)))$ is true. Case 2: $A$ is true. So $(B \implies C)$, then not $B$ or $C$. Case a) If not $B$, then $(A⟹(B⟹D))$ is true. Case b) $B$. So $C$. Case bi) If $D$ is false, ...


0

There must be something wrong with your rewritings -- what you have arrived at is false when all of the propositional variables are true (as well as when they're all false), whereas the original formula is true in that case.


1

$$({\sim} p\vee{\sim}q)\vee(p\vee q)={\sim}p\vee({\sim}q\vee(p\vee q))\text{ by associativity}\\={\sim}p\vee(({\sim}q\vee p)\vee q)\text{ by associativity} \\={\sim}p\vee((p\vee {\sim}q)\vee q)\text{ by commutativity} \\={\sim}p\vee(p\vee ({\sim}q\vee q))\text{ by associativity} \\=({\sim}p\vee p)\vee ({\sim}q\vee q)\text{ by associativity}$$


1

The operation $\vee$ is associative: $$(p \vee (q \vee r)) \leftrightarrow ((p \vee q) \vee r)$$ and commutative: $$(p \vee q) \leftrightarrow (q \vee p)$$ so you can change the order and distribute the parentheses as you please. Intuitively, no matter how the parentheses are distribute or what order $p,q,r,s$ are written in, the statement $p \vee q \vee r ...


5

I'd suggest proving $\Sigma\vdash D\to Y$ and $\Sigma\vdash H\to Y$ (and $\Sigma\vdash Y\to Y$), then using (4). Here's a proof of $\Sigma\vdash D\to Y$, first in a "friendly" form, then the (fairly mechanical) translation to a form using just the tools you've listed. Friendly form: Suppose $D$. Suppose further that not $Y$. By (1), $H$ would follow. ...


0

Hint: this is an explanation of why it is true, which you can cast into a structural induction if you wish to. If $\phi$ is a pure formula, in the sense of your question, and $v$ is a propositional variable in $\phi$, define an assignment that makes $v$ true if $v$ is not negated in $\phi$ and makes it false if $v$ is negated. This is possible by the ...


0

In his paper “Tout ensemble de formules de la logique classique est equivalent ´a un ensemble independant”, Iegor Reznikof showed the conclusion of your question, but unfortunately the original paper is in French. However you can find a translation in English here.


0

I would start with the most complex side of the statement you want to prove, which in this case is the left hand side, expand your definitions, and take it from there. $ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } ...


0

The (¬ϕ→¬ψ)→(ψ→ϕ) [CCNpNqCqp in Polish notation] axiom can get interpreted as meaning that if a negation of a variable is equivalent to the negation of another variable, then the variables will be equivalent. (¬ϕ→¬ψ) says that if the negation of the first proposition is true, then the negation of the next proposition is also true. Given the rule of ...


2

The "turnstile" symbol, used in the context $\Gamma \vdash \varphi$, means that, relative to the proof system we are working with, there is a derivation of the formula $\varphi$ from the formulae in $\Gamma$ with the rules and logical axioms of the proof system. In the Natural Deduction proof system, we can build-up this simple derivation : 1) $a \land ...


1

HINT. Existential quantification over finite domains (say, of size $n$) is equivalent to a $n$ term disjunction over all elements. So from your example, if the universe of discourse was $\{0,1\}$, then the solution to question 1) would be $P(0,0)\lor P(1,0)$. Similarly, universal quantification over finite domains (say, of size $n$) is equivalent to a $n$ ...


0

Your steps would be valid if you are trying to prove: $(A\to C)\wedge (C\to B')\wedge B\;\to\; A'$ $$\begin{array}{l|lrc} 0 & (A\to C)\wedge (C\to B')\wedge B & \text{Assumption} \\[1ex] 1 & (A \to C) & 0, \text{ Conjunctive Simplification} & P\wedge Q\vdash P \\ && \text{aka Conjunction Elimination} \\[1ex] 2 & (C \to B') ...


2

HINT: Every Boolean function $f$ in $n$ Boolean variables is defined by a propositional formula $\tau_f$ in $n$ propositional variables. Prove by induction on the complexity of $\tau_f$ that $f(1,\ldots,1)=1$ for every Boolean function $f$ such that $\tau_f$ is constructed using only the Boolean connectives $\land$ and $\lor$. Use the recursive construction ...


1

Not only is your solution correct IMO, but it is also a much cleaner one than the book offers. I would improve the way your solution is written though (see here for a typesetting guide): \begin{align} (p\to q)\land(p\to r) &\equiv (\neg p\lor q)\land(\neg p\lor r)\tag{Implication identity}\\[0.5em] &\equiv \neg p\lor(q\land r)\tag{Distributive ...


0

For (a) your answer seems correct but you are missing the hypothesis side, in your notation, so I would write something more like: $$ \{\alpha,\beta\} \vdash \alpha \qquad \mathrm{given} \\ \{\alpha\} \vdash \beta \to \alpha \qquad \mathrm{insertion} \\ \emptyset \vdash \alpha \to (\beta \to \alpha) \qquad \mathrm{insertion}$$ and since ...


2

$$(P' \land Q') \lor (P' \land Q) \lor (P \land Q')$$ By identity $A=(A\lor A)$ and associativity: $${\color{Green} {(P' \land Q')}} \lor (P' \land Q) \lor {\color{Green} {(P' \land Q')}} \lor (P \land Q')$$ By distributivity: $$(P' \land (Q' \lor Q)) \lor ((P' \lor P) \land Q')$$ Reduction by the law of excluded middle: $$(P' \land 1) \lor (1 \land Q')$$ ...


1

Consider $S$ as the universal set. Our given expression is this: $$(P^\prime\land Q^\prime)\lor (P^\prime \land Q)\lor (P\land Q^\prime)$$ Use the converse of distributive laws along with associativity laws to reduce the given expression as: $$\left\{P^\prime \land (Q^\prime \lor Q)\right\}\lor (P\land Q^\prime)=\{P^\prime \land S\}\lor (P\land ...


2

Take the model $\mathfrak A\,$ whose domain is $\{a,b \}$, and let $\alpha:=F(x)$ and $\beta:=G(x)$, and finally let $F=\{a \}$ and $G=\{b \}$. Recall that for finite domains $(\forall x)\varphi$ is equivalent to the conjunction $\varphi a_1 \land \varphi a_2 \,...\land \,\varphi a_n \; $ for an $n$ sized domain. I'll show that $\mathfrak A\,$ is a ...


2

Correction Applying Distribution to : $(\lnot p∨q)∧\lnot q$ we get : $(\lnot p \land \lnot q) \lor (q \land \lnot q) \equiv (\lnot p \land \lnot q) \lor F \equiv (\lnot p \land \lnot q).$ In the same way : $(\lnot p ∨ q)∧p \equiv (p \land q)$. Absorption is : $(\lnot p \lor q) \equiv (\lnot p \lor (p \land q))$.


2

The name predicate calculus has an historical heritage ... Today we prefer to call it first-order logic. For the "founding fathers" : Frege, Russell, the distinction between propositional and predicate calculi were not relevant; see Principia Mathematica and The Notation in Principia Mathematica. In the first modern mathematical logic textbook : David ...


0

It might be helpful to verbalise as follows: Left hand side: for every $x\in M$, if $\alpha(x)$ is true then so is $\beta(x)$. On the right hand side: if ($\forall x \in M \alpha(x)$) then ($\forall x \in M \beta(x)$) Then, it should be clear that we can make a following counterexample: $\alpha(0)$ is false, $\alpha(1)$ is true, $\beta(0)$ and $\beta(1)$ ...


0

As mrp notes in a comment, you really need to show more of your work--this lets us know what you are struggling with exactly, and it also shows that you are not just trying to have other people do your work. Since you edited your question and did show at least some of your work, I feel compelled to answer, but also note that it is generally discouraged to ...


1

We have that [see Enderton, page 88] : $\varphi$ and $\psi$ are logically equivalent ($\varphi \equiv \psi$) iff $\varphi \vDash \psi$ and $\psi \vDash \varphi$, where : Let $\Gamma$ be a set of wffs, $\varphi$ a wff. Then $\Gamma$ logically implies $\varphi$, written $\Gamma \vDash \varphi$, iff for every structure $\mathfrak A$ for the language ...


0

The argument is an example of the fallacy of negating the antecedent (and as such, the argument is not valid). Let $p$ denote "It rains." Let $q$ denote "John is sick." So $\lnot p$ denotes "It doesn't rain." And $\lnot q$ denotes "John is not sick." Then we have an invalid argument: $$p\rightarrow q$$ $$\lnot p$$ $$\therefore \lnot q$$ From $p ...


0

Let your statements be denoted as follows: $P : $ It is raining. $Q : $ John is sick. You are given that $P\to Q$. Then you are asked to evaluate the validity of $\neg P\to\neg Q$, the inverse of $P\to Q$. You can see that $P\to Q\not\equiv\neg P\to\neg Q$ (by truth table or otherwise); thus, the deduction that John wasn't sick because it wasn't raining ...


1

If the negation of $A\implies B$ were $A \implies \lnot B$, then they would have to have the opposite truth values for all valuations of $A$ and $B$. So let's just check that: $$\begin{array}{cc|cc} A & B & A\implies B & A\implies\lnot B \\\hline \text{False} & \text{False} & \text{True} & \color{red}{\text{True}} \\ \text{False} ...


-1

Try building both $\lnot$(A$\rightarrow$B) and (A$\rightarrow$$\lnot$B) up from their component well-formed formulas. Or write them in a prefix notation like the following: $\lnot$($\rightarrow$(A, B)) and $\rightarrow$(A, $\lnot$(B)) In the former we have "A" and "B" and then a conditional. Then we negate the conditional. In the latter we have "A" and ...


2

Let $L$ be the proposition that the left door leads to escape. You ask a question $Q$ (some proposition). Let $R$ be the truth-telling/lying status of the person you ask (so true if the person is a truth-teller, false if the person is a liar). The response from this person is the truth value of $Q \Leftrightarrow R$. So what you want to do is come up with ...


1

"Not every odd number is divisible by $2$" or "Some odd number is not divisible by $2$". These equivalent statements, while true, are absurdly weak; and you can obviously say something much stronger; but they are literally the negation of the original (false) statement.


3

Suppose that you wanted to prove to someone that the statement no odd number is divisible by $2$ is false; what would you have to do? You’d have to show that some odd number actually is divisible by $2$. That is exactly what it means to say that the original statement is false. Thus, its negation is there is an odd number that is divisible by $2$. All ...


1

The negation will be "There is at least one odd number not divisible by 2". Note that the given statement is false assuming any counterexample, so saying all odd numbers are counterexamples is overkill.


4

$ \newcommand{\T} {\text{True}} \newcommand{\F} {\text{False}}$ $$\begin{array} {cc|cc} A & B & A \implies \lnot B & A \not \implies B \\ \hline \T & \T & \F & \F \\ \T & \F & \T & \T \\ \F & \T & \T & \F \\ \F & \F & \T & \F \\ \end{array}$$ So in fact for material implication, $A \implies \lnot ...


5

Here is a more intuitive explanation. Suppose that $A$ and $B$ are unrelated. For example, $A$ could be "France is a country in Europe" and $B$ could be "I will win the lottery". It is certainly the case that we know $A$ does not imply $B$ for these sentences: knowing that France is in Europe tells me nothing about the future! But we also do not know that $A ...


1

Definition: $A\implies B \equiv \neg[A \land \neg B]$. Taking the negation, $\neg[A\implies B] \equiv A \land \neg B$. By definition, we also have $A\implies \neg B \equiv \neg[A \land B]$. Now, $A\land \neg B \not\equiv \neg [A \land B]$ Therefore, $\neg[A\implies B]\not\equiv A\implies \neg B$.


4

Consider this simple example: $$x>0\Rightarrow x>1.$$ This is clearly a false statement. Among the next two ones, which is true ? $$x>0\nRightarrow x>1$$ $$x>0\Rightarrow x\le1?$$


3

I am going to assume you are familiar with two equivalences (if not, then simply write up truth tables to verify them): $$ A\to B\equiv\neg A\lor B\quad(1)\qquad\text{and}\qquad\neg(A\lor B)\equiv\neg A\land\neg B\quad(2). $$ Why your book is right: We can negate anything by simply tacking on "it is not the case that...," and this is basically what your ...



Top 50 recent answers are included