Основы дискретной математики

Упражнение 1:

Номер 1

 Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1100 0111).
Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?

Ответ:

(1) (¬X ∨ Y ∨ Z) ∧ (X ∨ Y ∨ ¬ Z) ∧ (¬ X ∨ ¬Y ∨ Z)

(2) (X ∨ ¬Y) ∧ (¬X ∨ Y ∨ Z)

(3) (¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ ¬Z) ∧ (X ∨ Y ∨ Z)

(4) (¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ Z) ∧ (X ∨ ¬Y ∨¬ Z)

(5) (¬X ∧ ¬Y ∧¬Z) ∨ (X ∧ Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ Z)

Номер 2

 Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1101 1100).
Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?

Ответ:

(1) (X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)

(2) (X ∨ ¬Y∨ Z) ∧ (¬X ∨ ¬Y)

(3) (X ∨ ¬Y ∨ Z) ∧ (¬X ∨¬Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)

(4) (¬X ∨ Y ∨ Z) ∧ (X ∨¬Y ∨ Z) ∧ (X ∨ ¬Y ∨¬ Z)

(5) (¬X ∧ ¬Y ∧¬Z) ∨ (X ∧ ¬Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z)

Номер 3

 Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1011 0011).
Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию?

Ответ:

(1) (X ∨ ¬Y ∨ Z) ∧ (¬X ∨ Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)

(2) (X ∨ Y∨ ¬Z) ∧ (¬X ∨ Y)

(3) (X ∨ ¬Y ∨ Z) ∧ (¬X ∨¬Y ∨ ¬Z) ∧ (¬X ∨ ¬Y ∨ Z)

(4) (X ∧ Y ∧¬Z) ∨ (¬X ∧ Y ∧ Z) ∨ (¬X ∧ Y ∧ ¬Z)

(5) (X ∨ Y ∨ ¬Z) ∧ (¬X ∨Y ∨ Z) ∧ (¬X ∨ Y ∨¬ Z)

Упражнение 2:

Номер 1

 Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (x ∨ y) → (x ∧¬y ∧ z)

Ответ:

(1) (¬x ∨¬y) ∧ (¬x ∨ z)

(2) ¬y ∧ (¬x ∨ z)

(3) (x ∨ y ∨ z) ∧ (¬y ∨ z)

(4) ¬y ∧ (x∨ z)

(5) ¬y ∧ (¬x ∨¬y)

Номер 2

 Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: ¬ (¬x → (y + z))

Ответ:

(1) (¬x ∨¬y) ∧ (¬x ∨ z)

(2) ¬y ∧ (¬x ∨ z) ∧ (¬x ∨ y ∨ z)

(3) (x ∨ ¬y ∨¬z) ∧ (y ∨ z)

(4) ¬x ∧ ¬y ∧ (x∨ z)

(5) ¬x ∧ (¬y ∨ ¬z) ∧ (y ∨ ¬z)

Номер 3

 Какая из следующих конъюнктивных нормальных форм эквивалентна следующей формуле: (¬x+y) → (y ∧ z)

Ответ:

(1) (x ∨¬y) ∧ (¬x ∨¬y∨ z)

(2) y ∧ (¬x ∨ z) ∧ (x ∨ y ∨ z)

(3) (x ∨ y) ∧ (¬x ∨¬y∨ z)

(4) x ∧ ¬y ∧ (x∨ z)

(5) (x ∨ y) ∧ (¬y ∨ ¬z)

Упражнение 3:

Номер 1

 Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0011 1011).

I ) ¬X ∧ Y ∧ Z , II) X ∧ ¬Z, III) Y ∧ ¬Z, IV) Y, V) X ∧ ¬Y ∧ ¬Z

Ответ:

(1) I и III

(2) только IV

(3) только II

(4) II и IV

(5) II, IV и V

(6) II , III , IV и V

(7) I и V

Номер 2

 Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1100 1101).

I ) ¬ Y ∧ Z , II) ¬X, III) X ∧ Y ∧ Z, IV) ¬Y, V) X ∧ Z

Ответ:

(1) I и III

(2) только IV

(3) только V

(4) II, IV и V

(5) II и IV

(6) IV и V

(7) I и V

Номер 3

 Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1011 1010).

I ) ¬ X∧Y ∧ Z , II) ¬Z, III) ¬ X∧Y , IV) ¬Y, V) X ∧ ¬Z

Ответ:

(1) I и III

(2) только IV

(3) только V

(4) II, IV и V

(5) II иIII

(6) III , IV и V

(7) I и V

Упражнение 4:

Номер 1

 Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле
¬ (X → ( ¬Y → (X ∧ ¬ Z))) ∧ (Z ∨ ¬ (X ∧ Y))

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

Номер 2

 Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле
((X ∧ Y) → ¬ Z) ∧ (¬ X → ¬ Y)

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

Номер 3

 Сколько элементарных конъюнкций входит в сокращенную ДНФ, эквивалентную формуле
((¬ X ∧ ¬ Y) → (¬ Z ∨ (¬ X → ( Y ∧ Z)) ))

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

Упражнение 5:

Номер 1

 Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f= (0001 0111).

I) X*Y, II) X, III) Y, IV) X*Z, V) X*Y*Z, VI) Y*Z

Ответ:

(1) только I и III

(2) только IV и VI

(3) I, II и V

(4) II, IV и V

(5) I, IV и VI

(6) III , IV и V

(7) только I и V

Номер 2

 Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f= (0001 0101).

Ответ:

(1) X*Y

(2) X*Z

(3) Y

(4) Z

(5) X*Y*Z

(6) Y*Z

Номер 3

 Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(0001 0111).

Ответ:

(1) X*Y

(2) X

(3) Y

(4) X*Z

(5) X*Y*Z

(6) Z

Упражнение 6:

Номер 1

 Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((( Y ∧ Z) → ¬ (X ∨ Z)) ∧ ¬ (¬ Y∧ Z∧X))
и укажите, сколько в нем слагаемых.

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

Номер 2

 Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле (¬( ( X→Y) ∨ ¬(Y → X)) ∧ Z)
и укажите, сколько в нем слагаемых.

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

Номер 3

 Используя эквивалентные преобразования, постройте многочлен Жегалкина, эквивалентный формуле ((X ∨Y∨ Z) ∧ (X ∨ (Y→ Z))) ∧ (X ∨¬ Y∨ ¬ Z) 
и укажите, сколько в нем слагаемых.

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

Основы дискретной математики - тест 4