1

I don't want to ask my professor about this because I'm awful at this and he's not the, uhh, patient type of professor to say the least.

ANYWAY, it was my understanding that ¬(P → Q ) and (¬P → ¬Q ) mean two different things. And that Q → P is equal to (¬P → ¬Q ).

Yet one of the answers to a question says that Q → P is a logical consequence of ¬(P → Q ), which I just don't understand at all.

To confuse matters further, afaik ¬(p → q) ⟺ p ∧ ¬q is correct, so I guess I'm just lost and missing something here in the definition of logical consequence?

Any help would be much appreciated.

Daniel K.
  • 13
  • 3
  • Welcome to StackOverflow! You might get better answers over at the [Computer Science StackExchange](https://cs.stackexchange.com/) because StackOverflow is for questions about implementation. – D M Jan 10 '22 at 20:47
  • Thanks for the reply, you're probably right this isn't the best place, I think actually the math stackexchange is best suited so I'll try that one once I can post again :) – Daniel K. Jan 10 '22 at 21:12
  • `A` is a logical consequence of `B` if `B -> A` is always true. Go ahead and draw the truth table for `~(P -> Q) -> (Q -> P)`. You'll see that all entries come out as true. This of course is the "mechanical" explanation of it. If you're looking at it from a more linguistic perspective, think of when you can make `P` false while `Q` being true, given it isn't the case that `P -> Q`. You'll see that it never happens. – alias Jan 10 '22 at 22:02
  • Thank you for the explanation, this does indeed make sense, I really was just getting confused by the linguistics it seems. – Daniel K. Jan 10 '22 at 22:13

1 Answers1

1

Perhaps some more background - by logical consequence we usually mean the semantical notion of the entailment operator: the entailment A ⊨ B holds if B is true in all models in which A is true. In classical logic this is equivalent to saying that ⊨ A → B is true (i.e. the formula A → B is true in all models).

Let's have a look at the concrete consequence in question:

¬(P → Q) ⊨ Q → P

We only consider interpretations which make ¬(P → Q ) true. This is only the case if Q is false and P is true (making Q → P false and its negation true). But if Q is false, then Q → P is true because from a false premise follows everything.

Let's look if the two formulas are equivalent i.e. if also P → Q ⊨ ¬(P → Q):

Let's first go use the definition of implication and use de Morgan's rule to get:

P → Q ⊨ ¬¬P ∧ ¬Q

We can also remove the double negation that we end up with:

P → Q ⊨ P ∧ ¬Q

Now P → Q has three interpretations that make it true (P false + any value of Q and both P and Q true) but not even one makes P true and Q false (i.e. is a model of P ∧ ¬Q). Therefore the formulas are not equivalent.

lambda.xy.x
  • 4,918
  • 24
  • 35