Построение таблицы истинности онлайн

Как пользоваться калькулятором

1. Введите в поле логическую функцию (например x1 ∨ x2) или ее вектор (например 10110101)
2. Укажите действия, которые необходимо выполнить, с помощью переключателей
3. Укажите, требуется ли вывод решения переключателем «С раствором»
4. Нажмите кнопку «Построить»

Совершенная конъюнктивная нормальная форма

Совершенная конъюнктивная нормальная форма формулы (SKNF) — это эквивалентная формула, которая представляет собой конъюнкцию элементарных дизъюнкций, удовлетворяющую следующим свойствам:

1. Все элементарные предложения содержат все переменные, входящие в функцию F (x1, x2, . xn).
2. Все элементарные дизъюнкции различны.
3. Каждая элементарная дизъюнкция содержит переменную один раз.
4. Никакая элементарная дизъюнкция не содержит переменной и ее отрицания.

Минимизировать логические функции

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

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

где K — элементарная конъюнкция. Большинство методов минимизации BF полагаются на первые две идентичности. И третий — закон распределения — уменьшает количество букв в формуле, но выводит формулу из класса DNF. При минимизации BF используются разные термины (и обозначения) для элементарных полных союзов (PEC). Чаще всего используются термины «минтерм» и «составляющая единица». (Для полных элементарных дизъюнкций (PED) используются термины «maxterm» и «нулевая составляющая»). Слово «составной» означает «компонент», а название «minterm» происходит от определения конъюнкции как минимального значения его операндов. В этом случае используются обозначения mi — для minterm и Mi — для maxterm. Число i соответствует двоичной записи оценки переменной, для которой mi = 1.

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

Вы можете вставить всю карту или только выбранные объекты (меню «Операции»). ►Удалить операции

• Выбор клея
• Приклеиваем всю бумагу
• Удалите клеи
• Сохранить как docx
• Сохранить как png
• ✍ Помощь в устранении неполадок

Количество переменных Сетка

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

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

Видеоинструкция к калькулятору

Используемые символы

В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также числа, написанные после буквы (индекс переменной). Следовательно, имена переменных будут: a, x, a1, B, X, X1, Y1, A123 и так далее.

Для написания логических операций вы можете использовать как обычные символы клавиатуры (*, +,!, ^, ->, =), так и символы, известные в литературе (∧, ∨, ¬, ⊕, →, ≡). Если на вашей клавиатуре нет необходимого символа операции, используйте клавиатуру калькулятора (если он не виден, нажмите «Показать клавиатуру»), где доступны все логические операции и набор наиболее часто используемых переменных.

Чтобы изменить порядок операций, используйте круглые скобки ().

Обозначения логических операций

• И (И):&•∧*
• ИЛИ (ИЛИ):∨+
• НЕ):¬!
• Исключающее ИЛИ (XOR):⊕^
• Следствие:-> →=>
• Эквивалентность:=~≡ <=>
• Кадр Шеффера:↑|
• Проколите стрелку:↓

Что умеет калькулятор

• Составьте таблицу истинности по функциям
• Создайте таблицу истинности из двоичного вектора
• Постройте идеальную нормальную форму конъюнктивы (SKNF)
• Постройте идеальную дизъюнктивную нормальную форму (SDNF)
• Построить многочлен Жегалкина (с Паскалем, треугольником, неопределенными коэффициентами)
• Определите, принадлежит ли функция к каждому из пяти классов голодания
• Постройте карту Карно
• Минимизировать DNF и CNF
• Ищите фиктивные переменные

Что такое булева функция

Булева функция f (x1, x2, . xn) — это любая функция от n переменных x1, x2, . xn, в которой ее аргументы принимают одно из двух значений: 0 или 1, а сама функция принимает значения 0 или 1. То есть это правило, согласно которому произвольному набору нулей и единиц присваивается значение 0 или 1. Более подробную информацию о булевых функциях можно найти в Википедии.

Что такое таблица истинности?

Таблица истинности — это таблица, которая описывает логическую функцию, то есть отражает все значения функции для всех возможных значений ее аргументов. Таблица состоит из n + 1 столбца и 2n строк, где n — количество используемых переменных. В первых n столбцах записываются все возможные значения аргументов (переменных) функции, а в n + 1-м столбце записываются значения функции, которая принимает заданный набор аргументов.

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

Логические операции

Логическая операция — это операция инструкции, которая позволяет вам составлять новые инструкции, связывая более простые. Основные операции обычно называются конъюнкцией (∧ или &), дизъюнкцией (∨ или |), импликацией (→), отрицанием (¬), эквивалентностью (=), исключающим ИЛИ (⊕).

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

а	б	а ∧ б	а ∨ б	к	б	а → б	а = б	а ⊕ б
0	0	0	0	1	1	1	1	0
0	1	0	1	1	0	1	0	1
1	0	0	1	0	1	0	0	1
1	1	1	1	0	0	1	1	0

Операция И — логическое умножение (конъюнкция)

Операция логического И выполняет функцию пересечения двух операторов (аргументов), которые могут быть как простым, так и сложным логическим выражением. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения истинны.
Применяемые обозначения: A и B, A Λ B, A и B, A и B.
Результат операции И определяется следующей таблицей истинности:

А	Б	А и Б
0	0	0
0	1	0
1	0	0
1	1	1

Результат операции И истинен тогда и только тогда, когда утверждения A и B истинны одновременно, и ложны во всех остальных случаях.

Операция ИЛИ — логическое сложение (дизъюнкция, объединение)

Операция логического ИЛИ выполняет функцию объединения двух операторов, которые могут быть простым или сложным логическим выражением. Операторы, являющиеся источником логической операции, называются аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда хотя бы одно из исходных выражений истинно.
Применяемые имена: A или B, AVB, A или B, A || Б.
Результат операции ИЛИ определяется следующей таблицей истинности:

А	Б	А или В
0	0	0
0	1	1
1	0	1
1	1	1

Результатом операции ИЛИ является истина, когда A истинно, или B истинно, или оба A и B истинны одновременно, и ложь, когда аргументы A и B ложны.

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Применяемый номинал: A XOR B, A ⊕ B.
Таблица истинности:

А	Б	Б
0	0	0
0	1	1
1	0	1
1	1	0

Результат эквивалентности операции истинен, только если A и B одновременно истинны или ложны.

Операция НЕ — логическое отрицание (инверсия)

Логическая операция НЕ применяется к одному аргументу, который может быть простым или сложным логическим выражением. Результат операции НЕ следующий:

• если исходное выражение истинно, результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.

Следующие соглашения НЕ принимаются для операции отрицания:
не А, Ā, не А, ¬А,! К
Результат операции отрицания НЕ определяется следующей таблицей истинности:

А	не на
0	1
1	0

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

Алгоритм построения таблицы истинности логической функции

Определяет количество строк: количество строк = $ 2 ^ n + 1 $ (для строки заголовка), $ n $ — количество простых выражений. Например, для функций двух переменных есть $ 2 ^ 2 = 4 $ комбинаций наборов значений переменных, для функций трех переменных — $ 2 ^ 3 = 8 $ и т.д.

Определите количество столбцов: количество столбцов = количество переменных + количество логических операций. При определении количества логических операций также учитывается порядок их выполнения.

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

Попробуйте попросить учителей о помощи

Создайте таблицу истинности для логического выражения $ D = ar vee (B vee C)$.

Решение:

Определяем количество строк:

Количество простых выражений $ n = 3 $, поэтому

количество строк = 2 ^ 3 + 1 = 9$.

Определяем количество столбцов:

Количество переменных — 3$.

Количество логических операций и их последовательность:

Столбцы = 3 $ + 3 = 6$.

Заполняем таблицу с учетом таблиц истинности логических операций.

Для этого логического выражения постройте таблицу истинности:

Решение:

Определяем количество строк:

Количество простых выражений $ n = 3 $, поэтому

количество строк = 2 ^ 3 + 1 = 9$.

Определяем количество столбцов:

Количество переменных — 3$.

Количество логических операций и их последовательность:

1. отрицание ($ a$);
2. дизъюнкция, потому что она заключена в квадратные скобки ($ A vee B$);
3. соединение ($ (Avee B) igwedge overline$);
4. отрицание, которое мы обозначаем $ F_1 $ ($ overline <(Avee B) igwedge overline>$);
5. дизъюнкция ($ A vee C$);
6. соединение ($ (Avee C) igwedge B$);
7. отрицание, которое мы обозначаем $ F_2 $ ($ overline <(Avee C) igwedge B>$);

Столбцы = 3 + 8 = 11$.

Заполняем таблицу с учетом таблицы истинности логических операций.

Операция «ЕСЛИ-ТО» — логическое следование (импликация)

Эта операция соединяет два простых логических выражения, первое из которых является условием, а второе — следствием этого условия.
Применяемые купюры:
если A, то B; A влечет B; если A, то B; А → Б.
Таблица истинности:

А	Б	А → Б
0	0	1
0	1	1
1	0	0
1	1	1

Результат операции преемственности (импликация) ложен только тогда, когда посылка A истинна, а вывод B (следствие) ложно.

Как задать логическую функцию

Есть много способов определить логическую функцию:

• таблица истинности
• наборы характеристик
• вектор ценностей
• серая матрица
• формулы

Давайте посмотрим на некоторые из них:

Чтобы определить функцию через вектор значений, необходимо написать вектор из 2n нулей и единиц, где n — количество аргументов, от которых зависит функция. Например, функция с двумя аргументами может быть определена как: 0001 (операция И), 0111 (операция ИЛИ).

Чтобы определить функцию как формулу, вам нужно написать математическое выражение, состоящее из аргументов функции и логических операций. Например, вы можете определить такую ​​функцию: a∧b ∨ b∧c ∨ a∧c

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

На основе заданной SDNF (согласно таблице истинности) создается новая логическая схема (если не выбран элемент функции Create new circuit при булевой минимизации). Если расчеты производятся по оригинальной схеме и она вам понадобится в будущем, вы можете сохранить ее заранее (меню Действия / Сохранить). Имена переменных можно изменить. Для этого их необходимо выделить (первая строка таблицы). Количество переменных

а	б	c	ж
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Чтобы создать схему и задать параметры решения, необходимо нажать кнопку «Далее.
Дальше

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

• Действия в скобках
• Инверсия
• Соединение (&)
• Дизъюнкция (V), исключающее ИЛИ (XOR), сумма по модулю 2
• Следствие (→)
• Эквивалентность (↔)

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

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

⊗

Свойства элемента

Количество входов 1234 Размер текста Цвет Толщина линии Цвет пунктира — — — —
Размеры в пикселях и фон, белый Отмена ⊗

Соединение

Введите numberTextSizeColorLineThicknessColor с точками — — -Cancel ⊗

Список

Отмена

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Номинал номинала: A ↔ B, A ~ B.
Таблица истинности:

А	Б	Б
0	0	1
0	1	0
1	0	0
1	1	1

Результат эквивалентности операции истинен, только если A и B одновременно истинны или ложны.

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

Чтобы добавить логический элемент, выберите его левой кнопкой мыши, затем щелкните рабочее пространство.
Чтобы соединить элементы, вы должны сначала выделить их (один щелчок по объекту), затем нажать кнопку «Подключить». Чтобы подключиться к переменной xi, щелкните соответствующее имя. Построенная диаграмма может быть сохранена в формате docx или png.

Совершенная дизъюнктивная нормальная форма

Совершенная дизъюнктивная нормальная форма формулы (SDNF) — это эквивалентная формула, которая представляет собой дизъюнкцию элементарных конъюнкций со следующими свойствами:

1. Каждый логический член формулы содержит все переменные, входящие в функцию F (x1, x2, . xn).
2. Все логические элементы формулы различны.
3. Ни один логический термин не содержит переменной и ее отрицания.
4. Ни один логический член в формуле не содержит одну и ту же переменную дважды.

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

Способы представления булевой функции

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

• Совершенная дизъюнктивная нормальная форма (SDNF)
• Совершенная сослагательная нормальная форма (СКНФ)
• Алгебраическая нормальная форма (АНФ, многочлен Жегалкина)

Совершенная дизъюнктивная нормальная форма (ДНФ)

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

Например, DNF — это функция ¬abc ∨ ¬a¬bc ∨ ac, но не SDNF, поскольку в последней конъюнкции отсутствует переменная b.

Совершенная конъюнктивная нормальная форма (КНФ)

Простая дизъюнкция — это дизъюнкция одной или нескольких переменных или их отрицаний, и каждая переменная появляется там не более одного раза.
Конъюнктивная нормальная форма (CNF) — это конъюнкция простых дизъюнкций.
Совершенная конъюнктивная нормальная форма (CKNF) — это CNF относительно данного конечного набора переменных, каждая дизъюнкция которого включает в себя все переменные данного набора.

Например, CNF — это функция (a ∨ b) ∧ (a ∨ b ∨ c), но не SDNF, поскольку первая дизъюнкция не содержит переменной c.

Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Алгебраическая нормальная форма, полином Жегалкина, представляет собой форму для представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором операция соединения используется как произведение, а исключающее ИЛИ используется как добавление.

Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1

Алгоритм построения СДНФ для булевой функции

1. Создайте таблицу истинности для функции
2. Находит все наборы аргументов, для которых функция принимает значение 1
3. Напишите простые союзы для каждого из наборов в соответствии со следующим правилом: если переменная в наборе принимает значение 0, то она включается в соединение с отрицанием, а в противном случае без отрицания
4. Объедините все простые союзы, используя дизъюнкцию

Алгоритм построения СКНФ для булевой функции

1. Создайте таблицу истинности для функции
2. Находит все наборы аргументов, для которых функция принимает значение 0
3. Напишите простые дизъюнкции для каждого из наборов в соответствии со следующим правилом: если переменная в наборе принимает значение 1, то она входит в дизъюнкцию с отрицанием, иначе без отрицания
4. Объедините все простые дизъюнкции с помощью конъюнкции

Алгоритм построения полинома Жегалкина булевой функции

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

1. Создайте таблицу истинности для функции
2. Добавьте новый столбец в таблицу истинности и запишите в ячейки 1, 3, 5 . значения из тех же строк, что и предыдущий столбец таблицы истинности, и значения в строках 2, 4, 6 . сложите модуль два значения соответственно из 1, 3, 5 . строк.
3. Добавьте новый столбец в таблицу истинности и перепишите значения 1, 2, 5, 6, 9, 10 . строк в новый столбец и добавьте те, которые были перезаписаны в 3, 4, 7, 8, 11, 12..значения строк.
4. Повторяйте шаги каждый раз, удваивая количество перенесенных и свернутых элементов, пока длина не станет равной количеству строк в таблице.
5. Запись логических наборов, в которых значение последнего столбца равно единице
6. Вместо единиц в наборах напишите имена переменных, соответствующие набору (для набора ноль, напишите единицу) и объедините их, используя операцию исключающее ИЛИ.

Примеры построения различных представлений логических функций

Построены дизъюнктивные и дизъюнктивные совершенные нормальные формы, а также многочлен Жегалкина для функции трех переменных F = ¬ab∨¬bc∨ca

1. Построим таблицу истинности для функции

а	б	c	к	a∧b	б	b∧c	a∧b∨¬b∧c	c∧a	a∧b∨¬b∧c∨c∧a
0	0	0	1	0	1	0	0	0	0
0	0	1	1	0	1	1	1	0	1
0	1	0	1	1	0	0	1	0	1
0	1	1	1	1	0	0	1	0	1
1	0	0	0	0	1	0	0	0	0
1	0	1	0	0	1	1	1	1	1
1	1	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	1	1

Построение совершенной дизъюнктивной нормальной формы:

Мы находим наборы, на которых функция принимает истинное значение: {0, 0, 1} {0, 1, 0} {0, 1, 1} {1, 0, 1} {1, 1, 1 }

В соответствии с найденными наборами для всех переменных ставим элементарные конъюнкции, и если переменная в наборе принимает значение 0, то будет записано отрицание:

K1: {0, 0, 1} — a¬bc
K2: {0, 1, 0} — ab¬c
K3: {0, 1, 1} — abc
K4: {1, 0, 1} — a¬bc
K5: {1, 1, 1} — abc

Мы объединяем конъюнкции, используя дизъюнкцию, и получаем идеальную дизъюнктивную нормальную форму:
K1 ∨ K2 ∨ K3 ∨ K4 ∨ K5 = ¬a¬bc ∨ ¬ab¬c ∨ ¬abc ∨ a¬bc ∨ abc

Построение совершенной конъюнктивной нормальной формы:

Мы находим наборы, на которых функция принимает ложное значение: {0, 0, 0} {1, 0, 0} {1, 1, 0 }

В соответствии с найденными наборами ставим элементарные дизъюнкции во все переменные, и если переменная в наборе принимает значение 1, то будет записано отрицание:

D1: {0, 0, 0} — a∨b∨c
RE2: {1, 0, 0} — a∨b∨c
RE3: {1, 1, 0} — a∨¬b∨c

Соедините дизъюнкции конъюнкцией, и вы получите идеальную конъюнктивную нормальную форму: D1 ∧ D2 ∧ D3 = (a∨b∨c) ∧ (¬a∨b∨c) ∧ (¬a∨¬b∨c)