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

Если в логическую функцию вместо переменных подставить некоторые булевые функции, то в результате получается новая булевая функция, которая называется суперпозицией подставляемых функций (сложная функция). С помощью суперпозиции можно получать более сложные функции, которые могут зависить от любого числа переменных. Запись булевых функций через элементарные булевые функции будем называть формулой реализующей данную функцию.

Пример: Пусть задана элементарная булева функция xvy. Подставим вместо x функцию x1↓x2. Получаем функцию трех переменных (x1↓x2)vy. Если вместо переменной y подставить, например, x3⊕x4, то получаем новую функцию от четырех переменных: (x1↓x2)v(x3⊕x4). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.

Забегая вперед, отметим, что любая булева функция может быть представлена как суперпозиция элементарных функций. Для более компактной записи сложных функций введем следующие соглашения:

1) внешние скобки опускаются;

2) сначала производятся операции в скобках;

3) считается, что приоритет связок убывает в следующем порядке: ¬, &, v, →, ∼. Для равносильных связок и оставшихся связок {⊕,|,↓}, следует пока расставлять скобки.

Примеры: В формуле x·yvz скобки расставляются следующим образом: ((x·y)vz), т.к. операция & сильнее операции v согласно нашему соглашению.

1. В формуле xvy∼z→x скобки расставляются следующим образом: ((xvy)∼(z→x)).

2. В формуле (x⊕y)∼z→xyv¬z скобки расставляются следующим образом: ((x⊕y)∼(z→((xy)v(¬z)))).

3. Формула x→y→z, следуя нашему соглашению, записана не корректно, т.к. расстановка скобок приводит к двум разным функциям: ((x→y)→z) и (x→(y→z)).