Опубликовано

Релейно контакторная схема

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

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

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

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

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

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

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

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

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

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

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

Теорема:

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

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

Пусть дана функция и она представлена в ДНФ

Дерево конъюнктов для 2-х переменных

Возьмем дерево конъюнктов для переменных (см. картинку). Очевидно, что от вершины до «нижних» вершин дерево можно добраться за , а ребер у такого дерева

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

В результате можно построить контактную схему для любой функции со сложностью

> См также

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

ТЕМА 5 КОНТАКТНЫЕ И ЛОГИЧЕСКИЕ СХЕМЫ

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

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

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

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

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

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

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

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

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

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

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

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

==

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

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

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

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

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

==.

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

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

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

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

Функция

Графическое изображение

Функция

Графическое изображении

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

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

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

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

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

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

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

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

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

Отсюда

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

=,

Где .

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

< Предыдущая

  • Total: 0
  • 0
  • 0
  • 0
  • 0
  • 0

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

––––– РЕКЛАМА –––––

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

Как нарисовать красивую диаграмму в Canva

О сайте Canva мы уже много раз рассказывали в своих статьях. Этот онлайн-сервис для графического дизайна идеально подходит для создания инфографики, презентаций, афиш, наружной рекламы и др. Сегодня поговорим о том, как Канва поможет построить блок-схему онлайн.

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

Для начала выбираем понравившийся шаблон среди десятков различных вариантов.

Удобно, что большая часть макетов здесь предоставляется бесплатно

Дальше меняем элементы, редактируем текст, передвигаем блоки – в общем, полностью подгоняем макет под себя.

––––– РЕКЛАМА –––––

Настроить здесь можно абсолютно все: начиная от шрифта надписей и заканчивая структурой изображения

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

Кроме того, есть возможность добавить красивые диаграммы

Вы можете создавать блок-схему совместно со своими коллегами или партнерами – для этого нужно нажать на кнопку «Поделиться» и выслать приглашения по электронной почте или в соцсетях.

В этом же разделе также есть функция вставки созданного изображения на ваш интернет-ресурс. Достаточно просто скопировать фрагмент кода с диаграммой и вписать его в свой блог или сайт

Когда работа над блок-схемой закончена, нажимаем «Скачать».

Выбираем формат файла

К большим преимуществам использования Canva можно отнести то, что картинка по итогу сохраняется без каких-либо водяных символов.

Удобное построение логических цепочек с Draw.io

Еще одним бесплатным онлайн-сервисом, достойным вашего внимания, является Draw.io. Он считается одним из самых известных сайтов для создания схем, диаграмм, графиков и структур. Здесь так же, как и в Canva, есть возможность подключить русскоязычный интерфейс, что существенно облегчает процесс.

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

Спасибо Draw.io за удобное структурирование шаблонов – все они распределены по категориям, что позволяет выбирать нужный вариант максимально быстро

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

По сравнению с предыдущим сервисом, настройки здесь кажутся немного примитивными, но тем не менее присутствуют все необходимые параметры

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

Также есть возможность вставить в документ уже готовую схему или другое изображение, импортировав его с компьютера, облачного хранилища или интернет-ресурса

Для сохранения результата нажимаем «Файл» – «Сохранить как», после чего нам предлагают следующие варианты:

  • Google Drive;
  • OneDrive;
  • Dropbox;
  • GitHub;
  • Trello;
  • компьютер;
  • браузер.

Готовый файл скачивается в формате .xml.

Google chart – мощный инструмент для разработчиков

И наконец завершает наш список рекомендаций Google chart API. Он представляет собой библиотеку фрагментов кода, при встраивании которых на вашем сайте появляются красивые диаграммы, графики, структуры, таблицы и др.

Выбираем нужную категорию

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

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

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

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

Все рассмотренные нами программы абсолютно разные, поэтому выделить из них самую удобную невозможно. Все зависит от ваших целей и пожеланий. Если вам необходимо получить красивый графический продукт, то лучше Canva с этим не справится ни один сайт. Если нужна минималистичная схема без особых изысков – на помощь придет Draw.io. Если хотите прописать код для своей диаграммы – используйте Google chart API.

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

По сравнению с аналогичными приложениями

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

Цены

Бесплатная учетная запись пользователя имеет большую функциональность предоставляемых инструментов, но не сохраняет проекты. Тем не менее, можно просто сделать скриншот экрана и таким образом сохранить своё творчество)

Также недоступно совместное использование и печать. Вы можете экспортировать схемы в JPG, PNG, SVG или XML файлы и сохранять их локально.

Стандартный аккаунт позволяет сохранять до 200 диаграмм одновременно. За него взимается плата 4.95 долларов в месяц с одного пользователя.

Учетная запись для профессиональных пользователей обходится в 9.95 долларов в месяц и предлагает не ограниченное пространство для хранения схем.

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

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

Укажем на применение алгебры логики к анализу и синтезу релейно-контактных схем. Среди технических средств автоматизации значительное место занимают устройства релейно-контактного действия. Они находят широкое применение в телефонии, телеуправлении, автоматике и телемеханике, на железнодорожном транспорте, в вычислительной технике. Сейчас при конструировании таких устройств все больше и больше используется алгебра логики. Впервые идея использования алгебры логики для построения автоматических устройств была выдвинута в 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. Один из братьев Витя, Толя, Коля разбил окно. В разговоре участвуют еще двое братьев – Андрей и Дима.

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

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

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

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

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

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *