Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 23 ноября 2018 года; проверки требуют 3 правки.
Совершенная конъюнктивная нормальная форма (СКНФ) — одна из форм представления функции алгебры логики (булевой функции) в виде логического выражения. Представляет собой частный случай КНФ, удовлетворяющий следующим трём условиям:
· в ней нет одинаковых множителей (элементарных дизъюнкций);
· в каждом множителе нет повторяющихся переменных;
· каждый множитель содержит все переменные, от которых зависит булева функция (каждая переменная может входить в множитель либо в прямой, либо в инверсной форме).
Любая булева формула, не являющаяся тождественно истинной, может быть приведена к СКНФ.[1].
Пример нахождения СКНФ[править | править код]
Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности статьи минимизация логических функций методом Квайна:
 |
 |
 |
 |
|
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.
Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:
В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
Первый член СКНФ рассматриваемой функции выглядит так: 
Остальные члены СКНФ составляются по аналогии:[2]
См. также[править | править код]
- Конъюнктивная нормальная форма
- Дизъюнктивная нормальная форма
- Совершенная дизъюнктивная нормальная форма
Примечания[править | править код]
- ↑ Математическая логика. Методические указания по курсу “Основы дискретной математики для студентов специальности 220220”. Дата обращения: 25 марта 2016. Архивировано 9 апреля 2016 года.
- ↑ В.И. Игошин. Задачник-практикум по математической логике. 1986
Диана Загировна Филиппенкова
Эксперт по предмету «Информатика»
Задать вопрос автору статьи
Нормальная форма логической формулы не содержит знаков импликации, эквивалентности и отрицания неэлементарных формул.
Нормальная форма существует в двух видах:
-
конъюнктивная нормальная форма (КНФ) — конъюнкция нескольких дизъюнкций, например, $left(Avee overline{B}vee Cright)wedge left(Avee Cright)$;
-
дизъюнктивная нормальная форма (ДНФ) — дизъюнкция нескольких конъюнкций, например, $left(Awedge overline{B}wedge Cright)vee left(Bwedge Cright)$.
СКНФ
Совершенная конъюнктивная нормальная форма (СКНФ) — это КНФ, удовлетворяющая трем условиям:
-
не содержит одинаковых элементарных дизъюнкций;
-
ни одна из дизъюнкций не содержит одинаковых переменных;
-
каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.
Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.
Правила построения СКНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием.
СДНФ
Совершенная дизъюнктивная нормальная форма (СДНФ) — это ДНФ, удовлетворяющая трем условиям:
-
не содержит одинаковых элементарных конъюнкций;
-
ни одна из конъюнкций не содержит одинаковых переменных;
-
каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.
Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.
Правила построения СДНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.
Примеры нахождения СКНФ и СДНФ
Пример 1
Записать логическую функцию по ее таблице истинности:
Рисунок 1.
Решение:
Воспользуемся правилом построения СДНФ:
Рисунок 2.
Получим СДНФ:
[Fleft(x_1, x_2, x_3right)=left(overline{x_1}wedge overline{x_2}wedge overline{x_3}right)vee left(overline{x_1}wedge overline{x_2}wedge x_3right)vee left(x_1wedge overline{x_2}wedge overline{x_3}right)vee left(x_1wedge overline{x_2}wedge x_3right)vee left(x_1wedge x_2wedge x_3right)]
Воспользуемся правилом построения СКНФ:
Рисунок 3.
Получим СКНФ:
[Fleft(x_1, x_2, x_3right)=left(x_1vee overline{x_2}vee x_3right)wedge left(x_1vee overline{x_2}vee overline{x_3}right)wedge left(overline{x_1}vee overline{x_2}vee x_3right)]
«Построение СКНФ и СДНФ по таблице истинности» 👇
Пример 2
Функция задана таблицей истинности:
Рисунок 4.
Представить эту функцию в виде СДНФ и СКНФ.
Решение:
-
Запишем логическую функцию в СДНФ. Для удобства решения добавим к таблице вспомогательный столбец.
Используя правило составления СДНФ не забываем вводить знак отрицания для переменных со значением 0. Инвертировать нулевые значения переменных обязательно, т.к. иначе они превратят значения конъюнкций в нули основной функции.
Рисунок 5.
Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:
[Fleft(x_1,x_2,x_3,x_4right)=left(overline{x}wedge overline{y}wedge zwedge fright)vee left(overline{x_1}wedge x_2wedge overline{x_3}wedge overline{x_4}right)vee left(overline{x_1}wedge x_2wedge x_3wedge x_4right)vee left(x_1wedge overline{x_2}wedge overline{x_3}wedge overline{x_4}right).]
-
Запишем логическую функцию в СКНФ.
Используя правило составления СКНФ не забываем вводить знак отрицания для переменных со значением 1. Инвертировать единичные значения переменных обязательно, т.к. иначе они превратят значения дизъюнкций в единицы основной функции.
Рисунок 6.
Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:
[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 overline{x_4}right)wedge left(x_1vee x_2vee overline{x_3}vee x_4right)wedge left(x_1vee overline{x_2}vee x_3vee overline{x_4}right)wedge left(x_1vee overline{x_2}vee overline{x_3}vee x_4right)wedge left(overline{x_1}vee x_2vee x_3vee overline{x_4}right)wedge left(overline{x_1}vee x_2vee overline{x_3}vee x_4right)wedge left(overline{x_1}vee x_2vee overline{x_3}vee overline{x_4}right)wedge left(overline{x_1}vee overline{x_2}vee x_3vee x_4right)wedge left(overline{x_1}vee overline{x_2}vee x_3vee overline{x_4}right)wedge left(overline{x_1}vee overline{x_2}vee overline{x_3}vee x_4right)wedge left(overline{x_1}vee overline{x_2}vee overline{x_3}vee overline{x_4}right).]
Находи статьи и создавай свой список литературы по ГОСТу
Поиск по теме
Содержание
- 1 КНФ
- 2 СКНФ
- 3 Алгоритм построения СКНФ по таблице истинности
- 4 Пример построения СКНФ для медианы
- 4.1 Построение СКНФ для медианы от трех аргументов
- 4.2 Построение СКНФ для медианы от пяти аргументов
- 5 Примеры СКНФ для некоторых функций
- 6 См. также
- 7 Источники информации
КНФ
| Определение: |
| Простой дизъюнкцией (англ. inclusive disjunction) или дизъюнктом (англ. disjunct) называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза. |
Простая дизъюнкция
- полная, если в неё каждая переменная (или её отрицание) входит ровно один раз;
- монотонная, если она не содержит отрицаний переменных.
| Определение: |
| Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов. |
Пример КНФ:
СКНФ
| Определение: |
Совершенная конъюнктивная нормальная форма, СКНФ (англ. perfect conjunctive normal form, PCNF) — это такая КНФ, которая удовлетворяет условиям:
|
Пример СКНФ:
| Теорема: |
|
Для любой булевой функции , не равной тождественной единице, существует СКНФ, ее задающая. |
| Доказательство: |
|
Поскольку инверсия функции равна единице на тех наборах, на которых равна нулю, то СДНФ для можно записать следующим образом: Найдём инверсию левой и правой части выражения: Применяя дважды к полученному в правой части выражению правило де Моргана, получаем: Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана. |
Алгоритм построения СКНФ по таблице истинности
- В таблице истинности отмечаем те наборы переменных, на которых значение функции равно .
- Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть , то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
- Все полученные дизъюнкции связываем операциями конъюнкции.
Пример построения СКНФ для медианы
Построение СКНФ для медианы от трех аргументов
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно .
| x | y | z | |
| 0 | 0 | 0 | 0 |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть , то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
| x | y | z | ||
| 0 | 0 | 0 | 0 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
3. Все полученные дизъюнкции связываем операциями конъюнкции.
Построение СКНФ для медианы от пяти аргументов
| 0 | 0 | 0 | 0 | 0 | 0 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | |
| 0 | 0 | 0 | 1 | 0 | 0 | |
| 0 | 0 | 0 | 1 | 1 | 0 | |
| 0 | 0 | 1 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 0 | |
| 0 | 0 | 1 | 1 | 0 | 0 | |
| 0 | 0 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | 0 | 0 | |
| 0 | 1 | 0 | 1 | 1 | 1 | |
| 0 | 1 | 1 | 0 | 0 | 0 | |
| 0 | 1 | 1 | 0 | 1 | 1 | |
| 0 | 1 | 1 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 0 | 0 | 1 | 1 | 1 | |
| 1 | 0 | 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 0 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 0 | 1 | |
| 1 | 0 | 1 | 1 | 1 | 1 | |
| 1 | 1 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 0 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | 0 | 1 | |
| 1 | 1 | 0 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 0 | 0 | 1 | |
| 1 | 1 | 1 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 1 | 1 |
Примеры СКНФ для некоторых функций
Стрелка Пирса:
Исключающее или:
См. также
- Специальные формы КНФ
- ДНФ
Источники информации
- Википедия — СКНФ
- Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика
Совершенная конъюнктивная нормальная форма (скнф).
Конъюнктивной
нормальной формой (КНФ)
называется форма представления функции
в виде конъюнкции ряда членов, каждый
из которых является простой дизъюнкцией
аргументов (или их инверсий).
Примером КНФ может
служить следующая форма представления
функции:
Приведем формы
представления функций, не являющиеся
КНФ:
(здесь третий член
не является простой дизъюнкцией
аргументов или их инверсий);
(эта форма также не
является КНФ, так как в ней первый член
не связан с остальными операцией
конъюнкции).
В
совершенной
конъюнктивной нормальной форме (СКНФ)
в каждом члене КНФ должны быть представлены
все аргументы.
Для
перехода от КНФ к СКНФ необходимо
добавить к каждому члену, не содержащему
всех аргументов, члены вида , где хi
— аргумент, не представленный в члене.
Так как
,
то такая операция не может повлиять на
значение функции.
Добавление к
некоторому члену образует выражение
вида , которое можно привести к виду
Справедливость
данного равенства вытекает из
распределительного закона;
она может быть
показана также путем раскрытия скобок
в правой части выражения:
так
как
Рассмотрим переход
от КНФ к СКИФ на примере функции
Покажем применение
распределительного закона прн проведении
использованных здесь преобразований
над одним из членов выражения
Обозначим Тогда на
основании распределительного закона
Далее обозначим и
вновь применим распределительный закон
Подставив
сюда значения z1
и z2
получим соответствующие члены приведенного
выше выражения при переходе от КНФ к
СКНФ.
Совершенная КНФ
функции легко строится по таблице
истинности.
Рассмотрим в
качестве примера функцию, приведенную
в табл. 3.4; СКНФ этой функции имеет вид
|
|
(3.11) |
Выражение
содержит столько членов, связанных
операцией конъюнкции, сколько нулей
имеется среди значений функции f(x1,
x2,
x3)
в таблице истинности. Таким образом,
каждому набору значений аргументов, на
котором функция равна нулю, соответствует
определенный член СКНФ, принимающий на
этом наборе значение нуль. Так как члены
СКНФ связаны операцией конъюнкции, при
обращении в нуль одного из членов и вся
функция оказывается равной нулю.
Таким образом, можно
сформулировать следующее правило записи
СКНФ функции, заданной таблицей
истинности.
Следует записать
столько конъюнктивных членов,
представляющих собой дизъюнкции всех
аргументов, при скольких наборах значений
аргументов функция равна нулю, и если
в наборе значение аргумента равно
единице, то в дизъюнкцию входит инверсия
этого аргумента. Любая функция имеет
единственную СКНФ.
Структурная схема
логического устройства может быть
построена непосредственно по канонической
форме (СДНФ или СКНФ) реализуемой функции.
Получающиеся при этом схемы для функций
(3.10) и (3.11) показаны на рис. 3.26, а и б.
Недостаток такого метода построения
структурных схем, обеспечивающего, в
общем, правильное функционирование
устройства, состоит в том, что получающиеся
схемы, как правило, оказываются
неоправданно сложными, требуют
использования большого числа логических
элементов и, следовательно, имеют низкие
экономичность и надежность.
Во многих случаях
удается так упростить логическое
выражение, не нарушая функции, что
соответствующая структурная схема
оказывается существенно более простой.
Методы
такого упрощения функции, называемые
методами
минимизации функций,
рассматриваются ниже.
рис 3.26
Соседние файлы в папке 3 курс (заочка)
- #
- #
- #
- #
- #
- #
- #
- #
- #
Что такое СДНФ
Нормальная форма логической формулы характеризуется тем, что для нее не свойственны эквивалентность, отрицание формул неэлементарного типа и знаки импликации.
Существует две формы нормального типа: КНФ (конъюнктивная нормальная форма) и ДНФ (дизъюнктивная нормальная форма).
Определение
СДНФ — совершенная дизъюнктивная нормальная форма формулы. СДНФ — способ написания функции алгебры логики в качестве логического выражения.
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
СДНФ формулы — это равнозначная ей формула, которая представляет собой дизъюнкцию элементарных конъюнкций, при которых функция достигает показателя «1».
ДНФ выглядит следующим образом:
((A;wedge;overline B;wedge;C);vee;(B;wedge;C))
СДНФ обладает некоторыми определенными свойствами:
- включает различные элементарные конъюнкции;
- все логические слагаемые формулы содержат все переменные, которые входят в функцию F;
- ни в одном логическом слагаемом не содержится переменная и её отрицание.
К СДНФ возможно привести любую формулу алгебры логики. Исключение составляет только тождественно ложная формула. СДНФ можно получить как используя таблицы истинности, так и через равносильные преобразования.
Примечание
При построении таблицы истинности важно помнить, что логические переменные со значением «0» необходимо брать с отрицанием.
Что такое СКНФ
Определение
СКНФ — совершенная конъюнктивная нормальная форма. Формулу можно назвать таковой, когда она — конъюнкция неповторяющихся элементарных дизъюнкций.
КНФ имеет вид:
((A;vee;overline B;vee;C);wedge;(A;vee;C))
Формула должна соответствовать нескольким условиям, чтобы называться СКНФ:
- в ней отсутствуют одинаковые элементарные дизъюнкции;
- дизъюнкции не содержат одинаковые переменные;
- все дизъюнкции содержат каждую переменную из входящих в конъюнктивную нормальную функцию такого типа.
Правила построения по таблице истинности
Дизъюнктивная форма
Если функция равна 1, то для всех наборов переменных, при которых это происходит, записывается произведение. Однако переменные, которые имеют значение 0, берутся с отрицанием.
Конъюнктивная форма
Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.
Алгоритм приведения к СДНФ и СКНФ
Рассмотрим логическую функцию в виде таблицы истинности.
Алгоритм построения СДНФ по таблице истинности выглядит следующим образом:
- Отметить наборы переменных, значение функции F на которых равно 1.
- Записать для всех отмеченных наборов конъюнкцию всех переменных так: если значение некоторой переменной в этом наборе равняется 1, в конъюнкцию включается сама переменная. В случае противного результата, в конъюнкцию включается ее отрицание.
- Связать полученные конъюнкции операциями дизъюнкции.
Построим совершенную ДНФ:
И как результат получим следующую СДНФ:
(F(x_1,;x_2,;x_3);=;(overline{x_1}wedgeoverline{x_2}wedgeoverline{x_3});vee(overline{x_1};wedge;overline{x_2};wedge;x_3);vee(x_1;wedge;overline{x_2};wedge;overline{x_3});vee;(x_1;wedge;overline{x_2};wedge;x_3);vee;(x_1;wedge;x_2;wedge;x_3))
Алгоритм построения СКНФ по таблице истинности выглядит следующим образом:
- Отметить в таблице истинности наборы переменных, значение функции F на которых равно 0.
- Записать для всех отмеченных наборов дизъюнкцию всех переменных — в том случае, когда значение некоторой переменной в этом наборе равняется 0, в дизъюнкцию включается сама переменная, если происходит наоборот, то в дизъюнкцию включается ее отрицание.
- Связать полученные дизъюнкции операциями конъюнкции.
Построим совершенную КНФ:
И как результат получим следующую СКНФ:
(F(x_1,;x_2,;x_3);=;(x_1;vee;overline{x_2};vee;x_3);wedge;(x_1;vee;overline{x_2};vee;overline{x_3});wedge;(overline{x_1};vee;overline{x_2};vee;x_3))
Рассмотрев алгоритмы построения СДНФ и СКНФ ясно, что в случае подавляющей части наборов значений переменных функция равна 0, то значительно легче построить и СДНФ для получения ее формулы, а в обратном случае — СКНФ.
Доказательство эквивалентности
Эквивалентность — понятие, означающее, что две и более формул представляют одну и ту же функцию. Для обозначения эквивалентности могут использоваться следующие знаки: ( equiv , = , Leftrightarrow .)
Доказать эквивалентность формул можно двумя способами.
- Первый заключается в построении и сравнении таблиц истинности обеих функций. В этом случае результат будет истинным только в том случае, когда оба высказывания либо ложны, либо истинны.
- Второй вариант — метод эквивалентных преобразований. Суть этого метода — построение цепи эквивалентных формул на основе ранее доказанных эквивалентностей.
Далее следуют примеры с некоторыми эквивалентными преобразованием в булевой алгебре и новыми эквивалентностями, которые возможно получить с их помощью.
Поглощение
(x;vee;xy;=;x)
(x(x;vee;y);=;x;)
Доказательство эквивалентности:
(x;vee;xy;=;x;cdot;l;vee;xy;=;x(l;vee;y);=;x)
(x(x;vee;y);=;xx;vee;xy;=;x;vee;xy;=;x)
Склеивание
(xy;vee;xoverline y;=;x)
Доказательство эквивалентности:
(xy;vee;xoverline y;=;x(y;vee;overline y);=;x;cdot;l;=;x)
Обобщенное склеивание
(xz;vee;yoverline z;vee;xy;=;xz;vee yoverline z)
Доказательство эквивалентности
(xz;vee;yoverline z;vee;xy;=;xz;vee yoverline z;vee;xyz;vee;xyoverline z;=;xz;vee;yoverline z)
Расщепление
(x;vee;overline xy;=;x;vee;y)
Доказательство эквивалентности
(x;vee;overline xy;=;xy;vee;xoverline y;vee;overline xy;=;xy;vee;xoverline y;vee;xy;vee;overline xy;=;x;cdot;l;;vee;y;cdot;l;=;x;vee;y)
Примеры с решением
Задача №1
Приведите к СКНФ (((((Arightarrow B)rightarrowoverline A)rightarrowoverline B)rightarrowoverline C)).
Через применение закона де Моргана и правила( x;rightarrow;y;=;overline x;vee;y) упростим выражения:
(F;=;((((A;rightarrow;B);rightarrow;overline A);rightarrowoverline B);rightarrow;overline C);=;(((overline A;vee;B);rightarrow;overline A);rightarrow;overline B);rightarrowoverline C;);=)
(=;((((overline A;vee;B);rightarrowoverline A);rightarrowoverline B);rightarrow;overline C);=;((overline{((overline A;vee;B)};vee;overline A);rightarrowoverline B);rightarrowoverline C);=)
(=(((overline A;vee;B);vee;overline A);rightarrow;overline B);rightarrow;overline C);=((overline{(overline{(overline Avee B)};vee;overline A;)};vee;overline B);rightarrow;overline C);=)
(=;(overline{(overline{(overline{(overline A;vee;B)};vee;overline A)};vee;overline B)};vee;overline C);=;(((A;vee;B);vee;overline A);vee;overline B);vee;overline C;=)
(=;((overline{(overline A;vee;B)};vee;overline A);wedge;B);vee;overline C;=;(((A;wedge;overline B);vee;overline A);wedge B);vee;overline C;=)
(=((Aoverline B;vee;overline A);vee;overline A);wedge;B);vee;overline C;=(((A;wedge;overline B);vee;overline A);wedge;B);vee;overline C;=)
(=;((Aoverline B;vee;overline A);wedge;B);vee;overline C;=;(Aoverline BB;vee;overline AB);vee;overline C;=;(0;vee;overline AB);vee;overline C;=;overline AB;vee;overline C)
Далее приведем выражение к КНФ:
(F;=;overline AB;vee;overline C;;=;(overline A;vee;overline C);wedge;(B;vee;overline C))
Далее приведем выражение к СКНФ:
(F;=;(overline A;vee;overline C);wedge;(B;vee;overline C);=;(overline A;vee:overline C;vee;Boverline B);wedge;(Aoverline A;vee;B;v;overline C);=)
(=;(overline A;vee;overline C;vee;B);wedge;(A;vee;B;vee;overline C);wedge;(overline A;vee;overline C;vee;overline B);wedge;(overline A;vee;B;;overline C))
Задача №2
Используя эквивалентные преобразования, постройте ДНФ функции (f(widetilde x^n))
(f(widetilde x^3) = (overline{x_1}x_2;oplus;x_3);cdot;(x_1x_3;rightarrow;x_2))
Преобразуем функцию:
(f(widetilde x^3) = (overline{x_1}x_2;oplus;x_3);cdot;(x_1x_3;rightarrow;x_2) = ((overline{x_1}x_2;cdot;overline{x_3};);vee;(overline{overline{x_1}x_2};cdot;x_3));cdot;(overline{x_1x_3};vee;x_2);=)
(=;((overline{x_1}x_2overline{x_3});vee;((overline{overline{x_1}};vee;overline{x_2});x_3);cdot;(overline{x_1};vee;overline{x_3};vee;x_2);=;((overline{x_1}x_{2;}overline{x_3});vee;((x_1;vee;overline{x_2});x_3);cdot;(overline{x_1};vee;overline{x_3};vee;x_2);=)
(=;(overline{x_1}x_2overline{x_3};vee;x_1x_3;vee;overline{x_2}x_3);cdot;(overline{x_1};vee;overline{x_3};vee;x_2);=)
(=(overline{x_1}x_2overline{x_3};cdot(x_1vee x_3vee x_2);vee;x_1x_3;cdot;(overline{x_1};vee;overline{x_3};vee;x_2);vee;overline{x_2}x_3;cdot;(overline{x_1};vee;overline{x_3};vee;x_2));=)
(=;(overline{x_1}x_2overline{x_3};vee;(x_1;x_3overline{x_1};vee;x_1x_3overline{x_3};vee;x_1x_3x_2);vee;(overline{x_2}x_3overline{x_1};vee;overline{x_2}x_3overline{x_3};vee;overline{x_2}x_3x_2);=)
(=;(overline{x_1}x_2overline{x_3};vee;0;vee;0;vee;x_1x_2x_3;vee;overline{x_1}overline{x_2}x_3;vee;0;vee;0);=)
(=;overline{x_1}x_2overline{x_3};vee;x_1x_2x_3;vee;overline{x_1}overline{x_2}x_3)
