A reasoning for showing that "p implies not q" is equivalent to "not p or not q"

[Ozma]

It is easy to show, using truth tables, that [imath]p \implies \neg q[/imath] has the same truth values of [imath]\neg p \lor \neg q[/imath]; however, I was trying to find an "intuitive" way to remember this, and I came up with this reasoning: the disjunction is true when at least one of the proposition in it is true, false when both the propositions are false. Since the implication is false only if the antecedent is true and the consequence is false, the implication [imath]p \implies \neg q[/imath] is false only if [imath]p[/imath] is true and [imath]\neg q[/imath] is false, that is if [imath]p[/imath] and [imath]q[/imath] are both true. But if [imath]p[/imath] and [imath]q[/imath] are both true then [imath]\neg p \lor \neg q[/imath] is false. The implication is true if [imath]p[/imath] is true and [imath]\neg q[/imath] is true, if [imath]p[/imath] is false and [imath]\neg q[/imath] is true or if [imath]p[/imath] false and [imath]\neg q[/imath] is false (this latter is equivalent to [imath]\neg p[/imath] true and [imath]q[/imath] true); for all these three possibilities, it is [imath]\neg p \lor \neg q[/imath] true as well. So, in any possible case, the two have the same truth values. Is this reasoning correct?

 

[pka]

It is easy to show, using truth tables, that [imath]p \implies \neg q[/imath] has the same truth values of [imath]\neg p \lor \neg q[/imath]; however, I was trying to find an "intuitive" way to remember this, and I came up with this reasoning: the disjunction is true when at least one of the proposition in it is true, false when both the propositions are false. Since the implication is false only if the antecedent is true and the consequence is false, the implication [imath]p \implies \neg q[/imath] is false only if [imath]p[/imath] is true and [imath]\neg q[/imath] is false, that is if [imath]p[/imath] and [imath]q[/imath] are both true. But if [imath]p[/imath] and [imath]q[/imath] are both true then [imath]\neg p \lor \neg q[/imath] is false. The implication is true if [imath]p[/imath] is true and [imath]\neg q[/imath] is true, if [imath]p[/imath] is false and [imath]\neg q[/imath] is true or if [imath]p[/imath] false and [imath]\neg q[/imath] is false (this latter is equivalent to [imath]\neg p[/imath] true and [imath]q[/imath] true); for all these three possibilities, it is [imath]\neg p \lor \neg q[/imath] true as well. So, in any possible case, the two have the same truth values. Is this reasoning correct?

Do you know that [imath]\left( {P \Rightarrow Q} \right) \equiv \left( {\neg P \vee Q} \right)~?[/imath]

 

[Dr.Peterson]

Is this reasoning correct?

Yes, though I had trouble reading it. I'm going to format it differently to make it easier for me to follow:

The disjunction is true when at least one of the propositions in it is true, false when both the propositions are false.​

​

Since the implication is false only if the antecedent is true and the consequent is false,​

• the implication [imath]p \implies \neg q[/imath] is false only if [imath]p[/imath] is true and [imath]\neg q[/imath] is false, that is, if [imath]p[/imath] and [imath]q[/imath] are both true.
• But if [imath]p[/imath] and [imath]q[/imath] are both true then [imath]\neg p \lor \neg q[/imath] is false.

The implication is true ​

• if [imath]p[/imath] is true and [imath]\neg q[/imath] is true,
• if [imath]p[/imath] is false and [imath]\neg q[/imath] is true or
• if [imath]p[/imath] is false and [imath]\neg q[/imath] is false (this latter is equivalent to [imath]\neg p[/imath] true and [imath]q[/imath] true);
• for all these three possibilities, [imath]\neg p \lor \neg q[/imath] is true as well.

So, in any possible case, the two have the same truth values.​

I myself would say it more simply:

[imath]p \implies \neg q[/imath] is false only if p is true but (i.e. and) q is true. So it is true exactly when p is false or q is false. That is,
[imath]\neg p \lor \neg q[/imath]. [This is largely an application of De Morgan's law.]​

Of course, I usually remember it in the form @pka mentioned; and if I am inclined to forget that form, I remind myself by thinking the equivalent of what I just said:

[imath]p \implies q[/imath] is false only if p is true but q is false. So it is true when p is false or q is true. That is, [imath]\neg p \lor q[/imath].​

 

[Ozma]

Thanks to both of you for the help.

To pka: No, I didn't know. Knowing that, I can just substitute [imath]Q[/imath] with [imath]\neg Q[/imath] and obtain the result needed because it holds for any proposition and so, in particular, for the negation of any proposition?

To Dr. Peterson: Thanks for the formatting suggestion, indeed it is a little "narrow" reading it again. Your last sentence helps a lot and it is indeed way faster!