Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Конституенты нуля. Совершенные конъюнктивные и шефферовы нормальные формы





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

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

Определение. Пусть на наборе`a n =(a1, ... ,an ) булева функция f (х n)принимает значение 0. Дизъюнктивной конституентой нуля функции f назовем дизъюнкцию вида

D = х1Øa1Ú ... Ú хn Øan ,

где хi Øa i = i при a i =1 и хi Øai = хi при a i =0(1£ i £ n).

Аналогично шефферовой конституентой нуля функции f назовем подстановку вида S =| (х1 a1 , ... , хnan).

Как дизъюнктивная, так и шефферова конституенты нуля, соответствующие набору`a n , принимают значение 0 только на нем. На всех остальных наборах они равны 1.

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

x y z F Д 1 Д 2 Д 3

Решение. Функция принимает значение 0 на наборах (0, 1, 0), (0, 1, 1), (1, 0, 1). На наборе (0, 1, 0) дизъюнктивная конституента нуляД1= хÚуÚz, на наборе(0, 1, 1)Д2ÚуÚz , на наборе(1, 0, 1)Д3 =`хÚуÚz . В таблице дополнительно указаны векторы истинности конституент Д1 — Д3. Каждая из них выделяет ровно один из нулей в векторе истинности исходной функции.

Шефферовы конституенты получаем из Д1 — Д3, инвертируя внутренние переменные в них и заменяя дизъюнкцию функцией Шеффера. В итоге получим: S1 =| (х, у,`z); S2 =|(х, у, z); S3 =| (х,`у, z). Поскольку преобразование эквивалентное, векторы истинности S1 S3совпадают с векторами для Д1 — Д3.

Определение. Совершенной конъюнктивной нормальной формой (СКНФ) булевой функции f (х n) называют выражение вида:

f = D1& ... & Dр,

где D1, ... , Dр — дизъюнктивные конституенты нуля функции.

Совершенной шефферовой нормальной формой (СШНФ) булевой функции f ( х n)называют выражение вида:

f = Ø|( S1, ... , Sр ) ,

где S1, ... , Sр — шефферовы конституенты нуля функции f (n).

СКНФ, как и все КНФ, являются функциями в базисном наборе {Ø, &, Ú}. СШНФ можно наряду с основным представлением задать в однофункциональном базисном наборе {|}.

Пример 4. Построить СКНФ и СШНФ (для каждого из базисных наборов {Ø, |} и {| }) функции f = (11001011)из Примера 3.

Решение.

1. Дизъюнктивные конституенты нуляД1 — Д3найдены в Примере 3. СКНФ получаем, логически умножая их:

f = (х ÚÚ z) & (х ÚÚ`z) & (х Ú у Ú`z).

2. Шефферовы конституенты S1 S3также были найдены в Примере 3. СШНФ в базисном наборе {Ø, |}получаем, подставляя S1 S3в функцию Шеффера с последующим её инвертированием:

f =Ø| (| (x, y, z),| (x, y, z),|(x,`y, z)) .

СШНФ в базисном наборе {|}имеет вид:

f =|[|(|((x,х), y, (z,z)), | ((x,x), y, z), | ( x,( y,y), z )), |(| ((x,х), y, (z,z)), | ((x,x), y, z), | (x,( y,y), z))] .

Искомые формы построены.

СКНФ и СШНФ существуют только для функций, не равных тождественной единице. В случае, когда вектор истинности функции имеет только один нуль, ее СКНФ и СШНФ являются вырожденными.

Рассмотренные выше ДНФ, КНФ, ВНФ и ШНФ допускают неединственное представление функций. Совершенные формы являются их частными случаями.

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.