Решение Получение сднф




Скачать 227.69 Kb.
НазваниеРешение Получение сднф
Дата09.11.2012
Размер227.69 Kb.
ТипРешение
Представление функций алгебры логики


Основная форма представления функций алгебры логики (ФАЛ) - таблица истинности (ТИ), которая определяет значение функции на всех наборах переменных.

Помимо таблицы истинности, возможны и другие виды представления ФАЛ, наиболее распрост­раненными из которых являются совершенная дизъюнктивная нормальная форма, описывающая все наборы переменных, на которых функция принимает значение, равное 1, и совершенная конъюнктивная нормальная форма, описывающая все наборы переменных, на которых функция принимает значение, равное 0.

Рассмотрим способы перехода от одного вида представления ФАЛ к другому.


Пример 1

Пусть ФАЛ задана в виде таблицы истинности (табл.1).


Таблица 1

Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

1

0

0

1

0

2

0

1

0

0

3

0

1

1

1

4

1

0

0

1

5

1

0

1

1

6

1

1

0

0

7

1

1

1

1
Получить СДНФ и СКНФ этой функции.
Решение

Получение СДНФ.

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

f(x,y,z)СДНФ = (0,3,4,5,7)

Примечания:

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

Получение развернутой записи СДНФ включает следующие этапы.

Этап 1.

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

f(x,y,z) = xyz V xyz V xyz V xyz V xyz

Этап 2.

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

f(x,y,z) = xyz V xyz V xyz V xyz V xyz

000 011 100 101 111

Этап 3.

Расставить знаки отрицания над теми переменными, которым в двоичном эквиваленте соответствует 0:

f(x,y,z)СДНФ =xyz V x y z V xyz V xy z V x y z

0 0 0 0 1 1 1 0 0 1 0 1 1 1 1

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

Получение СКНФ.

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

f(x,y,z)СКНФ = (1,2,6)

Примечания:

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

Получение развернутой записи СДНФ включает следующие этапы.

Этап 1.

Записать конъюнкцию m дизъюнктивных термов, содержащих все переменные, от которых зависит функция, где m - количество наборов, на которых функция принимает значение, равное 0, то есть ко­ли­чест­во наборов, перечисленное в сокращенной записи СКНФ:

f(x,y,z) = (x V y V z) & (x V y V z) & (x V y V z)

Этап 2.

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

f(x,y,z) = (x V y V z) & (x V y V z) & (x V y V z)

0 0 1 0 1 0 1 1 0

Этап 3.

Расставить знаки отрицания над теми переменными, которым в двоичном эквиваленте соответствует 1:

f(x,y,z)СКНФ = (x V y Vz) & (x Vy V z) & (x Vy V z)

0 0 1 0 1 0 1 1 0

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


Пример 2

Пусть ФАЛ задана сокращенной записью СДНФ:

f(x,y,z)СДНФ = (0,1,2,5,7)

Представить таблицу истинности, а также полную и сокращенную записи СКНФ этой функции.
Решение

Получение таблицы истинности


Этап 1.

Подготовить ТИ для логической функции трех переменных:


Номер набора

x

y

z

f(x,y,z)

0

0

0

0




1

0

0

1




2

0

1

0




3

0

1

1




4

1

0

0




5

1

0

1




6

1

1

0




7

1

1

1





Этап 2.

Записать 1 в качестве значения функции в строки, соответствующие наборам, перечисленным в сокращенной записи СДНФ:


Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

1

0

0

1

1

2

0

1

0

1

3

0

1

1




4

1

0

0




5

1

0

1

1

6

1

1

0




7

1

1

1

1


Этап 3.

Записать 0 в качестве значения функции в остальные строки таблицы:


Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

1

0

0

1

1

2

0

1

0

1

3

0

1

1

0

4

1

0

0

0

5

1

0

1

1

6

1

1

0

0

7

1

1

1

1


Таблица истинности получена.


Получение СКНФ.

Получение СКНФ по ТИ описано в примере 1.

Результатом будет:

f(x,y,z)СКНФ = ∏(3,4,6) = (x V ¯y Vz ) & (x V y V z ) & (x Vy V z)


Пример 3

Пусть ФАЛ задана сокращенной записью СКНФ:

f(x,y,z)СКНФ = (2,3,4,5,7)

Получить полную и сокращенную записи СДНФ этой функции.
Решение

Так как получение ТИ в данном примере не требуется, то можно использовать следующий подход.

Этап 1.

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

f(x,y,z)СДНФ = (0,1,6)

Этап 2.

Получить полную запись СДНФ согласно указаниям примера 1. Результатом будет:

f(x,y,z)СДНФ =xyz Vxy z V x yz


Пример 4

Пусть ФАЛ задана в виде СДНФ:

f(x,y,z)СКНФ = xyz Vxy z Vx yz V xyz

Получить полную и сокращенную записи СКНФ этой функции.
Решение

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

f(x,y,z)СКНФ = xyz Vxy z Vx yzV x y z

1 0 0 0 0 1 0 1 0 1 1 1

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной дизъюнкции:

f(x,y,z)СДНФ = (4,1,2,7)

По полученной сокращенной записи СДНФ функции получим сокращенную запись СКНФ, перечислив под знаком обобщенной конъюнкции номера наборов, не вошедших в сокращенную запись СДНФ:

f(x,y,z)СКНФ = (0,3,5,6)

По сокращенной записи СКНФ получим ее полную запись согласно методике, изложенной в примере 1:

f(x,y,z)СКНФ = (x V y V z) & (xVy Vz) & (x V y Vz) & (x Vy V z)


Пример 5

Пусть ФАЛ задана в виде СКНФ:

f(x,y,z)СКНФ = (x Vy V z) & (x Vy Vz) & (x V y Vz)

Получить полную и сокращенную записи СДНФ этой функции.
Решение

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

f(x,y,z)СКНФ = (x Vy V z) & (x Vy Vz) & (x V y Vz)

0 1 0 0 1 1 1 0 1

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной конъюнкции:

f(x,y,z)СКНФ = (2,3,5)

По полученной сокращенной записи СКНФ функции получим сокращенную запись СДНФ, перечислив под знаком обобщенной дизъюнкции номера наборов, не вошедших в сокращенную запись СКНФ:

f(x,y,z)СДНФ = (0,1,4,6,7)

По сокращенной записи СДНФ получим ее полную запись согласно методике, изложенной в примере 1:

f(x,y,z)СКНФ =xyz Vxy z V xyz V x yz V x y z


Пример 6

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

f(x,y,z) =x V x yV x yz

Получить полную и сокращенную записи СКНФ этой функции.
Решение

Для решения этой задачи можно сначала получить СДНФ функции.

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

a = a b V ab

Тогда, последовательно повышая ранг для термов, зависящих не от всех переменных, получим:

x =x y Vxy =xyz Vx yz Vxy z Vxyz

xy = xyz V x yz

f(x,y,z) =x V xy V xyz =xyz Vx yz Vxy z Vxyz V xyz V x yz V x yz

После выполнения преобразования на основе эквивалентности

a V a = a

получим полную, а затем и сокращенную записи СДНФ:

f(x,y,z)СДНФ =xyz Vx yz Vxy z Vxyz V xyz V x yz

f(x,y,z)СДНФ = (3,2,1,0,7,6)

Последующие шаги по решению поставленной задачи рассмотрены ранее.

В результате получим:

f(x,y,z)СКНФ = (4,5)

f(x,y,z)СКНФ = (x V y V z) & (x V y Vz)


Пример 7

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

f(x,y,z) = (x V y) & (x Vz )

Получить полную и сокращенную записи СДНФ этой функции.
Решение

Решение этой задачи аналогично предыдущей.

Для получения СКНФ необходимо использовать следующие эквивалентности:

a = (a V b) & (a Vb)

a & a = a

Тогда получим:

x V y = (x V y V z) & (x V y Vz)

x Vz = (x V y Vz) & (x Vy Vz)

f(x,y,z) = (x V y V z) & (x V y Vz) & (x V y Vz) & (x Vy Vz)

f(x,y,z)СКНФ = (x V y V z) & (x V y Vz) & (x Vy Vz)

f(x,y,z)СКНФ = (4,5,7)

Исходя из полученной СКНФ функции, определим ее СДНФ:

f(x,y,z)СДНФ = (0,1,2,3,6)

f(x,y,z)СДНФ =xyz V xy z V x yz V x y z V x yz

Похожие:

Решение Получение сднф iconРешение проблем и получение советов. «Гид по Таро. Практическое решение проблем и получение советов»
«Гид по Таро. Практическое решение проблем и получение советов»: фаир-пресс; 2002
Решение Получение сднф iconРешение педсовета Директор гимназии
Организация деятельности оу, направленная на получение бесплатного общего образования. Охрана здоровья школьников
Решение Получение сднф iconРешение №42 от 24 мая 2012 года
Заслушав информацию о кандидате на получение стипендии имени А. И. Солженицына, Ученый совет решил
Решение Получение сднф iconЛабораторная работа булевы функции. Многочлены жегалкина
Цель работы: Изучить свойства булевых функций, методы построения днф, кнф, сднф, скнф, алгоритмы построения многочлена Жегалкина...
Решение Получение сднф iconПрограмма курса по выбору для учащихся учреждений, обеспечивающих получение
Существует широкий класс олимпиадных задач по программированию, имеющих естественное (и простое) решение в объектной среде исполнения....
Решение Получение сднф iconПрограмма курса по выбору для учащихся учреждений, обеспечивающих получение
Существует широкий класс олимпиадных задач по программированию, имеющих естественное (и простое) решение в объектной среде исполнения....
Решение Получение сднф iconФ. Ф. Спиридонов, А. М. Фирсов, В. В. Смирнов
Однако получить практические знания становится все сложнее ввиду объективных экономических причин. Частичное решение данной проблемы...
Решение Получение сднф iconПодведены итоги муниципального этапа конкурсных отборов на получение премии Губернатора хмао – Югры
Существления конкурсных отборов Претендентов на получение премии Президента рф, Губернатора Ханты-Мансийского автономного округа...
Решение Получение сднф iconО рекомендации кандидатов на получение стипендии Президента РФ заслушав информацию о кандидатах на получение стипендии Президента Российской Федерации, Учёный совет решил
Сиреканян Тамару Гарниковну, студентку факультета физической культуры и спорта (гр. Афк-401)
Решение Получение сднф iconСтавропольский институт экономики и управления
Целью изучения дисциплины является получение студентами представления о структуре и свойствах сырья и материалов для одежды, об оценке...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница