Scribd
Upload
78 views

Logic in Computer Science: BITS Pilani

Uploaded by

Pranjal Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
78 views

Logic in Computer Science: BITS Pilani

Uploaded by

Pranjal Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 12

Logic in Computer Science

Prof. Tathagata Ray


Associate Professor, BITS Pilani, Hyderabad Campus
[email protected]
BITS Pilani
Hyderabad Campus
Soundness

Theorem (Soundness) Let 1 , 2 , , and be


propositional logic formulas. If 1 , 2 , , is valid,
then 1 , 2 , , holds.

BITS Pilani, Hyderabad Campus


Proof

We have a proof for 1 , 2 , , .

Induction is on the length of the proof

Length of proof is just the number of lines involved.

: For all sequents 1 , 2 , , which have a


proof of length , its is the case that 1 , 2 , ,
holds.

BITS Pilani, Hyderabad Campus


Proof

Assume ( ) for each < and we try to prove .

Base Case: = 1 i.e. one line proof.

If the proof is of one line then it must be of the form.


1. premise

Since all other rules involve more than one line.


This means = 1 and 1 and equal i.e we are
dealing with sequent .
Then definitely .

BITS Pilani, Hyderabad Campus


Inductive Step

1. 1 premise
2. 2 premise
.
.
n. premise
.
.
.
k. justification
This part depends on the last rule applied

BITS Pilani, Hyderabad Campus


Last rule

Case I: Let suppose that the last rule is .


Then is of the form 1 2 . And the justification in line
refers to two lines further up which have 1 and 2 as
their conclusions. Let these lines be 1 and 2
respectively.
Thus we have a proof of 1 , 2 , , 1 and
1 , 2 , , 2 with length less than . Hence by
inductive hypothesis 1 , 2 , , 1 and
1 , 2 , , 2 .
Hence 1 , 2 , , 1 2 holds as well.

BITS Pilani, Hyderabad Campus


Next

Case II: Let suppose that the last rule is .


Then we must have proved , assumed or given as premise
some formula 1 2 in some line < .
Thus we have a shorter proof of the sequent 1 , 2 , ,
1 2 within that proof.
Similarly we obtain proofs of 1 , 2 , , , 1 and
1 , 2 , , , 2 , from the case analysis of .
Hence by inductive hypothesis 1 , 2 , , 1
2 , 1 , 2 , , , 1 and 1 , 2 , , , 2 .
Together 1 , 2 , , holds as well.

BITS Pilani, Hyderabad Campus


Completeness

Theorem (Completeness) Let 1 , 2 , , and be


propositional logic formulas. If 1 , 2 , , holds,
then 1 , 2 , , is valid.

BITS Pilani, Hyderabad Campus


Step 1 of Proof

Assuming 1 , 2 , , , we show that first 1


(2 (3 ( )). . ) holds.

Definition: A formula of propositional logic is called a


tautology iff it evaluates to True under all valuations i.e.
iff .

Example: Prove that ( ) is a tautology.

BITS Pilani, Hyderabad Campus


Step 1

Suppose 1 , 2 , , holds then let us verify that 1


(2 (3 ( )). . ) is indeed tautology.

It can evaluate to false only if all 1 , 2 , , evaluates to


True and but that will contradict 1 , 2 , , .
Hence 1 (2 (3 ( )). . )

BITS Pilani, Hyderabad Campus


Step 2

We want to prove the following theorem


Theorem: If holds, then is valid. In other words if
is tautology then is a theorem.

Using this fact and step 1 we can claim.


1 (2 (3 ( )). . ) is valid.

BITS Pilani, Hyderabad Campus


Step 3

Take the proof of


1 (2 (3 ( )). . ) and augment its proof
by introducing 1 , 2 , , as premises. Then apply
times on each of these premises (starting with 1 ,
continuing with 2 etc). Thus we arrive at conclusion
which gives us a proof for the sequent 1 , 2 , , .

BITS Pilani, Hyderabad Campus

You might also like