Применение дискретной в информатике

Таблица 1- Таблица истинности для функции (1)

x

y

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1.2.2 Конъюнктивная и дизъюнктивная нормальные формы (КНФ и ДНФ)

Дизъюнктивной нормальной формой называется формула, имеющая вид дизъюнкции элементарных конъюнкций.

Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций./2/

f(e1,e2,…,en)= x1e1x2e2…xnen (2)

Для приведения функции от двух переменных f(x,y) к ДНФ следует воспользоваться формулой 2 и таблицей 1.

Каждая булева функция f(x1,x2,…,xn), которая не идентична нулю, может быть записана в виде всевозможных булевых выражений типа

f(x,y)=( (3)

Каждую булеву функцию f(x1,x2,…,xn), которая не равна тождественно единице, можно представить в виде произведения всевозможных булевых выражений вида:

f(`e1,`e2,…,`e3) = x1e1 Ú x2e2 Ú … Ú xnen (4)

Для приведения функции от двух переменных f(x,y) к КНФ следует воспользоваться теоремой 2 и таблицей 1.Следовательно ДНФ=x&y.

1.2.1 Построение полинома Жегалкина. Полином Жегалкина определяется по формуле:

, где ki () попарно различные монотонные элементарные конъюнкции./2/

Для функции , которая зависит от трех переменных, полином Жегалкина будет следующий:

P(x, y) = B0ÅB1xÅB2yÅB3xy (3)

Метод неопределенных коэффициентов заключается в том, что последовательной подстановкой x, y и соответственно значений функций при них в данный полином, находим коэффициенты β0, β1, β2, β3, β4, β5, β6, β7. Значения переменных x, y и значение функции представлены в таблице 4:

Таблица 2 – значение функции