Use LOGIC!

While going through the first test, in preparation for term-test #1, I found that Part B of the first question was pretty time consuming and a tad difficult. Since it is part of the first question and each sub-question(i, ii, iii, iv, v, vi) was only worth 1 mark, this indicated that these questions weren't supposed to be that difficult.

################################################################################
The question:

Recall these python functions from lecture:

def quant1(L1, L2): return False in [x in L2 for x in L1]
def quant2(L1, L2): return True in [x in L2 for x in L1]
def quant3(L1, L2): return False not in [x in L2 for x in L1]
def quant4(L1, L2): return True not in [x in L2 for x in L1]


Part(B)

For each output (i)-(vi), either devise lists L1 and L2 so that the python expression:
[quant1(L1, L2), quant2(L1, L2), quant3(L1, L2), quant4(L1, L2)]
evaluates to that output, or else explain why it is impossible to devise such lists.


(i) [T,F,T,F]
(ii) [T,F,F,T]
(iii) [T,T,F,F]
(iv) [F,T,F,T]
(v) [F,F,T,T]
(vi) [F,T,T,F]


################################################################################

I was wondering why I was taking so long with these questions that are assumed to be easy, so I spent some time trying to figure out what the problem was.

My first attempts at these questions, for each of the questions (i) - (vi), I didn't have an attack plan. I just jumped straight into the question, creating a small random list in my head, and then going through each of the 4 quants individually. Now that I think about it, that was kind of crazy. No wonder why I took so long. I was going through each function in my head, sometimes more than once for a question using a newly created list in my head, and I did this for each question the first time. Thus I ran over 4*6 functions using random made up lists in my head. That was such a waste of time! That definitely wasn't the method the prof had intended.

So then I kept trying to see whether there was a better method, an attack plan, something we've learned in lectures. Then I thought to myself that this is a logic course, and we've went over negations many times. So I went back to the quant functions and wrote comments to indicate what they predicate in English:


def quant1(L1, L2): return False in [x in L2 for x in L1]
## Means there exists an element in L1 that is not in L2

def quant2(L1, L2): return True in [x in L2 for x in L1]
## Means there exists an element in L1 that is also in L2

def quant3(L1, L2): return False not in [x in L2 for x in L1]
## Means all elements in L1 are in L2

def quant4(L1, L2): return True not in [x in L2 for x in L1]
## Means no elements in L1 are in L2

Now I can clearly see that quant1 and quant3 are negations of each other and quant2 and quant4 are negations of each other as well.

"What can I do with this information?" I thought to myself. Well, if some quants are negations of each other, then they both can't be True at the same time in each list. Now that was an easy way to find the impossible lists in (i) - (vi).

Now, thinking logically, it only makes sense that each list would have 2 Trues and 2 Falses in them. Also if any quant predicate is True, the negation quant predicate must be False, and vice versa. So now that eliminates having to go through each of the 4 quants in the list because you can trust that the negation of a quant is false if that quant is true.

So now, thanks to logic, I've developed an attack plan! All I had to do, after filtering out the impossible lists, was to find the quants corresponding to the Trues in the list and then generate a list that would satisfy the quants for them.

Now, with all this knowledge in mind derived from logic, all I had to do was eliminate the lists that have Trues for the quant and it's negation quant in the same list, then generate a list that would satisfy 2 quants.

Why didn't I think of this sooner?!?!

Since it took me a while to figure all this out, I'm guessing I didn't have a good grasp on logic and utilizing logic yet. This course is meant to teach you about logic and how to apply it and a lot of logic definitely applied in this question. Using logic, you can develop techniques for analyzing these types of questions swiftly. It was a good thing that I ran into these problems and figured out better ways to attack the problems because it really helped me with the actual term-test which had similar questions!



Also, for any TA or Professor reading my posts, I know they're pretty long and I apologize for that. I just like to ramble on and I feel that shorter posts aren't sufficient.

Sorry for making you guys read all this!

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!"