程序代写代做代考 prolog PowerPoint Presentation

PowerPoint Presentation

Propositional Logic
cntd.

Fariba Sadri

What we have done so far on
Propositional Logic

• Syntax of wffs

• Practice on how to formalise English
sentences in propositional logic

• Truth tables for the semantics of the
connectives ¬, , , , 

• Tautologies, inconsistencies, contingencies

• Equivalences

What we will do now
in this set of slides

• Semantic consequence

• Natural deduction proofs

• Soundness and completeness

Recap Exercise

From 2012-13 examination paper:

a. Define a new connective  for exclusive-or,
using any (combination) of the usual
connectives, , , ¬, , . Thus p  q is to
mean either p or q but not both.

b. Use the new connective  together with any of the other
usual connectives to express the following sentences in
propositional logic, where either … or is to be understood as
exclusive-or. The propositions to be used are given in the text in
Italics inside brackets.

Either John will leave the company (jL) or Mary will (mL).

If John leaves then either the tax department will close
(closeTax), or Peter will be shared between two departments
(pShare) and an administrator will be recruited (recruitA).

If Mary leaves then either an administrator will be recruited or a
secretary will be recruited (recruitS), provided John is shared
between two departments (jShare).

Definition:

Semantic Consequence

Let

S be a set of wffs, and

W be a wff.

If whenever all the wffs in S are true W is also

true, then W is a semantic consequence of

Semantic Consequence cntd.

Denoted as

S ╞ W

“|=” is the semantic turnstile

(a metasymbol).

We also say W is semantically entailed by S.

If W is a tautology then

╞ W.

Exercise

Show the following:

a. A  B ╞ A  B

b. snow, mild  snow ╞ mild

c. Go back to one of the argument at the
beginning of the notes you think is valid
and show that the conclusion of the
argument is semantically entailed by the
premises.

Definitions:Valid, Satisfiable

• Valid is just another name for tautology.

So a formula is valid if it is true in every interpretation.

|= A if A is valid.

• A formula is satisfiable if it is true in at least one

interpretation.

Validity Satisfiability

A |= B ??

valid

unsatisfiable

A |= B and B |= A ??

valid

unsatisfiable

Inference

Example: Given

(pass_exams  pass_projects)  pass_MSc

pass_exams

pass_projects

one can infer (conclude)

pass_MSc.

Example: Given

thursday  logic_lecture

logic_lecture

Can you infer

 thursday ?

The “elections” example

Given

• If there are national elections then either the Tory
party wins or the Labour party wins.

• If the unions do not support the Labour party then
it does not win.

• There are national elections.

Can you infer

If the Tory party does not win then the unions
support the Labour party?

The “elections” example:

Formalisation in logic

Given

Elections Labour_wins  Tory_wins

Unions_support_Labour  Labour_wins

Elections

can you infer

Tory_wins  Unions_support_Labour ?

The “elections” example:

Abbreviation

Premise:

1. E  LT

2. UL

3. E

Conclusion:

T U

You can try to use truth tables to see if the

conclusion is semantically entailed by the

premises.

How many rows?

Too many!

E L T U LT ELT U L UL T TU

T T T T T T F F T F T

……..

Can you give an informal proof of the

conclusion from the premises without using

truth tables?

Performing inferences is very

important in many applications of

logic

Argument: Premise Conclusion
Modelling : Theory Consequences

Programming:

Specification Program

Specification Properties

Prolog:

Program Answers to queries

Rules of Inference

Natural Deduction

(Reasoning purely at the syntactic level)

-elimination (E)

X  Y X  Y

X Y

-introduction (I)

X,Y X,Y

XY YX

-elimination (E)

XY, X XY, Y

Y X

-introduction (I)

X X

XY YX

-elimination (E) (Modus Ponens)

X, XY

-introduction (I)

X assume

XY

-elimination and -introduction (Reductio Ad

Absurdum) (RAA) (Proof by contradiction)

X assume X assume

. .

Y, Y Y, Y

X X

Note: X and Y may be the same wff.

X assume X assume

. .

X, X X, X

X X

-introduction (I)

XY, YX

XY

-elimination (E)

XY XY

XY YX

Note: In all the inference rules X and Y stand for any

wffs. So the following, for example, is an

application of the elimination rule:

Given A(BC) and

(A(BC))  ((AD)  (E  F))

we can infer

(AD)  (E  F)

Example

You may be wondering why we need the I
rule. Here is an example that uses it.

Example:

If there is a shortage of petrol or the tax on
petrol is high then people are angry. There
is a shortage of petrol.

So people are angry.

Premise

1. (SP  HT)  Anger

2. SP

we want to conclude

Anger.

1. (SP  HT)  Anger given

2. SP given

?
Anger

1. (SP  HT)  Anger given

2. SP given

?
Anger  E

1. (SP  HT)  Anger given

2. SP given

?
SP  HT

Anger  E

Proof

1. (SP  HT)  Anger given

2. SP given

3. SP  HT 2,  I

4. Anger 1,3,  E

Example

Derive PQ from PQ.

1. P  Q given

??????

P  Q

Derive PQ from PQ.

1. P  Q given

??????

P  Q I

Example

Derive PQ from PQ.

1. P  Q given

2. P 1, E

3. P  Q 2, I

Example

Derive R from P, Q, (P  Q)R.

1. P given

2. Q given

3. (P  Q)R given

??????

1. P given

2. Q given

3. (P  Q)R given

??????

R E

1. P given

2. Q given

3. (P  Q)R given

4. P  Q 1,2, I

5. R 3,4, E

Example

Derive QR from P, (P  Q)R.

1. P given

2. (P  Q)R given

?????

Q  R

1. P given

2. (P  Q)R given

?????

Q  R I

1. P given

2. (P  Q)R given

Q assume

????

Q  R I

1. P given

2. (P  Q)R given

Q assume

????

R E

6. Q  R 3, 5, I

1. P given

2. (P  Q)R given

3. Q assume

4. P  Q 1, 3, I

5. R 2, 4, E

6. Q  R 3, 5, I

Example

Derive R from PQ, RP.

1. PQ given

2. RP given

????

R

1. PQ given

2. RP given

????

R RAA

1. PQ given

2. RP given

R assume

????

R RAA

1. PQ given

2. RP given

3. P 1, E

4. R assume

5. P 2, 4, E

6.R 3, 4, 5, RAA

├

P ├ W

denotes W is (syntactically) derivable from P.

├ is called the syntactic turnstile. It is a

symbol in the metalanguage.

Example:

In the last example:

PQ, RP ├ R

Definition

A derivation or proof of a wff W in propositional
logic from a given set P of wffs, called premises,
is a finite sequence of wffs such that the last wff is
W and each wff in the sequence is one of the
following:

 a premise, i.e. a wff in P

 an immediate consequence of one or more wffs
preceding it in the sequence, as determined by one
of the inference rules of propositional logic.

 An assumption (that is later discharged by an
application of I or RAA).

Exercise

Show

AB, BC ├ AC

(Transitivity of the implication.)

Exercise

Show

QR ├ (PQ)  (PR)

Exercise

Consider the following derivation:

1. A assume

2. A  A 1, 1, I

3. A 1, 2, E

Seemingly this proves ├A.

Is there anything wrong with it?

If so, what?

Exercise

Show

snow, mild snow ├ mild

It is enough to show:

p, q p ├ q

Some useful derived inference

rules

Double negation elimination (E)

X

Double negation introduction (I)

X___

X

Law of excluded middle

______

X  X

Proof by cases

XY, XZ, YZ

Modus Tollens

XY, Y

X

Contraposition

XY

YX

Dilemma

XY, XY

Exercises

• Give a formal proof for the “elections” example.

• Using the basic inference rules (I, E, I, E,
I, E, I, E, RAA), show that the derived
inference rules hold.

Show ├ (A  B)  (A  B)

1. (A  B) assume

2. (A  B) assume

3. A assume

4. B assume

5. A B 3,4,I

6. B 4,5,1,RAA

7. A  B 6,I

8. A 3,2,7,RAA

9.A  B 8,I

10. A  B 2,9,RAA

11. (A  B)  (A  B) 1,10,I

Be careful when you use

assumptions in a derivation

Notes

• The only inference rules that make use of

assumptions are RAA and I.

• It is very important to be clear about the scope of

assumptions.

• Any assumption made during a derivation will

remain in force, and ultimately count as one of the

premises for the conclusion, unless it gets

discharged before the conclusion is reached in the

proof.

Exercise

Show

├ ((PQ)  (PR))  (QR)

Exercise

Show

P, P ├ Q

Note:

This exercise shows that anything can be
derived from an inconsistent set of
premises.

Notes

 |-W denotes W is derivable from an empty set
of premises.

 Let A, B be wffs.

If A ├ B then ├ A  B.

If ├ A  B then A ├ B.

In general if

P is a set of wffs, and

P’ is a conjunction of the wffs in P, and

W is a wff then P ├ W iff ├ P’ W

Notes cntd.

 Proofs (derivations) are independent of the
“meaning” of the propositional symbol.

So a proof is still valid if the symbols are replaced
consistently.

Example: If we have a proof for

P, Q  P ├ Q

Then the following also holds (replacing P
with snow and Q with mild)

snow, mild snow ├ mild

winter  cold, globalWarming  ¬(winter  cold)

├  globalWarming

Notes cntd.

 For convenience, in a derivation we can use

instances of previous derivations. That is, if we

have previously shown

S ├ W, and we are now attempting a new

proof for another wff, but we

have so far shown

an instance of S, then we can write down the same

instance of W in the derivation without

reproducing its entire proof.

Exercise A

Show

PQ, RS ├ (PR)(QS).

Exercise B

Show

(PQ)  R ├ P  (QR) and

P  (QR) ├ (PQ)  R.

Exercise C

Formalise the following argument and show that it is valid.
You may use the theorems in A and B, above.

In Britain one of the three parties, Tory, Labour or Liberal Democrat, is
in power.

If the Tories are in power the government may support cuts in public
spending.

If Labour is in power the government may support tax increases.

If the Liberal Democrats are in power the government may support
proportional representation.

So in Britain the government may support cuts in public spending or
tax increases or proportional representation.

Soundness and Completeness

Propositional logic is both sound and complete.

Let S be any set of wffs, and let W be a wff.

Soundness means the following:

If S ├ W then S ╞ W.

Completeness means the following:

If S ╞ W then S ├ W.

So in propositional logic we are justified in
switching between syntactic proofs and
semantic consequences.

Example

A  B iff

A ╞ B and B ╞ A iff

A ├ B and B ├ A iff

A ╞ B and B ├ A

It also means in proofs we can use

equivalences.

But note in assessments you need to check the

specifications in the questions carefully.

Exercise

We know

PQ  PQ

PQ ├ PQ

PQ ├ PQ

Also

├ (PQ)  (PQ)

As an exercise show the last using inference rules.

Exercises

Given the equivalence

A  (BC)  (AB) C Show that

(PQ) R, (RS) ├ (P  (QS)).

Using the equivalences

AB  AB and

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

or otherwise show

├ (P  Q)  (Q  P).

Related Posts