Negation

Week three came with another new set of information: negation.  Using the &not symbol, we can negate a statement, making the negation which is true when the statement is false.  To begin a negation, we start at the beginning of a statement, as is intuitive.  A statement beginning &notall x in X becomes &exist x in X, and vice versa.

The trickier part of negation comes after: the not symbol moves through the statement to the claims made about the variables initialized but the first part of the statement.  Negating a claim is different depending on what the claim is.  If it is an implication, the negation of that would be antecedent and not consequent. This makes sense if you think about what makes an implication false: the antecedent being true and the consequent being false.  Taking this:

P(x) => Q(x)

when negated becomes

P(x) &and &not Q(x)

When dealing with a conjunction (an and claim); the negation becomes an implication with a false consequent:

P(x) &and Q(x)

becomes

P(x) => &not Q(x)

Seeing this, it almost becomes that implication and conjunction are opposites, so long as you remember which elements must be false.  The final case would then be negating a disjunction (an or statement).  For this case, the disjunction becomes a conjunction between two false elements:

P(x) &or Q(x)

becomes

&not P(x) &and &not Q(x)

This gets more complicated when you get to implications with multiple variable interactions on either side.  I was not completely clear on how to deal with this until Week 4's Monday class, but I feel like I have a firm grasp on how to deal with these negations now.  When moving a negation through a convoluted statement, you have to move from the bigger claims down to the smaller ones the large ones are made up of.  For instance:

(P(x) &and Q(x)) => (R(x) &and S(x))

The first thing to negate is the central implication.  Doing this, we take the antecedent as true and negate the consequent:

(P(x) &and Q(x)) &and &not(R(x) &and S(x))

and then follow the negation through the consequent:

P(x) &and Q(x) &and (R(x) => &not S(x))

and voila! A negated statement with multiple claims.

Quantifiers and Implications

One of the most important things I learned this week was about the differences between universal quantifiers and existential quantifiers.  If a statement has a universal quantifier (all), in order for it to be true it must have no falsifying example; there must be no instance where the statement is false.  Therefore, to prove the statement false, you need only one example where it is not true.  If instead you have a statement with an existential quantifier (some), to prove the statement True there must be one example where the statement holds.  To prove this statement False, there must be no instance where it is True.  When dealing with an empty string, it will prove a statement with a universal quantifier True, and one with an existential quantifier False.

Implications are interesting, and sometimes confusing to construct from English sentences.  An implication is made up of an antecedent and a consequent, in the direction of:

if antecedent then consequent

      In English, however, it is sometimes said: 

 consequent if antecedent 

     or it has confusing modifying words stuck in, such as unless, which is handled as an if not statement.  I personally find this a bit confusing as you add other modifiers, and so there may be a bit of extra practice done on this subject.

Personally, I am a little excited about this new outlook on implications; I can see future arguments with my siblings becoming more interesting when I can say that their point doesn't falsify mine, when in that context it probably should.  

Empty Sets and Misunderstandings

The first week of class culminated in working on the exercises for the first tutorial. I found the instructions fairly straight-forward, but I imagine I would have had a bit of difficulty if not for the lecture material. For example, I received a bit of clarity about the behaviour of empty sets; the value of a function returning whether all values in an empty set are in another non-empty set will not be false. Similarly, a function returning whether no values of the empty set are in the non-empty set will also not be false.

Something that I was slightly confused about through the week was what the syntax of the set-building functions meant for how the function worked. Using an example function from class:

def q0(S1, S2): ''' (set, set) -> bool Return whether ... ''' return not all({x in S2 for x in S1})

I was misreading the actual code; thinking that the x value was first referring to the values in S2 and then comparing them to the values in S1. My mistake was pointed out over piazza, and I realized that it is actually the other way round. It was a small misunderstanding, but the realization is infinitely helpful in figuring out what the function actually does.