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

A ® B º ØA Ú B.

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

Дадим определение еще нескольким логическим операциям.

Штрих Шеффера (антиконъюнкция): по определению (a|b) º (a & b).

Стрелка Пирса (антидизъюнкция): (a ¯ b), по определению (a ¯ b) º (a Ú b).

Кольцевая сумма (сложение по модулю 2): по определению (a Å b)º(a «b).

По определению таблицы истинности для этих трех операций имеют вид:

A	B	A | B	A ¯ B	A Å B
0	0
0	1
1	0
1	1

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

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

Пусть { x_i | i Î I } – некоторое множество логических переменных. Определим рекурсивно понятие формулы алгебры логики:

1. любая логическая переменная является формулой (атомарной);

2. если a и b – формулы, то выражения Øa, a x b, где x – логическая операция, являются формулами;

3. никаких других формул, кроме построенных по пп 1 и 2, нет.

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

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

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

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

Пример (на практику): ((((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)))).

лекция 14 (12.05.05)

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.1 Пусть две булевы функции заданы таблицей истинности. Для них переменная 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 (О подстановке формул)