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

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

Булевы функции одного и двух аргументов называют элементарными.

Схему, которая осуществляет элементарную логическую операцию, называют логическим элементом (вентилем).

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

Соответственно перечню логических операций различают три основных логических элемента (ЛЭ): И, ИЛИ, НЕ. Названия и условные графические обозначения основных логических элемен­тов, применяемых в компьютерной схемотехнике, представлены в табл. 3.8.

Зна­чения переменных (операндов) отображаются электрическими сигналами с двумя четко выраженными уровнями значений. Число входов элементов И, ИЛИ может быть произвольным, а элемент НЕ имеет всегда только один вход.

Таблица 3.8- Условные графические обозначения основных логических элемен­тов
Название операции	Название элемента	Условное графическое обозначение
Отрицание	НЕ
Дизъюнкция	ИЛИ
Конъюнкция	И
Отрицание дизъюнкции	НЕ ИЛИ
Отрицание конъюнкции	НЕ И
Отрицание эквивалентности	Исключающее ИЛИ
Эквивалентность	Эквивалентность
Импликация	ЕСЛИ, ТО
Запрет	НЕТ

 

При сравнении операций И, ИЛИ можно заметить, что, если в условиях, которые определяют операцию И, значения всех переменных и самой функции заменить их инверсией, а знак логического умножения – знаком логического сложения, получим постулаты, которые определяют операцию ИЛИ: если a∙ b = c, то + =

если a + b = c, то ∙ =

Это свойство взаимного преобразования постулатов операций логического сложения и умножения носит название принципа двойственности.

Две функции алгебры логики называются двойственными, если одна получается из другой заменой каждой операции конъюнкции на операцию дизъюнкции и наоборот.

Таблица 3.9 –Важные теоремы, отражающие основные соотношения алгебры логики
	x + 0 = x	x ∙ 1 = x
	x + 1 = 1	x ∙ 0 = 0
	x + x = x	x ∙ x = x
	x + = 1	x ∙ = 0
	= x	-
	x + y = y + x	x ∙ y = y ∙ x
	x + x ∙ y = x	x (x + y) = x
	x + (y + z) = (x + y) + z	x (y ∙ z) = (x ∙ y) z
	x + y ∙ z = (x + y) (x + z)	x (y + z) = x ∙ y + x ∙ z
	= ∙	= +
	(x + y) ( + y) = y	x ∙ y + ∙ y = y

Нетрудно заметить, что почти все вышеприведенные законы алгебры логики (кроме 5) обладают свойством двойственности, т.е. представлены парой соотношений, каждое из которых получается заменой операции И на ИЛИ, операции ИЛИ на И, логической 1 на логический 0 и логического 0 на логическую 1.

Например, для функции 11 F (a, b) = ab + b

двойственной является функция F’(a, b) = (a + b)( + b).

Принцип двойственности формулируется так: если функция F₁ и F₂ равносильны, то и двойственные им функции F’₁ и F’₂ также равносильны.

Необходимо отличать двойственные формы функции от инверсных функций, которые вытекают из исходных инвертированием последних. При этом не только все операции заменяются на двойственные, но и все переменные заменяются их инверсиями.

Например, для функции F (a, b) = ab + b

инверсной будет функция F (a, b) = ab + b = = ( + )(а + ).

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

Совокупность логических элементов (ЛЭ) которая позволяет реализовать логическую схему любой сложности, называется функционально полной системой.

Функционально полными системами являются системы:

- И и НЕ,

- ИЛИ и НЕ,

- И, ИЛИ, НЕ

На практике широкое применение нашли ЛЭ, которые совмещают функции элементов указанных выше функционально полных систем. Это элементы И-НЕ и ИЛИ-НЕ (рис. 3.1).

 

Рисунок 3.1 – Условные графические обозначения двухвходовых ЛЭ И-НЕ и ИЛИ - НЕ

Если рассмотреть выполнение операций И, ИЛИ и НЕ на элементах ИЛИ-НЕ то в соответствии с принципом двойственности, если a ∙ b = c, то + = . Инвертируя правую и левую часть первого выражения, получим + = = , т.е. логическая операция И может быть заменена операциями ИЛИ и НЕ.

На рис. 3.2 приведены примеры реализации основных логических операций с использованием только элементов ИЛИ-НЕ.

На рис. 3.3 приведены примеры реализации основных логических операций с использованием только элементов И-НЕ.

 

 

Рисунок 3.2 – Реализация логических операций И, ИЛИ, НЕ на базе элементов ИЛИ-НЕ

Рисунок 3.3 – Реализация логических операций И, ИЛИ, НЕ на базе элементов И-НЕ