Scribd Logo
Upload

Welcome to Scribd!

  • 105 views

    DACS 2101 - Discrete Structures: Homework #2 - Fall 2021

    Uploaded by

    Abbas Khan
    This document contains a homework assignment on discrete structures involving Boolean algebra and logic. It includes problems to: 1) Compute truth tables for Boolean functions 2) Find Boolean variable values that satisfy equations 3) Simplify Boolean expressions 4) Find Boolean products and sums that evaluate to specific values 5) Express Boolean functions using only OR and complement operators 6) Find outputs of Boolean circuits 7) Convert between binary, decimal, and hexadecimal number systems.

    Copyright:

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

    DACS 2101 - Discrete Structures: Homework #2 - Fall 2021

    Uploaded by

    Abbas Khan
    105 views3 pages
    This document contains a homework assignment on discrete structures involving Boolean algebra and logic. It includes problems to: 1) Compute truth tables for Boolean functions 2) Find Boolean variable values that satisfy equations 3) Simplify Boolean expressions 4) Find Boolean products and sums that evaluate to specific values 5) Express Boolean functions using only OR and complement operators 6) Find outputs of Boolean circuits 7) Convert between binary, decimal, and hexadecimal number systems.

    Original Title

    DACS 2101_HW_02

    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 homework assignment on discrete structures involving Boolean algebra and logic. It includes problems to: 1) Compute truth tables for Boolean functions 2) Find Boolean variable values that satisfy equations 3) Simplify Boolean expressions 4) Find Boolean products and sums that evaluate to specific values 5) Express Boolean functions using only OR and complement operators 6) Find outputs of Boolean circuits 7) Convert between binary, decimal, and hexadecimal number systems.

    Copyright:

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

    DACS 2101 - Discrete Structures: Homework #2 - Fall 2021

    Uploaded by

    Abbas Khan
    This document contains a homework assignment on discrete structures involving Boolean algebra and logic. It includes problems to: 1) Compute truth tables for Boolean functions 2) Find Boolean variable values that satisfy equations 3) Simplify Boolean expressions 4) Find Boolean products and sums that evaluate to specific values 5) Express Boolean functions using only OR and complement operators 6) Find outputs of Boolean circuits 7) Convert between binary, decimal, and hexadecimal number systems.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 3

    :Name :Student ID

    DACS 2101 - Discrete Structures


    Homework #2 – Fall 2021
    1. Compute the truth table of each of these Boolean functions. [4 pts]
    a) F(x, y, z) = x + yź

    x y z -z y-z x+y-z
    0 0 0 1 0 0
    0 0 1 0 0 0
    0 1 0 1 1 1
    0 1 1 0 0 0
    1 0 0 1 0 1
    1 0 1 0 0 1
    1 1 0 1 1 1
    1 1 1 0 0 1

    b) F (x, y, z) = x́ ý + xyz
    ´

    x y z -x -y -z -x.-y -x.-y.-z -x.-y + -x.-y.-z


    0 0 0 1 1 1 1 1 1
    0 0 1 1 1 0 1 0 1
    0 1 0 1 0 1 0 0 0
    0 1 1 1 0 0 0 0 0
    1 0 0 0 1 1 0 0 0
    1 0 1 0 1 0 0 0 0
    1 1 0 0 0 1 0 0 0
    1 1 1 0 0 0 0 0 0

    2. What values of the Boolean variables x and y satisfy xy


    ´ = x + y? [2 pts]

    -x.-y = x + y is only satisfied if and only if x = y. We can easily see that when x = y =
    0 or when x = y = 1 is when the equation is satisfied.

    3. Simplify these expressions. [2 pts]


    a) x ⊕ 0
    b) x ⊕ 1
    c) x ⊕ x
    d) x ⊕ x́

    4. Find a Boolean product of the Boolean variables x, y, and z, or their complements,


    that has the value 1 if and only if [2 pts]
    a) x = y = 1, z = 0.
    :Name :Student ID

    Since z = 0, then z = 1. The Boolean product is xy-z.

    b) x = y = 0, z = 1.

    Since x = y = 0, then -x = -y = 1. The Boolean product is –x-yz .

    5. Find a Boolean sum containing the Boolean variables x, y, and z, or their


    complements that has the value 0 if and only if [2 pts]
    a) x = z = 1, y = 0.

    Since y = 0, then -y = 1. The Boolean product is x + z + -y.

    b) x = y = z = 0.

    Since x = y = z = 0, then -x = -y = -z = 1. The Boolean product is –x + -y + -z.

    6. Express each of these Boolean functions using ONLY the “or” operator (+) and
    “complement” operator (´) (hint: try taking the complement of the expressions and
    apply De Morgan Law) [7 pts]
    a) xy

    = ((-x + -y) _)

    b) x́yz
    c) x( ý +¿x z)

    7. We have seen that the operators {+, . , ´} are functionally complete. It is easy to
    show that {+, ´} and { . , ´} are two smaller sets of operators that are functionally
    complete (by using the same technique as the previous exercise). In this exercise, we
    will show that the even smaller set {↓} is complete. ↓ is the NOR operator, which
    means x ↓ y = x +´ y.
    a) Express x́ with only x and the ↓ operator. [2 pts]

    x↓x

    b) Express xy with only x, y and the ↓ operator. [3 pts]

    (x ↓x) ↓ (y ↓y)

    c) Conclude that the set {↓} is complete. [3 pts]

    A set is said to be functionally complete if we can derive a set which is


    already functionally complete. Thus, the set {↓} is complete as we are able
    to derive a set which is already functionally complete.

    d) Verify it by expressing x́y+z using only x, y, z and the ↓ operator. [3 pts]

    8. Find the output (Boolean expression) of the two following circuits. [4 pts]
    :Name :Student ID

    = (-x.-y) + (-z + x)

    = (-x.-y-. z). (-x + y + -z)

    9. Fill in the following table of conversion between binary, decimal and hexadecimal.
    Show the operation that you performed for each conversion outside the table. [6 pts]

    Hexadecimal Decimal Binary


    285 645 1010000101
    73D 1853 11100111101
    ABC 2748 101010111100

    You might also like