Булевы функции п аргументов. СДНФ и скнф

Булева функция п аргументов задается на 2ⁿ наборах. Число таких функций равно .

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

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

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

Аналитическое выражение функции вида (1) называют совершенной дизъюнктивной нормальной формой (СДНФ), при этом под совершен­ной формой понимают аналитическое выражение функции, когда во все конъюнкции входят все аргументы, т. е. все конъюнкции имеют ранг п; под нормальной формой понимают выражение, в котором инверсии при­меняются только к отдельным аргументам.

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

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

· все полученные дизъюнкции объединя­ются знаками конъюнкции.