Boolean function and disjunctive normal form. Let x 1 , x 2 , ..., x n be a sequence of statement variables. Then any compound statement of these variables will be called a Boolean polynomial or Boolean function . p ( x 1 , x 2 , ..., x n ) - Boolean polynomial of variables x 1 , x 2 , ..., x n . 0 ( x 1 , x 2 , ..., x n ) = 0 and 1 ( x 1 , x 2 , ..., x n ) = 1 - special Boolean polynomials. If B = { 0 , 1 } , then p : B × B × ... × B −→ B . Examples of Boolean functions p 1 ( x ) = x ; p 2 ( x, y ) = x ∧ y ; p 3 ( x, y, z ) = y ′ ∧ ( x ∨ z ′ ) ; p 4 ( x, y, z ) = ( x ∧ y ∧ z ) ∨ ( z ∨ z ′ ) ; p 5 ( x, y, z ) = x ∨ y . x ′ denotes ∼ x (negation of x ). The most convenient way to describe a Boolean function is with its truth table, which is a list of all the values of the function. Example p ( x, y, z ) = y ′ ∧ ( x ∨ z )) x y z y ′ x ∨ z y ′ ∧ ( x ∨ z )) 1 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 So, for example we have: p (1 , 0 , 0) = 1 ; p (0 , 1 , 1) = 0 . Logic Having a truth table with 2 n rows, we would like to be able to find a Boolean function of n variables, truth table of which is a given table. Example Find a Boolean function p ( x, y, z ) , truth table of which has the form x y z p ( x, y, z ) 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 Logic First we locate each row that ends with 1. 2 For each of these rows we create a term of the form e 1 ∧ e 2 ∧ e 3 where e 1 = x if the entry of x is 1 and e 1 = x ′ if the entry of x is 0. Similarly, e 2 = y if the entry of y is 1 and e 2 = y ′ if the entry of y is 0. And similarly for e 3 . So, we have x ∧ y ∧ z ; x ∧ y ′ ∧ z ; x ′ ∧ y ∧ z ; x ′ ∧ y ′ ∧ z ′ . 3 Finally, we ”or” these expressions together to get the Boolean function p ( x, y, z ) = ( x ∧ y ∧ z ) ∨ ( x ∧ y ′ ∧ z ) ∨ ( x ′ ∧ y ∧ z ) ∨ ( x ′ ∧ y ′ ∧ z ′ ) . This is also the way to present a given Boolean function in disjunctive normal form . A Boolean function p ( x 1 , x 2 , ..., x n ) is said to be in disjunctive
... zobacz całą notatkę
Komentarze użytkowników (0)