Как перевести днф в кнф
«Учебник по дискретной математике ДНФ, СДНФ, КНФ, СКНФ»
Например, 
является простой конъюнкцией,
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.
Например, выражение 
является ДНФ.
Например, выражение 
является ДНФ, но не СДНФ. Выражение 
является СДНФ.
Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.
Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание).Например, выражение 
– простая дизъюнкция,
Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение 
– КНФ).
Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.
Например, выражение 
является СКНФ.
Приведем алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы:
а) переход от ДНФ к КНФ
Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:
Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;
б) переход от КНФ к ДНФ
Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)
Таким образом, получили ДНФ.
Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;
в) сокращение ДНФ (или СДНФ) по правилу Блейка
Применение этого правила состоит из двух частей:
— если среди дизъюнктных слагаемых в ДНФ имеются слагаемые 
, то ко всей дизъюнкции добавляем слагаемое К1К2. Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;
— если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например, 
Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ 
, после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):
в) переход от ДНФ к СДНФ
Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение 
,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:
г) переход от КНФ к СКНФ
Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение 
(это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):
Таким образом, из КНФ получена СКНФ.
Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.
Как привести к днф и кнф
Простой конъюнкцией называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза (либо сама, либо ее отрицание).
Например, 
является простой конъюнкцией,
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.
Например, выражение 
является ДНФ.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке.
Например, выражение 
является ДНФ, но не СДНФ. Выражение 
является СДНФ.
Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.
Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание).Например, выражение 
– простая дизъюнкция,
Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение 
– КНФ).
Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.
Например, выражение 
является СКНФ.
Приведем алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы:
а) переход от ДНФ к КНФ
Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:
Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;
б) переход от КНФ к ДНФ
Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)
Таким образом, получили ДНФ.
Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;
в) сокращение ДНФ (или СДНФ) по правилу Блейка
Применение этого правила состоит из двух частей:
— если среди дизъюнктных слагаемых в ДНФ имеются слагаемые 
, то ко всей дизъюнкции добавляем слагаемое К1К2. Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;
— если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например, 
Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ 
, после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):
в) переход от ДНФ к СДНФ
Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение 
,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:
г) переход от КНФ к СКНФ
Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение 
(это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):
Таким образом, из КНФ получена СКНФ.
Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.
4. Представление логических функций
в виде СДНФ (СКНФ)
(*)
а) Пусть f(x1, x2, …, xn)= 1. Тогда слева в формуле (* ) стоит 1. Докажем, что и справа в этом случае стоит 1, для чего достаточно указать одно дизъюнктное слагаемое, равное 1. Но среди всех наборов (s1, s2, …, sп) имеется набор s1 = х1, s2 = х2, …, sп = хп. Очевидно, что для этого набора слагаемое 
равно 1 (так как и 
.
б) Пусть f(x1, x2, …, xn) = 0. Предположим, что справа стоит не ноль, а единица, тогда какое-то слагаемое тоже должно равняться 1, т. е. для некоторого набора
Доказательство. Пусть f(x1,x2,…,xn) не равна тождественному нулю, тогда в дизъюнкции можно не записывать слагаемые, равные нулю, а из формулы (* ) следует следующее представление для данной функции
Следствие. Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание.
Набор функций, через которые можно выразить любые другие функции, называется полным набором (более точные формулировки даны в разд. 7). Таким образом, конъюнкция, дизъюнкция и отрицание являются полным набором.
По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х1, х2, …, хп), для которых f(x1, x2,…, xn) = 0, причем если хi = 1, то в этой дизъюнкции берем 
, если же хi = 0, то берем хi.
Пример. Составить для импликации и сложения по модулю 2 СДНФ и СКНФ.
Тогда СДНФ для этих функций:
СКНФ для этих функций:
5. Нахождение сокращенной ДНФ
по таблице истинности (карты Карно)
Доказано, что любую функцию (кроме тождественного нуля) можно представить в виде СДНФ. На практике часто бывает удобно получить (вместо СДНФ) как можно более “короткую” ДНФ. Словам “короткая ДНФ” можно придать разный смысл, а именно:
ДНФ называется минимальной, если она содержит наименьшее число букв (разумеется, среди всех ДНФ ей равносильных); ДНФ называется кратчайшей, если она содержит минимальное число знаков дизъюнкции Ú ; тупиковой, если уничтожение одной или нескольких букв в ней приводит к неравной ДНФ и сокращенной ДНФ, если ее упрощение проведено с помощью правила Блейка.
На практике наиболее важной представляется нахождение минимальной ДНФ, но алгоритм ее нахождения по существу является вариантом перебора всех равносильных ДНФ. Алгоритмически проще всего находить сокращенную ДНФ (эти алгоритмы были даны в разд. 3). Заметим, что если функция п переменныхзаданасвоейтаблицей истинности, топравило Блейка имеет простой геометрический смысл. Именно, если все возможные наборы переменных представить себе как вершины п-мерного куба со стороной равной 1 (всего вершин будет 2 п ) в декартовой системе координат, то надо отметить те вершины, на которых значение функции равно 1, и если какие-то из этих единиц лежат на “прямой”, “плоскости” или “гиперплоскости” в п-мерном пространстве, то в сокращенную ДНФ будут входить “уравнения” этих прямых или гиперплоскостей по известному правилу: если в это уравнение входило составной частью х = 0,то в сокращенную ДНФ входит 
, если х = 1, то просто х.Разумеется, геометрически все это изобразить можно только при п = 2, 3.
Карты Карно позволяют эти геометрические идеи использовать при п = 3, 4, 5, для функций, заданных своей таблицей истинности. При больших п картыКарнопрактическинеиспользуются. Рассмотрим отдельно (и более подробно) случаи п = 3, 4.
Составляем таблицу истинности для данной конкретной функции п = 3 в виде таблицы, приведенной в примере 5.1. (Заметим, что для х1и х2естественный порядок набора переменных здесь нарушен. Это сделано для того, чтобы при переходе от данного к следующему набору переменных в этом наборе менялась только одна цифра). Прямая содержит 2 вершины, плоскость – 4, гиперплоскости – 8, 16 и т. д. вершин, поэтому объединять можно 2 рядом стоящие единицы или 4, 8, 16 и т. д. Карты Карно соединяются “по кругу”, т. е. наборы (10) и (00) считаются рядом стоящими.
Пример 5.1. Пусть задана функция:
Видно, ее СДНФ содержит (по числу 1) 6 дизъюнктных слагаемых, но ее сокращенная ДНФ содержит (после объединения единиц) всего 2 буквы
Пример 5.2. Следующий пример показывает, “как соединять единицы по кругу”.
Здесь сокращенная ДНФ содержит 2 слагаемых (СДНФ содержала бы 5):
Пример 5.3. Пример показывает использование карт Карно при п = 4.
Здесь сокращенная ДНФ содержит 4 слагаемых (СДНФ содержит 8): 
При п = 5 использование карт Карно является несколько более сложным и здесь не приводится.
1. Исключение из Л связок -> и =, используя теоремы:
В результате этих действий связка будет расставлена в формуле А только перед пропозициональными символами или перед их отрицаниями. Вследствие этого могут появиться выражения вида —•—./?.
3. Удаление двойных отрицаний в соответствии с законом двойного отрицания 
4. Применение закона дистрибутивности
необходимое число раз, пока не будет получена КНФ.
Для получения ДНФ этим же алгоритмом нужно на этапе 4 применять второй из законов дистрибутивности
необходимое число раз, пока не будет получена ДНФ.
Пример. Приведем к КНФ следующую формулу:
1. Исключение импликаций
2. Внесение связки внутрь скобок
3. Удаление двойных отрицаний
4. Применение закона дистрибутивности (av(bAC)) v ((avb)A(avc)) 
Следовательно, исходная формула эквивалентна КНФ D]aD2 aD3, где
Приведение к ДНФ той же формулы выполняется точно также, и видно, что уже на этапе 3 искомая ДНФ построена, т. е. исходная формула эквивалентна ДНФ C1vC2vC3vC4, где 
Конъюнктивная нормальная форма играет важную роль в обработке знаний на ЭВМ: дизъюнкты, входящие в КНФ, являются посылками в принципе резолюции, используемом в качестве единственного правила вывода в механизме вывода языков логического программирования. Например, синтаксической основой языка программирования PROLOG являются предложения Хорна, а его логической основой является принцип резолюции.
Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ. [1] Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.
Содержание
Примеры и контрпримеры [ править | править код ]
Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:
Построение КНФ [ править | править код ]
Алгоритм построения КНФ [ править | править код ]
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Пример построения КНФ [ править | править код ]
Приведем к КНФ формулу
Преобразуем формулу F 
к формуле, не содержащей → :
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
По закону дистрибутивности получим КНФ:
k-конъюнктивная нормальная форма [ править | править код ]
k-конъюнктивной нормальной формой называют конъюнктивную нормальную форму, в которой каждая дизъюнкция содержит ровно k литералов.
Например, следующая формула записана в 2-КНФ:
Переход от КНФ к СКНФ [ править | править код ]
Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в неё выражение : Z ∧ ¬ Z = 0 (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:
Таким образом, из КНФ получена СКНФ.
Формальная грамматика, описывающая КНФ [ править | править код ]
Следующая формальная грамматика описывает все формулы, приведенные к КНФ:
где обозначает произвольную булеву переменную.
Задача выполнимости формулы в КНФ [ править | править код ]
В теории вычислительной сложности важную роль играет задача выполнимости булевых формул в конъюнктивной нормальной форме. Согласно теореме Кука, эта задача NP-полна, и она сводится к задаче о выполнимости формул в 3-КНФ, которая сводится и к которой в свою очередь сводятся другие NP-полные задачи.
Задача о выполнимости 2-КНФ формул может быть решена за линейное время.
Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.
Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.
Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина
введите функцию или её вектор
Построено таблиц, форм:
Как пользоваться калькулятором
Видеоинструкция к калькулятору
Используемые символы
Для смены порядка выполнения операций используются круглые скобки ().
Обозначения логических операций
Что умеет калькулятор
Что такое булева функция
Что такое таблица истинности?
Довольно часто встречается вариант таблицы, в которой число столбцов равно n + число используемых логических операций. В такой таблице также первые n столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.
Логические операции
Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).
Таблица истинности логических операций
| a | b | a ∧ b | a ∨ b | ¬a | ¬b | a → b | a = b | a ⊕ b |
| 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 ∨ 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
Алгоритм построения СДНФ для булевой функции
Алгоритм построения СКНФ для булевой функции
Алгоритм построения полинома Жегалкина булевой функции
Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.
Примеры построения различных представлений логических функций
Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных 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 |
| 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 >
В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 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 | |
| 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 0 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 1 | 1 | 0 | 0 | → | 0 |
| 1 | 1 | 1 | 1 | ⊕ 0 | 1 |
Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:
| a | b | c | F | 1 | 2 | |
| 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | 1 | → | 1 |
| 1 | 1 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:
| a | b | c | F | 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | → | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | ⊕ 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
Окончательно получим такую таблицу:
| a | b | c | F | 1 | 2 | 3 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):
Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc
Programforyou — это сообщество, в котором Вы можете подтянуть свои знания по программированию, узнать, как эффективно решать те или иные задачи, а также воспользоваться нашими онлайн сервисами.