程序代写代做代考 concurrency database algorithm asp Java SQL prolog AI javascript COMP 1.41  INTRODUCTION TO LOGIC

COMP 1.41  INTRODUCTION TO LOGIC

1

Logic and AI Programming:

Introduction to Logic

Introduction to Prolog

F. SADRI

Autumn Term

October – December

2

Course Material

Course material will be available via CATE,

including:

Notes

Tutorial Exercises

Tutorial Exercise Solutions

Coursework

3

CONTENTS

Introduction to logic

Propositional logic
• Syntax

• Semantics (Truth Tables)

• Rules of inference (Natural Deduction)

Predicate logic
• Syntax

• Informal semantics

• Rules of inference (Natural Deduction)

Prolog programming

Time permitting: Probabilistic Prolog or

Abductive Reasoniong

4

Books

background reading on logic

• Any book on logic will have useful examples.

• Richard Spencer-Smith, Logic and Prolog,

Harvester Wheatsheaf, (The library has a

number of copies)

• Jim Woodcock and Martin Loomes, Software

Engineering Mathematics”, Pitman Publishing

5

Books
Prolog

• Ivan Bratko, “Prolog programming for

artificial intelligence“, Addison-Wesley,

Third Edition, 2001 and later.

Assessments and Examination

• One Logic Coursework

• One Prolog Lab Assessment

• One Examination in May:

Paper M1 (Program Design and Logic) will have:

– two questions on Logic and

– two questions on Object-Oriented Design

6

Relevance of this course to

Spring Term Modules

• Logic-based Learning course

• Introduction to Artificial Intelligence

• System Verification

• Argumentation and Multi-Agent Systems

7

and to a lesser extent

• Databases

– Database languages, e.g. relational calculus and
some features of SQL

– Datalog: emerging e.g. in data integration,

information extraction, network monitoring,

security and cloud computing

8

Logic has many applications in

computing

For example:

• Basis of a family of programming
languages, e.g. Prolog, ASP (Answer Set
Programming).

• Basis of verification tools to reason about
C, Java and JavaScript programs, and
algorithms for concurrency, e.g. using
Separation Logic.

9

• Software engineering: Formal specifications

and formal verification of programs.

How do you make sure a program is

“correct”?

Review, again and again and ….

– Review the spec

– Review the design description

– Review the code

10

Test, again and again and ….

– Unit testing

– Integration testing

– Validation testing

11

But that is not enough.

How many tests do you run to be sure the

system is correct?

Logic provides a way of proving the system

correct and

this can be automated too.

12

13

Logic is also useful more

generally in life

• Clear thinking

• Judging validity of arguments and

justification of conclusions

• Spotting inconsistencies

• Awareness and avoidance of ambiguities of

natural language

14

Which of the following

arguments are valid?

Advertisement for a computing book: If you

don’t use computers you don’t need this

book. But you are a person who uses

computers. So you need this book.

If you work hard you will succeed. So if

you do not succeed you have not worked

hard.

15

Which of the following

arguments are valid?

Heard in a radio interview with a well-

known politician: All our problems have

come from the EU. So nothing good has

resulted for us from our membership of the

EU.

More reasoning exercises
1. All the trees in the park are flowering trees.

2. Some of the trees in the park are dogwoods.

3. All dogwoods in the park are flowering trees.

If the first two statements are true, the third

statement is

A. true

B. false

C. uncertain

16

More reasoning exercises

1. All the tulips in Zoe’s garden are white.

2. All the roses in Zoe’s garden are yellow.

3. All the flowers in Zoe’s garden are either white or yellow

If the first two statements are true, the third statement is

A. true

B. false

C. uncertain

17

More reasoning exercises

Fact 1: All dogs like to run.

Fact 2: Some dogs like to swim.

Fact 3: Some dogs look like their owners.

If these three statements are facts, which of the following statements

must also be a fact?

I. All dogs who like to swim look like their owners.

II. Dogs who like to swim also like to run.

III. Dogs who like to run do not look like their owners.

A. I only

B. II only

C. II and III only

D. None of the statements is a known fact.

18

Some arguments –

Are they valid?

It has been proven that all heroin addicts

smoked marijuana in their youth. Therefore,

smoking marijuana leads to heroin

addiction.

We cannot win the war on poverty without

spending money. So if we do spend money

we will conquer poverty.

19

20

Another argument – Is it valid?

One of the old arguments of tobacco spokesmen
against the claim that smoking causes lung cancer:

Lung cancer is more common among male
smokers than it is among female smokers. If
smoking were the cause of lung cancer, this would
not be true. The fact that lung cancer is more
common among male smokers means that it is
caused by something in the male make-up. If
follows that lung cancer is not caused by smoking,
but something in the male make-up.

Propositional Logic

• A good place to start.

• It is the core of many logics.

21

22

Components of a logic

• Language:

– alphabet : symbols

– syntax : rules for putting together the symbols

to make grammatically correct sentences.

• Semantics:

meaning of the symbols and the sentences.

• Inference rules

23

The Propositional Language:

Alphabet

• Propositional symbols

e.g. use_computers, need_book, p, q, r, s, p1

• Logical connectives:

 : and (conjunction)

 : (inclusive) or (disjunction)

: not (negation)

sometimes denoted as ~

 : implication (if-then)

 : double implication (if and only if)

24

The Propositional Language:

Syntax of a grammatically correct sentence

(well formed formula, wff)
• A propositional symbol is a wff.

• If W, W1 and W2 are wffs then so are

 (W) sometimes written as ~(W)

(W1  W2)

(W1  W2)

(W1  W2) (W2  W1)

(W1 W2)

• There are no other wffs.

25

Examples

Suppose p, q, r, s, t are propositions. Then:

(p  q) is a wff

(r   t) is not a wff

(p   q) is not a wff

((p  q)((p  r)  (s))) is a wff

( (p  q)  ((p  r)  (s)) )

Draw a parse tree.

26

Examples

Passing the exams and the project implies

passing the MSc.

(pass_exams  pass_proj)  pass_MSc

You do not pass the MSc and you do not get a

certificate if you do not pass the exams or you do

not pass the project.

( pass_exams  ¬ pass_proj) 

(¬ pass_MSc   get_certificate)

27

Exercise

Formulate the first two arguments from the

beginning of the notes.

Advertisement for a computing book: If you don’t

use computers you don’t need this book. But you

are a person who uses computers. So you need

this book.

 If you work hard you will succeed. So if you do

not succeed you have not worked hard.

28

Some notes on simplifying

syntax

• To avoid ending up with a large number of

brackets one can drop the outermost

brackets.

Examples:

(p  q) can be written as p  q

((p  q)  r) can be written as (p  q)  r.

29

• “ “ binds more closely than the other

connectives. This can be used to drop some

brackets.

Example

( (p)  q)  t can be written as

( p  q)  t

30

•  and  bind more closely than  and . This

can be used to drop some brackets.

Examples:

( p  q)  t can be written as

 p  q  t.

(p q)  (r  s) can be written as

p  q  r  s.

Binding Strength

of the Connectives

To avoid having to use many brackets, there is

a convention of ordering the connectives.

Also :

• Order of precedence

• Binding priority

31

Binding Strength

of the Connectives

Strongest ¬

Weakest 

32

Binding conventions: Examples

• p  q  r is understood as p  (q  r)

• ¬p  q is understood as (¬p)  q

• pqr is understood as (pq)r

I prefer the first and third bracketed versions.

They are more clear, and having a few

brackets is not much of a burden! Please

don’t write unreadable formulas like

p ¬q → ¬r ↔ ¬¬s ∧ t  ¬u
33

34

Use brackets to remove

ambiguity

Example:
P  Q  R

is ambiguous.

In general

P  (Q  R)

and

(P  Q)  R

are not equivalent (do not have the same meaning).

Binding conventions

So p  q  r

is a problem.

It needs brackets to disambiguate it.

But p ∧ q ∧ r and p ∨ q ∨ r

are fine (to be discussed later).

35

36

Exercise:

Which of the following are wffs?

Assume

p, q, r, sad, happy,

tall, rich, work_hard,

steal, borrow, and possess

are propositional symbols.

37

• rich  happy

• (p  q)  (r  p)

• p  q

• sad  happy

• happy  sad

38

• rich  happy

• rich  (work_hard  steal)

• (steal   borrow)  possess

• (steal  borrow)  possess

• steal  borrow  possess

39

• (pq  r)  (p q)

• p  p

• p p

We will look at

Parse trees

Principle connectives

Subformulas

in the lecture.

40

41

Notes on terminology

•  is a unary operator.

• The other connectives are binary operators.

• X  Y is called the disjunction of X and Y.

• X  Y X and Y are disjuncts.

• X  Y is called the conjunction of X and Y.

• X  Y X and Y are conjuncts.

• X is called the negation of X.

Notes on terminology cntd.

• A → B is called an implication.

A is called the antecedent,

B is called the consequent.

A Literal is a proposition or the negation of a

proposition.

42

Semantics

Provides

• The meaning of the simple (atomic) units

• Rules for putting together the meaning of

the atomic units to form the meaning of the

complex units (sentences).

Semantics specifies under what circumstances

a sentence is true or false.

43

44

T (truth) and

F (falsity)

are known as truth values.

45

Constructing Truth Tables for

the connectives

A  A

T F

F T

46

A B A  B

T T T

T F F

F T F

F F F

47

Example

John is not happy, but he is comfortable.

Represent as  h  c

Four possible cases

48

Example cntd.
h c  h  h c

T T F F

T F F F

F T T T

F F T F

49

A B AB

T T T

T F T

F T T

F F F

50

A B AB

T T T

T F F

F T T

F F T

51

Compare  with 

A B A  B

T T T

T F F

F T F

F F F

A B AB

T T T

T F F

F T T

F F T

52

A B AB

T T T

T F F

F T F

F F T

53

Note

For any wffs A and B, “A  B” is true

exactly when A and B have the same truth

values, i.e. when they are both true or both

false.

54

The truth value of a wff is uniquely

determined by the truth value of its

components.

Example:

The truth table for the wff (p  q)  (r  p)

is as follows:

55

p q r p  q r  p (p  q)  (r  p)

T T T T T T

T T F T T T

T F T T T T

T F F T T T

F T T T F F

F T F T T T

F F T F F F

F F F F T F

56

Exercise:

How many rows will there be in a truth table

for a wff containing n propositional

symbols?

2n

57

Exercise:

Recall we said the two wffs

P  (Q  R) and

(P  Q)  R

in general do not have the same meaning.

Under which interpretation(s) do the truth values of

the two wffs differ?

58

Notes

The connective “” stands for inclusive or, i.e.

p  q is interpreted as true when either
proposition is true or both are.

Often in English when we use “or” we intend
exclusive or, e.g.

• I’ll go shopping or I’ll stay at home.

• We will meet at his house or at the club.

59

Notes cntd.

In this propositional language there is no connective
for exclusive or, but we can still express the
concept, e.g.

(goShopping  stayHome) 

(goShopping  stayHome)

In general “p exor q” can be represented as:

(p  q)  (p  q)

Exercise:

Draw the truth table of the first wff above.

60

A B AB ¬(AB) A exor B

(AB) ¬(AB)

T T T F F

T F T T T

F T T T T

F F F T F

61

Notes cntd.

• Law of excluded middle:

A proposition (and consequently a wff) is either
true or false – there is no middle ground, no
“unknown”.

• So propositional logic is a 2-valued logic.

• There are other logics, including 3-valued ones.

• SQL, for example, implements 3-valued logic,
where comparisons with NULL, including that of
another NULL gives UNKNOWN.

Example NULL Values
Table T of people and their hair colours:

Name Hat Size Hair Colour

Helen NULL Brown

John Medium Red

Tom Large NULL

Select Name

From T

Where Hat Size=Large AND Hair Colour  Brown
62

63

A B A  B

T T T

T F T

F T T

F F F

T U T

U T T

F U U

U F U

U U U

• A proposition (and consequently a wff)
cannot be both true and false.

Exercise:

Draw the truth table for A A.

64

65

A ¬A A  A

T F F

F T F

66

Notes cntd.
• The interpretation of “” may be

unintuitive sometimes.

• The semantics of “” is very simple in

logic.

• A  B is simply the same as A  B.

• In English we use “ if .. then” in many

different ways, and sometimes quite

confusingly.

• Don’t read A  B as “A causes B”.

67

Some definitions

Definition :

A wff which evaluates to true in every interpretation
of its constituent parts is called a tautology.

Example A   A

A  A

The two wffs above represent the Law of excluded
middle.

68

A ¬A A ¬A

T F T

F T T

69

Definition

A wff which evaluates to false in every

interpretation of its constituent parts is

called an inconsistency (contradiction), or

is said to be inconsistent.

Example A  A

70

Definition

A wff which is neither a tautology, nor an

inconsistency is a contingency, or is said to

be contingent.

71

Exercise

For each of the following determine if it is a
tautology, inconsistency or contingency by
drawing the truth table.

a. P  (P  Q)

b. (P  Q)  (P  Q)

c. Q   P  (P  (Q  P))

d. (P  (Q  P))  P

e. (P  Q)  ( P  Q)

f. ((P  Q)  (R  S)  (P  R))  (Q  S)

72

Definition: Equivalence

Two wffs are equivalent iff their truth values

are the same under every interpretation.

A is equivalent to B is represented as

A  B .

“” is the metasymbol for equivalence.

73

Some useful equivalences

Double Negation Rule

A  A

Implication Rule

A B  A  B

74

Some useful equivalences

Commutative Rules

A  B  B  A

A  B  B  A

Associative Rules

(A  B)  C  A  (B  C)

(A  B)  C  A  (B  C)

Some useful equivalences

Idempotence

A ∧ A  A

A ∨ A  A

75

76

Some useful equivalences

Distributive Rules

A  (B  C)  (A  B)  (A  C)

A  (B  C)  (A  B)  (A  C)

De Morgan’s Rules

(A  B)  A  B

(A  B)  A  B

Some useful equivalences

A↔ B 

(A → B) ∧ (B → A)

77

Some useful equivalences

A ∧ B  B if ????

A ∧ B  B if A is a tautology

A  B  B if ????

A  B  B if A is an inconsistency

78

79

Exercise

Show

A B  (A  B)

Example

I get an MSc  I get big salary 

(I get an MSc   I get big salary )

Exercises

Show

A  B  (A  B)  ( A   B)

Show

A  B  ¬A  ¬B

80

Showing A  B  ¬A  ¬B

LHS  (A B)  (B A)

RHS  (A  B)  (¬B ¬A)

 (¬B ¬A)  (A  B) commutativity of 

Compare LHS with RHS:

LHS  (A B)  (B A)

RHS  (¬B ¬A)  (A  B)

81

And both correspondences are an instance of

one equivalence:

X  Y  ¬Y  ¬X

So this equivalence is enough to prove

LHS  RHS.

82

Showing X  Y  ¬Y  ¬X

X  Y 

¬X  Y  implication rule

¬X  ¬¬Y  double negation

¬¬Y  ¬X  commutativity of 

¬Y  ¬X implication rule

83

84

Back to Exercise

For each of the following determine if it is a
tautology, inconsistency or contingency by
drawing the truth table.

a. P  (P  Q)

b. (P  Q)  (P  Q)

c. Q   P  (P  (Q  P))

d. (P  (Q  P))  P

e. (P  Q)  ( P  Q)

f. ((P  Q)  (R  S)  (P  R))  (Q  S)