Как составить контактную схему для формулы

В начале прошлого века известный физик П. Эренфест впервые указал на возможность применения аппарата алгебры логики в технике. Эта идея нашла свое воплощение в работах советского физика В. И.Шестакова, американского математика К. Шеннона и японского инженера А. Какасима. Первыми объектами применения алгебры логики для решения технических задач были контактные схемы. Под контактными схемами мы будем понимать электрические цепи, содержащие только контакты. Каждый контакт может находиться в двух состояниях – разомкнут (0) и замкнут (1). Такие цепи мы будем изображать диаграммой, на которой возле контактов пишется или . Причем значение 1 этих переменных соответствует прохождению тогда через данный контакт, а значение 0 нет.

Если контакты X и y соединены последовательно, то цепь замкнута, когда оба контакта замкнуты и разомкнуты, когда хотя бы один из контактов разомкнут. Ясно, что такой схеме

Соответствует булева функция .

Если контакты X и y соединены параллельно то цепь замкнута, когда хотя бы один контакт замкнут и разомкнут, когда оба контакта разомкнуты. Ясно, что такой схеме

Соответствует булева функция .

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

Например, контактная схема

Реализуется булевой функцией .

Однако, поскольку одна и та же булева функция может быть выражена различными формулами, то ее реализация контактными схемами неоднозначна. Всегда можно построить много различных контактных схем, соответствующих данной функции. Такие схемы называют эквивалентными. Задача синтеза контактной схемы состоит в построении контактной схемы по заданной булевой функции, которая может быть задана как формулой, так и таблицей. В обоих случаях необходимо выразить функцию через операции конъюнкции, дизъюнкции и отрицания. Каждая операция конъюнкции соответствует последовательному соединению контактов. В результате параллельного соединения получаем контактную схему. Из множества эквивалентных схем, путем упрощения формул выделяют наиболее простую схему. Центральной проблемой синтеза контактных схем является построение для данной булевой функции более простой схемы. Часто эта проблема сводится к минимизации булевых функций, т. е. к такому их представлению, в котором соответствующие формулы содержат минимальное количество вхождений переменных.

Рассмотрим схему

Данная схема реализуется следующей формулой:

Упростим данную формулу. Используя закон дистрибутивности, получаем:

==

Следовательно, данную схему можно упростить, заменив ее следующей эквивалентной схемой:

Решим теперь следующую задачу: из контактов составить по возможности более простую схему так, чтобы она замкнулась тогда и только тогда, когда замкнуты не менее двух контактов.

Составим таблицу истинности для булевой функции, соответствующей требуемой контактной схеме

X	Y	Z
0	0	0	0
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

Найдем для данной булевой функции совершенную ДНФ:

Упростим данную формулу

==.

Данной формуле соответствует следующая контактная схема:

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

Пусть имеется некоторое устройство, имеющее n упорядоченных «входов» и один «выход», причем внутренняя структура этого устройства нас не интересует. На каждый из входов могут подаваться два сигнала, которые мы будем обозначать символами 0 и 1. При каждом наборе сигналов на входах и выходе возникает один из сигналов 0 или 1. Причем набор сигналов на входах однозначно определяет сигнал на выходе. Очевидно, что каждое такое устройство реализует булеву функцию.

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

Функция	Графическое изображение	Функция	Графическое изображении

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

Например, схема

Реализуется булевой функцией

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

Например, булева функция реализуется логической схемой

Рассмотрим построение логической схемы на примере одноразрядного сумматора, выполняющего арифметическое сложение двоичных чисел и , к-го разряда и переноса из младшего разряда . Пусть – получаемая сумма, а – перенос в старший разряд, тогда получаем следующую таблицу истинности такого сумматора.

0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Отсюда получаем

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

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

0	0	0	0	0
0	0	0	1
0	0	1	0	1
0	0	1	1
0	1	0	0	1
0	1	0	1
0	1	1	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1
1	0	1	0
1	0	1	1	0
1	1	0	0
1	1	0	1	0
1	1	1	0
1	1	1	1	1

Отсюда

Используя методы, которые будут рассмотрены в разделе 6, нетрудно упростить выражение для :

=,

Где .

Теперь строим логическую схему:

< Предыдущая		Следующая >

Релейно-контактные схемы

Укажем на применение алгебры логики к анализу и синтезу релейно-контактных схем. Среди технических средств автоматизации значительное место занимают устройства релейно-контактного действия. Они находят широкое применение в телефонии, телеуправлении, автоматике и телемеханике, на железнодорожном транспорте, в вычислительной технике. Сейчас при конструировании таких устройств все больше и больше используется алгебра логики. Впервые идея использования алгебры логики для построения автоматических устройств была выдвинута в 1910 году известным физиком П.Эренфестом. Но только в 30-х годах эта идея нашла свое воплощение в работах советского физика В.И. Шестакова, американского математика К.Шеннона и японского инженера А.Накосима.

Контактная схема представляет собой устройство из проводников и контактов, связывающих полюса источника тока. Контакт бывает в двух состояниях:

а) контакт разомкнут и тогда ему приписывают 0;

б) контакт замкнут и тогда ему приписывают 1.

Контакт «не » ( ) – это контакт, который работает в противоположном режиме с , т.е. когда контакт замкнут, контакт обязательно разомкнут.

Дизъюнкции ставится в соответствие схема, состоящая из параллельного соединения контактов X, Y, так как цепь будет замкнута тогда и только тогда, когда замкнут хотя бы один из контактов.

Конъюнкции ставится в соответствие схема, состоящего из последовательного соединения контактов X, Y, так как цепь будет замкнута тогда и только тогда, когда замкнуты оба контакта одновременно.

Каждый контакт подключен к некоторому реле. В схеме одинаковыми буквами обозначаются контакты, подключенные к одному и тому же реле. Всей схеме ставится в соответствие булева функция F, которая равна 1, если схема проводит ток, и 0 в противном случае. Эта функция называется функцией проводимости схемы, а ее таблица – условиями работы схемы. Две схемы с одинаковыми функциями проводимости называются равносильными. Средства алгебры высказываний позволяют упрощать схемы, используя отношение равносильности формул алгебры высказываний.

□ По данной схеме запишем формулу, определяющую функцию проводимости, и упростим ее:

.

Таким образом, – функция проводимости и

§5. Решение логических задач методами алгебры логики.

Под логической задачей будем понимать задачу, где основным видом деятельности является выявление отношений между объектами задачи, а не нахождение количественных характеристик объектов. Суть применения алгебры логики к решению логических задач состоит в том, что, имея конкретные условия логической задачи, стараются записать их в виде формулы алгебры логики. В дальнейшем путем равносильных преобразований упрощают полученную формулу. Простейший вид формулы, как правило, приводит к ответу на все вопросы задачи.

Покажем на ряде конкретных примеров, как использовать возможности алгебры логики для решения элементарных логических задач.

Пример 1. При составлении расписания уроков на некоторый день учителя просили, чтобы их уроки были:

1. математик – первым или вторым;

2. историк – первым или третьим;

3. литератор – вторым или третьим.

Можно ли удовлетворить просьбы всех учителей?

=<Математика будет первым уроком>;

= <Математика будет вторым уроком>;

= <История будет первым уроком>;

= <История будет третьим уроком>;

= <Литература будет вторым уроком>;

= <Литература будет третьим уроком>.

Тогда на языке алгебры эту задачу можно записать в виде формулы , после равносильных преобразований которой можно будет дать ответ на вопрос задачи:

Выяснили, что имеется две возможности:

1. , , ;

2. , , .

Вопросы для самоконтроля по теме «Логика высказываний»

1. Что понимается под высказыванием? Привести примеры.

2. Являются ли высказываниями следующие предложения:

а) два плюс два равно пяти;

б) функция – периодическая;

в) существует рациональное число такое, что х > 7.

3. Определить операции отрицания, дизъюнкции, конъюнкции, импликации, эквиваленции и задать их с помощью таблиц истинности.

4. Найти истинностные значения следующих высказываний:

а)

б) ;

в) .

5. Что понимается под формулой алгебры высказываний?

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

а) для , , ;

б) для , .

7. Построить таблицу истинности формулы .

8. Что называется тождественно истинной (ложной) формулой? Проверить, является ли каждая из формул тождественно истинной:

а)

б) .

9. Какие формулы называются равносильными? Как доказать равносильность формул? Проверить равносильность

.

10. Записать первые десять основных равносильностей алгебры высказываний. Доказать законы поглощения и законы де Моргана.

11. Записать законы двойного отрицания; исключения импликации; введения дизъюнкции; введения конъюнкции; замены эквиваленции; контрапозиции; противоположностей; доказательства от противного; транзитивности импликации; транзитивности эквиваленции. Обосновать законы доказательства от противного и закон контрапозиции.

12. Упростить формулу .

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

14. Перевести предложение на логический язык и построить его отрицание: «Если вечером я буду не занята, то пойду в кино или на дискотеку».

15. Упростить релейно-контактную схему:

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

17. Один из братьев Витя, Толя, Коля разбил окно. В разговоре участвуют еще двое братьев – Андрей и Дима.

– Это мог сделать только Витя или Толя – сказал Андрей.

– Я окно не разбивал, – возразил Витя, – Коля тоже.

– Вы оба говорите неправду, – заявил Толя.

– Нет, Толя, один из них сказал правду, а другой неправду, – возразил Дима.

–Ты, Дима, неправ, – вмешался Коля.

Их отец, которому, конечно, можно доверять, уверен, что трое братьев сказали правду. Кто разбил окно?

Источник

Анализ и синтез релейно-контактных схем

Одно из применений алгебры высказываний – анализ и синтез релейно-контактных схем.

Еще в 1910 году физик П.С. Эренфест указал на возможность применения аппарата алгебры логики при исследовании релейно-контактных схем. Каждой схеме можно поставить в соответствие некоторую формулу алгебры высказываний, и каждая формула алгебры высказываний реализуется с помощью некоторой схемы.

Рассмотрим 2-х-полюсные переключатели, т.е. такие, которые имеют два состояния: «замкнуто» — 1, «разомкнуто» — 0. На схеме будем изображать:

Определение 7. Переключатель, который сблокирован с X так, что он замкнут, если X разомкнут, и разомкнут, если X замкнут, называется инверсным и обозначается .

Конъюнкция двух высказываний X и Y будет представлена двухполюсной схемой с последовательным соединением двух переключателей X и Y.

Эта схема пропускает ток тогда и только тогда, когда истины и X, и Y одновременно, то есть истина конъюнкция X&Y.

Дизъюнкция двух высказываний X и Y изобразится двухполюсной схемой с параллельным соединением двух переключателей X и Y.

X Y

Эта схема пропускает ток в случае, если истинно высказывание X или истинно высказывание Y, то есть истина дизъюнкция X Y.

Таким образом, всякую булеву формулу можно трактовать как некоторую последовательно-параллельную схему от 2-х-полюсных переключателей. Все свойства булевых операций переносятся на соответствующие операции над переключателями. Формула, которую можно составить для каждой схемы называется функцией проводимости схемы, а таблица значений – условиями работы схемы.

Определение 8. Две схемы называются равносильными, если имеют одинаковые функции проводимости.

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

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

Задача 1.Составить РКС, обладающая следующей функцией проводимости:

Задача 2.Составить РКС обладающая следующей функцией проводимости:

Задача 3.Составить РКС обладающая следующей функцией проводимости:

Ей соответствует функция проводимости:

F(X,Y,Z)

F(X,Y,Z)

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

Ей соответствует функция проводимости:

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

Ей соответствует функция проводимости:

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

Данной схеме соответствует функция проводимости:

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

Данной схеме соответствует функция проводимости:

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

Данной схеме соответствует функция проводимости:

Задача 10.Построить РКС с четырьмя переключателями, которая проводит ток тогда и только тогда, когда замыкаются не все переключатели, а только некоторые из них.

Составим таблицу значений функции проводимости F (X, Y, Z, T) этой схемы:

В правом столбце звездочками отметим те строки, на которых функция F (X, Y, Z, T) обращается в 0, запишем для неё выражение, используя СКНФ, потому что наборов значений аргументов, на которых функция обращается в 0, значительно меньше, чем наборов значений аргументов, на которых функция обращается в 1, и значит, СКНФ будет более простой, чем СДНФ:

Задача 11. Построить схему с тремя переключателями, которая замыкается тогда и только тогда, когда замкнут либо один, либо два переключателя. При построении использовать не более шести контактов.

Составим таблицу значений функции проводимости F (X, Y, Z) этой схемы:

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

F (X, Y, Z, T) обращается в 1, запишем для неё выражение, используя СКНФ, потому что наборов значений аргументов, на которых функция обращается в 0, значительно меньше, чем наборов значений аргументов, на которых функция обращается в 1, и значит, СКНФ будет более простой, чем СДНФ:

Задача 12.Требуется составить схему с четырьмя переключателями X, Y, Z, T. Схема должна проводить ток тогда и только тогда, когда будут замкнуты переключатели X и Y или Z и T.

Составим таблицу значений функции проводимости F (X, Y, Z, T) этой схемы:

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

F (X, Y, Z, T) обращается в 1, запишем для неё выражение, используя СДНФ:

Задача 13.Построить контактную схему для оценки результатов некоторого спортивного соревнования тремя судьями при следующих условиях: судья, засчитывающий результат, нажимает имеющуюся в его распоряжении кнопку, а судья, не засчитывающий результат, кнопки не нажимает. В случае, если кнопки нажали не менее двух судей должна загореться лампочка (положительное решение судей принято простым большинством голосов).

Работа РКС описывается функцией Буля трех переменных F (X, Y, Z), где переменные высказывания X, Y, Z означают:

Таблица истинности функции F (X, Y, Z) имеет вид:

X Y Z	F(X, Y, Z)
1 1 1
1 1 0
1 0 1
0 1 1
1 0 0
0 1 0
0 0 1
0 0 0

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

Источник

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

Определение:

Контактная схема (англ. contact circuit) представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание.

Определение:

Контакт (англ. contact) — ребро схемы, помеченное символом переменной или ее отрицанием. Каждому ребру в схеме сопоставляется какая то переменная (не обязательно каждой переменной сопоставляется ребро)

Принцип работы

Определение:

Замкнутый контакт (англ. closed contact) — контакт схемы, над которым написана или значение переменной равно .

Определение:

Разомкнутый контакт (англ. open contact) — контакт схемы, над которым написан или значение переменной равно .

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

Построение контактных схем

Представление одного из базисов в контактных схемах

Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации трех логических элементов:

Построение контактных схем

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

Примеры построения некоторых функций

Задача о минимизации контактной схемы

Определение:

Две контактные схемы называются эквивалентными (англ. equivalent contact circuits), если они реализуют одну и ту же булеву функцию.

Определение:

Сложностью контактной схемы (англ. the complexity of the contact circuit) называется число ее контактов.

Определение:

Минимальная контактная схема (англ. minimal contact circuit) — схема, имеющая наименьшую сложность среди эквивалентных ей схем.

Определение:

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

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

• Осуществляем переход от контактной схемы к её булевой функции .
• Упрощаем , то есть отыскиваем функцию (на том же базисе, что и , равносильную и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать карты Карно.
• Строим схему , реализующую функцию .

Теорема:

Любую булеву функцию можно представить контактной схемой, сложностью

Доказательство:

Пусть дана функция и она представлена в ДНФ Дерево конъюнктов для 2-х переменных Возьмем дерево конъюнктов для переменных (см. картинку). Очевидно, что от вершины до “нижних” вершин дерево можно добраться за , а ребер у такого дерева Соединим нижние вершины, которые соответствуют конъюнктам функции, с вершиной контактами, над которыми написана . От этого в схему добавится не более, чем ребер и тогда сложность останется . В результате можно построить контактную схему для любой функции со сложностью

См также

• Построение функциональной схемы

Источники информации

• Контактные схемы
• Encyclopedia of Math — Contact sheme
• Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике
• М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы.

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

Простой импликантой частичной функции f называется элементарная конъюнкция К, для которой выполняются условия:

1) ∃_αК(α) = 1, f(а) = 1;

2) ∀_β f(B) = 0 → K(B) = 0;

3) если из импликанты К удалить любую букву, получится
формула К’ такая, что ∃_γК'(γ) = 1, f(γ) = 0.

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

Критерий существования декомпозиции заданного вида:

Частичная функция f представляется в виде
f(u,v,w) = g(u,w,h(u,v)) тогда и только тогда для каждого фиксированного набора а значений переменных из множества и таблица функции f_α(v,w) допускает доопределение до таблицы, со держащей столбцы не более двух различных типов.

Контактной схемой называется неориентированный граф,
каждому ребру (контакту) которого приписан символ перемен-
ной в некоторой степени и выделены две вершины, которые на-
зываются полюсами.

Частная производная булевой функции f(x₁ , x₂ ,…, x_n) по пременной X_i определяется так:

fx_i = f(x₁, …,x_i-1, 0, x_i+1, …, x_n) + f(x₁, …,x_i-1, 1, x_i+1, …, x_n).

Тестом относительно множества G = {g_i} попарно различных
булевых функций называется множество наборов значений переменных Т такое, что ∀_i∀_k≠i∃_i∈T(g_i(e) ≠ g_k(e)).

Задание 2.6.1

1. Реализовать частичную функцию f(x,y,z,w) формулами
над базисом конъюнкция, дизъюнкция, отрицание четырьмя спо-
собами:

а) методом Квайна;

б) исходя из минимальной ДНФ, найден-
ной с помощью карт Карнау;

в) исходя из минимальной КНФ,
найденной с помощью карт Карнау;

г) методом последовательно-
го разложения по переменным xyzw.

2. Для простейшего представления построить схему из функ-
циональных элементов типа конъюнкция, дизъюнкция, отри-
цание.

3. Реализовать простейшее представление контактной схемой.

4. Проверить возможность разделительной декомпозиции
функции f(x,y,z,w) в виде g(u,v,h(p,t)), где u,v,p,t —некоторая
перестановка переменных xyzw.
Если декомпозиция указанного вида возможна, реализовать её
схемой с ветвлениями из функциональных элементов типа конъ-
юнкция, дизъюнкция, отрицание. Указать сложность построен-
ной схемы.

Таблица 2.6.1

№	f(x,y,z,w)		№	f(x,y,z,w)
1	–011-11-0–011-		11	-1-0-0111–1-011
2	1–10-0-010–01-		12	11–01-0-01-011-
3	-0-1-001–1110-1		13	1–101-1–1000-1
4	11–0-11-1-1-100		14	-010-1-001-1-1-0
5	–100-11–01-101		15	0-0-11-1-1101–1
6	1–101—100-110		16	1–01-11-0-0110-
7	0-110-1010–1-1-		17	0–01-1-11101-11
8	10-1-10010–10–		18	11—0-1-0100-10
9	-10-101–1-011-0		19	0-111–10-1-00-1
10	1–0-110-1-011-0		20	1-10—011-0011-
21	01-1-10-011–01-		26	-0-0-1111-0-00-1
22	–1-01-000-1111-		27	11-00-10–0-00-1
23	0-1–1-00-11-001		28	–011-11-0-0-001
24	-10–0111-10–01		29	10—0111–011-1
25	1–01-1–1010-10		30	-1-10-110-1-101-

Пример решения задания 2.6.1 Решим задание 2.6.1 для функции f(x,y,z,w) = (-10101—- 0-11-0). Запишем таблицу функции f в виде карты Карнау (табл. 2.6.1а). Для отыскания сокращённой ДНФ выпишем в список М0 все нулевые наборы функции, а в М1 — единичные наборы (табл. 2.6.1b). Будем перебирать все единичные наборы из списка М1 который запишем в виде первого столбца. Для каждого из единичных наборов будем заменять последовательно его символы на неопределённый символ “-” и смотреть, не будет ли совпадать с точностью до неопределённого символа полученная комбинация с каким-либо набором, вошедшим в список М0. Если совпадение есть, переходим к следующему символу, а если нет — помечаем набор “крестиком”, выписываем результат замены во второй столбец и переходим к следующему символу или к следующему набору.

Затем совершаем аналогичную процедуру над наборами из второго столбца и так далее. В результате наборы, не помеченные крестиком, будут соответствовать простым импликантам, из которых состоит сокращенная ДНФ (табл. 2.6.1с). Итак, простые импликанты нашей функции таковы: xyw, yz, xw , zw , yw, xz. а) Изобразим матрицу Квайна (табл. 2.6.Id), в которой строки соответствуют единичным наборам функции, а столбцы простым импликантам.

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

(2∨3∨4∨5)-(3∨5)-(3∨4)-(1∨6)-(4∨6) = (3∨5⋅4)>(6∨1⋅4) =
= 3⋅6∨5⋅4⋅6∨3⋅1⋅4∨5⋅1⋅4.

Видим, что наименьшую длину имеет символическая конъюнкция 3⋅6, которая соответствует минимальной ДНФ xw ∨ xz.

Сложность найденной минимальной ДНФ равна 4.

б) При нахождении минимальной ДНФ с помощью карты
Карнау (табл. 2.6.1е), мы доопределяем функцию f так, чтобы покрытие имело более простой вид.

Тогда все единицы покроются двумя квадратами 2×2 xw и xz,
соответствующая минимальная ДНФ совпадает с ДНФ, найденной в п. а).

в) Для отыскания минимальной КНФ покрываем нули карты
Карнау (табл. 2.6.1f) двумя квадратами 2×2: x ∨ w и x ∨ z .

Соответствующая минимальная КНФ такова: (х ∨ w) ⋅ (x ∨ z).

Сложность её равна 4.

г) Проведём разложение по набору переменных xyzw. На первом этапе, раскладывая по переменной х, имеем:

f(x, у, z, w) = x ⋅ f(0, у, z,w) ∨ x ⋅ f(1, у, z, w).

Изобразим таблицы функций f(0,y,z,w) и f(1,y,z,w)
(табл. 2.6. 1g).

Каждая из функций f(0,y,z,w) и f(1,y,z,w) не доопределима
до константы, но f(1,y,z,w) доопределима до z.
Изобразим таблицы (табл. 2.6.1h) функций f(0,0,z,w) и
f(0,1,z,w).

Видим, что f(0,0,z,w) и f(0,1,z,w) доопределимы до w и 1 соответственно. Получаем разложение исходной функции: f(x, у, z, w) = x⋅ (y ⋅ w v у ⋅ 1) v х⋅ z = x ⋅ (w v у) v х⋅ z . Во время упрощений мы применяли тождества с константами и правило вычёркивания. Сложность полученной формулы оказалась равной 5. 2) В качестве простейшего представления возьмём минимальную ДНФ xw v xz и реализуем её схемой из функциональных элементов (рис. 2.6.1, а). Реализуем ту же минимальную ДНФ контактной схемой (рис. 2.6.1, b). 3) Реализуем ту же минимальную ДНФ контактной схемой (рис. 2.61, b). 4) Запишем двумерную таблицу функции f (табл. 2.6.1i). Видим, что таблица допускает доопределение до строк только двух типов (табл. 2.6.1 j).

Значит, f(x,y,z,w) допускает разделительную декомпозицию
вида f(x,y,z,w) = g(z,w,h(x,y)).

Найдём вид функций g и h.

т.е. h(x,y) = (1110), h(x,y) = x   y.

Строкам I типа соответствует функция φ(z, w) = (0101) = w.

Строкам II типа соответствует функция Ψ(z, w) = (1101) = z.

Тогда функция f выражается через h, φ, Ψ так:

f(x, y, z, w) = h(x, у) ⋅ φ(z, w) v h(x, y) ⋅ Ψ(z, w) =
= (x v y) ⋅ w v (x v y) ⋅ z.

Соответствующая схема из функциональных элементов с ветвлениями будет иметь вид (рис. 2.6.1, с).

Сложность схемы равна количеству функциональных элементов, её образующих, т. е. 8.

Задание 2.6.2

1. Представить функцию f(x₁,x₂,x₃,x₄,x₅) декомпозицией
вида g(x_i,x_k,x_p,h(x_i,x_m,x_n)), где x_ix_kx_px_ix_mx_n —некоторая
перестановка переменных x₁,x₂,x₃,x₄,x₅.

2. Реализовать найденную декомпозицию схемой с ветвлениями, используя функциональные элементы типа отрицание, конъюнкция и дизъюнкция. Указать сложность полученной схемы.

3. Построить минимальную ДНФ с помощью карт Карнау,
указать сложность найденной формулы.

Таблица 2.6.2

№	i	f(x1,x2,x3,x4,x5)
1	1	1-01	1101	10–	1-0-	1-1-	111-	000-	-011
2	2	1-1-	00-0	-001	-001	–0-	11-0	01-1	0-01
3	3	110-	01-0	1-11	0-00	1-11	011-	111-	011-
4	4	-011	-000	-111	-000	1-10	100-	11-0	-001
5	5	0-10	-000	10-0	01-1	0010	-11-	–11	-11-
6	1	-001	–01	1-01	-101	–11	1–1	00-0	001-
7	2	-11-	0-00	0–1	-00-	00-0	-10-	-101	-10-
8	3	-1-0	010-	11–	01-0	11–	0110	–11	0110
9	4	0-1-	00–	01-1	0-00	10–	10-1	1-1-	100-
10	5	-010	-00-	-1–	0101	-01-	0-11	-1-1	1–1
11	1	10–	11-1	-001	1-01	-1-1	11-1	0-0-	0-11
12	2	–11	00-0	-001	0001	–00	1-00	010-	-101
13	3	1-00	-100	1-11	01-0	1-1-	011-	1–1	0-10
14	4	–11	00-0	011-	-00-	1010	-001	-110	-0-1
15	5	00-0	00-0	1010	0-01	0-10	-111	1-11	–1-
16	1	-00-	1-01	-0-1	110-	111-	11-1	000-	0–1
17	2	111-	00-0	0-0-	000-	000-	1-00	-101	0-0-
18	3	-10-	01-0	1-11	0-00	1-11	–10	111-	0110
19	4	001-	-000	-111	00-0	101-	1001	1-1-	1001
20	5	0-1-	000-	101-	01-1	00-0	01-1	11-1	111-
21	1	10-1	110-	1-01	-101	-111	-11-	0-00	0011
22	2	-1-1	0-0-	-0–	0001	-0-0	1100	-1-1	0101
23	3	1100	-10-	-111	010-	-1-1	0-10	1-11	-1-0
24	4	0-11	-000	0-11	0-00	1-10	10-1	111-	10-1
25	5	-01-	0-00	-0-0	0-01	-01-	0–1	1-11	1-11
26	1	1001	11-1	1-01	–0-	1-11	1-1-	0-00	0-1-
27	2	111-	0-00	0-01	0-01	00–	110-	0101	01-1
28	3	-100	01–	1111	010-	1-1-	01-0	1111	0-10
29	4	001-	0000	01-1	00-0	10-1	1001	–1-	10-1
30	5	0-10	00–	101-	01-1	001-	0111	-1-1	111-

Пример решения задания 2.6.2

Решим задание 2.6.2 для i = 5 и функции

f(x₁,x₂,x₃,x₄,x₅) = (10-10–0 –01 -1– 0-10 010- 1–0 –1-).

Выпишем значения функции f в виде таблицы (табл. 2.6.2а):

Выясним, возможна ли декомпозиция вида

f = g(x₅,x₁,x₂,h(x₅,x₃,x₄))     (*)

или

f = g(x₅,x₃,x₄,h(x₅,x₁,x₂)).     (**)

Для этого выпишем двумерные таблицы функции f для
х₅ = 0 и x₅ = 1 так, чтобы в заголовках строк и столбцов были
написаны наборы х₁х₂ и х₃х₄ соответственно. Получим
(табл. 2.6.2b).

Как видим, таблица функции f, соответствующая х₅ = 0, не
доопределима так, чтобы использовались столбцы только двух
типов, и не доопределима до вида, в котором используются строки только двух типов. Значит, декомпозиция вида (*) или (**)
невозможна.

Проверим, допустима ли декомпозиция вида

f = g(x₅,x₂,x₃,h(x₅,x₁,x₄)) или f = g(x₅,x₁,x₄,h(x₅,x₂,x₃)).

Для этого выпишем двумерные таблицы функции f для
х₅ = 0 и х₅ = 1 так, чтобы в заголовках строк и столбцов были написаны наборы х₂х₃ и х₁х₄ соответственно. Получим (табл. 2.6.2с).

Видим, что в этом случае обе таблицы допускают доопределение до столбцов двух типов.

Для х₅ = 0 столбцам I типа соответствует функция

φ⁽⁰⁾(x₂,x₃) = (1001) = x₂, x₃ ∨ x₂,x₃, а столбцу II типа — функция
Ψ⁽⁰⁾(x₂,x₃) = (0101) = x₂.

Введём функцию

Вектор значений h⁽⁰⁾(x₁,x₄) равен (1101), значит.

h⁽⁰⁾(x₁,x₄) = x₁,x₄

f(x₁,x₂,x₃,x₄,0) = h⁽⁰⁾(x₁,x₄) ⋅ φ⁽⁰⁾(x₂,x₃) ∨ h⁽⁰⁾(x₁,x₄) ⋅ Ψ⁽⁰⁾(x₂,x₃) =

= (x₁,x₄)(x₂,x₃ ∨ x₁ ∨ x₄⋅ x₂

Рассмотрим таблицу, соответствующую х₅ = 1.

Столбцам I типа соответствует функция

φ⁽¹⁾(x₂,x₃) = (0101) = хx₃, столбцам II типа — функция

Ψ⁽¹⁾(x₂,x₃) = (1110) = x₂ ∨ x₃.

Введём функцию

Вектор значений h⁽¹⁾(x₁,x₄) равен (1001), значит,

h⁽¹⁾(x₁,x₄) = x₁,x₄ ∨ x₁,x₄.

f(x₁,x₂,x₃,x₄,1) = h⁽¹⁾(x₁,x₄) ⋅ φ⁽¹⁾(x₂,x₃) ∨ h⁽¹⁾(x₁,x₄) ⋅ Ψ⁽¹⁾(x₂,x₃) =

=(x₁,x₄ ∨ x₁,x₄)x₃ ∨ x₁,x₄ ∨ x₁,x₄ ⋅ x₂ ∨ x₃.

Получаем искомое представление для f:

f(x₁,x₂,x₃,x₄,x₅) =x₅ ⋅ f(x₁,x₂,x₃,x₄,0) ∨ x₅ ⋅ f(x₁,x₂,x₃,x₄,1)

= x₅((x₁ ∨ x₄)(x₂x₃ ∨ x₂,x₃) ∨ x₁ ∨ x₄ ⋅ x₂) ∨ x₅((x₁x₄ ∨ x₁x₄)x₃ ∨ x₁,x₄ ∨ x₁,x₄ ⋅(x₂ ∨ x₃)).

2. Реализуем это представление схемой с ветвлениями.

Ввиду громоздкости полученного выражения реализуем
схемами S₀ (рис. 2.6.2, а) и S₁ (рис. 2.6.2, b) соответственно f(x₁,x₂,x₃,x₄,0) иf(x₁,x₂,x₃,x₄,1), а саму функцию реализуем блок-схемой S (рис. 2.6.2, с).

Сложность построенной схемы равна 24.

3. Найдём минимальную ДНф с помощью карты Карнау (табл. 2.6.2d). Все единицы карты Карнау могут быть покрыты двумя двухслойными прямоугольниками и тремя однослойными. Минимальная ДНФ будет иметь вид: x3 ⋅ x5 ∨ x2 ⋅ x3 ⋅ x4 ⋅ x5 ∨ x1 ⋅ x2 ⋅ x3 ⋅ x5 ∨ x1 ⋅ x4 ⋅ x5 ∨ x1 ⋅ x2 ⋅ x5 Её сложность равна 16.

Задание 2.6.3

1. С помощью частных производных найти оптимальный для
метода каскадов порядок дизъюнктивного разложения функции
f(x,y,z,w) по её переменным на первых двух этапах.

2. Используя результаты п. 1, построить контактную схему методом каскадов, указать сложность построенной контактной схемы.

Таблица 2.6.3

№	f(x,y,z,w)		№	f(x,y,z,w)
1	1110 0110 1010 1101		16	0111 0101 1101 1111
2	0011 1100 1101 0111		17	0010 1011 1101 1110
3	0110 1101 1100 1111		18	0011 1110 1101 0000
4	1110 0111 1100 0111		19	0101 1010 1111 1101
5	0010 1110 1111 0011		20	0101 1101 1110 0011
6	1110 1101 0010 1111		21	0010 1101 1001 0110
7	1110 1010 0010 0110		22	1110 1101 0101 1010
8	1110 1000 1111 0110		23	0010 1010 1110 1111
9	1101 0110 1110 0001		24	0110 1001 1100 1101
10	1011 0111 1010 0110		25	0010 0000 1000 1110
11	1101 0001 0010 1111		26	0010 1010 0001 1111
12	1110 0100 1110 1001		27	0101 1101 0000 1011
13	0001 1000 1100 0110		28	1101 1000 0110 1110
14	1101 1111 0010 1101		29	1000 0110 0101 1001
15	1001 1101 0011 1000		30	1101 0111 1101 0011

Пример решения задания 2.6.3 Решим задание 2.6.3 для функции f(x, у, z, w) = = (1010 0100 0100 1010). Запишем таблицу функции f(x,y,z,w) в виде карты Карнау (табл. 2.6.3а).

Найдём полином Жегалкина:

Определим оптимальный для метода каскадов порядок разложения. По определению, fx(x,y,z,w) = f(0,y,z,w) + f(1,y,z,w). Таблица для fx имеет вид (табл. 2.6.3b). Видим, что | fx |= 6. Аналогично, fy(x,y,z,w) = f(x,0,z,w) + f(x,1,z,w). Таблица для fy имеет вид (табл. 2.6.3с). Видно, что | fy |= 6. Продолжаем отыскание частных производных. fy (x,y,z,w) = f(x, у,0, w) + f(x,y,1, w). Таблица для fz, имеет вид (Табл. 2.6.3d). Заметим, что | fz |= 2. И далее, fw(x,y,z,w) = f(x, у, z,0) + f(x, у, z,1). Таблица для fw имеет вид (табл. 2.6.3е).

Как видно, | f_w |= 6.

Так как набольшее число единиц в таблице имеют f_x, f_y
и f_w, то на 1 и 2 этапах метода каскадов разложение ведём по
любой из переменных x,y,w. Выберем, например, в качестве первой переменной, по которой будем проводить разложение, х,
а второй — w.

Получим: f(x,y,z,w) = x ⋅ f(0,y,z,w) ∨ х ⋅ f(1,y,z,w).

Выпишем таблицы функций f(0,y,z,w) и f(1,y,z,w)
(табл. 2.6.3f).

3. Строим контактную схему методом каскадов (рис. 2.6.3, а). На втором этапе разложение ведём по переменной w.

f₀(y,z,w) = w ⋅ f₀(y,z,0) ∨ w ⋅ f₀(y,z,1) =

= w ⋅ (1 + y + 0 +0) ∨ w ⋅ (1 + y + 1 +yz) =

= w ⋅ (1 + y) ∨ w ⋅ (y + yz) = w ⋅ y ∨ w ⋅ y ⋅ (1 + z) = w ⋅ y ∨ w ⋅ y ⋅ z.

f₁(y,z,w) = w ⋅ f₁(y,z,0) ∨ w ⋅ f₁(y,z,1) =

= w ⋅ (y + 0) ∨ w ⋅ (y+1+z+yz) = w ⋅ y ∨ w ⋅ f₁₁(y,z).

Осталось разложить функцию f₁₁(y,z)

f₁₁(y,z) = z ⋅ f₁₁(y,0) ∨ z ⋅ f₁₁(y,1) = z ⋅ (y+1) ∨ z ⋅ (y+1+1+y) =

z ⋅ y ∨ z ⋅ 0 = z ⋅ y.

Изобразим полученную контактную схему (рис. 2.6.3, b).

Сложность построенной схемы равна количеству контактов
в ней, т. е. 8.

Задание 2.6.4

Для функции f(x,y,z,t), заданной своей ДНФ:

1. Построить таблицу данной булевой функции.
2. Найти минимальную ДНФ. Исходя из минимальной ДНФ,
   построить контактную схему.
3. Построить контактную схему методом каскадов, отыскав
   оптимальный порядок разложения переменных с помощью частных производных.
4. Исходя из простейшей контактной схемы, построить минимальный тест для нахождения неисправности:
   а) для вариантов с чётными номерами — типа замыкания
   ровно одного контакта
   
   б) для вариантов с нечётными номерами —типа размыкания
   ровно одного контакта.

Таблица 2.6.4

№	f(x,y,z,t)		№	f(x,y,z,t)
1	xyz ∨ xyz ∨ xyzt ∨ yzt		4	xyzt ∨ xzt ∨ xyzt
2	xyzt ∨ xzt ∨ xyzt ∨ xzt ∨ yz		5	xyzt ∨ xyzt ∨ xzt
3	xyzt ∨ xyzt ∨ xyzt ∨ xzt		6	xzt ∨ xyzt ∨ yzt
7	xyzt ∨ xyt ∨ xyzt ∨ xyt zt		19	xyz ∨ yzt ∨ xyzt
8	xyz ∨ xyt ∨ xyzt		20	xyzt ∨ xyzt ∨ xyzt ∨ yzt
9	xyzt ∨ xyzt ∨ xyt		21	xyt ∨ xyt ∨ xyzt yzt
10	xyzt ∨ xyzt ∨ xyzt ∨ xyt		22	xyzt ∨ xzt ∨ xyzt yzt
11	xzt ∨ xyt ∨ xzt ∨ xyzt		23	xyzt ∨ xyz ∨ xyzt
12	xyzt ∨ xyz ∨ xyzt ∨ xyz ∨ xt		24	xyzt ∨ xyzt ∨ yzt
13	xyzt ∨ xyz ∨ xyzt		25	xyzt ∨ xyzt ∨ xyzt ∨ yzt
14	xyzt ∨ xyzt ∨ xyz		26	xzt ∨ xzt ∨ xyzt ∨ yzt
15	xyzt ∨ xyzt ∨ xyz ∨ xyzt		27	xyzt ∨ xyt ∨ xyzt ∨ xyt ∨ yz
16	xyt ∨ xyz ∨ xyzt xyt		28	xyzt ∨ yzt ∨ xyzt
17	xyzt ∨ yzt ∨ xyzt ∨ xyz ∨ xy		29	xyzt ∨ xyzt ∨ xzt
18	xyzt ∨ yzt ∨ xyzt		30	xyzt ∨ xyzt ∨ xyzt ∨ xyz

Пример решения задания 2.6.4 Решим задание 2.6.4 для f(x,y,z,t) = x yzt ∨ xy ∨ xyt ∨ xzt, выбрав в п. 4 неисправность типа размыкания ровно одного кон- такта. 1. Построим таблицу функции f{x,y,z,t) в виде карты Карнау (табл. 2.6.4а). 2. Все единицы карты Карнау покрываем тремя прямоугольниками. Соответствующая минимальная ДНФ будет иметь вид yzt v xtv xz. Упростим формулу: yzt ∨ xt ∨ xz = yzt ∨ x(t ∨ z). Реализуем это представление контактной схемой (рис. 2.6.4, а). 3. При отыскании оптимального порядка разложения по методу каскадов заметим, что | fx | = 6,| fy | = 2, | fz | = 2, | ft | = 2.

Так что на первом шаге разложение будем производить по
переменной х, а на втором этапе можно проводить разложение
по любой оставшейся переменной, например, по у.

Получаем:

f(x, у, z, t) = x ⋅ f(0, у, z, t) ∨ x ⋅ f(1, у, z,t) =

= x ⋅ (yzt) ∨ х ⋅ (y ∨ ytv zt) =

= хyzt ∨ х ⋅ (у ∨ t ∨ zt) = xyzt ∨ x ⋅ (y ∨ t ∨ z).

Разложение по у нет необходимости делать.

Строим контактную схему (рис. 2.6.4, b).

4. Так как контактная схема, полученная в п. 2, имеет более
простой вид, будем работать с ней.

Занумеруем все контакты схемы (рис. 2.6.4, с).

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

Пусть f₀(x,y,z,t) = f(x,y,z,t), а при неисправности i-го контакта схема реализует функцию f_i(x, у, z,t).

Если исправно работающая контактная схема на некотором
наборе аргументов принимает значение 0, значит, на её изображении между полюсами нет цепи из сплошных линий. Ясно, что
при наличии неисправности типа размыкания контакта на том же
наборе аргументов полюсы контактной схемы тем более не соединены цепью из сплошных линий. Значит, на всех нулевых наборах функции f(x,y,z,t) все функции f_i(x,y,z,t), i = 1,2,…,6
также принимают значение, равное 0.

При построении теста нас не интересуют наборы аргументов, на которых значения всех функций совпадают, поэтому напишем таблицу всех функций fi(x,y,z,t), i = 1,2,…,6, вписывая в неё только те наборы аргументов, на которых исходная функция равна 1. При заполнении таблицы для каждого набора аргументов изобразим схему. Например, для набора (0,0,1,0) схема примет вид (рис. 2.6.4, d).

Видим, что цепь из сплошных линий, соединяющая полюсы схемы, разрывается, если разомкнут 4, 5 или 6 контакт, т. е. на наборе
(0,0,1,0) значение 0 принимают функции f₄, f₅ и f₆. Изобразим
вид контактной схемы на всех единичных наборах функции
f(x,y,z,t) (рис. 2.6.4, е).

Заполняем “таблицу неисправностей”, вписывая для каждого
набора аргументов нули в столбцы, соответствующие функциям с
номерами, записанными в кружочках. Получим следующую таблицу (табл. 2.6.4b).

Таблица 2.6.4b

xyzt	f0	f1	f2	f3	f4	f5	f6
0100	1	1	1	1	0	0	0
1000	1	0	0	1	1	1	1
1001	1	0	1	1	1	1	1
1010	1	1	1	1	0	0	0
1011	1	0	1	0	1	1	1
1100	1	0	0	1	1	1	1
1101	1	0	1	1	1	1	1
1111	1	0	1	0	1	1	1

Видим, что некоторые столбцы таблицы совпадают. Это означает, что неисправности типа размыкания одного контакта неотличимы в случае разомкнутости 4, 5 или 6 контактов.

Объединяем неотличимые неисправности в классы неисправностей.

Получим 5 классов:

g₀ = {f₀}, g₁ = {f₁}, g₂ = {f₂}, g₃ = {f₃}, g₄ = {f₄, f₅, f₆}.

Строим таблицу классов неисправностей, таблицу, не содержащую одинаковых столбцов.

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

Получим (табл. 2.6.4с):

Выясним, какие из наборов 1-5 войдут в минимальный тест. Для этого выпишем все сочетания индексов {i,k} и для каждого сочетания укажем номера наборов, на которых отличаются функции gi и gk.

Упростим полученное выражение, применяя формулу поглощения.

Получим: К_T = 2⋅5⋅(1∨4).

С помощью дистрибутивного закона преобразуем это выражение в ДНФ, тогда каждой символической конъюнкции будет соответствовать минимальный тест. Имеем:

К_T = 2⋅5⋅(1∨4) = 2⋅5⋅1∨2⋅5⋅4

В качестве минимального теста можно взять, например, совокупность 1, 2 и 5 наборов, т. е. найден минимальный тест

T_min = { (0,1,0,0), (1,0,0,0), (1,1,1,1)}.

Задание 2.6.5

1. Построить таблицу значений функции, реализуемой данной
контактной схемой.

2. Найти минимальную ДНФ с помощью карты Карнау,
построить на её основе контактную схему, равносильную исходной.

Таблица 2.6.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Пример решения задания 2.6.5

Решим задание 2.6.5 для контактной схемы. Рассмотрим вид контактной схемы на всех 8 наборах переменных x,y,z, изображая разомкнутые контакты пунктирной линией, а замкнутые — сплошной. Рассмотрим набор (0,0,0). Видим, что в данном случае между полюсами нет маршрута, составленного из сплошных линий, значит, на этом наборе функция, реализованная данной схемой, равна нулю, f(0,0,0) = 0.

Рассмотрим изображение схемы на остальных наборах:

f(0,0,1) = 0
f(0,1,0) = 1
f(0,1,1) = 1
f(1,0,0) = 1
f(1,0,1) = 1
f(1,1,0) = 1
f(1,1,1) = 0
Запишем найденные значения функции f(x,y,z) в карту Карнау (табл. 2.6.5а). Минимальная ДНФ: ху ∨ xz ∨ ху. Преобразуем формулу: ху ∨ xz ∨ ху = = ху ∨ x(z ∨ y). Соответствующая контактная схема имеет вид: Задание выполнено.