Логические функции

Существует несколько способов задания логических функций.

1. Словами. Например, для операции значение функции истинно, если хотя бы один из ее аргументов принимает единичное значение.

2. Таблицей истинности. Например,

Функция Y соответствует так называемому мажоритарному элементу "2 из трех". Словами: "Функция истина, если по крайней мере два из трех аргументов равны 1". В таблице конкретный ряд (строка) значений аргументов, например, 0 1 0, называется набором. От табличной формы записи можно перейти к аналитической. Из таблицы видно, что значения функции истинны только для некоторых наборов значений переменных.

а) X ₁ = 0, X ₂ = 1, X ₃ = 1, т. е. для сочетания ;

б) X ₁ = 1, X ₂ = 0, X ₃ = 1, т. е. для сочетания ;

в) X ₁ = 1, X ₂ = 1, X ₃ = 0, т. е. для сочетания ;

г) X ₁ = 1, X ₂ = 1, X ₃ = 1, т. е. для сочетания .

Каждое из произведений переменных, для которых значение функции истинно, называется минтермом, или конституентом единицы, а функцию можно представить в виде суммы минтермов (т. к. каждый минтерм равен 1, то сумма равна 1):

Y = + + + .

Функция представлена в виде дизъюнкции произведений переменных или их отрицаний. Если каждое слагаемое содержит все переменные или их отрицания, то такая форма записи называется совершенной дизъюнктивной нормальной формой (СДНФ).

Совершенно также можно выделить и нулевые значения функции, имеющиеся в таблице: если истинное значение - это Y, то неистинное (нулевое) - это :

а) X ₁ = 0, X ₂ = 0, X ₃ = 0, т. е. для сочетания ;

б) X ₁ = 0, X ₂ = 0, X ₃ = 1, т. е. для сочетания ;

в) X ₁ = 0, X ₂ = 1, X ₃ = 0, т. е. для сочетания ;

г) X ₁ = 1, X ₂ = 0, X ₃ = 0, т. е. для сочетания .

Так как эти сочетания дают 0, то, сложив их, получим тоже 0:

= + + + .

Используя принцип двойственности или правило де Моргана, получим

.

Функция в этом случае задана в виде произведения (конъюнкции) сумм переменных или их отрицаний. Так как в суммы входят все переменные или их отрицания, то такая форма записи называется совершенной конъюнктивной нормальной формой (СКНФ).

Сами же суммы, для которых значение функции неистинно, называют макстермами, или конституентами нуля.