Приложение булевых функций к теории релейно-контактных схем

Цепи переключателей (релейно-контактные схемы) - устройство из проводников и двухпозиционных контактов замыкающие контакты - нормально разомкнутые x размыкающие контакты - нормально замкнутые x x x 1 - схема проводит ток при данных состояниях переменных f ( x1, x2 ,..., xn )   0 - схема не проводит ток при данных состояниях переменных - функция проводимости последовательное соединение x2 x1 x1 параллельное соединение f ( x1, x2 )  x1 & x2 f ( x1, x2 )  x1  x2 x2 Теорема. всякая булева функция может быть реализована с помощью релейно-контактной схемы x ~ y  x  y  & x  y  x y  x y x x x y y y Задачи теории релейно-контактных схем 1) Задача синтеза - построить схему, проводящую ток при определенных условиях Имеется одна лампочка в лестничном пролете двухэтажного дома. Построить схему так, чтобы на каждом этаже своим выключателем можно было бы включать и выключать лампочку, независимо от положения другого выключателя. Функция проводимости  ( x, y) должна менять свое значение при изменении любого из аргументов  ( x, y) y x  ( x, y)  x y  xy 1 y x 1 y x 1 1 1 1 2) Задача анализа - упрощение схем равносильные схемы - одна проводит ток тогда и только тогда, когда другая проводит ток -составлены из одних и тех же реле -обладают одинаковыми функциями проводимости f ( x, y, z )  x z  z x xy  x yz  x z y  x yz  xz y  yz  x z x z y x x x y z z y y z Двоичный полусумматор 0+0=0 0+1=1 1+0=1 1+1=10 y x 1 1 1 1 S ( x, y) - значение, записываемое в тот же разряд P( x, y) - значение, переносимое в старший разряд S ( x, y) P( x, y) 1 1 1 S ( x, y)  x y  x y P( x, y)  xy x y x y x y Одноразрядный двоичный сумматор k – номер разряда xk 1 1 1 1 yk 1 1 1 1 Sk ( xk , yk , Pk 1) Pk ( xk , yk , Pk 1) Pk 1 Sk ( xk , yk , Pk 1) Pk ( xk , yk , Pk 1) 1 1 1 1 1 1 1 1 1 1 1 1 xk yk xk yk xk yk xk xk Pk 1 Pk 1 yk xk Sk ( xk , yk , Pk 1)  xk yk Pk 1  xk yk Pk 1  xk yk Pk 1  xk yk Pk 1  yk Pk 1 yk  xk yk  xk yk Pk 1  xk yk  xk yk Pk 1 Pk ( xk , yk , Pk 1)  xk yk Pk 1  xk yk Pk 1  xk yk Pk 1  xk yk Pk 1   yk Pk 1  xk Pk 1  xk yk   yk  xk Pk 1  xk yk Приёмная комиссия в составе трех членов комиссии и одного председателя решает судьбу абитуриента большинством голосов. В случае равного распределения голосов большинство определяется той группой, в которой оказался председатель приемной комиссии. Построить автомат, обеспечивающий определение большинства голосов. председатель x1 x2 x3 x4 f 0000000011111111 0000111100001111 0011001100110011 0101010101010101 0 00 00 0 0 10 11 1 11 11 f  x2 x3x4  x1x3  x1x2  x1x4  x2 x3x4  x1 x3  x2  x4  x3 x4 00 01 11 10 x1x2 00 01 11 10 1 1 1 1 1 1 1 1 f  x1x2 x3x4  x1 x2 x3x4  x1 x2 x3 x4  x1 x2 x3x4  x1x2 x3 x4  x1x2 x3x4  x1x2 x3 x4  x1x2 x3x4 x2 x3 x4 x2 x1 x3 x4 2) Задача анализа схем x2 x3 x4 f1  x2 x3 x4 x2 x1 x3 f3  x1 f 2  x1 x2  x3  x4  x4 f 2  x2  x3  x4 f  f1  f3  x2 x3 x4  x1 x2  x3  x4  Логические интегральные схемы Логические элементы x1 x2 & И x1 x2 1 ИЛИ x1 1 НЕ 1) Задача синтеза схем Приёмная комиссия в составе трех членов комиссии и одного председателя решает судьбу абитуриента большинством голосов. В случае равного распределения голосов большинство определяется той группой, в которой оказался председатель приемной комиссии. Построить автомат, обеспечивающий определение большинства голосов. председатель x1 x2 x3 x4 f 0000000011111111 0000111100001111 0011001100110011 0101010101010101 0 00 00 0 0 10 11 1 11 11 f  x2 x3x4  x1x3  x1x2  x1x4  x2 x3x4  x1 x3  x2  x4  x1x2 x3 x4 00 01 11 10 00 01 11 10 1 1 1 1 1 1 1 1 f  x1x2 x3x4  x1 x2 x3x4  x1 x2 x3 x4  x1 x2 x3x4  x1x2 x3 x4  x1x2 x3x4  x1x2 x3 x4  x1x2 x3x4 f  x2 x3x4  x1x3  x1x2  x1x4  x2 x3x4  x1 x3  x2  x4  x1 x2 & x1 x3 & x1 x4 & x2 x3 x4 x2 x3 x4 1 f1 1 f2 & x1 x2 x3 x4 & 1 f f3 2) Задача анализа схем f 2  f1x1   x2  x3  x4 x1 f1  x2  x3  x4 & f3  x2 x3 x4 f  f 2  f3   x2  x3  x4 x1  x2 x3x4 Минимизация недоопределённых (частичных) булевых функций x3 x4 00 01 11 10 x1x2 x3 x4 00 01 11 10 x1x2 00 01 11 10 1 1 1 f  x1 00 1 01 11 10 1 1 f  x1 x3  x3 x 4 Логические сети «логические ворота» - электронная схема – электронные компоненты, собранные в цепь, имеющую несколько входов и один выход, принимающие одно из двух значений 0 или 1 (низкое или высокое напряжение) AND - ворота x1 x2 OR - ворота z NOT - ворота x1 x2 z z  x1 & x2 z  x1  x2 z x zx Теорема. всякая булева функция может быть реализована с помощью логической сети x  y  x  y  & x  y  x y  x y x y z x y z Задачи теории логических сетей 1) Задача синтеза - построить сеть у которой выход описывается определенным булевым выражением 2) Задача анализа - упрощение сетей L – сложность сети (число ворот) Эквивалентные сети - любой из возможных наборов значений переменных приводит к одинаковому значению выхода x f y z f ( x, y, z )  x yz  x z  z x xy  x z y  x yz  xz y  yz  x y f z L5 L  11