Условие:
Наборы значений трех аргументов X, Y и Z булевой функции f упорядочены лексикографически. Ее значения задаются следующей последовательностью 8 нулей и единиц: f=(1011 0011).
Какая из следующих формул является совершенной конъюнктивной нормальной формой, задающей эту функцию
(X ∨ Y ∨ ≠g Z) ∧(≠g X ∨ Y)
(X ∨ ≠g Y ∨ Z) ∧(≠g X ∨ Y ∨ ≠g Z) ∧(≠g X ∨ ≠g Y ∨ Z)
(X ∨ ≠g Y ∨ Z) ∧(≠g X ∨ ≠g Y ∨ ≠g Z) ∧(≠g X ∨ ≠g Y ∨ Z)
(X ∨ Y ∨ ≠g Z) ∧(≠g X ∨ Y ∨ Z) ∧(≠g X ∨ Y ∨ ≠g Z)
(X ∧ Y ∧ ≠g Z) ∨(≠g X ∧ Y ∧ Z) ∨(≠g X ∧ Y ∧ ≠g Z)
Решение:
Для функции f от трех переменных X, Y, Z нам дано значение f=(1011 0011) при упорядочивании значений (X, Y, Z) в лексикографическом порядке, т.е. для наборов значений: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1). Шаг 1. Расставим значения функции согласно последовательности. Заданная последовательность f = 1 0 1 1 0 0 1 1 означает: (0,0,0) → 1 (0,0,1) → 0 (0,1,0) → 1 (0,1,1) → 1 (1,0,0) → 0 ...