And More Proofs

This week assignment 2 was posted, so I have started (and almost finished it) with my partner.  This is the first time in the two years of University I've been through that I'm working with someone else on a project, and it seems to be going very well.  There is a small part of one proof we are stuck on, so hopefully a bit of sleeping on it and staring at the paper will get us over it (or convince us it just doesn't matter).  I guess we'll see how it goes.

We're putting our proof structure into practice now, which is somewhat more difficult than writing general proofs.  On the bright side, this week's material is sort of blurring into last week's for me, so there's not a whole ton of new stuff to study while I'm focusing on my other classes, which tend to take a bit more time to deal with.  I have found that a lot of the conversations I have now end up with me going 'hey! That's what we're doing in 165' which is cool, I suppose.  I have started to feel a bit like this is just being put out into space randomly? Hopefully I'm posting what I'm supposed to, and I guess I'll work on the question we're supposed to solve at some point soon.

Anyway, hope everyone else's blogs are going okay, have a good week and good luck with assignment 2.

Proving and Disproving Statements

Week 6, so we're halfway through the semester, yay!  This week was about proofs, which may or may not suck, we'll just have to wait and see.  The structure seems fairly straightforward, assume and conclude and assume and conclude, that part's actually fun.  The thinking part, however, may prove to be a little challenging.

Starting off with a straightforward proof. you pretty much set up your domains (assume \forall variables and find an example \exists variable) and then do all of your proving-stuff until you can claim that the rest of the statement is true.  Then you have to go back and close all of your assumptions with conclusions, which in class Danny did at the same time as he made the assumption.  Said like this, it sounds super easy but I know i'm going to find it crazy hard to muddle through all of the proving stuff.

To disprove a statement, you just prove the negation of it, since the negation is only true when the statement is false.  Once you have the negation, you just go through all of the same steps.  It is also possible to go through the proof and disprove it by finding a contradiction, but that seems much more difficult, so I'll stick with proving the negation for as long as I possibly can.

The tests came back this week, and for the most part mine went over fairly well, so hopefully the rest of the class keeps on like that.  I hope everyone else is happy with their results, good luck with the rest of the term!

Introductions and Proofs

Just as a little pre-amble, sorry about the changes in notation, I keep trying to find a way to insert the actual symbols but I have yet to figure it out.  I'll try to stick to just the backslashes from now on.

This week was the week of the first midterm.  I actually had a big midterm in biochemistry the day before this one, so my studying may have slipped off the top-priority spot.  Ignoring that fact, I feel like it went really well, I was well prepared despite my lack of thorough preparation, if that makes any sense.  In any case, we continued with proof structure this week, which I find really fun, but I like things that have easy-to-follow steps and procedures.

The biggest thing so far this week has definitely come from tutorial (yet again), notation in proofs and symbol introduction:

Creating a general proof without actually proving anything is an integral part of solving a proof; it helps you to organize your thoughts and find out what you actually have to prove.  Here's an example:

to prove : \forall x \in D, \exists y \in D', P(x, y)

assume x in D     #domain assumption

    find y'

        [proof of y' \in D']

        then y' \in D'

        [proof of P(x, y')]

        then P(x, y')

    then \exists y \in D', P(x, y)    # \exists -intro.

then \forall x \in D, \exists y \in D', P(x, y)     # \forall -intro.

Now this only uses the quantifier introductions; there are also \and -intros, \or -intros, and =>-intros.  They can be used under specific conditions:

\and - intro:

    If you are proving P(x) \and Q(x), ignoring the quantifier, you can introduce an \and symbol if you prove P(x) and Q(x) separately.

\or - intro:

    If you are proving P(x) \or Q(x), again ignoring the quantifier, if you assume P(x) and then prove Q(x), you can introduce the \or symbol, because it is inclusive - of Q(x) is true it doesn't matter if P(x) is or not.

=> -intro:

    If you are proving P(x) => Q(x), ditto with the quantifier, this proof actually follows the same formula as for an \or -intro.  The only way for an implication to be false is for the antecedent to be true and the consequent to be false, so we assume P(x) and prove Q(x), and we can then introduce the => symbol.

Proofs

This week, I received a rough introduction to generating proofs of logic statements.  The most important part of this, at least to me, was in reasoning my steps, and which actual steps to take.  The most important equivalences are:

implication

x => y  =  \not x \or y

distributive property

x \and (y \or z)  =  (x \and y) \or (x \and z)

deMorgan's law

\not(x \and y)  =  \not x \or \not y

When writing proofs it is important to explain the reasoning behind your steps, so that your audience can easily read through your work and understand the thought process behind it.