2.1.3 Формулы

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

Перечислим правила построения формул.

1. Всякая переменная, быть может с индексами,  это формула. Логические константы 0 и 1  это формулы.

2. Если формула, то и это формулы.

3. Если и формулы, то , , это формулы.

4. Других формул нет.

Пример. Последовательности символов  это формулы. Последовательность формулой не является.

Всякая формула определяет некоторую логическую функцию, по-другому говорят, что формула реализует некоторую логическую функцию. За каждой формулой скрыта таблица истинности. Поэтому нужно уметь вычислять значение формулы во всякой строке таблицы истинности, на всяком наборе значений ее аргументов. Порядок вычисления значения формулы определяется скобками. Если скобок нет, значение формулы вычисляется слева направо в соответствии со старшинством операций. Иерархия операций (в порядке убывания старшинства) задается так: ,(&, |, ↓), , →, (~, ). В скобках указаны равносильные операции.

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

Утверждение. Каковы бы ни были формулы x, y, z справедливы следующие равносильности

1. x x = x; x&x = x (идемпотентность);

2. x y = y x; xy = yx (коммутативность);

3. x (y z) = (x y) z; x(yz) = (xy)z (ассоциативность);

4. (xy) x = x; (x y)x = x (законы поглощения);

5. x (yz) = (x y)(x z); x(y z) = (xy) (xz) (законы дистрибутивности);

6. x 1 = 1; x&1 = x (свойства единицы);

7. x 0 = x; x&0 = 0 (свойства нуля);

8. (инволютивность);

9. (законы де Моргана);

10. (свойства дополнения).

Замечание. Для упрощения обозначений символ коньюнкции & часто опускается, вместо x&y пишут просто xy.

Другие полезные равносильности:

= x|y = .

Доказательство проводится построением соответствующих таблиц истинности.

2.1.4 .Суперпозиция функций алгебры логики

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

Строгое определение суперпозиции дается по индукции.

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

а. Из какой-либо функции переименованием какой-то из ее переменных x_ij, буква x_ij заменяется некоторой буквой y. В этом случае . В частности, буква y может совпадать с одной из переменных x_is функции . Тогда говорят об отождествлении переменных x_ij и x_is.

Пример. Пусть . Тогда  это суперпозиции ранга 1;

б. Подстановкой некоторой функции вместо какого-то аргумента x_ij одной из функций .

Тогда . Эта функция зависит от аргументов x_i1,…, x_ij-1, x_ij+1,…, , x_r1,…, .

Пример. В условиях предыдущего примера функции , , ,  это суперпозиции ранга 1.

Определение. Суперпозиции ранга 1 образуют класс , суперпозиций ранга 1. Суперпозиции ранга 1 функций из множества образуют класс ,…, суперпозиции ранга 1 функций из множества образуют класс суперпозиций ранга p+1 функций исходной системы .

Определение. Суперпозицией функций из системы называется всякая функция, входящая в какой-либо из классов , р=0, 1, 2,…. Здесь  исходная система функций (суперпозиции ранга ноль).

Пример. Функции , , , ,  это суперпозиции функции системы

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

Замечание 2.

Замечание 3. Если все функции исходной системы обладают некоторым свойством, которое наследуется всякой суперпозицией ранга 1, то этим свойством обладают все функции из системы _{,…, системы} ,…, все суперпозиции функций из .

Замечание 4. Описывая правила построения формулы, мы неявно пользовались понятием суперпозиции, ведь всякая формула  это суперпозиция функций x~y, и символов констант 0 и 1.