Составители:
Рубрика:
7
– каждой единице в таблице истинности ставится в соответствие
конъюнкция ранга n, где n – число аргументов функции; рангом конъ-
юнкции называют число аргументов, входящих в конъюнкцию, причем
в этой конъюнкции аргумент входит без инверсии, если в соответству-
ющем наборе он принимает значение 1, и с инверсией, если принимает
значение 0;
– все полученные конъюнкции объединяются знаками дизъюнкции.
Например, для мажоритарной функции аналитическое выражение
будет иметь вид
F =
1
x
x
2
x
3
∨ x
1
2
x
x
3
∨ x
1
x
2
3
x
∨ x
1
x
2
x
3
. (1)
Аналитическое выражение функции вида (1) называют совершенной
дизъюнктивной нормальной формой (СДНФ), при этом под совершен-
ной формой понимают аналитическое выражение функции, когда во все
конъюнкции входят все аргументы, т. е. все конъюнкции имеют ранг n;
под нормальной формой понимают выражение, в котором инверсии при-
меняются только к отдельным аргументам.
Если в таблице истинности число нулей существенно меньше числа
единиц, используют аналитическую запись в виде совершенной конъ-
юнктивной нормальной формы (СКНФ). Она строится по следующим
правилам:
– каждому нулю в таблице истинности ставится в соответствие дизъ-
юнкция ранга n, где n – число аргументов функции; рангом дизъюнкции
называют число аргументов, входящих в дизъюнкцию, причем в этой
дизъюнкции аргумент входит без инверсии,
если в соответствующем наборе он прини-
мает значение 0, и с инверсией, если прини-
мает значение 1;
– все полученные дизъюнкции объединя-
ются знаками конъюнкции.
Возьмем, например, функцию F, представ-
ленную следующей таблицей истинности
(табл. 4).
СДНФ этой функции представляет собой
шесть конъюнкций ранга 3, объединенные
знаками дизъюнкции, т. е. достаточно гро-
моздкое выражение. В то же время СКНФ
этой функции будет выглядеть так:
Таблица 4
x
1
x
2
x
3
FF
00010
00101
01010
01110
10001
10 110
11010
11110
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
