Scribd Logo
Upload

Welcome to Scribd!

  • 98 views

    DS Mid 1 Solution

    Uploaded by

    Areeb Saqib Butt
    This document contains a course outline for Discrete Structures at the National University of Computer and Emerging Sciences, Lahore Campus. It includes details like the course name, code, program, semester, duration, date, section, exam type, and number of pages. The document then provides 5 questions assessing skills in translating between propositional logic, predicate logic, and English statements. It also involves determining satisfiability of a propositional logic statement about student enrollment in a class.

    Copyright:

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

    DS Mid 1 Solution

    Uploaded by

    Areeb Saqib Butt
    98 views2 pages
    This document contains a course outline for Discrete Structures at the National University of Computer and Emerging Sciences, Lahore Campus. It includes details like the course name, code, program, semester, duration, date, section, exam type, and number of pages. The document then provides 5 questions assessing skills in translating between propositional logic, predicate logic, and English statements. It also involves determining satisfiability of a propositional logic statement about student enrollment in a class.

    Original Title

    DS mid 1 solution

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains a course outline for Discrete Structures at the National University of Computer and Emerging Sciences, Lahore Campus. It includes details like the course name, code, program, semester, duration, date, section, exam type, and number of pages. The document then provides 5 questions assessing skills in translating between propositional logic, predicate logic, and English statements. It also involves determining satisfiability of a propositional logic statement about student enrollment in a class.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    98 views2 pages

    DS Mid 1 Solution

    Uploaded by

    Areeb Saqib Butt
    This document contains a course outline for Discrete Structures at the National University of Computer and Emerging Sciences, Lahore Campus. It includes details like the course name, code, program, semester, duration, date, section, exam type, and number of pages. The document then provides 5 questions assessing skills in translating between propositional logic, predicate logic, and English statements. It also involves determining satisfiability of a propositional logic statement about student enrollment in a class.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 2

    National University of Computer and Emerging Sciences, Lahore Campus

    Course Course
    Name: Discrete Structures Code: CS-211

    Program: Computer Science Semester: Fall 2018

    Total
    Duration: 60 Minutes Marks: 4+4+4+4+4

    Paper Date: October 2, 2018 Weight 15

    Section: ALL Page(s): 2

    Exam Type: Sessional - I Solution

    QUESTION 1: Translate the following English sentences into propositional logic using the relevant propositions
    and predicates:
    W: Planet has water O: Planet has oxygen N: Planet has nitrogen
    F: Planet has food L: Planet has life

    Operators you are allowed to use: {^, v, , →, ↔}. No other operators or propositional/predicate symbols
    are allowed.
    SOLUTION
    a. Whenever there is oxygen and water on a planet, it has food: O ^ W → F

    b. A planet has neither water nor oxygen but it has nitrogen: W ^O ^ N

    c. A planet that has water can have either nitrogen or food but not both: W → ((N↔F))

    d. It is necessary to have oxygen and water to have life on a planet : L → O ^ W

    QUESTION 2: Translate the following to predicate calculus. You are allowed to use the quantifiers: {, ∀} and
    the connectives: {^, v, , →, ↔}. No other operators or propositional/predicate symbols are allowed.
    A(x): x is an astronaut V(x,y): x visits y S(x): x is a star
    P(x): x is a planet M(x): x is a mathematician

    SOLUTION
    a. Every astronaut is also a mathematician: ∀x (A(x) → M(x))

    b. There are some astronauts who are mathematicians and have visited some planet: x (A(x) ^ M(x) ^ V(x,y) ^
    P(y))

    c. There are some mathematicians who have not visited any star: x ( M(x) ^ ∀y( S(y) → V(x,y) ) )

    d. All astronauts who have visited a star have also visited all planets: ∀x ( A(x) ^ y( (V(x,y) ^ S(y) ) ^ (∀z( P(z)
    → V(x,z) ) )

    QUESTION 3: Translate each expression into proper English statements.


    M(x) = x is Maroon, G(x) = x is green, R(x) = x is Russian.  is the not operator

    SOLUTION

    Department of Computer Science Page 1 of 2


    a. ∀x (M(x)  G(x)): All Maroon are not green
    b. ∃x ( (M(x) ∧ G(x))  R(x)) : There are some Maroon and Green which are not Russian
    c. ∀x ( M(x) ∧ R(x)): Everything is Maroon and Green
    d. ∀x( M(x)  (G(x) ∧ R(x)) ): All Maroon are Green and Russian
    QUESTION 4: There are 4 students: S,M,N,P. If M enrolls in discrete math then N also enrolls in discrete math.
    P and S always stay together, so if one enrolls then the other one also enrolls and if one of them does not enroll
    then the other one also does not enroll. Either S or M but not both enroll in discrete math. N is not enrolled in
    discrete math.

    Translate all the above facts to propositional logic using the set of connectives: {^, v, , →, ↔} and next use the
    concept of satisfiability and rules of inference to determine who is enrolled in discrete math. Truth table, and
    informal reasoning will not be accepted and marks will be given only on the quality of your answer.
    SOLUTION
    The given facts are:
    M→N (1)
    P↔S (2)
     (S↔M) (3)
    N (4)

    using (1) and (4) and apply Modus Tolens


    M (5)

    using (3) using logical identity for biconditional:


    (S → M) ^ (M → S) (6)

    using simplification on (6)


    (M → S) (7)

    Using Modus Ponens on (5) and (7), we conclude


    S (8)

    Using (2) and (8)


    P (9)

    From the above we conclude that M and N are not enrolled (4) and (5)
    and P and S are enrolled in discrete math (8) and (9)

    QUESTION 5: Show that [ p ∧ (p  q) ]  q is a tautology using logical equivalences (and not truth table) .
    SOLUTION
    [ p ∧ (p  q) ]  q
      [ p ∧ (p  q) ] v q (from logical identity of implication)
      [ p ∧ [ p v q ] ] v q (from logical identity of implication)
    [q]vq (apply resolution on (p) and ( p v q) )
    T (negation law)
    Hence proved that the given expression is a tuatology

    Department of Computer Science Page 2 of 2

    You might also like