Переход от таблицы истинности к СКНФ и СДНФ

1 2

Нормальная форма логической формулы существует в двух видах:

А) Конъюнктивная нормальная форма (КНФ) – конъюнкция нескольких дизъюнкций, например,

Б) Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция нескольких конъюнкций, например,

2.1 Совершенная конъюнктивная нормальная форма (СКНФ)

Совершенная конъюнктивная нормальная форма (СКНФ) - это КНФ, удовлетворяющая трем условиям:

- не содержит одинаковых элементарных дизъюнкций;

- ни одна из дизъюнкций не содержит одинаковых переменных;

- каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.

Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.

Правило построения СКНФ по таблице истинности

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

2.2 Совершенная дизъюнктивная нормальная форма (СДНФ)
Совершенная дизъюнктивная нормальная форма (СДНФ) - это ДНФ, удовлетворяющая трем условиям:

- не содержит одинаковых элементарных конъюнкций;

- ни одна из конъюнкций не содержит одинаковых переменных;

- каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.

Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.

Правило построения СДНФ по таблице истинности

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

Пример

СДНФ

СКНФ

Примечание: ˅ - Логическое ИЛИ («сложение»);

˄ - Логическое И («умножение»).

3. Таблица истинности дискретного автомата

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

Вариант №1
К1	К2	К3	U1
0	0	0	0
0	0	1	1
0	1	0	1
1	0	0	1
0	1	1	1
1	1	0	1
1	0	1	1
1	1	1	0
Вариант №2
К1	К2	К3	U1
0	0	0	0
0	0	1	1
0	1	0	0
1	0	0	1
0	1	1	1
1	1	0	0
1	0	1	1
1	1	1	1
Вариант №3
К1	К2	К3	U1
0	0	0	0
0	0	1	1
0	1	0	1
1	0	0	0
0	1	1	0
1	1	0	0
1	0	1	0
1	1	1	0
Вариант №4
К1	К2	К3	U1
0	0	0	1
0	0	1	1
0	1	0	0
1	0	0	0
0	1	1	1
1	1	0	1
1	0	1	0
1	1	1	0

Вариант №5

К1

К2

К3

Вариант №6

К1

К2

К3

Вариант №7

К1

К2

К3

Вариант №8

К1

К2

К3

Вариант №9

К1

К2

К3

Вариант №10

К1

К2

К3

Вариант №11

К1

К2

К3

Вариант №12

К1

К2

К3

Вариант №13

К1

К2

К3

Вариант №14

К1

К2

К3

Вариант №15

К1

К2

К3

Вариант №16

К1

К2

К3

Вариант №17

К1

К2

К3

Вариант №18

К1

К2

К3

Вариант №19

К1

К2

К3

Вариант №20

К1

К2

К3

Реализовать дискретный автомат в программном средстве, используя следующие микросхемы: 7408, 7432, 7404

Пример реализации дискретного автомата в программе

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

К1	К2	К3	U1
1	0	0	1
0	0	0	1
1	1	0	1
0	0	1	1
1	0	1	1
0	1	0	0
1	1	1	0
0	1	1	1

Рисунок – Комбинация ключей К1=0, К2=1, К3=0

Рисунок – Комбинация ключей К1=0, К2=0, К3=0

Следует учесть, что при данной реализации схемы ключи (переключатели) в замкнутом положении выдают сигнал «0» (синий квадрат), а в разомкнутом – «1» (красный квадрат). Для удобства можно поставить после них логический элемент «НЕ».

4. Реализация дискретного автомата на микросхемах К155ЛЛ1, К555ЛИ3, К155ЛИ1, КМ155ЛН1

4.1 Микросхема К155ЛИ1

Микросхемы К155ЛИ1, КМ155ЛИ1 (7408) представляет собой четыре логических элемента 2И.

1	Номинальное напряжение питания	5В + 5%
2	Выходное напряжение низкого уровня	≤ 0,4 В
3	Выходное напряжение высокого уровня	≥ 2,4 В
4	Входной ток низкого уровня	≤ -1,6 мА
5	Входной ток высокого уровня	≤ 0,04 мА
6	Входной пробивной ток	≤ 1 мА
7	Ток потребления при низком уровне выходного напряжения	≤ 33 мА
8	Ток потребления при высоком уровне выходного напряжения	≤ 21 мА
9	Потребляемая статическая мощность на один логический элемент	≤ 35,4 мВт
10	Время задержки распространения при включении	≤ 19 нс
11	Время задержки распространения при выключении	≤ 27 нс

4.2 Микросхема К155ЛЛ1

Микросхемы К155ЛЛ1, КМ155ЛЛ1 (7432) представляют собой четыре логических элемента 2ИЛИ.

1	Номинальное напряжение питания	5В + 5%
2	Выходное напряжение низкого уровня	≤ 0,4 В
3	Выходное напряжение высокого уровня	≥ 2,4 В
4	Входной ток низкого уровня	≤ -1,6 мА
5	Входной ток высокого уровня	≤ 0,04 мА
6	Входной пробивной ток	≤ 1 мА
7	Ток потребления при низком уровне выходного напряжения	≤ 38 мА
8	Ток потребления при высоком уровне выходного напряжения	≤ 22 мА
9	Потребляемая статическая мощность на один логический элемент	≤ 39,4 мВт
10	Время задержки распространения при включении	≤ 22 нс
11	Время задержки распространения при выключении	≤ 15 нс

4.3 Микросхема К155ЛН1

Микросхемы К155ЛН1, КМ155ЛН1 (7404) представляет собой шесть логических элементов НЕ.

1	Номинальное напряжение питания	5В + 5%
2	Выходное напряжение низкого уровня	≤ 0,4 В
3	Выходное напряжение высокого уровня	≥ 2,4 В
4	Входной ток низкого уровня	≤ -1,6 мА
5	Входной ток высокого уровня	≤ 0,04 мА
6	Входной пробивной ток	≤ 1 мА
7	Ток потребления при низком уровне выходного напряжения	≤ 33 мА
8	Ток потребления при высоком уровне выходного напряжения	≤ 12 мА
9	Потребляемая статическая мощность на один логический элемент	≤ 19,7 мВт
10	Время задержки распространения при включении	≤ 15 нс
11	Время задержки распространения при выключении	≤ 22 нс

4.4 Микросхема К155ЛИ3

Микросхемы К155ЛИ1, КМ155ЛИ1 (7408) представляет собой четыре логических элемента 2И

1	Номинальное напряжение питания	5В + 5%
2	Выходное напряжение низкого уровня	≤ 0,4 В
3	Выходное напряжение высокого уровня	≥ 2,4 В
4	Входной ток низкого уровня	≤ -1,6 мА
5	Входной ток высокого уровня	≤ 0,04 мА
6	Входной пробивной ток	≤ 1 мА
7	Ток потребления при низком уровне выходного напряжения	≤ 33 мА
8	Ток потребления при высоком уровне выходного напряжения	≤ 21 мА
9	Потребляемая статическая мощность на один логический элемент	≤ 35,4 мВт
10	Время задержки распространения при включении	≤ 19 нс
11	Время задержки распространения при выключении	≤ 27 нс