Суперпозиция и формулы алгебры логики
f( x2,x3,x4 ) = ( 1,0,1,0,0,1,0,1 ).
Определение. Формулой алгебры логики называется выражение, описывающее суперпозицию логических функций.
Например, формула
F = f3{ f1( x3,x1 ), f2[ x1, f3( x1,x2 ) ] }. (1.1)
описывает суперпозицию функций f1, f2 и f3.
Формулы, входящие в основную формулу, называются подформулами. Обычно формулы, как правило, имеют более привычный вид, при котором знаки логических операций стоят между переменными. Такая запись формулы называется инфиксной.
Например, пусть f1 –дизъюнкция, f2 – конъюнкция, а f3 – сложение по mod 2. Тогда формула (1.1) в инфиксной записи будет иметь вид:
F = ( x3
x1 ) 
( x1 & ( x1x2 )
). (1.2)
Любая формула задает способ ее вычисления, если известно, как вычислить вхо-дящие в нее функции.
Пример. Вычислить значение выражения (1.2) при х1 = х2 = 1, х3 = 0.
Вычисления будем производить в следующем порядке:
х3 х1 = 0 1
= 1 , x1
x2 = 1 1 = 0,