Набор логических функций двух переменных

Аргументы	Функция	Название функции
Х1 Х2
					у1 = 0 у2 = х1 х2 у4 = х1 у6 = х2 х1 х2             у16 = 1	Константа 0 Конъюнкция, операция И Запрет по х2 Тождественность х1 Запрет по х1 Тождественность х2 Исключающее ИЛИ, неравнозначность (сумма по модулю 2) Дизъюнкция, операция ИЛИ Операция ИЛИ – НЕ (стрелка Пирса) Равнозначность, эквива- лентность Инверсия х2, отрицание х2 Импликация от х2 к х1 Инверсия х1, отрицание х1 Импликация от х1 к х2 Операция И – НЕ (штрих Шеффера) Константа 1

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

Операция отрицания над одной переменной характеризуется следующими свойствами: функция у = 1 при аргументе х = 0 и у = 0, если х = 1. Обозначается отрицание чертой над переменной: (игрек равен не икс). Соответственно .

Операция логического умножения для двух переменных характеризуется так: 0∙0 = 0; 0∙1 = 0; 1∙0 = 0; 1∙1 = 1, т.е. функция у = 1, если все аргументы равны 1.

Операцию логического сложения обозначают . Она означает, что: 0 0 = 0; 0 1 = 1; 1 0 = 1; 1 1 = 1, т.е. у = 1, если хотя бы один аргумент равен 1.

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

Логическая функция может быть задана словесно, алгебраическим выражением и таблицей истинности. Например, функцию , заданную в виде словесного описания: = 1, когда значения переменных , и = 0, когда , можно представить в виде таблицы истинности (таблица 10.3) или в алгебраической форме (см. таблицу 10.2). Для операций конъюнкции и дизъюнкции табличная форма задания имеет вид – таблица 10.4.

Таблица 10.3	Таблица 10.4

Таблица истинности содержит все N = 2ⁿ возможные наборы значений переменных и значения функции, соответствующие каждому из наборов.

Чтобы осуществить переход от табличного представления к алгебраическому, каждому числовому набору переменных ставится в соответствие минтерм m_i. Минтерм (конституента единицы) – это конъюнкция всех переменных, причем те переменные, которые в наборе имеют значение 1, представляются в прямом виде, а те, которые имеют значение 0, − в инверсном. Тогда искомое алгебраическое выражение представляется в виде следующей логической суммы:

(10.4)

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

Например, требуется получить алгебраическую запись функции у₁₀,заданной таблицей 10.3. Для этого необходимо в соответствии с выше изложенной методикой составить минтермы (таблица 10.5) и воспользоваться выражением (10.4). Получится

Таблица 10.5

Минтермы, макстермы и значения функции у₁₀

 

		Минтермы	Макстермы	Значения функции у10

 

 

Другая алгебраическая форма представления функции получается при использовании макстермов. Макстермом (конституентой 0) называется дизъюнкция всех переменных, причем те переменные, которые в наборе имеют значение 1, представляются в прямом виде, а те, которые имеют значение 0, − в инверсном. Алгебраическое выражение функции получается в виде логического умножения:

(10.5)

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

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

При относительно небольшом числе переменных (n ≤ 6) весьма удобным и наглядным является графическое представление функций в виде так называемых карт минтермов, наиболее распространенной формой которых считаются карты Карно. Техника представления функций с помощью карт Карно изложена, например, в [6].

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

 

Таблица 10.6