е) элемент «ИЛИ – НЕ»;

ж) элемент «И – НЕ»

Рисунок хх.2 Временные диаграммы работы ЛЭ:

а) дизъюнктора; б) конъюнктора;

в) элемента «»; г) инвертора

трицание (инверсия) и повторение – БФ, ТИ которых были приведены в таблице хх.1. Отрицание обозначается чертой, которая ставится над переменной. Например, отрицание переменной х, читаемое «НЕ х», записывается в виде . Условное обозначение ЛЭ, реализующего отрицание (инвертора), изображено на рисунке хх.1.в, а его временные диаграммы на рисунке хх.2.г. Условное обозначение ЛЭ, реализующего повторение (повторителя), изображено на рисунке хх.1.г.

Сложение по модулю два (исключающее «ИЛИ») – БФ, ТИ которой соответствует F₆ в таблице хх.2. Обозначается с помощью знака «», например F=xy. Условное обозначение ЛЭ, реализующего сложение по модулю два, изображено на рисунке хх.1.д, а его временные диаграммы на рисунке хх.2.в.

Стрелка Пирса (функция «ИЛИ – НЕ») – БФ, ТИ которой соответствует F₁ в таблице хх.2. Обозначается с помощью знака «». Условное обозначение ЛЭ, изображено на рисунке хх.1.е.

Штрих Шеффера (функция «И – НЕ») – БФ, ТИ которой соответствует F₇ в таблице хх.2. Обозначается с помощью знака «/». Условное обозначение ЛЭ, изображено на рисунке хх.1.ж.

Равнозначность (эквивалентность) – БФ, ТИ которой соответствует F₉ в таблице хх.2. Обозначается с помощью знака «» или «~».

Импликация от х к у – БФ, ТИ которой соответствует F₁₁ в таблице хх.2. Обозначается с помощью знака «».

Хх.3 Понятие о СДНФ и СКНФ

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

.

ДНФ заданной БФ можно записать несколькими способами, причем одна запись будет отличаться от другой.

.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.

.

Совершенной ДНФ (КНФ) называется такая ДНФ (КНФ), в состав каждой элементарной конъюнкции (дизъюнкции) которой входят все переменные, входящие в БФ.

Для нахождения СДНФ и СКНФ любой БФ существуют следующие алгоритмы.

Пусть БФ трех переменных F задана таблицей истинности (таблица хх.3).

Таблица хх.3 ТИ для F.

x	y	z	F
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Составим СДНФ для F:

• выделяем наборы переменных, на которых функция равна 1;

• записываем для этих наборов конъюнкции, при этом если переменная равна 1, то эта переменная записывается без отрицания, если же переменная равна 0, то такая переменная записывается с отрицанием;

• объединяем элементарные конъюнкции знаками дизъюнкций;

• полученное выражение будет являться совершенной ДНФ.

.

Алгоритм нахождения СКНФ:

• выделяем те наборы переменных, на которых функция равна 0;

• из этих наборов переменных составляем дизъюнкции, учитывая то, что если переменная равна 0, то она записывается без отрицания, а если 1 – с отрицанием;

• объединяем элементарные дизъюнкции знаками конъюнкций;

• полученное выражение является совершенной КНФ.

.

Рангом функции называется наибольшее число переменных, входящих в ДНФ.

Длиной функции называется число элементарных конъюнкций (дизъюнкций) входящих в эту функцию.

Универсальными БФ называются такие БФ, при помощи которых можно описать (представить) любое логическое выражение.

Кратчайшей называется функция, имеющая наименьший ранг и наименьшую длину.

Хх.4 Основные законы (аксиомы) БА

Булеву алгебру можно применять, зная три основные операции: «И», «ИЛИ», «НЕ». Однако полезно знать некоторые основные тождества (тавтологии), приведенные в таблице хх.4.

Таблица хх.4 Основные тождества БА

N	Название	Формулировка
1	Коммутативности (переместительный)
2	Ассоциативности (сочетательный)
3	Дистрибутивности
4	Соотношения абсорбции
5	Теорема де Моргана
6	Двойного отрицания
7	Двойственности
8	Пустого множества
9	Универсального множества
10	Склеивания
11	Поглощения
12	Следствие из 3
13	Обобщенный закон Клода- Шеннона

Хх.5 Свойства функции сложения по модулю два

В таблице хх.5 приведены основные свойства функции сложения по модулю два.

Таблица хх.5 Свойства функции «»

N	Название	Формулировка
1	Определение операции
2	Коммутативности
3	Ассоциативности
4	Дистрибутивности
5	«Закон де Моргана»
6	Соотношения для

Хх.6 Свойства стрелки Пирса и штриха Шеффера

Основные свойства стрелки Пирса и штриха Шеффера приведены в таблице хх.6.

Таблица хх.6 Свойства функций «» и «/»

N	Название	Формулировка
1	Определение функции «»
2	Определение функции «/»
3	Коммутативности
4	«Закон де Моргана»
5	Соотношения для

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

Хх.7 Способы определения равносильности БФ

Существует три метода определения равносильности БФ:

• при помощь ТИ;

• при помощи законов алгебры логики;

• приведением к СДНФ или СКНФ.

Пусть даны три функции: ;

;

.

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

Хх.7.1 Определение равносильности БФ с помощью ТИ

Таблица хх.7 ТИ для определения равносильности F₁, F₂, F₃

x	y			xy
0	0	1	1	0	0	1	1	1	1
0	1	1	0	0	1	0	1	1	1
1	0	0	1	0	0	0	0	0	0
1	1	0	0	1	0	0	1	1	1

Если несколько функций принимают на всех наборах одни и те же значения, то эти функции равносильны. Получаем, что F₁= F₂= F₃.

Хх.7.2 Определение равносильности БФ при помощи логических преобразований

.

.

Получили, что F₁= F₂= F₃.

Доказательство равносильности нескольких функций данным методом является самым сложным и требует очень хорошего знания свойств и законов БФ.

Хх.7.3 Определение равносильности БФ при помощи СДНФ

Сразу можно сделать вывод, что F₁ является СДНФ.

Любую БФ, равно как и ее ДНФ можно представить в виде СДНФ.

.

.

Получаем, что F₁= F₂= F₃.

Хх.8 Выражение одних БФ через другие

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

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

Однако ясно, что построение одной логической схемы из множества ЛЭ разных типов бывает нецелесообразно. В некоторых случаях гораздо эффективнее логическая структура, составленная из однотипных элементов.

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

Из определений бинарных функций (таких как «», «», «/» и т.д.) можно заметить, что свойствами базиса обладают наборы «И – НЕ», «ИЛИ – НЕ», «И – ИЛИ – НЕ». Так мы их и будем называть: базис «И – НЕ», базис «ИЛИ – НЕ», базис «И – ИЛИ – НЕ». Но этими наборами не исчерпываются все возможные функционально полные системы. Существует также базис «», базис «/», базис « – И – 1» и другие.

Попытаемся выразить через стрелку Пирса и штрих Шеффера основные операции БА.

Дизъюнкция выражается следующим образом:

;

.

Конъюнкция выражается как:

;

.

Хх.9 Закон двойственности

Двойственной формой БФ называется такая форма, которая получается из заданной формы путем замены дизъюнкции на конъюнкцию и конъюнкции на дизъюнкцию. Двойственная форма функции F обозначается F^*. Например, для булевой функции трех переменных двойственная форма запишется в виде .

Закон двойственности: если две БФ тождественны между собой, то и их двойственные формы тоже тождественны.

Следует заметить, что двойственную форму необходимо отличать от инверсной.

Хх.10 Функциональная декомпозиция БФ

Любую заданную БФ можно представить двумя способами:

• с помощью двух составляющих;

• разложением на множители.

При этом используется метод разложения БФ по одной, двум и более переменным.

В первом случае функция представляется в виде .

Во втором – в виде

.