Функции Алгебры Логики (ФАЛ). Способы задания функций. Понятие Базиса. СДНФ, СКНФ. Переход из одного базиса в другой.

Алгебра логики— раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывания могут быть только истинными или ложными.

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

Функция алгебры логики – функция, аргументы и значения которой могут принимать 2 значения - истина или ложь.

Способы задания: СДНФ, СКНФ, таблицы истинности.

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

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

1) Коньюнкция (и), Дизъюнкция (или), Отрицание (не);

2) Штрих Шеффера (и-не | );

3) Стрелка Пирса (или-не).

Базис изображают в виде СКНФ и СДНФ.

1) Совершенная дизъюктивная нормальная форма- дизъюнкция элементарных коньюнкций, в каждый из которых входят все наборы переменных. Значения функции принимают Дизъюнктивная нормальная форма называется совершенной, если все входящие в неё элементарные произведения являются конституен­тами единицы для одного и того же множества аргументов данной функции.

2) Совершенная коньюктивная нормальная форма – коньюнкция элементарных дизъюнкций, в каждую из которых входят все переменные из набора. Значения функции принимают 0. Конъюнктивная нормальная форма называется совершенной, если все входящие в неё элементарные дизъюнкции являются конституен­тами нуля для одного и того же множества аргументов данной функции.

Любая ФАЛ имеет только одну СДНФ и СКНФ.

Для получения совер­шенных нормальных форм существуют различные способы, основными из которых являются: табличный и аналитический.

Переход из базиса 3-х ф-ий к штриху Шеффера или стреле Пирса:

Исходная ф-ия представлена в виде СДНФ или СКНФ.

a) проставляются скобки;

b) коньюнкция меняется на “|”, а дизъюнкция на стрелку Пирса.

Исколючения:

· если вся ф-я состоит из одной импликанты – берется отрицательная терма;

· если терм состоит из однобуквенного импликанта - берется с отрицанием.