Скачать

Представление булевых функций в СКНФ

Курсовая работа

«Представление булевых функций в СКНФ»



Введение

В курсе дискретной математики изучаются функции, область определения которых – дискретное множество. Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов.


Теоретическая часть

В теории дискретных функциональных систем булевой функцией называют функцию типа \mathsf{B}^n\to\mathsf{B}, где \mathsf{B}=\{0,1\}– булево множество, а n – неотрицательное целое число, которое называют арностью или местностью функции. Элементы 0 (ноль) и 1 (единица) стандартно интерпретируют как истину и ложь, хотя в общем случае их смысл может быть любым. Элементы \mathsf{B}^nназывают булевыми векторами. В случае n = 0 булева функция превращается в булеву константу.

Каждая булева функция арности полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины . Число таких векторов равно 2n. Поскольку на каждом векторе функция может принимать значение либо 0, либо 1, количество всех n-арных булевых функций равно 2^{2^n}. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:

x1

x2

xn

f(x1, x2,…, x1)

000f (0,0,…, 0)
100f (1,0,…, 0)
010f (0,1,…, 0)
110f (1,1,…, 0)

\vdots

\vdots

\vdots

\vdots

\vdots

011f (0,1,…, 1)
111f (1,1,…, 1)