1. Формулы алгебры высказываний. Эквивалентность формул. Приведенные формулы, двойственности. Закон двойственности.

Высказыванием называется всякое утверждение, о котором можно вполне определенно и объективно сказать истинно оно или ложно.

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

Импликацией высказываний A и B называется высказывание, которое принимает значение ложь тогда и только тогда, когда A истинно, а B ложно. Обозначается АВ.

Эквиваленцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда высказывания A и B имеют одинаковые значения. Обозначение операции - АВ (АВ).

Пропозициональной переменной называется переменная, значениями которой являются простые высказывания. Обозначим высказывательные переменные через X₁, X₂, . . . , X_n.

Формулами алгебры высказываний являются:

1) логические константы 1, 0;

2) пропозициональные переменные;

3) если А и В формулы, то каждое из выражений А, (А  В), (А  В), (А  В), (А ~ В) есть формула;

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

Формулы А и В называются эквивалентными (обозначается А  В), если при любых значениях высказывательных переменных значение формулы А совпадает со значением формулы В.

Формула называется выполнимой, если существует такой набор значений переменных, при которых эта формула принимает значение И.

Формула называется опровержимой, если существует такой набор значений переменных, при которых эта формула принимает значение Л.

Формула называется тождественно истинной (ТИ-формулой) или тавтологией, если эта формула принимает значение И при всех наборах значений переменных.

Формула называется тождественно ложной (ТЛ-формулой) или противоречием, если эта формула принимает значение л при всех наборах значений переменных.

Формула называется приведенной, если она содержит операции конъюнкции, дизъюнкции и операцию отрицания, относящуюся к высказывательным переменным.

2. Булевы функции. Теорема с разложением Булевых функций. Представление Булевых функций нормальными формами.

Любую формулу алгебры логики можно рассматривать как функцию, определенную на множестве B={1, 0}, где 1 соответствует значению “и”, а 0 – значению “л”.

Функцией алгебры логики (логической функцией) или булевой функцией f(x₁,x₂,...,x_n) называется отображение f : B ⁿB, определенное на множестве упорядоченных наборов элементов множества B и принимающее значения из этого множества. Обозначим через P_n - множество булевых функций n переменных.

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

При любом фиксированном упорядочении наборов булева функция n переменных полностью определяется вектор-столбцом своих значений, размерность которого равна числу наборов значений функции, то есть 2ⁿ . Поэтому число различных функций n переменных равно числу различных двоичных векторов длины 2ⁿ, то есть , т.е. | | = . Нулем (единицей) булевой функции назовем упорядоченный набор значений переменных, на котором значение функции равно 0 (1).

Теорема 4.3 (о разложении булевых функций). Любую булеву функцию можно представить в виде

где дизъюнкции берутся по всем возможным наборам ( ).

Из этой теоремы непосредственно следует представление булевой функции в виде СДН-формы.