🗊Презентация Основы математической логики. Функции алгебры логики

О с н о в ы м а т е м а т и ч е с к о й л о г и к и Ф у н к ц и и А л г е б р ы Л о г и к и

Функции а л г е б р ы л о г и к и Переменные xi, принимающие значения из множества {0,1} называются двоичными переменными. Функция (х1, х2, …, хn) от двоичных переменных, принимающая, как и ее аргументы, значения 0,1, называется функцией алгебры логики (ФАЛ) или переключательной функцией (ПФ). Такие функции называют также двоичными, логическими или булевыми функциями. ФАЛ характеризуются: числом двоичных переменных n; областью определения функции – число наборов kн=2n; общим числом различных функций kф= 2kн.

Булева ф у н к ц и я о д н о г о аргумента

Булева функция двух аргументов

Булева функция д в у х аргументов

Функционально п о л н ы й набор На практике используют не все функции, а только те, которые методом суперпозиции (подстановка вместо элементов одной функции других функций) обеспечивают представление любой другой функции. Набор таких функций называют функционально полным набором (ФПН). Существует несколько ФПН. Один из них основной ФПН – конъюнкция, дизъюнкция, инверсия. Дискретный преобразователь, который после обработки входных двоичных сигналов выдаёт на выходе сигнал, являющийся значением одной из логических операций, называется логическим элементом (ЛЭ).

Л о г и ч е с к и е э л е м е н т ы Конъюнктор, схема «И» Дизъюнктор, схема «ИЛИ»

Л о г и ч е с к и е э л е м е н т ы Стрелка Пирса, Штрих Шеффера, схема «ИЛИ-НЕ» схема «И-НЕ» (A B) (A  B)

Ф у н к ц и о н а л ь н а я схема, с т р у к т у р н а я формула

Построение функциональных схем логических устройств

Построение функциональных схем логических устройств

Определение структурной формулы по функциональной схеме

Дизъюнктивная нормальная форма и конъюнктивная нормальная форма Элементарная конъюнкция – логическое произведение (конъюнкция) аргументов или их отрицаний, среди аргументов могут быть одинаковые. Пример. А & В & С – элементарная конъюнкция (А & В) – НЕ элементарная конъюнкция, есть отрицание выражения. Элементарная дизъюнкция – логическая сумма (дизъюнкция) аргументов или их отрицаний, среди аргументов возможны одинаковые. Примеры.  А V В или X V  Y V  Z, но X V Y & Z НЕ элементарная дизъюнкция, имеется конъюнкция Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ) Пример. X & X V X & Y & Z ; X & Y V Y V X & Z Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (КНФ). (X V Y V X) & (X V Z) ; X & (X V Y) & (X V Z) ;

Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием). Пример. X & Y & Z V X & Y & Z , но X & Y V  Y V X &  Z НЕ СДНФ Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием). Пример. (X V Y V Z) & (X V  Y V Z), но (X V Y V Х) & ( X V Z) НЕ СКНФ