Scribd Logo
Upload

Welcome to Scribd!

  • 50 views

    Logic in Computer Science: BITS Pilani

    Uploaded by

    Pranjal Gupta

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Logic in Computer Science: BITS Pilani

    Uploaded by

    Pranjal Gupta
    50 views12 pages

    Original Title

    Introduction_1_sep_17.pptx

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    50 views12 pages

    Logic in Computer Science: BITS Pilani

    Uploaded by

    Pranjal Gupta

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 12

    Logic in Computer Science

    Prof. Tathagata Ray


    Associate Professor, BITS Pilani, Hyderabad Campus
    rayt@hyderabad.bits-pilani.ac.in
    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