A « B º (A ® B)&( B ® A) º (A & B) Ú (ØA & ØB) º (ØA Ú B) & (A Ú ØB).

A ® B º ØA Ú B.

Доказательство: с помощью таблиц истинности.

4.1.2 Построение формул

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

Пусть {x_i | iÎI} – некоторое множество логических переменных. Формулой алгебры логики является любая логическая переменная (атомарной формулой) или выражение, построенное из формул с помощью логических операций.

Данное определение задает синтаксис формул, т.е. формальные законы их построения. Приведенные выше таблицы истинности являются интерпретациями логических операций и задают семантику формул (т.е. придают им смысл).

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

Любая формула, кроме элементарной, должна быть заключена в наружные круглые скобки. Однако обилие скобок затрудняет чтение формул, поэтому в алгебре логики приняты некоторые соглашения относительно расстановкискобок: 1) внешние скобки не пишутся; 2) знак конъюнкции можно обозначать точкой или не писать; 3) на множестве {, &, Ú, ®, «, |, ¯, Å } вводится приоритет операций, который определяется посредством транзитивного отношения > «быть сильнее» и отношения эквивалентности ~«быть равносильным». Если все равносильные операции объединить в классы эквивалентности {}, то можно записать: {} > {&, |, ¯} > {Ú} > {®} > {«, Å}.

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

Пример 4.1 ((((a&b)&c)Úd)®((aÚb)&a)) º abc Ú d ® (aÚb)&a, в итоге в формуле осталась только одна пара скобок, которая нужна для того, чтобы дизъюнкция выполнилась прежде конъюнкции. И наоборот, расставим скобки в формуле в соответствии с последовательностью выполнения операций: xÅy«z®uÚv&w¯x|y º ((xÅy)«(z®(uÚ(((v&w)¯x)|y)))).

4.1.3 Булевы функции и формулы

Функцией алгебры логики (ФАЛ) от n переменных x₁, x₂, …, x_n называется функция f:{0,1}ⁿ®{0,1}, т.е. функция, которая произвольному набору
(s₁, …, s_n) нулей и единиц ставит в соответствие значение f(s₁, …, s_n)Î{0,1}.

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

Утверждение Для булевой функции от n аргументов существует 2ⁿ различных наборов аргументов.

Булева функция f(x₁, x₂, …, x_n) называется полностью определенной, если ее значения определены на всех 2ⁿ наборах переменных. В противном случае функция частично определенная.

Функция существенно зависит от переменной x_i, (или переменная x_i – существенная), если $ такой набор значений x₁, x₂, …, x_n , что . В противном случае переменная x_i – несущественная (фиктивная).

x1	x2	f1	f2

Пример 4.2 Пусть две булевы функции заданы таблицей истинности. Для них переменная x₁ существенная, а x₂ – несущественная.

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

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

Пусть даны формулы F(y₁, y₂, …, y_m ), f₁(x₁, x₂, …, x_n ), …, f_m(x₁, x₂, …, x_n ). Тогда подстановкой формул f_i в формулу F называется следующая конструкция: (F| y_i f_i )(x₁, x₂, …, x_n) º F(f₁(x₁, x₂, …, x_n ), …, f_m(x₁, x₂, …, x_n )).

Теорема 4.2 (О подстановке формул)