Быстрый поиск

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

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

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

Введение

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

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

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

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

x1	x2	…	xn	f(x1, x2,…, x1)
0	0	…	0	f (0,0,…, 0)
1	0	…	0	f (1,0,…, 0)
0	1	…	0	f (0,1,…, 0)
1	1	…	0	f (1,1,…, 0)
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
0	1	…	1	f (0,1,…, 1)
1	1	…	1	f (1,1,…, 1)