Сднф по вектору значений

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

Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина

введите функцию или её вектор

Построено таблиц, форм:

Видео:Построение СДНФСкачать

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

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

Видео:Построение СДНФ и СКНФ по таблице истинностиСкачать

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

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

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

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

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

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

• И (AND): & • ∧ *
• ИЛИ (OR): ∨ +
• НЕ (NOT): ¬ !
• Исключающее ИЛИ (XOR): ⊕ ^
• Импликация: -> → =>
• Эквивалентность: =

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

• Строить таблицу истинности по функции
• Строить таблицу истинности по двоичному вектору
• Строить совершенную конъюнктивную нормальную форму (СКНФ)
• Строить совершенную дизъюнктивную нормальную форму (СДНФ)
• Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
• Определять принадлежность функции к каждому из пяти классов Поста
• Строить карту Карно
• Минимизировать ДНФ и КНФ
• Искать фиктивные переменные

Видео:A.2.15 Построение совершенных дизъюнктивной и конъюнктивной нормальных форм (СДНФ и СКНФ)Скачать

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

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

Видео:СДНФ и СКНФ Табличный способСкачать

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

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

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

Видео:Пример сведения булевой функции к СДНФ и СКНФСкачать

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

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

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

Видео:Построение минимальной ДНФ преобразованием СДНФСкачать

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

Есть множество способов задать булеву функцию:

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

Рассмотрим некоторые из них:

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

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

Видео:Для чего нужны СДНФ и СКНФ? Душкин объяснитСкачать

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

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

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

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

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

Например, ДНФ является функция ¬a bc ∨ ¬a ¬b c ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.

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

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

Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ 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 = ¬a b∨ ¬b c∨ca

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

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

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

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

Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:

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

Найдём наборы, на которых функция принимает ложное значение:

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

Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:

Построение полинома Жегалкина:

Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:

Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:

Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:

Окончательно получим такую таблицу:

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

Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc

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

Видео:Сведение булевой функции к СДНФ и СКНФСкачать

Построение СКНФ и СДНФ по таблице истинности

Вы будете перенаправлены на Автор24

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

Нормальная форма существует в двух видах:

конъюнктивная нормальная форма (КНФ) — конъюнкция нескольких дизъюнкций, например, $left(Avee overlinevee Cright)wedge left(Avee Cright)$;

дизъюнктивная нормальная форма (ДНФ) — дизъюнкция нескольких конъюнкций, например, $left(Awedge overlinewedge Cright)vee left(Bwedge Cright)$.

Совершенная конъюнктивная нормальная форма (СКНФ) — это КНФ, удовлетворяющая трем условиям:

не содержит одинаковых элементарных дизъюнкций;

ни одна из дизъюнкций не содержит одинаковых переменных;

каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.

Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.

Видео:СДНФ СКНФ Полином Жегалкина для логических выраженийСкачать

Правила построения СКНФ по таблице истинности

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

Совершенная дизъюнктивная нормальная форма (СДНФ) — это ДНФ, удовлетворяющая трем условиям:

не содержит одинаковых элементарных конъюнкций;

ни одна из конъюнкций не содержит одинаковых переменных;

каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.

Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.

Видео:СДНФ и СКНФСкачать

Правила построения СДНФ по таблице истинности

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

Видео:Нормальные формы ДНФ, КНФ, СДНФ, СКНФСкачать

Примеры нахождения СКНФ и СДНФ

Записать логическую функцию по ее таблице истинности:

Решение:

Воспользуемся правилом построения СДНФ:

[Fleft(x_1, x_2, x_3right)=left(overlinewedge overlinewedge overlineright)vee left(overlinewedge overlinewedge x_3right)vee left(x_1wedge overlinewedge overlineright)vee left(x_1wedge overlinewedge x_3right)vee left(x_1wedge x_2wedge x_3right)]

Воспользуемся правилом построения СКНФ:

[Fleft(x_1, x_2, x_3right)=left(x_1vee overlinevee x_3right)wedge left(x_1vee overlinevee overlineright)wedge left(overlinevee overlinevee x_3right)]

Готовые работы на аналогичную тему

Функция задана таблицей истинности:

Представить эту функцию в виде СДНФ и СКНФ.

Решение:

Запишем логическую функцию в СДНФ. Для удобства решения добавим к таблице вспомогательный столбец.

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

Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:

[Fleft(x_1,x_2,x_3,x_4right)=left(overlinewedge overlinewedge zwedge fright)vee left(overlinewedge x_2wedge overlinewedge overlineright)vee left(overlinewedge x_2wedge x_3wedge x_4right)vee left(x_1wedge overlinewedge overlinewedge overlineright).]

Запишем логическую функцию в СКНФ.

Используя правило составления СКНФ не забываем вводить знак отрицания для переменных со значением 1. Инвертировать единичные значения переменных обязательно, т.к. иначе они превратят значения дизъюнкций в единицы основной функции.

Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:

[Fleft(x_1,x_2,x_3,x_4right)=left(x_1vee x_2vee x_3vee x_4right)wedge left(x_1vee x_2vee x_3vee overlineright)wedge left(x_1vee x_2vee overlinevee x_4right)wedge left(x_1vee overlinevee x_3vee overlineright)wedge left(x_1vee overlinevee overlinevee x_4right)wedge left(overlinevee x_2vee x_3vee overlineright)wedge left(overlinevee x_2vee overlinevee x_4right)wedge left(overlinevee x_2vee overlinevee overlineright)wedge left(overlinevee overlinevee x_3vee x_4right)wedge left(overlinevee overlinevee x_3vee overlineright)wedge left(overlinevee overlinevee overlinevee x_4right)wedge left(overlinevee overlinevee overlinevee overlineright).]

Видео:СДНФ и СКНФ Аналитический способ приведенияСкачать

СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

1. Услуги проектирования
2. Алгебра логики [Г.И. Просветов, Е.А. Фоминых, Ф.Г. Кораблёв]
3. СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

Видео:Переход от ДНФ к СДНФ, от КНФ к СКНФСкачать

СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

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

• полная, если в неё каждая переменная входит ровно 1 раз;
• монотонная, если она не содержит отрицаний переменных.

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

Пример ДНФ: $f(x,y,z) = (x land y) lor (y land neg )$

СДНФ — это такая ДНФ, которая удовлетворяет условиям:

• в ней нет одинаковых простых конъюнкций
• каждая простая конъюнкция полная

Пример СДНФ: $f(x,y,z) = (x land neg land z) lor (x land y land neg )$

Теорема: Для любой булевой функции $f(vec )$, не равной тождественному нулю (), существует СДНФ, ее задающая.

Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона.

$f(vec ) = neg x_i wedge f(x_1, dots ,x_ ,0,x_ , dots ,x_n) vee x_i wedge f(x_1, dots ,x_ ,1,x_ , dots ,x_n)$

Данное соотношение легко проверить подстановкой всевозможных значений $x_i$ . Эта формула позволяет выносить $x_i$ за знак функции. Последовательно вынося $x_1$, $x_2$. $x_n$ за знак $f(vec )$, получаем следующую формулу :

$ f(vec ) = neg x_1 wedge neg x_2 wedge . wedge neg x_ wedge neg x_n wedge f(0,0. 0,0)

$neg x_1 wedge neg x_2 wedge . wedge neg x_ wedge x_n wedge f(0,0. 0,1)

x_1 wedge x_2 wedge . wedge x_ wedge neg x_n wedge f(1,1. 1,0)

$ $x_1 wedge x_2 wedge . wedge x_ wedge x_n wedge f(1,1. 1) $

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от $n$ переменных мы имеем < < < $2^ $ > > > конъюнктов. Каждый из них соответствует значению функции на одном из < < < $2^ $ > > > возможных наборов значений $n$ переменных. Если на некотором наборе $f(vec )=0$, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же $ f(vec )=1$, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.

Алгоритм построения СДНФ по таблице истинности

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

Видео:Приведение булевой функции к ДНФСкачать

Пример построения СДНФ для медианы

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

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

Все полученные конъюнкции связываем операциями дизъюнкции. $ langle x,y,z rangle = (x land y land z) lor (neg land y land z) lor (x land neg land z) lor (x land y land neg )$

Видео:ДНФСкачать

Примеры СДНФ для некоторых функций

Стрелка Пирса: $x downarrow y = (neg land neg )$

Исключающее или: $x oplus y oplus z = (overline land overline land z) lor (overline land y land overline ) lor (x land overline land overline ) lor (x land y land z)$

Совершенной дизъюнктивной нормальной формой формулы $A(x_1,x_2,…,x_n)$ называется ДНФ, обладающая следующими свойствами:

а > в ней нет одинаковых дизъюнктивных элементов;

б > ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;

в > ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;

г > в каждой элементарной конъюнкции содержится либо $X_i$, либо $overline _i$, где $i = 1, n$.

Условие а > – г > являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:

1) если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $Bwedge (X_ivee overline _i) equiv (Bwedge X_i)vee (Bwedge overline _i)$;

2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;

3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Формула называется дизъюнктивной нормальной формой , если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: $A_1vee A_2vee . vee A_n$ , где каждое $A_n$ — элементарная конъюнкция.

Формула $A$ от $k$ переменных называется совершенной дизъюнктивной нормальной формой , если:

$A$ является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция $k$ переменных $x_1,x_2,…,x_k$, причем на $i$-м месте этой конъюнкции стоит либо переменная $x_i$ либо ее отрицание;

Все элементарные конъюнкции в такой ДНФ попарно различны.

Например: $A = x_1 wedge$ НЕ $x_2 vee x_1 wedge x_2$

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

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

Теорема о СДНФ: Пусть $f(x_1 x_2, …, x_n)$ – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию $f$.

Алгоритм построения СДНФ по таблице истинности:

• В таблице истинности отмечаем наборы переменных, на которых значение функции $f = 1$.
• Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
• Все полученные конъюнкции связываем операциями дизъюнкции.

Далее:

Нахождение потенциала

Теорема о предполных классах

Механические приложения тройного интеграла

Упрощение логических функций

Определение двойного интеграла

Критерий полноты . Лемма о немонотонной функции

Свойства потока векторного поля

Вычисление поверхностного интеграла первого рода

Поверхностный интеграл второго рода и его свойства

Вычисление площади поверхности

Класс $S$. Теорема о замкнyтости класса $S$

Формула Грина

Механические приложения двойного интеграла

Логические следствия

Огравление $Rightarrow $

📸 Видео

Синтез логических выражений (СКНФ и СДНФ)Скачать

A.2.16 Минимизация СДНФ методом КуайнаСкачать

Что такое конъюнктивная и дизъюнктивная нормальные формы? Душкин объяснитСкачать

Построение СКНФСкачать