51. Алгебра логики. Функции алгебры логики. Существенные и несущественные переменные. Бинарные логические операции. Формула. Суперпозиция функций. Таблицы истинности и таблицы Кэли.

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

Алгебра логики как раздел математической логики изучает строение сложных логических высказываний (логических формул) и способы установления их истинности с помощью алгебраических методов.

Рассмотри двухэлементное множество B и двоичные переменные, принимающие значения из B

Алгебра, образованная множеством B вместе со всеми возможными операциями на нем, называется алгеброй логики.

Функцией алгебры логики (или логической функцией) от n переменных называется n-арная операция на B, т.е. f : Bn ® B.

Логическая функция f(x1, …, xn) — это функция, принимающая значения 0, 1.

Множество всех логических функций обозначается P2, множество всех логических функций n переменных — P2(n).

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

Пусть дано множество (конечное или бесконечное) исходных функций å={f1, ..., fm}. Символы переменных х1, ..., хn, ... и констант 0 и 1считают формулами глубины 0. Любая формула имеет глубину k+1, если она имеет вид fi(F1, ..., Fnl), где fiSÎ, ni — количество аргументов fi, а F1, ..., Fnl — формулы, максимальная из глубин которых равна k. F1, ..., Fnl называются подформулами F, fi называется внешней или главной операцией формулы F. Все подформулы формул F1, ..., Fnl — также считаются подформулами F.

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

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

См. вопрос №17