Днф и кнф примеры с решением

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

Самый простой метод построения совершенной дизъюнктивной и конъюнктивной нормальных форм – с помощью таблиц истинности. Для перехода к ДНФ и КНФ используют методы эквивалентных преобразований, правила де Моргана, свойства поглощения, правило Блейка и т.п.

Полином Жегалкина может быть построен как с помощью последовательных преобразований, так и по таблице истинности (метод неопределенных коэффициентов).

Все эти примеры разобраны ниже. Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.

Другие примеры решений о булевых функциях:

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

Нормальные формы (КНФ, СКНФ, ДНФ и СДНФ): примеры решений

Задача 1. Привести к КНФ и СКНФ.

$$((((A o B) o ar A) o ar B) o ar C).$$

Задача 2. С помощью эквивалентных преобразований построить д.н.ф. функции:

$$f(x)=(overlinex_2 oplus x_3) cdot (x_1 x_3 o x_2) $$

Задача 3. Используя СКНФ, найдите наиболее простую формулу алгебры высказываний от четырех переменных, принимающую значение 0 на следующих наборах значений переменных, и только на них:

Задача 4. Привести данные выражения к ДНФ, пользуясь правилами де Моргана. Если возможно, сократить ДНФ, используя свойство поглощения и правило Блейка.

Многочлен Жегалкина: примеры решений

Задача 5. Представив функцию формулой над множеством связок $<&, ->$, преобразовать затем полученную формулу в полином Жегалкина функции $f(x)$ (используя эквивалентности):

$$f(x) = (x_1 vee x_2) cdot (x_2 | x_3)$$

Задача 6. Задана булева функция: $$ f(x_1, x_2, x_3) = overline vee ((x_1 wedge overline ) | overline<(x_2 | overline )>$$ А) Построить таблицу истинности, найти двоичную форму булевой функции и привести ее к СДНФ и СКНФ.
Б) Найти многочлен Жегалкина.

Задача 7. Для заданной логической функции перейти к полиному Жегалкина.

Решение задач на заказ

Выполняем для студентов очников и заочников решение заданий, контрольных и практических работ по любым разделам булевой алгебры, в том числе задачи по построению СДНФ, СКНФ, полинома Жегалкина на заказ. Также оказываем помощь в сдаче тестов. Подробное оформление, таблицы, графики, пояснение, использование специальных программ при необходимости. Стоимость примера от 100 рублей , оформление производится в Word, срок от 2 дней.

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

Например, является простой конъюнкцией,

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

Например, выражение является ДНФ.

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

Например, выражение является ДНФ, но не СДНФ. Выражение является СДНФ.

Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.

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

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение – КНФ).

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

Например, выражение является СКНФ.

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

а) переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;

б) переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)

Таким образом, получили ДНФ.

Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;

в) сокращение ДНФ (или СДНФ) по правилу Блейка

Применение этого правила состоит из двух частей:

– если среди дизъюнктных слагаемых в ДНФ имеются слагаемые , то ко всей дизъюнкции добавляем слагаемое К₁К₂. Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;

– если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,

Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ , после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):

в) переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

г) переход от КНФ к СКНФ

Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):

Таким образом, из КНФ получена СКНФ.

Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.

4. Представление логических функций
в виде СДНФ (СКНФ)

Будем использовать логическую функцию “эквивалентность”, записанную в виде х у . Напомним, что 0 0 = 1; 0 1 =0; 1 0 = 0; 1 1 = 1.Таким образом, х у = 1 тогда и только тогда, когда х = у.

Лемма. Любая логическая функция f(x₁, x₂, …, x_n) может быть представлена в виде дизъюнкции 2 п дизъюнктных слагаемых, причем дизъюнкция берется по всевозможным наборам из E n . Этот факт будем записывать следующим образом:

(*)

где дизъюнкция проводится по всевозможным наборам (s₁, s₂, …, s_п) из Е п .

а) Пусть f(x₁, x₂, …, x_n)= 1. Тогда слева в формуле (* ) стоит 1. Докажем, что и справа в этом случае стоит 1, для чего достаточно указать одно дизъюнктное слагаемое, равное 1. Но среди всех наборов (s₁, s₂, …, s_п) имеется набор s₁ = х₁, s₂ = х₂, …, s_п = х_п. Очевидно, что для этого набора слагаемое равно 1 (так как и .

б) Пусть f(x₁, x₂, …, x_n) = 0. Предположим, что справа стоит не ноль, а единица, тогда какое-то слагаемое тоже должно равняться 1, т. е. для некоторого набора

Это означает (по свойствам конъюнкции), что , откуда следует, что х₁=s₁, х₂=s₂ ,…, х_п=s_n, но в этом случае f ( s₁, s₂, . s_n) f(x_1,x₂, …,x_n) = 0 и, значит, справа нет слагаемого, равного 1, т. е. в этом случае и справа и слева в формуле (* ) стоит 0. Лемма доказана.

Теорема. Если булева функция не равна тождественному нулю, то ее можно представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборы переменных (х₁,х_2, …,х_n), для которых f(х₁,х₂, …,х_n) =1, и составляем простую конъюнкцию для этого набора так: если х_i = 0, то берем в этой конъюнкции , если х_i = 1, то берем х_i. Составляя дизъюнкцию этих простых конъюнкций, придем к СДНФ.

Доказательство. Пусть f(x_1,x₂,…,x_n) не равна тождественному нулю, тогда в дизъюнкции можно не записывать слагаемые, равные нулю, а из формулы (* ) следует следующее представление для данной функции

Запись означает, что дизъюнкция берется по всем наборам ( s₁, s₂, . s_n) , для которых f ( s₁, s₂, . s_n) = 1. Так как (если s₁=0), из формулы (**) следует утверждение теоремы.

Следствие. Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание.

Из предыдущей теоремы видно, что следствие верно для любой функции, не равной тождественному нулю. Однако если f(x₁, x₂,…, x_{n) =}0, то ее также можно выразить через конъюнкцию, дизъюнкцию и отрицание, например, так: f(x₁, x₂,…, x_{n) = x1} ,и, несмотря на то, что последнее выражение не является простой конъюнкцией (и, значит, не является СДНФ), тем не менее тождественный ноль также выражен через нужные три функции.

Набор функций, через которые можно выразить любые другие функции, называется полным набором (более точные формулировки даны в разд. 7). Таким образом, конъюнкция, дизъюнкция и отрицание являются полным набором.

По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х₁, х₂, …, х_п), для которых f(x₁, x₂,…, x_n) = 0, причем если х_i = 1, то в этой дизъюнкции берем _, если же х_i = 0, то берем х_i.

Пример. Составить для импликации и сложения по модулю 2 СДНФ и СКНФ.

х

у

х® у

х + у

Тогда СДНФ для этих функций:

СКНФ для этих функций:

5. Нахождение сокращенной ДНФ
по таблице истинности (карты Карно)

Доказано, что любую функцию (кроме тождественного нуля) можно представить в виде СДНФ. На практике часто бывает удобно получить (вместо СДНФ) как можно более “короткую” ДНФ. Словам “короткая ДНФ” можно придать разный смысл, а именно:

ДНФ называется минимальной, если она содержит наименьшее число букв (разумеется, среди всех ДНФ ей равносильных); ДНФ называется кратчайшей, если она содержит минимальное число знаков дизъюнкции Ú ; тупиковой, если уничтожение одной или нескольких букв в ней приводит к неравной ДНФ и сокращенной ДНФ, если ее упрощение проведено с помощью правила Блейка.

На практике наиболее важной представляется нахождение минимальной ДНФ, но алгоритм ее нахождения по существу является вариантом перебора всех равносильных ДНФ. Алгоритмически проще всего находить сокращенную ДНФ (эти алгоритмы были даны в разд. 3). Заметим, что если функция п переменныхзаданасвоейтаблицей истинности, топравило Блейка имеет простой геометрический смысл. Именно, если все возможные наборы переменных представить себе как вершины п-мерного куба со стороной равной 1 (всего вершин будет 2 п ) в декартовой системе координат, то надо отметить те вершины, на которых значение функции равно 1, и если какие-то из этих единиц лежат на “прямой”, “плоскости” или “гиперплоскости” в п-мерном пространстве, то в сокращенную ДНФ будут входить “уравнения” этих прямых или гиперплоскостей по известному правилу: если в это уравнение входило составной частью х = 0,то в сокращенную ДНФ входит , если х = 1, то просто х.Разумеется, геометрически все это изобразить можно только при п = 2, 3.

Карты Карно позволяют эти геометрические идеи использовать при п = 3, 4, 5, для функций, заданных своей таблицей истинности. При больших п картыКарнопрактическинеиспользуются. Рассмотрим отдельно (и более подробно) случаи п = 3, 4.

Составляем таблицу истинности для данной конкретной функции п = 3 в виде таблицы, приведенной в примере 5.1. (Заметим, что для х₁и х₂естественный порядок набора переменных здесь нарушен. Это сделано для того, чтобы при переходе от данного к следующему набору переменных в этом наборе менялась только одна цифра). Прямая содержит 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. Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
2. Укажите действия, которые необходимо выполнить с помощью переключателей
3. Укажите, требуется ли вывод решения переключателем "С решением"
4. Нажмите на кнопку "Построить"

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

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

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

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

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

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

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

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

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

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

Булева функция 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 столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.

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

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

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

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 — позвольте нам писать код для вас и вы получите качественное решение в короткие сроки по привлекательной цене!