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 Построение формул
Из логических переменных с помощью логических связок можно составлять конструкции, которые образуют формулы алгебры логики.
Пусть {xi | 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 переменных x1, x2, …, xn называется функция f:{0,1}n®{0,1}, т.е. функция, которая произвольному набору
(s1, …, sn) нулей и единиц ставит в соответствие значение f(s1, …, sn)Î{0,1}.
ФАЛ называются также булевыми функциями, двоичными функциями или переключательными функциями. Аргументы булевой функции являются булевыми переменными. Булеву функцию можно задать таблицей истинности.
Утверждение Для булевой функции от n аргументов существует 2n различных наборов аргументов.
Булева функция f(x1, x2, …, xn) называется полностью определенной, если ее значения определены на всех 2n наборах переменных. В противном случае функция частично определенная.
Функция 
существенно зависит от переменной xi, (или переменная xi – существенная), если $ такой набор значений x1, x2, …, xn 
, что 
. В противном случае переменная xi – несущественная (фиктивная).
| x1 | x2 | f1 | f2 |
Пример 4.1 Пусть две булевы функции заданы таблицей истинности. Для них переменная x1 существенная, а x2 – несущественная.
По определению булевы функции равны, если одна из другой получается введением или удалением несущественных переменных.
Одна и та же функция может иметь множество реализаций формулами над данным базисом (т.е. множеством логических операций). Формулы, реализующие одну и ту же функцию, называются равносильными (т.е. на всех наборах переменных их значение истинности совпадает). Отношение равносильности формул является отношением эквивалентности.
Пусть даны формулы F(y1, y2, …, ym ), f1(x1, x2, …, xn ), …, fm(x1, x2, …, xn ). Тогда подстановкой формул fi в формулу F называется следующая конструкция: (F| yi fi )(x1, x2, …, xn) º F(f1(x1, x2, …, xn ), …, fm(x1, x2, …, xn )).
Теорема 4.2 (О подстановке формул)