Программирование построение логических схем

Редактор схемы логических элементов

Созданную логическую схему можно сохранить в форматах docx и png (меню Действия ). По логической схеме можно построить СКНФ, СДНФ, полином Жегалкина, карты Вейча-Карно, а также минимизировать булеву функцию.

Инструкция к сервису

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

Булевы функции

С помощью этого калькулятора по булевой функции строится таблица истинности, определяются свойства функции и другие параметры (см. вкладку Параметры решения ). ► При этом вводится только само логическое выражение без префикса. Например, при f(x,y,z) = x → y!z , ввести необходимо только x → y!z .
Введеное выражение также можно упростить, используя законы логики высказываний (на следующем шаге выбрать параметр Упростить выражение ).

(. ) — ввод скобок, x -отрицание ( NOT , ! , ¬), & — логическое И, AND, ∧, *, v — логическое ИЛИ, OR, ∨, = — эквивалентность, ˜, ≡, ↔, ⊕ — сумма по модулю 2, | — штрих Шеффера, И-НЕ, AND-NOT, ↓ — стрелка Пирса, ИЛИ-НЕ, OR-NOT, ← — обратная импликация.

Для вложенного отрицания необходимо использовать знак ! . Например, x v y = !(x v y ) или x v y = x v !y
Далее Построить схему

По найденной таблице истинности можно определить логические значения высказываний, например, при x=0 , y=0 , z=1
Чтобы проверить высказывание на истинность или ложность, функцию необходимо вводить без знака равно ( = ). Например, A+B → A&B =1 , необходимо ввести A+B → A&B . Если в результате преобразований получится, что f=1 , то высказывание истинно, если f=0 — ложно.

Логические (функциональные) элементы являются наиболее распространенными: в силу полноты системы любую булеву функцию (БФ) можно представить в виде суперпозиции дизъюнкции, конъюнкции и отрицания. В качестве функциональных элементов (ФЭ) можно рассматривать любые булевы функции, при этом их можно соединять друг с другом, подавая выходы одних элементов на входы других (суперпозиция БФ).

Отрицание, ¬

Конъюнкция, &

Дизъюнкция, v

Сумма по модулю 2, x⊕y

Стрелка Пирса, x↓y

Эквивалентность, x↔y

Импликация, x→y

Штрих Шеффера, x|y

Основные равносильности логики высказываний

Название	Формула
Закон исключенного третьего	X v !X ≡ И
Закон противоречия	X & !X ≡ Л
Закон коммутативности	X & Y ≡ Y & X X v Y ≡ Y v X
Закон ассоциативности	(X & Y)&Z ≡ X&(Y&Z) (X v Y) v Z ≡ X v (Y v Z)
Закон дистрибутивности	X&(Y v Z) ≡ X&Y v X&Z X v Y&Z ≡ (X v Y)&(X v Z)
Закон двойного отрицания	!!X ≡ X
Закон идемпотентности	X&X ≡ X, X v X ≡ X
Законы де Моргана	!(X v Y) ≡ !X & !Y !(X & Y) ≡ !X v !Y
Закон поглощения	X v X&Y ≡ X X&(X v Y) ≡ X
Законы склеивания	(X & Y)v(X & !Y) ≡ X (X v Y)&(X v !Y) ≡ X
Замена импликации	X → Y ≡ !X v Y
Замена эквиваленции	X = Y ≡ X&Y v !X&!Y

Пример . Упростите выражение: (x˅y˅z)→(x˅y)*(x˅z)
Упростим функцию, используя основные законы логики высказываний.
Замена импликации: A → B = !A v B
Для нашей функции:
(x v y v z)→((x v y) (x v z)) = x v y v z v (x v y) (x v z)
Упростим функцию, используя законы де Моргана: !(A v B) = !A & !B
Для нашей функции:
x v y v z = x y z
По закону дистрибутивности:
(x v y) (x v z) = x v x z v y x v y z
получаем:
f = x y z v x v x z v y x v y z
После элементарных преобразований получаем:
f = x y z v x v x z v y x v y z = x y z v x v y z
f = y z v y z v x

Минимизация булевых функций

В данном сервисе для минимизации булевых функций используются метод Квайна и карт Карно-Вейча. После получения минимальной формы имеется возможность заново построить логическую схему. Если исходная схема понадобится в дальнейшем, то ее можно предварительно сохранить (меню Действия/Сохранить ).

1. Kx v K ≡ K — тождество поглощения;
2. Kx v K x ≡ K — тождество склеивания;
3. Kx v Ky ≡ K(xvy) — дистрибутивный закон,

Метод карт Карно

После минимизации можно получить логическую схему функции и построить таблицу истинности (кнопка Далее )
Далее

Этот метод используется для БФ не более, чем с шестью аргументами и основан на тождестве склеивания: Kx v K x ≡ K — две элементарные конъюнкции (ЭК) склеиваются, если они отличаются только знаком инверсии одного аргумента. Чтобы облегчить нахождение таких пар (четверок, восьмерок,…) склеивающихся ЭК, используют специальное представление БФ в виде таблицы – карты Карно (другое название — диаграмма Вейча). Чтобы заполнить карту Карно необходимо щелкнуть левой кнопкой мышки на соответствующую ячейку.
Карта Карно обладает той особенностью, что две ПЭК, соответствующие соседним клеткам карты, отличаются знаком инверсии только одного аргумента, т.е. их можно склеивать. Причем соседними являются не только клетки, например, с номерами 1 и 3, но и клетки с номерами 12 и 8, 12 и 4, т.е. карту можно «сворачивать» в цилиндр, соединяя горизонтальные (вертикальные) ее границы.
Две единицы «склеиваются» каждый раз, когда они стоят рядом в строке или столбце (карту можно свернуть в цилиндр). В результате склеивания число букв, входящих в ПЭК, уменьшается на единицу.

Минимизая функции через равносильные преобразования

Алгоритм минимизии логической функции

1. Замена импликации и эквиваленции.
2. Упрощение функции через законы де Моргана.
3. Раскрытие скобок, используя законы поглощения, исключенного третьего, противоречия.
4. Минимизация через закон дистрибутивности.

Алгоритм Куайна построения сокращенной ДНФ

1. Получить СДНФ функции.
2. Провести все операции неполного склеивания.
3. Провести все операции поглощения.

Построение логической схемы по таблице истинности

По заданной СДНФ (по таблице истинности) определяются существенные и фиктивные переменные, полином Жегалкина и принадлежность классам T0,T1, S, M, L. ► Также можно создать новую логическую схему (если не выбран пункт Строить новую схему при минимизации булевой функции). Если вычисления происходят по исходной схеме и она понадобится в дальнейшем, то ее можно предварительно сохранить (меню Действия/Сохранить ).

Пример . Найдите СДНФ(А) и СКНФ(А) с помощью равносильных преобразований и таблицы истинности, если A = x v y v(x→y)&x Таблица истинности

x	y	x	y	x v y	x v y	x→y	(x→y)&x	x v y v(x→y)&x
0	0	1	1	1	0	1	0	0
0	1	1	0	1	0	1	0	0
1	0	0	1	1	0	0	0	0
1	1	0	0	0	1	1	1	1

Упростим функцию, используя основные законы логики высказываний.
Замена импликации
A → B = !A v B
Для нашей функции:
x→y = x v y
f = x v y v ( x v y) x
Упростим функцию, используя законы де Моргана онлайн.
!(A v B) = !A & !B
!(A & B) = !A v !B
Для нашей функции:
x v y = x y
f = x y v ( x v y) x
По закону дистрибутивности:
x x = 0
( x v y) x = y x
x y v ( x v y) x = x y v y x
f = x y
Используя равносильные преобразования, найдем СДНФ(А).
СДНФ(А) = x y
Используя равносильные преобразования, найдем СДНФ(А).
1. Для получения элементарных дизъюнкций используем закон дистрибутивности XvYZ=(XvY)(XvZ).
2. Закон исключенного третьего Xv!X=1. При этом элементарную дизъюнкцию можно отбросить (в силу равносильности C & 1 = C).
3. По закону поглощения XvXYZ = X
A = x y
Из КНФ А путем равносильных преобразований получаем СКНФ А, последовательно добиваясь выполнения четырех свойств СКНФ А.
1. Если элементарная дизъюнкция В, входящая в КНФ А, не содержит переменную x_i, тогда заменяем В на Bv(x_i & !x_i) = (B v x_i)(B v !x_i)
2. Если в некоторую элементарную дизъюнкцию В переменная x_i входит дважды, то лишнюю переменную нужно отбросить, так как x_i v x_i = x_i.
3. Если КНФ А содержит две одинаковых элементарных дизъюнкций, то одну можно отбросить, так как B & B = B
4. Если в элементарную дизъюнкцию входит пара x_i v !x_i, то ее можно отбросить так как x_i v !x_i=1, а истинное высказывание из конъюнкции можно выбросить (в силу равносильности C & 1 = C).
A = (x v y y ) (y v x x ) = (x v y) (x v y ) (y v x) (y v x )
A = (x v y) (x v y ) (y v x) (y v x )
СКНФ(А) = (x v y) (x v y ) ( x v y)
Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:
1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x₁,x₂. x_n).
2. Все логические слагаемые формулы различны.
3. Ни одно логическое слагаемое не содержит переменную и её отрицание.
4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.
F = x y
Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:
1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x₁,x₂. x_n).
2. Все элементарные дизъюнкции различны.
3. Каждая элементарная дизъюнкция содержит переменную один раз.
4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание
F = (x v y) (x v y ) ( x v y)

Список литературы

1. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.,1992.
2. Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: Часть 2, М.: Мир, 1990.
3. Горбатов В.А. Основы дискретной математики. – М.: Высш. школа, 1986. – 312 с.

Источник

Блок -схема онлайн

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

Добавить это приложение в закладки

Добавить это приложение в закладки

Отправьте ссылку для скачивания по адресу

Отправьте нам свой отзыв

Что такое блок -схема?

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

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

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

Когда использовать блок -схему?

• Анализ и улучшение процесса:Блок -схемы могут быть использованы для анализа и улучшения существующих процессов, разбивая их на их компонентные части и определяя области для улучшения. Это может помочь оптимизировать процессы и повысить эффективность.
• Развитие системы:Блок -схемы обычно используются в компьютерном программировании, чтобы помочь разработать и понять программные системы. Их можно использовать для визуализации потока информации и логики в системе, что облегчает проектирование и реализацию.
• Управление проектом:Блок -схемы можно использовать в управлении проектами для планирования и координации задач и действий. Они могут помочь определить зависимости между задачами и визуализировать критический путь проекта.
• Обучение и документация:Блок -схемы могут использоваться для документирования процедур и рабочих процессов, что облегчает понимание и следовать их сотрудникам. Они также могут использоваться в учебных программах, чтобы помочь новым сотрудникам понять сложные процессы.
• Принятие решений:Блок-схемы можно использовать для принятия решений, предоставляя визуальное представление различных вариантов и их потенциальных результатов. Это может помочь прояснить сложные процессы принятия решений и облегчить более информированное принятие решений.

Символы и определения блок -схемы

• Flowline: Линия потока показывает направление процесса, соединяя два блока друг с другом.
• Termina or Terminator: Терминал или терминатор представляет собой начальную или конечную точки процесса блок -схемы.
• Process: Символ процесса является наиболее распространенным компонентом блок -схемы и указывает на шаг в процессе.
• Decision: Этот символ представляет решение, которое вы или ваша команда должны принять, чтобы достичь следующего шага процесса. Как правило, это истинное или ложное решение или вопрос «да» или «нет», на который вам нужно ответить.
• Document: Этот символ представляет единственный документ.
• Input/Output: Символ ввода/вывода представляет процесс внедрения или вывода внешних данных.

Создать блок-схемы с шаблонами

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

Создайте блок-схему бесплатно и загрузите ее в формате PDF, изображений или Visio. Ваша блок-схема доступна повсюду и может использоваться мгновенно с любого устройства.

Используйте готовые шаблоны, чтобы легко рисовать нужные схемы.

Источник