Запись бф через сп.(сднф)

f =(x1,…,xn)= x1 x2x3…xn. Поставим каждой переменной с отрицанием в соответствие 0, а без -1. Тогда мы получим n-значное двоичное число, различных совершенных произведений будет столько, сколько различных n-значных двоичных чисел, т.е. 2ⁿ. Если между цифрами двоичного числа, соответствующего СП, поставить запятые, то на него можно смотреть как на координаты вершин n-мерного куба, т.е. каждому СП соответствует вершина n-мерного куба, которая называется собственной вершенной данного СП. СП=1 в своей собственной вершине и только в ней. Отсюда вытекает правило построения функции через СП: 1)в таблице отыскиваем 1, 2) в каждой строке, где стоят 1, записываем СП, 3) берем дизъюнкцию этих СП.

Построение бф через сс.(скнф)

Возьмем СС функции и поставим в соответствие `х -1, х – 0. Тогда очевидно, что различных СС=2ⁿ, и эти двоичные числа можно рассматривать как вершины n-мерного куба, которые называются собственными вершинами соответствующих СС. СС=0 в своей собственной вершине и только в ней. Отсюда следует правило построения функции f через СС: 1) нужно в строках, где стоят 0 функции, записать соответствующие их СС, 2) взять их дизъюнкцию.

Запись БФ через СП(СС) называется СДНФ(СКНФ). Из изложенного следует, что всегда можно функцию выразить через операции ,, . Заметим, что если функция f=const 1, то она не имеет СКНФ, и наоборот. По виду функции в совершенной форме всегда можно сказать, будет она const, или нет. Если функция задана аналитически, то ее всегда можно привести к СФ. Для этого ее сначала упрощают так, чтобы она содержала три операции ,, , а затем, используя формулы хх=0 , хх=1, приводят к СФ.

Разложение функции по переменным.

Разложить функцию по переменным значит представление ее в виде конъюнкции переменных, умноженных на функции меньшего числа переменных. x^=xÚ`x`s, где х- булев. переменная, а s ={0,1}. x⁰=x 0Ú`x 1. x<sup>s</sup>={x, если s=1;`x, если s=0}. s^s=1. Пусть f(x_n) и 0<=m<=n, тогда имеет место f(x_n)=[x₁ ^s1 x₂ ^s2 … x_m ^sm f(s1,s2,s3,…,sm,x_m+1,…,xn)], где …………^{( s1… sn)} дизъюнкция берется по всем наборам переменных.

Минимизация БФ методом Вейча.

После того, как аналитически записали через СП функцию, ее надо упростить, т.е. минимизировать. Минимизацию можно проводить преобразованием выражения таким образом, чтобы было как можно меньше членов дизъюнкции (min число элементов). Или минимизацию проводят по числу букв, что соответствует минимальному числу входов. Минимизация проводится в классе операций ,, . Если мы получили min форму в этом классе, то это не значит, что дальнейшее упрощение невозможно. Назовем элементарное произведение рангом r, если оно содержит r сомножителей. Два элементарных произведения одного ранга называют соседними, если они отличаются одним отрицанием. Два соседних ЭП ранга r можно заменить ЭП ранга r-1, которое равно их общей части (склейка). Если мы имеем конъюнкцию двух ЭП, одно из которых является собственной частью другого, то конъюнкцию можно заменить одним ЭП, которое совпадает с собственной частью большего произведения.