A Very Powerful Manipulation Rule

There is one manipulation rule that I feel is not emphasized enough (for me at least) and that is:

P ⇒ Q       ⇔     ¬P ∨ Q

To me, this is one of most powerful manipulation rules that is extremely important to know so I didn't just want to memorize it. I wanted to understand it.

At first, It was kind of hard to wrap my head around the idea that "If P is true, then Q must be true" is the exact same as "P is not true or Q is true." When trying to connect these two statements using English only, it felt kind of hard to visualize, for me at least.

So I ended up working out several different ways to try to grasp this idea logically.

First, I did the truth tables:

P	Q	P ⇒ Q	¬P ∨ Q
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

After I did the truth tables, it was clearly evident that the implication and the logical disjunction statements were identical (according to the truth table). However, in terms of wording and a way of making English sense of it in my head, I was still not fully understanding this. So I continued:

Second, I did the Venn Diagram for both:

For P ⇒ Q : If P is true, then Q must be true, meaning there cannot be anything in the set of P where Q is not true, hence:

(Where P is the antecedent, Q is the consequent, and U is the universe. White is unoccupied)

For ¬P ∨ Q : Everything that is not P can be occupied and all of Q can be occupied, hence:

(Where P and Q are both predicates and U is the universe. White is unoccupied)

After creating the Venn Diagrams for both. It was starting to make a lot more sense. The Venn Diagrams are exactly the same. Since P implies Q means that "If P is true, then Q must be true" which means that there can't be any P's that aren't Q, then that would mean anything that's not P is fine. Also, if it's not P, then it doesn't matter what Q is for the implication as a whole to be true; vacuously. This is making a lot of sense. However, I still wanted to justify this some more!

Finally, I found negating the implication helped finalize my understanding of this manipulation rule:

First, "If P is true, then Q must be true" may be reworded with sets: "Every D that is also a P is also a Q" which would symbolically be:

∀x ∈ D, P(x) ⇒ Q(x)

So, if this was negated, the English would be "There exists a D that is also a P but is not Q." Symbolically:

∃x ∈ D, P(x) ∧ ¬Q(x)

So, I tried to negate the negation, to get back the original implication using De Morgan's Law:

¬(∃x ∈ D, P(x) ∧ ¬Q(x))

∀x ∈ D, ¬(P(x) ∧ ¬Q(x))

∀x ∈ D, (¬P ∨ Q)

Here I stopped and I didn't bother to change the disjunction back to an implication because I now saw that they are truly equivalent. This may have seemed like a roundabout way to get this the implication and disjunction stuck in your head, but this really helped me out! I thought to myself "I think I fully understand this concept now!"

Venn Diagram Madness............

I came across something confusing for CSC165 Tutorial Exercise #1:

Drawing a Venn Diagram that Falsifies statement
d) "There is one of the three python programs that fails all three test suites."

So to falsify the above statement, you'd have to create a Venn Diagram portraying a situation where all python programs pass at least one test suite. If a python program passes at least 1 test suite, then it is not in the set of python programs that "fails all three test suites". Thus all we have to show on the Venn Diagram is that all of the 3 python programs in set Q passes at least one test suite. So technically, the programs can exist anywhere in Q, either in the overlapping Q and T area or just the Q area itself since the Q area itself just represents python programs, not stating how many test suites they pass or fail. So I figured the diagram for this would be:

(**Where Q is the set of 3 python programs, T is the set of universal python programs that pass all 3 test suites, and P is the universe of python programs. Also, O represents area must be occupied, X represents area that must not be occupied, and ? represents area could be empty or occupied.)

However, this diagram does not really say anything definite about making the statement false. For example, since ? represents may be empty or may be occupied, let's say for example that the overlapping T and Q area was empty. Now all the python programs in Q are in the Q only region. In this case, we may have a situation that falsifies the above statement (if all the programs in Q passed at least one test) or we may also have a situation that does not falsify it (any one of the python programs may fail all 3 tests and still be in this region). So this diagram wouldn't be enough to falsify the above claim.

During the tutorial, the Venn Diagram that was presented in answer to d) false situation was:

This Venn Diagram makes sense in that it presents a situation where the statement would be false for sure (if all of the 3 python programs passes all 3 test suites, then there can't be any that failed all 3), but there was just something still bothering me about this diagram. The area in Q may be occupied, not necessarily must not be. This diagram presents one situation where the statement would be false, but not a general diagram showing how to make the statement false. I don't know if I'm conveying myself properly, sorry for the confusion. For example, let's consider the Venn Diagram portraying a False situation for a) "All three python programs that passes all test suites." The correct diagram is:

However, another situation that would make the a) statement False would be this Venn Diagram:

This diagram would show a situation where a) would be False but it wouldn't be the correct most general Venn Diagram.

This is the feeling I'm getting for the tutorial provided Venn Diagram. I feel as if there is another region needed to indicate either programs that passed at least 1 test suite or a region indicating programs that failed all test suite.

The good thing about this experience is that after writing this blog, my head is a lot more clear about this whole situation!

First time SLOGger

Hhhhhmmmmmmmmmmmm. This will be an internet milestone for me. This is not only my first time slogging, it's my first time doing anything related to blogging as well!

This will be interesting!