avangard-pressa.ru

A « B º (A ® B)&( B ® A) º (A & B) Ú (ØA & ØB) º (ØA Ú B) & (A Ú ØB). - Логика

A ® B º ØA Ú B.

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

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

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

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

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

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

Любая формула, кроме элементарной, должна быть заключена в наружные круглые скобки. Однако обилие скобок затрудняет чтение формул, поэтому в алгебре логики приняты некоторые соглашения относительно расстановкискобок: 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 переменных 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.2 Пусть две булевы функции заданы таблицей истинности. Для них переменная 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 (О подстановке формул)