1.2. Суперпозиция и формулы алгебры логики

Определение. Суперпозицией функций f₁, … , f_m называется функция f,

полученная с помощью подстановок этих функций друг в друга и переименования переменных.

Пример. Пусть даны функции f₁( x₁, x₂ ) = ( 0, 1, 1, 0 ) и f₂( x₁, x₂ ) = (1, 0, 1, 0).

Тогда функция f( x₂, x₃, x₄ ) = f₁[ x₂, f₂(x₃, x₄) ] будет суперпозицией функций f₁ и f₂.

Табличное задание функций f₁ и f₂ представлено табл. 1.7. С помощью данной таблицы найдем табличное задание искомой функции f( x₂, x₃, x₄ ), которое представле-но в табл. 1.8.

Таблица 1.7

Таблица 1.8

Для построения табл. 1.8 вначале, пользуясь табл. 1.7, строим функцию f₂(x₃, x₄) для всех строк табл. 1.8. При этом роль переменных х₁, х₂ табл. 1.7 играют переменные х₃, х₄ соответственно.

Затем, по табл. 1.7 для f₁, строим функцию f₁[ x₂, f₂(x₃, x₄) ].При этом роль переменных х₁, х₂ табл. 1.7 играют переменная х₂ и f₂( x₃,x₄ ) соответственно.

Полученная функция и будет искомой. Ее векторный вид:

f( x₂,x₃,x₄ ) = ( 1,0,1,0,0,1,0,1 ).

Определение. Формулой алгебры логики называется выражение, описывающее суперпозицию логических функций.

Например, формула

F = f₃{ f₁( x₃,x₁ ), f₂[ x₁, f₃( x₁,x₂ ) ] }. (1.1)

описывает суперпозицию функций f₁, f₂ и f₃.

Формулы, входящие в основную формулу, называются подформулами. Обычно формулы, как правило, имеют более привычный вид, при котором знаки логических операций стоят между переменными. Такая запись формулы называется инфиксной.

Например, пусть f₁ –дизъюнкция, f₂ – конъюнкция, а f₃ – сложение по mod 2. Тогда формула (1.1) в инфиксной записи будет иметь вид:

F = ( x₃ x₁ ) ( x₁ & ( x₁ x₂ ) ). (1.2)

Любая формула задает способ ее вычисления, если известно, как вычислить вхо-дящие в нее функции.

Пример. Вычислить значение выражения (1.2) при х₁ = х₂ = 1, х₃ = 0.

Вычисления будем производить в следующем порядке:

х₃ х₁ = 0 1 = 1 , x₁ x₂ = 1 1 = 0,

x₁ & ( x₁ x₂ ) = 1 & 0 = 0, F = 1 0 = 1.

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

Пример. Составить таблицу задания функции f( x₁,x₂ ), которая задана формулой:

f( x₁,x₂ ) = ( ( x₁ & x₂ ) x₁) x₂.

Искомая функция строится за три шага и представлена в табл. 1.9. Сначала строится подформула х₁ & x₂, затем подформула ( х₁ & x₂) x₁, а затем и сама функция.

Таблица 1.9

Пример. Составить таблицу задания функции

f( x,y,z ) = ( x → y ) → ( ( x y ) → ( x z ) ).

Табл. 1.10 показывает процесс построения данной функции. Последний столбец этой таблицы является значениями искомой функции.

Таблица 1.10

Определение. Эквивалентными (равносильными) называются формулы, представляющие одну и ту же функцию.

Эквивалентными формулами будут формулы в выражениях (1.3). В отличие от

табличного задания функции представление функции формулой не единственно.

Например, функцию Шеффера, функцию стрелка Пирса и можно представить следующими эквивалентными формулами:

х₁ / x₂ ~ ~ ,

x₁ ↓ x₂ ~ & ~ , (1.3)

Справедливость этих формул доказывает табл.1.11.

Таблица 1.11

Пример. Проверить равносильность функций:

f₁ = x₁ ( x₂ ~ x₃ ) и f₂ = ( x₁ x₂ ) ~ ( x₁ x₃ ).

Для проверки этого составим следующую таблицу.

Таблица 1.12

Из табл. 1.12 видно, что 5 и 8 столбцы одинаковы. Это означает эквивалентность данных функций, т.е . f₁ ~ f₂.

Замечание. В формулах, у которых внешняя функция является конъюнкцией, или дизъюнкцией, или сложением по mod 2, или импликацией, или функцией Шеффера, внешние скобки не пишутся.

Например, пишут х₁ → х₂ вместо ( х₁ → х₂ ).

Не пишутся также скобки у выражения, над которым стоит знак отрицания.

Например, пишут вместо ( ).