Базовые логические функции. Основные понятия алгебры логики презентация

Базовые логические функции

Основные понятия алгебры логики Алгебры логики - раздел математической логики, в котором изучаются логические операции над выражениями, представленными в двоичной форме(истина-ложь, ноль-единица). Алгебра логики находят широкое применение при синтезе и анализа схем ЭВМ, так как информация представляется в двоичном виде и реализуется с помощью физических элементов которые могут пропускать или не пропускать ток, иметь на выходе высокий или низкий уровень сигнала (напряжения или тока – ноль или единицу) .

Основные понятия алгебры логики логическая переменная это такая переменная, которая может принимать одно из двух значений: истинно или ложно (да или нет, единица или ноль), что хорошо согласуется с двоичным представление информации в ЭВМ. логическая константа это такая постоянная величина, значением которой может быть: истинно или ложно (да или нет, единица или ноль). логическая функция это такая функция, которая может принимать одно из двух значений (истинно или ложно, да или нет, единица или ноль), в зависимости от текущего значений её аргументов, в качестве которых используются логические переменные.

Логическая функция Логическая функция может быть одного (n=1) или нескольких (n >1) аргументов. Значение логической функции определяется комбинацией конкретных значений переменных, от которых она зависит. Комбинация конкретных значений переменных (аргументов функции) называется набором. Количество различных наборов N для «n» переменных определяется как: N= 2n.

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

Таблица истинности

Логическое выражение Логическим выражением называется комбинация логических переменных и констант, связанных элементарными базовыми логическими функциями (или логическими операциями), которые могут разделяться скобками. Например, логическую функцию у1, определенную выше приведенной таблице истинности, можно представить в виде логического выражения: где « ͞ », «+», «*» - знаки базовых логических функций

Булевый базис. Набор элементарных логических операций, с помощью которого можно задать любую, сколь угодно сложную логическую функцию, называется «функционально полная система логических функций» или базисом. Наиболее распространенный, который в качестве базовых логических функций использует функцию одной переменной « НЕ» ( функция отрицания), и две функции двух переменных «И» (конъюнкция или логическое умножения) и «ИЛИ» (дизъюнкция или логическое сложение). Эта система получила название система Булевых функций или Булевый базис.

Основные законы алгебры Буля В алгебре Буля используется следующая приоритетность выполнения операций: - сначала рассчитываются значения имеющих место отрицаний и скобок, - затем выполняются операция И (логическое умножение); - самый низший приоритет имеет операция ИЛИ ( логическая сумма). При работе с булевыми логическим выражениями используются следующие законы и правила. Переместительный (коммутативный) закон. Закон справедлив как для конъюнкции, так и для дизъюнкции. х1 + х2 + х3 + х4 .= х4 + х3 + х2+ х1 - от перемены мест логических слагаемых сумма не меняется; х1 * х2 * х3 * х4 .= х4 * х3 * х2* х1 - от перемены мест логических сомножителей их произведение не меняется.

Основные законы алгебры Буля Сочетательный (ассоциативный) закон. Закон справедлив как для конъюнкции, так и для дизъюнкции. х1 + х2 + х3 + х4.= (х2 + х3 )+ х1 + х4.=( х1 + х4 )+ (х2 + х3) - при логическом сложения отдельные слагаемые можно заменить их суммой; х1 * х2 * х3 * х4.= (х2 * х3) )* х1 * х4.=( х1 * х4)* (х2 * х3) - при логическом умножении отдельные логические сомножители можно заменить их произведением. Распределительный (дистрибутивный) закон. (х1 + х2 )* х3 .= х1 * х3 + х2* х3. (х1 + х2 )*( х1 + х3)= х1 + х2* х3.

Правило де Моргана - отрицание суммы равно произведению отрицаний; -отрицание произведения равно сумме отрицаний. Правило справедливо при любом числе логических операндов.

Операция склеивания Операция склеивания: - операция склеивания для конъюнкций =А - операция склеивания для дизъюнкций, Операции с отрицаниями: x - двойное отрицание равносильно отсутствию отрицания;

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

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

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

Минимизация логических выражений Учитывая то, что одну и ту же логическую функцию можно представить различными выражениями, перед реализацией функции в виде логической схемой весьма важным является выбор из всех возможных выражений, соответствующих данной функции, самое «простое». Решить эту проблему можно за счет использования процедуры минимизации логического выражения.

Карты Карно - Вейча Карта Карно для «n» логических переменных представляет собой множество квадратов (клеток), объединённых в близкую к квадрату прямоугольную форму. Каждая такая клетка соответствует одному набору логических переменных, причем наборы двух соседних клеток должны отличаться на значение одной переменной (представляются в коде Грея и образуют склеивающиеся наборы). Карта Карно задает своего рода таблицу истинности. Записываемая функция должна быть представлена в СДНФ(СКНФ). Запись функции в карту осуществляется за счет установки «1»(0 - СКНФ) в те клетки карты, где функция принимает единичное (нулевое) значение.

Этапы минимизации Для выполнения минимизации представленной в карте Карно функции необходимо выполнить два этапа: охватить множество клеток карты Карно контурами; записать минимальное выражение для заданной функции в виде дизъюнкции конъюнкций для СДНФ (или конъюнкция дизъюнкций для СКНФ), где каждая конъюнкция (дизъюнкция) соответствует одному из введенных на карте контуров.

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

Логические соседи

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

Логические соседи

Правила охвата клеток Охват клеток карты контурами выполняется с соблюдением следующих правил: контурами необходимо охватить все клетки с единичными (нулевыми для СКНФ) значениями;  контур должен иметь прямоугольную форму; в контур может входить такое количество клеток, которое равно целой степени числа «2»; в контур могут входить клетки, являющиеся логическими соседями; в контур необходимо включить максимальное количество клеток с учетом выше приведенных требований; контуров должно быть минимальное количество.

Правила записи Запись минимального выражения заданной функции имеет вид дизъюнкции простых конъюнкций для СДНФ (конъюнкцию дизъюнкций для СКНФ), и формируется следующим образом: -   соответствующая контуру конъюнкция (дизъюнкция для СКНФ), должна включать, только те переменные, которые имеют постоянное значение во всех клетках, охваченных рассматриваемым контуром; - переменные, которые имеют разные значения для клеток, охваченных рассматриваемым контуром склеиваются и   не должны входить   в конъюнкцию (дизъюнкцию для СКНФ).

Функциональные узлы ЭВМ Функциональные узлы ЭВМ комбинационного типа

Шифратор Шифратор (кодер) - это устройство, преобразующее m- разрядный позиционный код в n- разрядный двоичный код. В позиционном коде число определяется позицией единиц в серии нулей, или позицией нуля в серии единиц. (Или проще - единичный сигнал на одном из входов в n-разрядный двоичный код). Наибольшее применение он находит в устройствах ввода информации (пультах управления) для преобразования десятичных чисел в двоичную систему счисления.

Шифратор Предположим, на пульте десять клавиш с гравировкой от 0 до 9. При нажатии любой из них на вход шифратора подается единичный сигнал (Х0, ..., Х9). На выходе шифратора должен появиться двоичный код (Y0, ..., Y9) этого десятичного числа. Как видно из таблицы истинности, в этом случае нужен преобразователь с десятью входами и четырьмя выходами.

Реализация шифратора

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

Таблица истинности для дешифратора трехразрядного двоичного кода десятичных цифр:

Дешифратор на три входа

Цифровой мультиплексор Пропускает(коммутирует) сигнал с одного из входов на один выход в зависимости от состояния двоичного кода на адресных входах.

Цифровой компаратор Сравнивает два двоичных числа http://naf-st.ru/articles/digit/sum/

Одноразрядный двоичный сумматор

Сумматор

Функциональные узлы ЭВМ Функциональные узлы ЭВМ последовательного типа (элементы с памятью)

Составляющие цифрового сигнала

Асинхронный RS - триггер

Синхронный D-триггер  Когда на вход С подан логический 0, триггер хранит информацию. Если на вход С подать логическую 1, то триггер записывает значение с информационного входа D.

Т- триггеры

Регистр

Регистр сдвига

Цифровой счетчик Цифровой счетчик импульсов - это цифровой узел, который осуществляет счет поступающих на его вход импульсов. Результат счета формируется счетчиком в заданном коде и может храниться требуемое время. Счетчики строятся на триггерах, при этом количество импульсов, которое может подсчитать счетчик определяется из выражения N = 2n - 1, где n - число триггеров,

Четырехразрядный двоичный счетчик

Цифровой счетчик Используются следующие разновидности счетчика: -     счетчики прямого счета; -     счетчики обратного счета; -     реверсивные счётчики.