Запись сднф по таблице истинности

Содержание

Содержание
  1. Как пользоваться калькулятором
  2. Видеоинструкция к калькулятору
  3. Используемые символы
  4. Обозначения логических операций
  5. Что умеет калькулятор
  6. Что такое булева функция
  7. Что такое таблица истинности?
  8. Логические операции
  9. Таблица истинности логических операций
  10. Как задать логическую функцию
  11. Способы представления булевой функции
  12. Совершенная дизъюнктивная нормальная форма (ДНФ)
  13. Совершенная конъюнктивная нормальная форма (КНФ)
  14. Алгебраическая нормальная форма (АНФ, полином Жегалкина)
  15. Алгоритм построения СДНФ для булевой функции
  16. Алгоритм построения СКНФ для булевой функции
  17. Алгоритм построения полинома Жегалкина булевой функции
  18. Примеры построения различных представлений логических функций
  19. Построение совершенной дизъюнктивной нормальной формы:
  20. Построение совершенной конъюнктивной нормальной формы:
  21. Построение полинома Жегалкина:
  22. А Вы знаете, что мы пишем программы на C, C++, C#, Pascal и Python?
  23. Почему именно мы?
  24. Как с нами связаться?
  25. Правила построения СКНФ по таблице истинности
  26. Правила построения СДНФ по таблице истинности
  27. Примеры нахождения СКНФ и СДНФ
  28. Построение СКНФ согласно таблице истинности
  29. Построение СДНФ согласно таблице истинности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Брокер системных событий можно отключить

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

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

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

a b a ∧ b a ∨ b ¬a ¬b a → b a = b a ⊕ b
1 1 1 1
1 1 1 1 1
1 1 1 1
1 1 1 1 1 1

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

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

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

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

Чтобы задать функцию через вектор значений необходимо записать вектор из 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. Построим таблицу истинности для функции

a b c ¬a ¬a ∧b ¬b ¬b ∧c ¬a ∧b∨ ¬b ∧c c∧a ¬a ∧b∨ ¬b ∧c∨c∧a
1 1
1 1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1
1 1
1 1 1 1 1 1 1
1 1
1 1 1 1 1

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

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

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

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

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

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

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

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

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

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

a b c F 1
1 1 ⊕ 0 1
1 1 1
1 1 1 ⊕ 1
1
1 1 1 ⊕ 0 1
1 1
1 1 1 1 ⊕ 0 1

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

a b c F 1 2
1 1 1 1
1 1 1 ⊕ 0 1
1 1 1 ⊕ 1 1
1
1 1 1 1 1
1 1 ⊕ 0
1 1 1 1 1 ⊕ 1

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

a b c F 1 2 3
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 ⊕ 0
1 1 1 1 1 ⊕ 1
1 1 ⊕ 1 1
1 1 1 1 1 ⊕ 1 1

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

a b c F 1 2 3
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1
1 1 1 1 1
1 1 1
1 1 1 1 1 1

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

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

А Вы знаете, что мы пишем программы на C, C++, C#, Pascal и Python?

Так что если Вам нужно написать программу на C/C++, C#, Pascal или Python — мы с радостью поможем с этим!

В том числе мы занимаемся репетиторством по информатике и программированию, а также готовим к ОГЭ и ЕГЭ!

Почему именно мы?

  • Более 1800 выполненных заказов;
  • Более 170 отзывов;
  • Качественное решение
  • Короткие сроки и привлекательные цены
  • Различные акции и скидки

Как с нами связаться?

  • группа Вконтакте: vk.com/programforyou
  • наша почта: order@programforyou.ru

Programforyou — позвольте нам писать код для вас и вы получите качественное решение в короткие сроки по привлекательной цене!

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

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

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

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

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

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

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

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

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

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

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

Попробуй обратиться за помощью к преподавателям

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

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

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

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

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

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

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

Читайте также:  Как в debian настроить wifi

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

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

Решение:

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

[Fleft(x_1, x_2, x_3
ight)=left(overlinewedge overlinewedge overline
ight)vee left(overline
wedge overlinewedge x_3
ight)vee left(x_1wedge overline
wedge overline
ight)vee left(x_1wedge overline
wedge x_3
ight)vee left(x_1wedge x_2wedge x_3
ight)]

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

[Fleft(x_1, x_2, x_3
ight)=left(x_1vee overlinevee x_3
ight)wedge left(x_1vee overline
vee overline
ight)wedge left(overlinevee overline
vee x_3
ight)]

Задай вопрос специалистам и получи
ответ уже через 15 минут!

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

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

Решение:

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

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

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

[Fleft(x_1,x_2,x_3,x_4
ight)=left(overlinewedge overlinewedge zwedge f
ight)vee left(overlinewedge x_2wedge overlinewedge overline
ight)vee left(overline
wedge x_2wedge x_3wedge x_4
ight)vee left(x_1wedge overlinewedge overlinewedge overline
ight).]

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

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

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

[Fleft(x_1,x_2,x_3,x_4
ight)=left(x_1vee x_2vee x_3vee x_4
ight)wedge left(x_1vee x_2vee x_3vee overline
ight)wedge left(x_1vee x_2vee overlinevee x_4
ight)wedge left(x_1vee overlinevee x_3vee overline

ight)wedge left(x_1vee overlinevee overlinevee x_4
ight)wedge left(overlinevee x_2vee x_3vee overline

ight)wedge left(overlinevee x_2vee overlinevee x_4
ight)wedge left(overline
vee x_2vee overlinevee overline

ight)wedge left(overlinevee overlinevee x_3vee x_4
ight)wedge left(overline
vee overlinevee x_3vee overline

ight)wedge left(overlinevee overlinevee overlinevee x_4
ight)wedge left(overline
vee overlinevee overlinevee overline

ight).]

Так и не нашли ответ
на свой вопрос?

Просто напиши с чем тебе
нужна помощь

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

Выделяют такие виды формы нормального типа:

  • КНФ (конъюнктивная нормальная форма), где подразумевается конъюнкция того или иного количества дизъюнкций, как пример, ;
  • ДНФ (дизъюнктивная нормальная форма), где осуществляется дизъюнкция конъюнкций, как пример, .

Совершенная КНФ является разновидностью конъюнктивной нормальной формы, удовлетворяющей такие условия:

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

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

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

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

  • отсутствие одинаковых элементарных конъюнкций;
  • конъюнкции не свойственно обладать одинаковыми переменными;

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

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

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

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

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

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

Прибегнем к правилу построения совершенной ДНФ

Получаем такую СДНФ

Задействовав правило её построения:

Представить функцию как СДНФ и СКНФ, при том, что она задаётся таблицей истинности.

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

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

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

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

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

Оцените статью
Adblock detector