Учебное пособие: Математические и логические основы информатики

S3 = {f15(x,y)} - отрицание конъюнкции (штрих Шеффера).

S4 = {f9(x,y)} - отрицание дизъюнкции (стрелка Пирса).

S5 = {φ3(x), f14(x,y)} - отрицание, импликация.

В последующем мы увидим, что с точки зрения проектирования вычислительных устройств особый интерес представляют S3 и S4.

Общий критерий функциональной полноты системы булевских функций, выражающий необходимые и достаточные условия, носит название критерия Поста-Яблонского.[6] Его изложение выходит, к сожалению, за рамки настоящего пособия.

Применение аппарата булевских функций к анализу и синтезу комбинационных схем

Рассмотрим так называемые схемы из функциональных элементов (комбинационные схемы), вычисляющие (реализующие) булевские функции.

Под функциональным элементом будем понимать некоторое устройство (внутренняя структура которого нас не интересует[7] ), обладающее такими свойствами:

1) оно имеет n³1 упорядоченных входов и один выход;

2) на входы этого устройства могут подаваться сигналы, принимающие два значения, которые будем обозначать через 0 и 1;

3) при каждом наборе сигналов на входах устройство выдает один из сигналов (0 или 1) в тот же момент, в который поступили сигналы на входе;

4) набор сигналов на входах однозначно определяет сигнал на выходе, то есть, если в различные моменты времени на входы поступает одна и та же комбинация сигналов, то в эти моменты на выходе будет один и тот же сигнал.

С каждым функциональным элементом с n входами сопоставим булевскую функцию от n переменных f(x1,x2,…,xn), определяемую следующим образом: входу с номером i(i = 1, 2, … , n) ставится в соответствие переменная xi и с каждым набором <a1, a2, … , ai, …, an> этих переменных (aiÎ{0,1}) сопоставляется числ?