Дискретная математика. Ерош И.Л - 12 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

12
стью, поэтому на заре развития вычислительной техники публикова
лись работы, в которых рекомендовалось все комбинационные схемы
строить на мажоритарных элементах.
2.3. Булевы функции n аргументов. СДНФ и СКНФ
Булева функция n аргументов задается на 2
n
наборах. Число таких
функций равно
2
2
n
. Если булева функция задана таблицей истиннос
ти, то она может быть представлена в аналитической форме с исполь
зованием операций конъюнкции, дизъюнкции и инверсии с помощью
следующих правил:
– каждой единице в таблице истинности сопоставляется конъюнкция
ранга n, где n – число аргументов функции; рангом конъюнкции называ
ют число аргументов, входящих в конъюнкцию, причем в эту конъюнк
цию аргумент входит без инверсии, если в соответствующем наборе он
принимает значение 1, и с инверсией, если принимает значение 0;
– все полученные конъюнкции объединяются знаками дизъюнкции.
Например, для мажоритарной функции аналитическое выражение
будет иметь вид
M = ùx
1
x
2
x
3
Ú x
1
ùx
2
x
3
Ú x
1
x
2
ùx
3
Ú x
1
x
2
x
3
. (2.1)
Аналитическое выражение функции вида (2.1) называют совершен
ной дизъюнктивной нормальной формой (СДНФ) функции, при этом
под нормальной формой понимают выражение, в котором инверсии
применяются только к отдельным аргументам, под совершенной фор
мой понимают аналитическое выражение функции, когда во все конъ
юнкции входят все аргументы, т. е. все конъюнкции имеют ранг n.
Если в таблице истинности число нулей
существенно меньше числа единиц, исполь
зуют аналитическую запись в виде совер
шенной конъюнктивной нормальной формы
(СДНФ). Она строится по следующим пра
вилам:
– каждому нулю в таблице истинности
сопоставляется дизъюнкция ранга n, где
n – число аргументов функции; рангом дизъ
юнкции называют число аргументов, входя
щих в дизъюнкцию, причем в эту дизъюнк
цию аргумент входит без инверсии, если в
соответствующем наборе он принимает зна
чение 0, и с инверсией, если принимает зна
чение 1;
Таблица 2.4
X
1
X
2
X
3
FF
00010
00101
01010
01110
10001
10110
11010
11110

Страницы