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

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

Пример 1.3.1. Пусть задана элементарная булева функция x˅y. Подставим вместо x функцию x₁↓x₂. Получаем функцию трех переменных (x₁↓x₂)˅y. Если вместо переменной y подставить, например, x₃⊕x₄, то получаем новую функцию от четырех переменных: (x₁↓x₂)˅(x₃⊕x₄). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.

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

    Для более компактной записи сложных функций введем следующие соглашения: 1) внешние скобки опускаются; 2) сначала производятся операции в скобках; 3) считается, что приоритет связок убывает в следующем порядке: (инверсия), ˄ или , ˅ или +, →, ~. Для равносильных связок и оставшихся связок ⊕, |, ↓, следует пока расставлять скобки.

Пример 1.3.2. В формуле x˄y˅z скобки расставляются следующим образом: ((x˄y)˅z), т.к. согласно нашему соглашению операция ˄ имеет более высокий приоритет, чем операция ˅.

         В формуле x˅y~z→x скобки расставляются следующим образом: ((x˅y)~(z→x))

            В формуле (x⊕y)~z→x˄y˅z скобки расставляются следующим образом: ((x⊕y)~(z→((x˄y)˅(z)))).

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