Logic and Applications Days 2-4

I normally manage to get a post out each day I’m studying a module, but I’ve really struggled for time this time round. I’ve had a few items in my personal calendar that I didn’t want to miss, but over and above that the workload on this module is pretty intense.

There’s a coursework assignment each week, which constitutes a whole lot of work, but I’ve also chosen to switch from handwritten assignments to preparing my work in LaTeX. It’s made me pretty uncomfortable preparing extensive handwritten documents (on the order of 6-12 pages) for a few reasons. A mistake I make could involve wasting a lot of time re-writing a document, backing up a paper document regularly kinda doesn’t work, and handing in paper documents involves either physical locality or the good old Royal Mail. An electronic version has none of these drawbacks.

On the other hand, preparing this kind of material electronically is non-trivial, as there’s a lot of odd tabular layouts and logic formulae involved. I discounted anything other than LaTeX out of hand, as word processors aren’t really designed for that kind of material. Preparing this stuff electronically is more time consuming initially, but I console myself with the thought that I can correct a mistake very easily!

Anyway, Logic and Applications. We covered the relatively simple Propositional Logic in the first two weeks, and moved onto First Order Logic in weeks three and four, on into week five. So far, the idea seems to be to encode knowledge and deduce from that knowledge more information using rules that can be proven to derive correct conclusions.

Why different types of logic? Propositional logic is simplest, has certain helpful properties as a result, and has limitations you run into pretty quickly .

For example, in Propositional logic, we can encode explicit facts, like “Paul’s Mother is Helen” and “Helen is Female” and work with those facts, but we can’t generalise from there. For example, we can’t add “Jo’s Mother is Sylvia” to our system and deduce that Sylvia is female. To do that would require an ability to say something like “Mothers are Female”. We can’t do that without variables and quantifiers, so we need something more expressive. First Order logic gives us that additional expressivity, for the price of it being more difficult to learn and understand, and being undecidable. That last bit means that in general, no algorithm exists that can be guaranteed to give a yes or no answer as to the truth of a formula expressed in First Order Logic in a finite amount of time.

So, lots of fun to be had with proofs, algorithms and understanding some really abstract stuff!


Logic and Applications Day 1

It’s the start of year three, and I visited UoM last Friday to got through my options and choices for what will almost certainly be the most important year of my MSc.

As usual, I need to choose taught modules. I need to get at least two done, but three would wrap up the taught part of the course completely, which would be a great place to be at the end of the year. I’m going for a bit of an AI flourish to finish with “Logic and Applications” to start in September, followed by “Ontology Engineering for the Semantic Web” Starting November, with a gap in March and then potentially “Text Mining” in April.

I also need to choose a final project, which I’ll need to complete over the course of a year, do some original work in the field of Computer Science and produce a dissertation on the order of 60-100 pages. The big question is do I want to put forward a project of my own devising, or take one that has been proposed by the CS School or a company? In order to complete this part of the course (which counts 50% of the final grade), I need to complete a further special module called “Research Skills and Professional Issues” which runs between November and March. It’s a big decision on a piece of work that’ll sink a huge chunk of my time over the next two years, so I’ll be getting in touch with the project organiser to help me evaluate my choices. One way or another though, it needs to start this year to be do-able in the remaining time.

So there’s a lot of stuff to do – and to pay for. I hadn’t thought about it, but this setup essentially means that I’ll be paying for the remainder of the course this year – well, pretty much now – which is just over £3,000. Ouch!

So anyway, whilst all that’s going on, the first module has started – Logic and Applications. This is a new module this year which seems to have at least partially replaced the Knowledge Representation and Reasoning course that I naively attempted back in 2008… having not fully understood the pre-requisites, I crashed and burned hard and ended up dropping it, as a result achieving nothing for the whole first half of my first year.

This time, the course doesn’t have any pre-reqs, but I’ve spent the last couple of months reading up on Propositional Logic, Resolution, Theorem Provers and First Order Logic, and last week implemented a satisfiability checking algorithm called DPLL and an implementation of a logic-based game called Hunt The Wumpus (specifically because there’s great reference material in AIMA to check my approach) to prove to myself that I understood the concepts. As a result, it looks like I’m pretty much covered up to at least week/day three, which is a good thing.

So, Logic and Applications Day 1 – propositional logic, set theory, mathematical proofs and satisfiability went pretty well. It introduced a couple of gaps in my knowledge, more on the mathematics side of things – what is a reflexive-transitive closure and how would I create and use one, for example. Now to get the week one coursework done… after all, the weekly coursework counts 50% of the marks for this module.

As an aside, the Blackboard system that we used in the first SSD&X module hasn’t resurfaced in any other modules so far. In fact, the preferred method for submission based on my experience is…. wait for it… paper. It’s a bit odd, having spent the last ten years passing papers and documents around pretty much exclusively in a digital medium.

I can sort of see why for this module, at least – the mathematical content means that there’s a lot of symbolic stuff going on, and they’re testing the ability to do the maths, not use tools like LaTeX. That said, those tools seem to be essential for anyone working in CS, so maybe you could make the case that all the CS modules should teach and promote their use.

It will present me with a problem, as it always does. There will be a coursework set in the last lecture day to be handed in during reading week, and I’m not taking time off work to get over to Manchester purely to hand in a piece of paper.