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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. проставляются скобки;

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

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

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

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

4. Задача минимизации фал. Правило склеивания. Основные тождества алгебры логики.

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

• Метод последовательного упрощения аналитического выражения базируется на преобразовании ФАЛ с использованием основных законов и тождеств АЛ.

• В диаграммы Вейча записываются все конституенты единицы, входящие в СДНФ (конституенты нуля, входящие в СКНФ) той или иной булевой функции. Цель преобразований - получить как можно меньшее число прямоугольников, чтобы число членов СДНФ уменьшилось, получив в итоге МДНФ.

• В случае, когда количество переменных больше, необходимо использовать метод Квайна Мак-Класки (см. вопрос 5).

Задача минимизации ФАЛ: Найти аналитическое выражение заданной ФАЛ в форме, содержащей минимальное число переменных.

Основные законы:

коммутативность А+В=В+А

Сочетательный (А+В)+С=А+(В+С)

Двойственность not(A+B)=notA*notB

Распределительный (А+В)*С=АС+ВС

Правило склеивания: AX+AnotX=A

Тождества алгебры логики:

А+0=А А*1=А not notА=A

A+1=1 A*0=0

A+A=A A*A=A

A+notA=1 A*notA=0