Конспект лекций по дискретной математикеРефераты >> Математика >> Конспект лекций по дискретной математике
Определение: Булева функция от n аргументов fn(x) называется вырожденной по аргументу xi, если ее значение не зависит от этого аргумента, то есть для всех наборов аргументов имеет место равенство:
f(x1, x2, . , xi-1, 0, xi+1, . , xn) = f(x1, x2, xi-1, 1, xi+1, . , xn).
Функция запрета x1Dx2 принимает значение, равное нулю при равенстве запрещающей переменной (x2) единице и повторяет значение аргумента x1 при равенстве запрещающей переменной нулю.
Понятие импликации в Булевой алгебре отождествляется с выражением следования (если . то . ).
Пример: Имеют место два простых высказывания.
А. На небе тучи.
В. Идет дождь. В®А
| А | В | В®А |
| f | f | t |
| f | t | f |
| t | f | t |
| t | t | t |
Из истины не может следовать ложь!
Некоторые функции от трех переменных.
| Значение аргументов | Значение функций | ||||
| Сумма по модулю 2 | Исключающее ИЛИ | Функция мажоритарности | |||
| x1 | x2 | x3 | x1Åx2Åx3 | XOR (x1,x2,x3) | x1#x2#x3 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 |
Функция - сумма по модулю 2 и исключающее ИЛИ являются эквивалентными только для двух аргументов.
n
Общее разнообразие функций от n аргументов равно 22
В самом компактном виде любую Булеву функцию можно представить символически: 
, где n-количество аргументов, а N-десятичный эквивалент двоичного набора значений функции на упорядоченном множестве аргументов.
Пример:
f3(x)=x1Åx2Åx3=
Невырожденные функции от двух переменных с добавлением функции отрицания принято называть функциями Булевой алгебры. С учетом обращаемости некоторых базовых функций к некоторым аргументам, их общее количество равно девяти.
Нормальные формы Булевых функций
Нормальные формы - это особый класс аналитических выражений, используемых при решении задачи минимизации Булевых функций и для перехода от табличной формы задания к аналитической. Нормальные формы строятся на основании операций конъюнкции, дизъюнкции и отрицания, причем отрицание только единственной переменной.
Определение: Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) конечного числа попарно различимых переменных или их отрицаний.
Элементарную конъюнкцию (дизъюнкцию) принято называть конъюнктивным (дизъюнктивным) термом.
В частном случае терм, как конъюнктивный так и дизъюнктивный может состоять из единственной буквы (литерала). Под буквой будем понимать аргумент Булевой функции и его отрицания.
Примеры конъюнктивных термов:
_ _
x1, x2, x1x3, x2x4x5 (терм)
_ _
x1x2, x1x2x3 (не терм)
Рангом терма называется количество букв входящих в него.
Дизъюнктивной (конъюнктивной) нормальной формой Булевой функции называется дизъюнкция (конъюнкция) конечного числа попарно различимых конъюнктивных (дизъюнктивных) термов.
Скачать реферат
