Формулы. Реализация функций формулами.

Булевы формулы строятся исходя из более простых (элементарных) формул. Р2 - множество всех булевых функций.

Р2(n) — множество всех булевых функций от n переменных. Пусть DР2

1)Для любой fD f(x1,...xn)- формула над множеством D.

2)Если f0D и f0=f0(x1,...xn), A1,...An – то или формулы над множеством D содержат переменные (x1,...xn), не обязательно все, или каждая из них является одной из этих переменных, то результат подстановки A1,...An в f0 также будет формулой над D.

Каждой формуле U в множестве D будем сопоставлять булеву функцию, о которой будем говорить, что она реализуется данной формулой. При этом будем полагать, что если формула U реализует функцию f, то она так же реализует и любую равную ей функцию.

Тождественные функции являются формулами над любым множеством функций.

Ф-ция реализуется формулой, вообще говоря, не единственным образом. Если некоторая ф-ция f реализуется ф-лой над множ ф-ции D, то ф-цию f называют суперпозицией функций множ D. Если ф-ция f-суперпозиция ф-ции множ D, то в соответствии с определением ф-лы, она может быть построена с ф-ции множ D.

Процедура построения конкретной ф-лы, реализующей ф-ции, назыв. строением этой ф-лы.

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