In propositional logic, the statement "If pigs can fly, then elephants can lay eggs." validates to true because the antecedent validates to false.  In other words, given $a \rightarrow b$, if a is false, the entire statement is true. Why?  Just because the antecendent is false doesn't mean that another fact depends on it, right?
5225
I am studying entailment in classical first-order logic.  The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is: $$\begin{array}{|c|c|c|} \hline p&amp;q&amp;p\Rightarrow q\\ \hline T&amp;T&amp;T\\ T&amp;F&amp;F\\ F&amp;T&amp;T\\ F&amp;F&amp;T\\\hline \end{array}$$  I 'get' lines 1, 2, and 3, but I do not understand line 4.      Why is the statement $(p \Rightarrow q)$ True if both p and q are False?  We have also been told that $(p \Rightarrow q)$ is logically equivalent to $(~p || q)$ (that is $\lnot p \lor q$).  Stemming from my lack of understanding of line 4 of the Truth Table, I do not understand why this equivalence is accurate.       Administrative note. You may experience being directed here even though your question was actually about line 3 of the truth table instead. In that case, see the companion question  And even if your original worry was about line 4, it might be useful to skim the other question anyway; many of the answers to either question attempt to explain both lines.
99500
Sometimes, in a math paper, we read something like "Although a priori this statement could be true, it is in fact false, as proven by this theorem". But aren't all mathematical statements a priori? So why include that misleading bit of language in the beginning?
87884
I have a mathematical proposition of the form "If $A$, then $B$". I'm thinking about this problem from several different perspectives, so I will segment these different perspectives into separate paragraphs as follows.   If I have a statement $A \implies B$ that is true by definition (no proof provided), is it then correct to say that the contrapositive statement $\neg B \implies \neg A$ (NOT $B \implies$ NOT $A$) must also be true, without providing any proof?  In other words, if $A \implies B$ that is true by definition, then does this imply that the contrapositive statement $\neg B \implies \neg A$ is also true by definition? Trying to think of this from the perspective of logic notation and truth tables, would it be correct to write that $(A \implies B) \implies (\neg B \implies \neg A)$? This way, since we know that $A \implies B$ is true, we must logically have (according to truth tables) that $\neg B \implies \neg A$ is also true, right?   I would greatly appreciate it if people would please take the time to clarify this.
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?
47166
we recently got the statement that $(P \land Q) \to P$ is a tautology, but i do not get why it is one, since it is wrong for certain cases of P and Q.
113904
I've been seeing arguments of this form for awhile:   (agreed true premise) Some predicate P was applicable to behavior/event/thing A in the past. Variations: P(A) may have been true at some particular past time t, or over all past time T. (fallacious consequence) Therefore P(A) is true now. Variations: P(A) must be true now and all futures.   But I haven't known what to call them (e.g., when "calling out" their utterers). The problem seems to me to be due to ignoring (empirical) context and quantity (but has nothing to do with logical quantification). Some examples:   Mass immigration was "good for America" in its (past) history. Therefore mass immigration must be "good for America" now. (P=good for America, A=mass immigration) (even more logically problematic) Humans have been burning fossil fuels for centuries, and "there was no crisis then." Therefore, to claim that fossil fuel combustion is "a crisis now, one must believe that we've been in crisis for centuries." (P=not crisis-producing, A=fossil fuel combustion)   Does this fallacy (or cognitive bias, but this failure "feels logical" to me--ICBW) have a widely-accepted name? Given the extensive and systematic attention to logic and rhetoric over millenia, I suspect this has been previously taxonomized.
79184
Excerpt from a mathematical proof that serves to prove by contradiction, using the Well Ordered Principle, that predicate P(n) is true for all nonzero integers n.     If n belongs to set C i.e. n >= c, then P(n) is false.      This implies the contrapositive,      If P(n) is true, n has to not be a part of set C i.e n &lt; c.   I know that the above implication is valid but why so? How should I know that n cannot take on 2 values simultaneously -- n being both >= c and &lt; c, thus P(n) being both true and false simultaneously? (Yes I am thinking Dialetheism, maybe even quantum logic but I know nothing other than that quantum logic defies certain aspects of propositional logic.) What is the basis behind a predicate (or any proposition) being either true or false? Or would the simultaneity be possible just that I wouldn't be dealing with a proposition to begin with?  Also, if you don't mind, please do let me know if you feel my understanding of concepts and terminologies (i.e. discrete, predicate, contrapositive, assume) are erroneous. I am extremely new to discrete mathematics and could really use the extra guidance.  Thank you.
85117
Out of curiosity I wanted to translate modus ponens into a logical statement and condense/solve it in some way, and I ended up getting True:  $p \land (p \rightarrow q) \rightarrow q$  $=p \land (\lnot p \lor q) \rightarrow q$  $=\lnot(p \land (\lnot p \lor q)) \lor q$  $=\lnot((p \land \lnot p) \lor (p \land q)) \lor q$  $=\lnot(\text{False} \lor (p \land q)) \lor q$  $=\lnot(p \land q) \lor q$  $=\lnot p \lor \lnot q \lor q$  $=\lnot p \lor \text{True}$  $=\text{True}$  I'm not really sure what to make of this. Is modus ponens a tautology? How is it useful in practice if it's not really saying anything?
70405
$((\neg \alpha \to \alpha) \to \alpha) $  Hi, I am trying to prove this.  Can someone gives me some hints to start the question... My friend told me I might need to use deduction theorem here, but I have no clue to approach it..  Axiom 1: A→(B→A).  Axiom 2: (A→(B→C))→((A→B)→(A→C)).  Axiom 3: (¬B→¬A)→((¬B→A)→B).  To clarify: A, B, C, α, and β are propositions (i.e. assigned True or False). → and ¬ have the standard logical meanings.
20189
Question: Can you provide an example of a claim where the base case holds but there is a subtle flaw in the inductive step that leads to a fake proof of a clearly erroneous result? [Note: Please do not answer with the very common  example.]  Comment: Sometimes inductive arguments can lead to controversial conclusions, such as the ,  and a host of other paradoxes. However, I am interested in examples of a more mathematical nature (as opposed to linguistic) where the inductive argument is subtly flawed and leads to erroneous conclusions.   Note: If you provide an answer, please do so in a way similar to how current answers are displayed (gray out the flaw so people can be challenged to discover it).
49673
Here is what my book says about the different ways implications are worded     I am struggling with how "if p, then q" is logically equivalent to "p only if q"  The example I came up with   With "if p, then q" - If Russell plays in the NFL, he plays football.  With "p only if q" - Russell plays in the NFL only if he plays football.  Say Russell plays in the NFL, plays football and plays soccer.   With regards to that statement, my thought would be that "If Russell plays in the NFL, he plays football" implication would evaluate to true because Russell plays in the NFL and he plays football. However, with regards to "Russell plays in the NFL only if he plays football", wouldn't this evaluate to false because it says that the only way for Russell to play in the NFL is if he plays football. That means that playing football and soccer would not be a path for Russell to play in the NFL because it is not the  defined only way, only playing football.   Can someone clarify this?
2316
Soundness: $a \vdash b \implies a \vDash b$, i.e. if we can prove something, it will also be true. We don't want a system where we start out with something true and dedice something false. However it is conceivable that even if our system is sound, maybe it's quite incomplete/limited regarding what we can express, which is why we also would like...  Completeness: $a \vDash b \implies a \vdash b$, i.e. if we can show something is true, it's also provable. We want to be able to prove all true statements. However it is conceivable that even though we can prove all true statements, maybe it also proves false ones as well, which is why we'd also like the soundness property from before.  Do I have the right idea?   If so, how would I begin to prove soundness? If we are already given $a \vdash b$ I'm not sure what all we must iterate over in e.g. propositional logic to show that we always get true statements. Especially since it seems possible I could pick a false $b$ that contradicts.
37289
Couple of days back I asked  question. And after reading comments and answer there, even though I knew the definitions of the different terms (tautology, contradiction, contingent, satisfiable, unsatisfiable, valid and invalid) involved, I was quick to realize that I dont know a lot of subtleties, especially connection between these terms. I didnt find one place discussing all these connections. So I spent some time reading comments and answers on that and other linked post and come up with some understanding which I have put below and want your confirmation for it.     First some quick definitions (you may skip this as this super basic. I have put it to avoid any possible ambiguity):         Tautology: a formula that is true in every possible interpretation   Contradiction: a formula that is false in every possible interpretation   Satisifiable: a formula that is true under at least one interpretation   Unsatisfiable: a formula is unsatisifable if it is contradiction   Valid: a formula is valid if and only if it is true under every interpretation   Invalid: a formula is that is false under at least one interpretation      Doubt  Now to get hold of the connection between all these terms. I prepared below figure:    Next as stated in  comment, "Not a typeX" has two meanings: (1) "The negation of a typeX" and "Not a statement that can be categorized as a typeX".   So, with this in mind, I came up with following relations:   $¬$ tautology $=$ $¬$ valid $=$ contradiction $=$ unsatisfiable $¬$ contradiction $=$ $¬$ unsatisfiable $=$ tautology $=$ valid Not a tautology $=$ not a valid $=$ invalid $=$ can be either contradiction or contingent Not a contradiction $=$ not an unsatisfiable $=$ satisfiable $=$ can be either tautology or contingent $¬$ satisfiable $≠$ (unsatisfiable $=$ contradiction) $=$ invalid $=$ can be contradiction or contingent  $¬$ invalid $≠$ (tautology $=$ valid) $=$ satisfiable $=$ can be tautology or contingent Not an invalid $=$ valid $=$ tautology Not a satisfiable $=$ unsatisfiable $=$ contradiction   Above,    $\neg$ means "negation" (or I dont know if it will be more correct or will add more sense if I say a "Boolean negation") "Not a TypeX" means statement "cannot be categorized as TypeX" $=$ simply means "is" $\neq$ simply means "is not"   I know these are pretty much basic stuff but was source of a lot of confusion for me and I wanted all these related things noted down at one place in correct way. Can anyone confirm if above bullet points and figure are correct?
88291
Let a statement P is "X is true if and only if Y is true". What is the negation of P? I am little confused. It seems that digital equivalent of this statement is P = X and Y. Hence negation of P is (not X) or (not Y) i.e. Either X or Y is false. Am I right guys?
55069
I was doing some review of propositional logic from Enderton's book. In one section(pg. 26 of the 2nd edition), he explains the idea that given wffs $\sigma_1, \sigma_2, \cdots, \sigma_k$ and $\tau$, one can use truth tables to check whether or not $\{ \sigma_1, \cdots, \sigma_k \} \models \tau$. Then he gives some examples of how one might in an educated way avoid checking all combinations of assignments of the propositional variables used in the sigmas and in $\tau$. This part looks o.k to me.  But then Enderton says "The stronger the antecedent(the expression on the left side), the weaker the conditional." He then gives the examples  \begin{align} (P \wedge Q) &amp;\models P \\ (P \rightarrow R) &amp;\models ((P \wedge Q) \rightarrow R) \\ (((P \wedge Q) \rightarrow R) \rightarrow S) &amp;\models ((P \rightarrow R) \rightarrow S) \end{align} What does he mean by this? Which antecedent is stronger, the first or the third? Maybe a question to start out with is: what do "strong" and "weak" even mean here? Thanks for any help/clarification!  Sincerely,  Vien
93187
I have just started studying implication in mathematics. So, you'll probably have an idea of where my confusion lies right from the get go.  In the truth table, where $A \implies B$ we obtain this result:  A   B   T/F ___________ T | T | T T | F | F F | T | T F | F | T   Now, my confusion here is regarding why $A\implies B$ given A is false, and B true. The others I understand. The first and last one are obvious, the second one implies, to me anyway, that given A implies B, the truth of B rests upon the truth of A, B is false, A is True, which cannot be, thus not B given A is false.  Now... then, why is B true despite the fact that A is false? Or rather, why is the statement B given not A, True. The truth of B is implied from the truth of A, but A is a false statement. So it's very contradictory that this may be, and in fact, if you go through a real life example, you would find that the third statement seems to be false.  Say $A$ is the statement that it is dark outside, and $B$ the statement that the sun is not on our side of the earth. If it is not dark outside, than stating that the sun is on the other side of the planet must be wrong (in my example i'm going to claim that the sun is the only light source).  Side note:  I just had a thought, if A is false, does that mean you can conclude... mmm, whatever? I mean, B is implied via the truth of A, if A is false, B is NOT implied, but then B could be EITHER true or false, I suppose. Is this correct?  However, would that not mean that A does not imply anything when false. Would that not set the 3rd and 4th statement to be undefined?
69943
I found a statement that says  $$\forall x[P(x) \rightarrow Q] \equiv \exists x[P(x)] \rightarrow Q$$  Where $Q$ is a formula that does not contain $x$. I need to know when exactly would the equivalence hold. Can we just convert $\forall$ quantifiers to $\exists$. Is there a way to prove the right hand side statement from the left hand side?