Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    BooleanFunctions QA

    Uploaded by

    ironmanfire121
    The document describes Boolean algebra and Boolean functions. It defines Boolean operations like complement, sum, and product. A Boolean function takes variables that can only be 0 or 1 as inputs and outputs 0 or 1. Boolean expressions can be built from variables and operations. Laws like idempotent, identity, commutative, associative, distributive, and De Morgan's laws are given. Examples show defining, expressing, and proving properties of Boolean functions.

    Copyright:

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

    BooleanFunctions QA

    Uploaded by

    ironmanfire121
    9 views4 pages
    The document describes Boolean algebra and Boolean functions. It defines Boolean operations like complement, sum, and product. A Boolean function takes variables that can only be 0 or 1 as inputs and outputs 0 or 1. Boolean expressions can be built from variables and operations. Laws like idempotent, identity, commutative, associative, distributive, and De Morgan's laws are given. Examples show defining, expressing, and proving properties of Boolean functions.

    Original Title

    BooleanFunctions-QA

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes Boolean algebra and Boolean functions. It defines Boolean operations like complement, sum, and product. A Boolean function takes variables that can only be 0 or 1 as inputs and outputs 0 or 1. Boolean expressions can be built from variables and operations. Laws like idempotent, identity, commutative, associative, distributive, and De Morgan's laws are given. Examples show defining, expressing, and proving properties of Boolean functions.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    9 views4 pages

    BooleanFunctions QA

    Uploaded by

    ironmanfire121
    The document describes Boolean algebra and Boolean functions. It defines Boolean operations like complement, sum, and product. A Boolean function takes variables that can only be 0 or 1 as inputs and outputs 0 or 1. Boolean expressions can be built from variables and operations. Laws like idempotent, identity, commutative, associative, distributive, and De Morgan's laws are given. Examples show defining, expressing, and proving properties of Boolean functions.

    Copyright:

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

    ICS 241: Discrete Mathematics II (Spring 2015)

    12.1 Boolean Functions


    Boolean algebra provides the operations and rules for working with the set {0, 1}.

    Boolean Complement

    • x ≡ ¬x

    • 0=1

    • 1=0

    Boolean Sum

    • x+y ≡x∨y

    • 0+0=0

    • 0+1=1

    • 1+0=1

    • 1+1=1

    Boolean Product

    • x·y ≡x∧y

    • 0·0=0

    • 0·1=0

    • 1·0=0

    • 1·1=1

    Boolean Functions

    Let B = {0, 1}. Then B n = {(x1 , x2 , . . . , xn )|xi ∈ B for 1 ≤ i ≤ n} is the set of all possible
    n-tuples of 0s and 1s. The variable x is called a Boolean variable if it assumes values only from
    B, that is, if its only possible values are 0 and 1. A function from B n to B is called a Boolean
    function of degree n.

    Boolean Expressions

    The Boolean expressions in the variables, x1 , x2 , . . . , xn are defined recursively as 0, 1, x1 , x2 , . . . , xn


    are Boolean expressions; if E1 and E2 are Boolean expressions, then E 1 , (E1 E2 ), and (E1 + E2 )
    are Boolean expressions. Each Boolean expression represents a Boolean function.

    1
    ICS 241: Discrete Mathematics II (Spring 2015)

    Boolean Identities
    Identity Name
    x=x Law of the double complement
    x+x=x
    Idempotent laws
    x·x=x
    x+0=x
    Identity laws
    x·1=x
    x+1=1
    Domination laws
    x·0=0
    x+y =y+x
    Commutative laws
    xy = yx
    x + (y + z) = (x + y) + z
    Associative laws
    x(yz) = (xy)z
    x + yz = (x + y)(x + z)
    Distributive laws
    x(y + z) = xy + xz
    (xy) = x + y
    De Morgan’s laws
    (x + y) = xy
    x+x=1 Unit property
    xx = 0 Zero property

    Duality

    The dual of a Boolean expression is obtained by interchanging Boolean sums and Boolean products
    and interchanging 0s and 1s.

    Abstract Definition of Boolean Algebra

    A general Boolean algebra is a set B with elements 0 and 1, two binary operators ∧ and ∨, and a
    unary operator ¬ that satisfies the following laws for all x, y, and z in B:

    • Identity laws:

    – x∨0=x
    – x∧1=x

    • Complement laws:

    – x ∨ ¬x = 1
    – x ∧ ¬x = 0

    • Associative laws:

    – (x ∨ y) ∨ z = x ∨ (y ∨ z)
    – (x ∧ y) ∧ z = x ∧ (y ∧ z)

    • Commutative laws:

    2
    ICS 241: Discrete Mathematics II (Spring 2015)

    – x∨y =y∨x
    – x∧y =y∧x

    • Distributive laws:

    – x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
    – x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

    12.1 pg. 818 # 5

    Use a table to express the values of each of these Boolean functions.

    a) F (x, y, z) = xy
    x y z x xy
    1 1 1 0 0
    1 1 0 0 0
    1 0 1 0 0
    1 0 0 0 0
    0 1 1 1 1
    0 1 0 1 1
    0 0 1 1 0
    0 0 0 1 0

    b) F (x, y, z) = x + yz
    x y z yz x + yz
    1 1 1 1 1
    1 1 0 0 1
    1 0 1 0 1
    1 0 0 0 1
    0 1 1 1 1
    0 1 0 0 0
    0 0 1 0 0
    0 0 0 0 0

    c) F (x, y, z) = xy + (xyz)
    x y z y xy xyz (xyz) xy + (xyz)
    1 1 1 0 0 1 0 0
    1 1 0 0 0 0 1 1
    1 0 1 1 1 0 1 1
    1 0 0 1 1 0 1 1
    0 1 1 0 0 0 1 1
    0 1 0 0 0 0 1 1
    0 0 1 1 0 0 1 1
    0 0 0 1 0 0 1 1

    3
    ICS 241: Discrete Mathematics II (Spring 2015)

    d) F (x, y, z) = x(yz + yz)


    x y z y z yz yz yz + yz x(yz + yz)
    1 1 1 0 0 1 0 1 1
    1 1 0 0 1 0 0 0 0
    1 0 1 1 0 0 0 0 0
    1 0 0 1 1 0 1 1 1
    0 1 1 0 0 1 0 1 0
    0 1 0 0 1 0 0 0 0
    0 0 1 1 0 0 0 0 0
    0 0 0 1 1 0 1 1 0

    12.1 pg. 818 # 9

    What values of the Boolean variables x and y satisfy xy = x + y?

    xy = 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.

    12.1 pg. 818 # 11

    Prove the absorption law x + xy = x using the other laws.

    x + xy
    = x · 1 + xy by identity law
    = x(1 + y) by distributive law
    = x(y + 1) by commutative law
    = x · 1 by domination law
    = x by identity law

    12.1 pg. 818 # 13

    Show that xy + yz + xz = xy + yz + xz.

    Simply create a table and list the values.

    x y z x y z xy yz xz xy yz xz xy + yz + xz xy + yz + xz
    1 1 1 0 0 0 0 0 0 0 0 0 0 0
    1 1 0 0 0 1 0 1 0 0 0 1 1 1
    1 0 1 0 1 0 1 0 0 0 1 0 1 1
    1 0 0 0 1 1 1 0 0 0 0 1 1 1
    0 1 1 1 0 0 0 0 1 1 0 0 1 1
    0 1 0 1 0 1 0 1 0 1 0 0 1 1
    0 0 1 1 1 0 0 0 1 0 1 0 1 1
    0 0 0 1 1 1 0 0 0 0 0 0 0 0

    You might also like