Department of Computer Science

Logic and Computation CS1005

Introduction to the Module

Department of Computer Science
Module Leader
Pof David Gilbert
My job:
Teaching: Lectures, marking …
Research: Publishing, Grants …

Research topics: applications of computer science to biology

and medicine:-
bioinformatics, systems and synthetic biology, modelling,
computational design of biological systems, personalised
health care, systems medicine.
david.gilbert@brunel.ac.uk
Logic and Computation, 01 Introduction Slide 2
Department of Computer Science
The CS1005 Team
Dr Nour Ali
Research: Software Architecture, Self-Adaptive Systems,
Reverse Engineering, Mobile and Ambient Awareness.

Dr Derek Groen
Research: Modelling and simulation, Multiscale computing,
High performance computing, bloodflow simulations, N-body
simulations, refugee movement simulations.

Dr Rishi Ruttun
Research: Human Computer Interaction, web-based learning and
business systems, individual differences, visual and audio
instructional aids (speech and non-speech sounds), multimedia,
disorientation, learning performance and learner attitudes.

Logic and Computation, 01 Introduction Slide 3

Department of Computer Science
Staff roles in CS1005

• David Gilbert: Manage the module, teach, mark

• Other Academic Staff (Drs Ali, Groen &

Ruttun): Assist in teaching and marking

• GTAs: To give assistance (not to give lectures).

Ask them for help in labs!

Logic and Computation, 01 Introduction Slide 5

Department of Computer Science
When? Timetable
Term 1

Term 2

Logic and Computation, 01 Introduction Slide 6

Department of Computer Science
Where? Campus
Labs (HALB 223)

Lectures
(Eastern
Gateway)

Logic and Computation, 01 Introduction Slide 7

Department of Computer Science
Lectures

1 hour max to “set the scene”.

You will be required to do more reading as

instructed.

Will not necessary cover every detail of

topics you need to study.

Logic and Computation, 01 Introduction Slide 8

Department of Computer Science
Laboratory Sessions
Depends on the lecture topic:

For example:
• Worksheets to read for more details of topics
• Questions to work through (similar to exam
questions)

Logic and Computation, 01 Introduction Slide 9

Department of Computer Science
Golden rules!
• Come on time – please do not be late to
the sessions.
• Attend every lecture & lab that you are
scheduled for.
• Turn off mobile phones in the lectures and
labs.
• No ‘chit chat’ in the lectures.

Logic and Computation, 01 Introduction Slide 10

Department of Computer Science
Blackboard
All data for this module will be available via
Blackboard:

• Slides
• Worksheets

Logic and Computation, 01 Introduction Slide 11

Department of Computer Science
Reading

No set text for entire course though

Recommended (see study guide):

• Epp, S.S. 1995/2004, Discrete mathematics with

applications, 2nd or 3rd edition, PWS Publishing
Company, Boston.

Logic and Computation, 01 Introduction Slide 12

Department of Computer Science
Assessment

• Coursework (25%): One multiple choice test, via

wiseflow

• Exam (75%): One multiple choice examination,

via wiseflow

• Note: Don’t aim to fail the exam!

[retakes are capped…]

Logic and Computation, 01 Introduction Slide 13

Department of Computer Science
The future…

MAPK modelling david.gilbert@brunel.ac.uk 14

Department of Computer Science
Is challenging!
Next year?
2027?
2021? DivisionManager
#getajob
2030+?
2024?
TeamLeader BigBoss

MAPK modelling david.gilbert@brunel.ac.uk 15

Department of Computer Science
The Big Questions
• What is / is not a computer?
• phone, TV, glasses, Alexa, robot, finch, drone, …
• What is computation?
• How can I represent/model the real world in way so
that I can solve problems?
• Is everything computable?
• Will my method scale up?
• How long will it take?
• Do I need a bigger machine or a smarter method?
• What’s the Next Big Thing???
Logic and Computation, 01 Introduction Slide 16
Department of Computer Science
The Key Topics
• History of Computing (Prof Gilbert)
• Turing Machines (Dr Nour, Prof Gilbert)
• Language theory – formal grammars (Prof Gilbert)
• Logic (Dr Ruttun)
• Mathematics (Dr Groen)
• Data structures & complexity (Dr Ali, Prof Gilbert)
• Cutting Edge Computational Logic (Dr Ali, Dr Groen, Dr
Ruttun)
Logic and Computation, 01 Introduction Slide 17
Department of Computer Science
What !!???

Turing?

Logic?

Languages?
Data
structures?
Complexity? Maths?

Logic and Computation, 01 Introduction Slide 18

Department of Computer Science Some Motivation
(Why study this?)
• Turing machines – underpin all computational machinery

• Formal grammars – gives you a powerful tool to handle text &

other data!

• Logic in Computing: Ability to think abstractly, derive new

results from existing, identify flawed logic in people arguments,
model the real world

• Discrete mathematics: needed to model the real world

• Data structures for modelling: how to encode problems as well

known data structures, in preparation to compute over them.

Logic and Computation, 01 Introduction Slide 19

Department of Computer Science Charles Babbage
Difference engine (1830’s)
Difference engine – reconstructed (Science
Museum), and Analytical engine decimal
computer with notion of sequential
instructions

Logic and Computation, 01 Introduction Slide 20

Department of Computer Science
Alan Turing (1912-1954)
• British Mathematician
• Developed the concept of
the Turing Machine
• In 2nd World War developed
“The Bombe” to break the
Enigma codes (@Bletchley
Park)
• Developed, worked & used
early computers

Logic and Computation, 01 Introduction Slide 21

Department of Computer Science Colossus – Tommy Flowers, unsung
hero
• The use of machines to break
into Lorenz, the high-grade
cipher machine used by Hitler
and his High Command to
encipher strategic messages was
the brain-child of Bletchley Park
Codebreaker, Max Newman.
• Colossus was developed by
General Post Office engineer,
Tommy Flowers, to help speed
up the process.

Logic and Computation, 01 Introduction Slide 22

Department of Computer Science
Power of Turing Machines
What can Turing Machine calculate?

What Turing Machines can’t do…

Logic and Computation, 01 Introduction Slide 23

Department of Computer Science
Importance of Language
Noam Chomsky (1928-) is a
linguist, cognitive scientist,
historian, social critic, and
political activist.
• Also developed a language hierarchy
• Useful for compilation process in computers
• Simplest languages are regular languages

Logic and Computation, 01 Introduction Slide 24

Department of Computer Science
Why regular expressions are useful
Power editing!

Change all hyphens ‘-’ into underscores

Change the variable X1 into Y1 in the current line

Remove the ‘#’ symbol at the start of the next 10 lines

Change all words at the beginning of a sentence to start

with a capital letter.

Logic and Computation, 01 Introduction 25

Department of Computer Science Binary notation and Punchcards
(1940/50’s)
Zuse’s z3 used discarded movie reels – hole
or no hole to denote 1s and 0s

Logic and Computation, 01 Introduction Slide 26

Department of Computer Science Logic

p and q
p or q
Not p
p implies q

If it is sunny or raining, I
will use an umbrella
p q p or q
T T T
T F T
F T T
F F F
Logic and Computation, 01 Introduction 27
Department of Computer Science
Logic – an example
• Bank Managers and Academics at a party
• Academics always truthful(!), Bank Managers always lie
• You arrive at the party and meet two people:
• A says: “B is an Academic”
• B says: “A and I have different professions”
• What are A and B?

Logic and Computation, 01 Introduction Slide 28

Department of Computer Science
Logic – an example
• Bank Managers and Academics at a party
• Academics always truthful(!), Bank Managers always lie
• You arrive at the party and meet two people:
• A says: “B is an Academic” A B
• B says: “A and I have different professions”
• What are A and B?

Logic and Computation, 01 Introduction Slide 29

Department of Computer Science
Logic – an example
• Bank Managers and Academics at a party
• Academics always truthful(!), Bank Managers always lie
• You arrive at the party and meet two people:
• A says: “B is an Academic”
• B says: “A and I have different professions”
• What are A and B?

• Suppose A is an Academic – What A says is true so…

• B is an Academic too – What B says must also be true …
• “A and I have different professions” – a contradiction!

• Therefore, A cannot be an Academic (so he is a lying BM)…

• So B cannot be an Academic either …
• So they are both Bank Managers!
Logic and Computation, 01 Introduction Slide 30
Department of Computer Science Errors

"for some integer x , it is true that x > 2 but x2 is

not greater than 5"

“All healthy people eat an apple a day

Keisha eats an apple a day
Therefore, Keisha is healthy”

Logic and Computation, 01 Introduction 31

Department of Computer Science Boolean Algebra and Hardware

Logic and Computation, 01 Introduction 32

Department of Computer Science Von Neumann architecture

CPU
Control Unit
Input Arithmetic Output
logic unit

Memory This performs

both arithmetic
and logic
Hungarian mathematician, operations
John von Neumann
Logic and Computation, 01 Introduction 33
Department of Computer Science (Discrete) Mathematics

Graph Theory
Discretization

Set Theory
Discrete Simulation
Department of Computer Science Sets, Graphs and Sequences

1. Sets
2. Graphs
3. Sequences
4. Proof by induction

Logic and Computation, 01 Introduction 35

Department of Computer Science
Russell’s Paradox

In a town there is a barber who shaves all

men (and only those men) who do not shave
themselves.

Q: Does the barber shave himself?

Logic and Computation, 01 Introduction 36

Department of Computer Science
Halting Problem

Similar to Russell’s paradox:

If you run a piece of code you often get
caught in an infinite loop…

“Can we write an algorithm, that will take in

an algorithm, and data, and output “Loops
forever” if running the code results in an
infinite loop or “Halts” otherwise?

Logic and Computation, 01 Introduction 37

Department of Computer Science Social Networks
Who is the most
‘influential’ member?

Social cohesion: the

communities within
the network
Logic and Computation, 01 Introduction 38
Department of Computer Science
Cutting Edge Computational Logic

Logic and Computation, 01 Introduction 39

Department of Computer Science
Learning Outcomes
• Demonstrate an understanding of first order logic and
simple approaches to reasoning

• Demonstrate an understanding of the basic principles of

Turing machines

• Demonstrate an understanding of regular expressions and

parse trees

• Apply basic discrete mathematics to model simple

problems

Logic and Computation, 01 Introduction Slide 40

Department of Computer Science
Good Luck with the Module!
• No labs in this first week

• First CS1005 Lecture and Lab:

• Week 2 (4th Oct)
• History of Computing and Logic
Slides available shortly after the lecture
Lab solutions directly after the lab sessions

Logic and Computation, 01 Introduction Slide 41