If $(P \implies Q),$ then $\lnot(P\land\lnot Q)$

Question

In this correct:

If $(P \implies Q)$ is true, then $\lnot(P\land\lnot Q)$ is true.

I came up with this in my search to understand implication and the two troublesome, for me, lines in the truth table. I am only able to write this sentence, I do not have the knowledge to prove it - yet. I can show that the truth table columns for two statements are the same.

This is either my first glimmer of light or my first false step.

I wrote "¬(P∧¬Q) is true" to describe both the line in the truth table where P is true and Q is false and further explore the implication connective. I thought that "if (P⟹Q) is true, then ¬(P∧¬Q) is true" would either have the same truth table as each of it's component statements or it would not. De Morgan's theorem is something that I have read and may have understood. It is not something that I can use yet. I know there are some who can just look at it and tell something, but I do not know yet what that something is. I assume that there may come a time when I will be able to do so. If that time arrives, it will be because of the patient effort those who wrote the answers below.

Answer 1

There are two ways to approach this question.

• The first one it to start with natural language and with the ordinary expression " if...then" and, from this starting point, to ask ourselves: what do we mean when we utter " if A, then B". For example what do I mean if I do the promise : " If you travel to Mars before the end of this month, I'll buy a car for you.".

I think you will agree that, the only way for my promise to turn into a false one is the case where (1) the person actually manages to travel to Mars before the end of the month, and (2) I do not buy a car for her. In all other cases ( the 3 remaining ones on the truth table) , I will not have said something false, my promise-statement will be a true one.

• In the second approach, one forgets natural language, starts with the truth table of the " $\rightarrow$ " operator ( without even trying to "read" the symbol in natural language) and considers this truth table as its definition. By inspecting the truth table, you will see that the proposition $(P{\rightarrow}Q)$ is true on line $1$, $2$, and $4$. That is to say, $(P{\rightarrow}Q)$ is true just in case we are not on line $2$, where $P$ is true and $Q$ is false. Translating " just in case" as a biconditional or as an equivalence, we therefore have

$(P{\rightarrow}Q)$ if and only if $NOT(P\wedge NOT-Q)$

( Read : P implies Q is true iff it is not the case that ( P is true and Q is false).

• *As you see, in the second approach, there is no real point in asking "why" this is true. This is simply the definition of the " $\rightarrow$" operator.*

• The "construction" of propositional calculus could be explained by the following story: (1) we have a truth table ( which is one amongst the 16 posssible truth tables for a binary connective). (2) We therefore know that there is such a binary connective with this truth table. (3) Then, we decide to assign to it the symbol " $\rightarrow$ ". (4) And after that, due to the fact we notice that this operator will be useful to define logical implication, we decide to read it as " material implication" or " if...then".

Note : on the distinction between material implication and logical implication, you may have a look at Seymour Lipschutz, Outline Of Set Theory, Chapter on The Algebra Of Propositions ( at archive.org).

Answer 2

The material conditional (that mathematically defined truth-functional operator) is, as you no doubt found out at this point, an imperfect match to the English conditional.

For example, if I say "If bananas are yellow, then the sky is blue", you are apt to say: "No, that's not true. Sure, bananas are yellow, and the sky is blue, but they have nothing to do with each other. So, I consider that a false statement". But note, the truth-table for the material conditional would say: "True, because $T \to T = T$"

Or how about this: "If John lives in London , then John lives in Germany". To this, you would probably just say "False! London is in England, not Germany!". Well, note that if John lives in Paris, then John lives in London nor Germany, and so the material conditional analysis would say: "F \to F = T!"

This mismatch is known as the Paradox of Material Implication

Interestingly, though, your case should be fairly unproblematic though. That is, if we have "If $P$ then $Q$" then it should be clear that you can't have $P$ being True but $Q$ being False. Indeed, the row of the truth-table where we say that $P \to Q$ is False when $P$ is True and $Q$ is False is the one row that is completely unproblematic when we try to use the material conditional to analyze 'If ... then ...' statements: of course the statement $P \to Q$ is False in that case. And so that mans that if we do have $P \to Q$ being true, then clearly we cannot have that $P$ is true and $Q$ is False, i.e. we then have $\neg (P \land \neg Q)$. So, we have

$$\text{If } (P \to Q) \text{ then } \neg (P \land \neg Q)$$

Answer 3

Notice that $$P\Longrightarrow Q$$ is the same as $$\neg P\vee Q$$ which is the same as $$\neg(P\wedge \neg Q)$$ by de Morgan's law, which is the expression you are asking about.

Answer 4

To show that "If $A$ then $B$", you need to show that for each row where $A$ is true, $B$ is true as well, or conversely, there are no rows where $A$ is true but $B$ is false.

P  Q   P -> Q   -(P ^ -Q)   ⊨?
1  1      1         1       ✓ (P -> Q is true and -(P ^ -Q) is also true)
1  0      0         0       ✓ (P -> Q is not true)
0  1      1         1       ✓ (P -> Q is true and -(P ^ -Q) is also true)
0  0      1         1       ✓ (P -> Q is true and -(P ^ -Q) is also true)

Since every row has a checkmark, the implication holds.

If you found that the two statements have the same truth values in all of the rows, then the above follows from that: If in every row, if $A$ is true then $B$ is true and if $B$ is true then $A$ is true, then you showed that $A$ and $B$ are logically equivalent ($A$ if and only if $B$). And in that case, you obviously also have that whenever $A$ is true $B$ is true, so $A$ logically implies $B$ (if $A$ then $B$).