Oc-windows.ru

IT Новости из мира ПК
41 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Восстановите логическую функцию по ее таблице истинности

скнф и сднф — что это?

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

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

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

КНФ: (left (xvee barvee z right )wedge left (yvee z right ))

ДНФ: ( left (xwedge barwedge z right )vee left (ywedge z right ))

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

СКНФ: ( (xvee yvee bar)wedge ( xvee barvee z ))

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

СДНФ: ( ( xwedge ywedge bar) vee ( xwedge bar wedge z ) )

логика

булева алгебра

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

Пример: Восстановите логическую функцию по ее таблице истинности:

1

1

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

Получаем СДНФ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать еще:  Как включить дискретную видеокарту

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

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

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

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

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

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

конъюнктивная нормальная форма (КНФ) — конъюнкция нескольких дизъюнкций, например, $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)]

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

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

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

Решение:

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

Используя правило составления СДНФ не забываем вводить знак отрицания для переменных со значением 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 < z >)$

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

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

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

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

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

$f(vec < x >) = neg x_i wedge f(x_1, dots ,x_ < i-1 >,0,x_ < i+1 >, dots ,x_n) vee x_i wedge f(x_1, dots ,x_ < i-1 >,1,x_ < i+1 >, dots ,x_n)$

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

$ f(vec < x >) = neg x_1 wedge neg x_2 wedge . wedge neg x_ < n-1 >wedge neg x_n wedge f(0,0. 0,0)

$neg x_1 wedge neg x_2 wedge . wedge neg x_ < n-1 >wedge x_n wedge f(0,0. 0,1)

x_1 wedge x_2 wedge . wedge x_ < n-1 >wedge neg x_n wedge f(1,1. 1,0)

$ $x_1 wedge x_2 wedge . wedge x_ < n-1 >wedge x_n wedge f(1,1. 1) $

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

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

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

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

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

xyz$langle x,y,z rangle$
1
11
111
1
111
111
1111

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

xyz$ langle x,y,z rangle $
1
1
111$(neg < x >land y land z)$
1
111$(x land neg < y >land z)$
111$(x land y land neg < z >)$
1111$(x land y land z)$

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

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

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

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

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

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

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

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

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

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

1) если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $Bwedge (X_ivee overline < X >_i) equiv (Bwedge X_i)vee (Bwedge overline < X >_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, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
  • Все полученные конъюнкции связываем операциями дизъюнкции.

Далее:

Класс Te . Теорема о замкнутости Te

Теорема Остроградского

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

Теорема о заведомо полныx системаx

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

Гармонические поля

Полином Жегалкина. Пример.

Свойства криволинейного интеграла второго рода

Формула Гаусса — Остроградского

Выражение площади плоской области через криволинейный интеграл

Условия независимости криволинейного интеграла от пути интегрирования

Поток векторного поля через поверхность

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

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

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

Ссылка на основную публикацию
Adblock
detector
×
×