I came across the following example that explains the Law of Implication, which I cannot wrap my head around. How is it that:$$p \Rightarrow q$$ Is logically equivalent to: $$\neg p \lor q$$?
122834
This question comes from from my algebra paper:  $(p \rightarrow q)$ is logically equivalent to ... (then four options are given).   The module states that the correct option is $(\sim p \lor q)$. That is:      $$(p\rightarrow q) \iff (\sim p \lor q )$$   but I could not understand this problem or the solution. Could anybody help me?
4650
I was looking at an exercise where it asked the following:  $$\begin{array}{ccc} p&amp;q&amp;p\rightarrow q \\ T&amp;T&amp;T \\ &amp;\ldots \end{array}$$  So, for the third column, I just put $T$ which was correct but I didn't understand what $\rightarrow$ meant. I have seen $\implies$ but I haven't the arrow. Are they the same thing?  Thanks a bunch!
42468
Okay I have the following fitch proof almost figured out, from here I know I have to move forth in conlcuding but I don't know what I am missing  (2 premises)  S → (R ∨ P)  P → (¬R → Q)   my work below  new scope assume S   Rule: > elim  R ∨ P  New scope assume R  Q∨R     Rule: V intro  End scope – (new scope assume P)  ¬R → Q         Rule: > Elim  my confusion comes where I go from here  Q∨R            rule Taut Con ??  Goal:├ S → (Q ∨ R)
47685
I know, I know, there are tons of questions on this -- I've read them all, it feels like. I don't understand why $(F \implies F) \equiv T$ and $(F \implies T) \equiv T$.  One of the best examples I saw was showing how if you start out with a false premise like $3=5$ then you can derive all sorts of statements that are true like $8=8$ but also false like $6=10$, hence $F \implies T$ is true but so is $F \implies F$.  But for me examples don't always do it for me because how do I know if the relationship always holds even outside the example? Sometimes examples aren't sufficiently generalized.  Sometimes people say "Well ($p \implies q$) is equivalent to $\lnot p \lor q$ so you can prove it that way!" except we arrived at that representation from the truth table in the first place from disjunctive normal form so the argument is circular and I don't find it convincing.  Sometimes people will use analogies like "Well assume we relabeled those two "vacuous cases" three other ways, $F/F, F/T, T/F$ -- see how the end results make no sense?" Sure but T/T makes no sense to me either so I don't see why this is a good argument. Just because the other three are silly doesn't tell me why T/T is not silly.   Other times I see "Well it's just defined that way because it's useful"... with no examples of how it's indeed useful and why we couldn't make do with some other definition. Then this leads to the inevitable counter-responders who insist it's not mere definition of convenience but a consequence of other rules in the system and so on, adding to the confusion.  So I'm hoping to skip all that: Is there some other way to show without a doubt that $(F \implies q) \equiv T$?
100108
I have a statement,     Either p or q   and I have to write it in terms of logical connectives but I don't get which logical connector should I be using? Here is what I did (I think there could have been a better way to do this)     $(p \lor q ) \land (\neg((p \Rightarrow q) \land (q \Rightarrow p)))$
119413
Suppose A is a necessary condition for B. Does this mean $A\Rightarrow B$ or does it mean $B\Rightarrow A$?  Suppose P is a sufficient condition for Q. Does this mean $P\Rightarrow Q$ or  $Q\Rightarrow P$?
17301
I tried to prove that $(p \to q) \lor (q \to p)$ is a tautology.  I used $p$ and $¬q$ as conditions. (Premises 1 and 5)  I managed to get to a solution, but I'm not sure if it's right.  Can you please check it?   Thank you!!!:)
79811
In Wikipedia,  in the last axiom of the Natural deduction system, it says "From [accepting $p$ allows a proof of $q$], infer $(p \to q)$." Isn't that a tautology? In the big table "Basic and Derived Argument Forms" that follows, I see it using a new symbol "$\vdash$" to express "therefore". Isn't that something can be done by the symbol "$\to$"? For example, what's the difference between "$(p \land q) \vdash p$" and "$(p \land q) \to p$"?  An interesting symbolic representation of the last axiom of NDS is that $(p \vdash q) \vdash (\vdash p \to q)$. Which I don't understand why is made so complicated.    What also puzzles me is in the  that follows. Since you list "$A$" as a promise, which is basically saying "assuming $A=\text{True}$", then why you have to go around such a big circle, using disjunction, conjunction, and conjunction elimination to prove back that "$A$" is true? If it is me, I would say "assuming $A=\text{True}$, we will know that $A=\text{true}$. Bang! Now we get $A \vdash A$, so we have $\vdash A \to A$." What's wrong in this deduction?
67978
The distributive property is very simple and it says p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r ), but here how is (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ ¬r) ≡ (p ∧ ¬r) ∨ (¬q ∧ q) which someone told me is according to the distributive property, but I didn't get it.    In simple words, can someone please tell me in parallel &amp; exactly how this proposition (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ ¬r) ≡ (p ∧ ¬r) ∨ (¬q ∧ q) matches the distributive property p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r )? What each variable in distributive property means in that proposition. Million Thanks!
46909
I have to prove if the following statement is true or false $$\forall x : (P(x) \lor Q(x)) \Leftrightarrow \forall x : P(x) \lor \forall x : Q(x)$$  I understand the first statement as, for every $x$, at least one of the functions $P$, $Q$ is true. For the second statement, at least one of the functions $P$, $Q$ is true for every $x$. Is this correct? When yes, how could I prove this? Using the distributive law will clearly render me the wrong result.
56921
$$\big((P\rightarrow Q)\rightarrow P\big) \rightarrow P$$  I need to solve this using simple natural deduction rules  these can be hypothesis, $\rightarrow$ intro, $\rightarrow$ elim, conj and disjunct intro and elim, and negation intro (Reductio ad absurdum) and negation elimination (Double)
11482
Using the Fitch system, how do I prove $((p \implies q) \implies p)\implies p$? I started with the hypotheses $(p \implies q) \implies p$ and $\sim p$. However, from these hypotheses I did not get the desired contradiction to solve the question.  Thanks sb45
26846
Is there a proof for the logical equivalence of $a \rightarrow b$ and $\lnot a \vee b$?
38704
I am currently working through Velleman's book How To Prove It and was asked to prove the following  $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$  This is my work thus far  $(P \to Q) \wedge (Q \to P)$  $(\neg P \vee Q) \wedge (\neg Q \vee P)$ (since $(P \to Q) \equiv (\neg P \vee Q)$)  $\neg[\neg(\neg P \vee Q) \vee \neg (\neg Q \vee P)]$ (Demorgan's Law)  $\neg [(P \wedge \neg Q) \vee (Q \wedge \neg P)]$ (Demorgan's Law)  At this point I am little unsure how to proceed.   Here are a few things I've tried or considered thus far:  I thought that I could perhaps switch some of the terms in step 3 using the law of associativity however the $\neg$ on the outside of the two terms prevents me from doing so (constructing a truth table for $\neg (\neg P \vee Q) \vee (\neg Q \vee P)$ and $\neg (\neg P \vee \neg Q) \vee \neg (P \vee Q)$ for sanity purposes)  I can't seem to apply the law of distribution since the corresponding terms are negated.  Applying demorgans law to one of the terms individually on step 2 or 3 doesnt seem to get me very far either.  Did I perhaps skip something? Am I even on the right track? Any help is appreciated
57027
I am reading Velleman's "How to Prove it", and in one example he proves  $\neg \exists x P(x)  \implies \forall x \neg P(x)$    in the following way:    Suppose $\neg \exists x P(x)$. Let x be arbitrary. Suppose $P(x)$. Since we have a specific $x$ for which P(x) is true, it follows that $\exists x P(x)$, which is a contradiction. Therefore $\neg P(x)$. Since $x$ was arbitrary, we can conclude that $\forall x \neg P(x)$, so $\neg \exists x P(x)  \implies \forall x \neg P(x)$    What makes me confused is the line in bold text, that is "Suppose $P(x)$". The reason is that he writes that he is doing proof by contradiction, but $P(x) \not\iff \neg\forall x \neg P(x)$. He is not treating all possible cases where $\forall x \neg P(x)$ is false by assuming $P(x)$, does he? So how can this be a valid proof by contradiction?    Edit: I deleted my first example since it was clearly not representative for the problem.  Edit 2: So the thing that I am opposing I guess is that $\neg \forall x \neg P(x)$ is not $P(x)$. And from what I have undestood, a proof by contradiction should use the negation of the consequent which I do not think that Velleman does.
28448
Here is my proof, I would appreciate it if someone could critique it for me:  To prove this statement true, we must proof that the two conditional statements ("If $\mathcal{P}(A)⊆ \mathcal{P}(B)$, then $A⊆B$," and, If $A⊆B$, then $\mathcal{P}(A)⊆ \mathcal{P}(B)$) are true.    Contrapositive of the first statement: If $A \nsubseteq B$, then $\mathcal{P}(A) \nsubseteq \mathcal{P}(B)$  If $A \nsubseteq B$, then there must be some element in $A$, call it $x$, that is not in $B$: $x \in A$, and $x \notin B$. Since $x \in A$, then $\{x\} \in \mathcal{P}(A)$; moreover, since $x \notin B$, then $\{x\} \notin \mathcal{P}(B)$, which proves that, if $A \nsubseteq B$, then $\mathcal{P}(A) \nsubseteq \mathcal{P}(B)$. By proving the contrapositive true, the original proposition must be true.    To prove the second statement true, I would implement nearly the same argument, so that isn't necessary to write. So, does this proof seem correct? Also, was the contrapositive necessary? Or is there another way to prove the initial statement?
12666
I have a feeling it's not, because ¬¬P → P is not provable. If it is, I'm not sure what kind of reductio I'd need to negate ¬(¬¬P → P). I believe a textbook somewhere said it was provable in intuitionistic logic, so am I missing something or is the textbook wrong?