The Information on this Page is Preliminary!

Topics

1. languages,
2. automata,
3. grammars

We shall now take what may appear as a detour by looking at some very basic, but also very useful, topics in elementary logic. In the remainder of this course, I hope that you'll appreciate that what looks like a detour is, in fact, not so! Logic is an important working tool for Computer Science --- as Moshe Vardi often says, logic is the "calculus" of our discipline. The two lectures that we'll have today will serve as an introduction to propositional (aka Boolean) logic and its uses as a problem solving and modelling tool in Computer Science.

Time and Location

Reading Material

Exercises

• Problems 3 and 4 on this page.
• Problems 1-5 on this page. More seriously, classify these formulae as tautologies, contingencies or contradictions:
  1. P --> P
  2. P and (not P)
  3. P and (Q or P)
  4. P --> (Q --> P)
  5. P <--> (not P and Q)
  6. (P and Q) --> P
• Problems 1-2 on this page.
• Exercises 7 and 15 on this page. (You may wish to try several of the other exercises there too!)
• Per, Kristian, Ole and Jens are to hold an Xmas-party. Unfortunately, they are almost out of money which severely limits the amount of beer at the party. In fact, they have to make do with one Tuborg, one Carlsberg, one Xmas , and one Carl's Special. However, the four guys have individual requirements which must be fulfilled at all costs. In particular, Per only drinks Tuborg and Carlsberg; Kristian only drinks Carlsberg and Xmas; Ole essentially drinks everything except Xmas, and Jens can only drink Carlsberg and Carl's Special. Is it possible to plan the party drinking so that they all get something to drink? Model this situation using propositional logic, and help these guys!
• [This exercise is due to Stanley Burris. Do it, it's fun!] The island of Tufa has two tribes, the Tu's who always tell the truth, and the Fa's who always lie.
  A traveller encountered three residents A, B and C of Tufa, and each made a statement to the traveller:
  • A said, "A or B tells the truth if C lies."
  • B said, "If A or C tells the truth, then it is not the case that exactly one of us is telling the truth."
  • C said, "A or B is lying if, and only if, A or C is telling the truth."
  Determine, as best as possible, which tribes A, B and C belong to. Of course, using propositional logic helps!
• [New Exercises]
  1. Given a DFA A and a string w, can you write a propositional formula F_A,w that is satisfiable iff A accepts w?
  2. You are given a graph G = (V,E). Write a propositional formula F_G that is satisfiable iff G has a Hamiltonian path.
  3. [This exercise is due to Nimal Nissanke.] Is the following argument valid? Provide a reason why it is/isn't.

     If a misalignment of the clocks of the robot implies a shortage of its power, then there will be a delay in the descent of the buggy to the Martian surface.
     Misalignment of the clocks of the robot prevents commands from Mission Control reaching the robot, and delays the descent of the buggy to the Martian surface.
     If the solar batteries are fully drained during the Martian night or there is a delay in the descent of the buggy to the Martian surface, then there is a power shortage in the robot.
     I can therefore conclude that there is a power shortage in the robot.