Переключательные схемы

1. Переключательные схемы

2.

Рассматриваются
электрические
ПС,
представляющие собой соединенные проводниками
переключатели и источники тока.
Условимся обозначать символом 1 протекание
тока в проводниках и символом 0 – отсутствие тока
в проводниках.
P2
P1
P3
A
B
P4
P5

3.

Переключатель - электромагнитное реле с
контактами и индукционной катушкой, состояние
которой
моделируется
пропозициональной
переменной X: X=1 - в катушке идет ток, и X=0 - в
катушке тока нет.
Контакты реле – замыкающие или размыкающие.
Через замыкающий контакт реле ток проходит в том
и только том случае, если X=1 - такой контакт
моделируется пропозициональной переменной X.
Через размыкающий контакт реле ток проходит в
том и только том случае, если X=0 - такой контакт
моделируется
отрицанием
пропозициональной
переменной X .

4.

Пример. Пусть в ПС на рис.1 переключатели
P1 , P5 имеют общую катушку реле с током X 1 и
переключатели P2 , P4 имеют общую катушку реле
с током X 2 , причем
контакты P1, P2 , P4 –
замыкающие и контакты P3 , P5 – размыкающие.
Тогда такая ПС с помощью булевых переменных
X 1 , X 2 , X 3 изображается следующей диаграммой:
X2
X1
X2
X 3
X 1

5.

Переключатели p,q могут быть
последовательно или параллельно.
соединены
p
p
q
q
Рис.3
Рис.4
Через
последовательно
соединенные
переключатели p,q ток проходит в том и только том
случае,
если
моделирующие
их
формулы
1 такое соединение моделируется
формулой .
Через параллельно соединенные переключатели
p,q ток не проходит в том и только том случае, если
0 - такое соединение моделируется
формулой .

6.

В
результате
любая
электрическая
ПС
моделируется некоторой формулой , которая
принимает значение 1 в том и только том случае,
если в ПС идет ток.
Соответствующая такой формуле булева
функция F называется функцией проводимости
ПС, так как она показывает, при каких значениях
булевых переменных (т.е. переключателей данной
схемы) в ПС идет электрический ток.
С
другой
стороны,
каждая
формула
( X 1 ,..., X n ) моделирует ПС с функцией
проводимости F : эта схема так конструируется из
переключателей X 1 , X 1 ,..., X n , X n , что в ней при
значениях X 1 1 ,..., X n n проходит ток в том и
только том случае, если F 1 ,..., n 1 .

7.

Переключательную схему, моделирующую формулу
( X 1 ,..., X n ) , можно представлять в виде устройства с
n входами и одним выходом, которое преобразует
X 1 1 ,..., X n n
входные булевы значения
в
выходное булево значение F 1 ,..., n 1 .
Графически
диаграммой:
такое
устройство
a1
a2
an
Ф
F 1 ,..., n 1
изображается

8.

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

9.

( X 1 ..., X n ) X 1 ... X n
Формула
моделирует устройство с n входами и одним
выходом, которое изображается диаграммой
1
2
Ф
1 2 ... n
и называется AND-элементом.

10.

Формула ( X 1 ..., X n ) X 1 ... X n моделирует
устройство с n входами и одним выходом, которое
изображается диаграммой
1
2
1 2 ... n
и называется OR-элементом.

11.

Примеры.
1. Построим ПС, которая моделирует сложение двух
двоичных цифр и называется полусумматором. Такая
ПС имеет два входа a1 , a2 и два выхода f (a1 , a2 ) , g (a1 , a2 ) ,
которые
описывают
два
разряда
суммы
a1 a2 .
Таблица этих булевых функций имеет следующий вид:
a1 a2
f (a1 , a2 )
g (a1 , a2 )
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1

12.

СДНФ функций:
g ( X1, X 2 ) X1 X 2 ,
f ( X 1 , X 2 ) ( X 1 X 2 ) ( X 1 X 2 )
( X 1 X 2 ) ( X 1 X 2 ) g ( X 1 X 2 )
Полусумматор представляется диаграммой:
a1
g (a1 , a2 )
f (a1 , a2 )
a2

13.

Символически
полусумматор
изображается диаграммой:
f (a1 , a2 )
a1
a2
ПС
g (a1 , a2 )

14.

2. Построим ПС, которая моделирует
сложение трех двоичных цифр и называется
полным сумматором. Такая ПС имеет три
входа a1 , a2 , a3 и два выхода f (a , a , a ) , g (a1 , a2 , a3 ) ,
которые описывают два разряда суммы
a1 a2 a3 .
3. Построить ПС, которая моделирует
сложение двух трехразрядных двоичных
чисел a1a2 a3 , b1b2b3 . Такая ПС имеет шесть
входов a1 , a2 , a3 , b1 , b2 , b3 и четыре выхода
d1 , d 2 , d3 , d 4 , которые описывают четыре разряда
суммы a1a2a3 b1b2b3 .
1
2
3

15. Минимизация СДНФ

16.

Рассмотрим вопрос минимизации ДНФ D .
Конъюнкт q называется импликантом формы
D, если D q q . Импликанты, минимальные
по числу вхождений в них булевых
переменных,
называются
простыми
импликантами. Дизъюнкция всех простых
импликант формы D называется сокращенной
ДНФ.
Лемма 1. Любая ДНФ D эквивалентна
некоторой сокращенной ДНФ.

17.

Сокращенную ДНФ формы СДНФ D можно
получить
методом
Квайна
с
помощью
последовательного применения следующих двух видов
операций:
1) операция склеивания, которая для конъюнктов q
и пропозициональных переменных X определяется по
формуле:
(q X ) (q X ) (q X ) (q X ) q ;
2) операция поглощения, которая для конъюнктов q,
пропозициональных переменных X и значений
{0,1} определяется по формуле:
(q X ) q q .

18.

Пример. Найдем сокращенную ДНФ для СДНФ
D ( X Y Z ) ( X Y Z )
( X Y Z ) ( X Y Z ) ( X Y Z ) .
В результате применения операции склеивания к
различным парам конъюнктов многочлена D
получим ДНФ и последующего применения
операции поглощения к различным парам
конъюнктов получим формулу ( X Z ) Y , которая
является сокращенной ДНФ формулы D.

19.

В общем случае сокращенная ДНФ формы D не
является минимальной формой, так как она может
содержать лишние импликанты, удаление которых
не изменяет булеву функцию FD . В результате
удаления таких лишних импликант получаются
тупиковые ДНФ.
Тупиковые ДНФ с наименьшим числом
вхождений в них булевых переменных называются
минимальными ДНФ.
Лемма 2. Любая ДНФ D эквивалентна некоторой
минимальной ДНФ.

20.

Минимальная ДНФ формы D получается с помощью
матрицы Квайна:
столбцы матрицы помечаются конъюнктами
p1 ,..., pm формы D ;
строки матрицы помечаются
q1 ,..., qk сокращенной ДНФ формы D ;
импликантами
на пересечении строки qi и столбца p j ставится
символ , если импликант qi является частью
конъюнкта p j .
Тупиковые ДНФ - дизъюнкции тех минимальных
наборов импликант, в строках которых имеются
звездочки для всех столбцов матрицы Квайна.
Тупиковые ДНФ с наименьшим числом вхождений
булевых
переменных
являются
искомыми

21.

Пример. Найдем минимальную ДНФ для формулы
D ( X Y Z ) ( X Y Z )
( X Y Z ) ( X Y Z )
.
В результате применения операций склеивания и
поглощения получим D ( X Y ) ( Y Z ) ( X Z )
- сокращенная ДНФ формулы D.
Минимальный набор импликант, в строках которых
имеются звездочки для всех столбцов матрицы
Квайна, состоит из конъюнктов X Y и X Z .
( X Y ) ( X Z ) - минимальная ДНФ
Значит,
формулы D.

22.

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