Курсовая работа
«Представление булевых функций в СКНФ»
Введение В курсе дискретной математики изучаются функции, область определения которых – дискретное множество. Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов.
Теоретическая часть
В теории дискретных функциональных систем булевой функцией называют функцию типа , где – булево множество, а n – неотрицательное целое число, которое называют арностью или местностью функции. Элементы 0 (ноль) и 1 (единица) стандартно интерпретируют как истину и ложь, хотя в общем случае их смысл может быть любым. Элементы называют булевыми векторами. В случае n = 0 булева функция превращается в булеву константу.
Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2n. Поскольку на каждом векторе функция может принимать значение либо 0, либо 1, количество всех 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)
0 1 … 1 f (0,1,…, 1) 1 1 … 1 f (1,1,…, 1)
Нульарные функции
При n = 0 количество булевых функций сводится к двум, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами.
При n = 1 число булевых функций равно . Им соответствуют следующие таблицы истинности.
x
g1 ()
g2 (=) g3 (1) g4 (0) 0 1 0 1 0 1 0 1 1 0
Здесь:
g1 (x) – отрицание (обозначения: ),
g2 (x) – тождественная функция,
g3 (x) и g4 (x) – соответственно, тождественная истина и тождественная ложь.
Бинарные функции
При n = 2 число булевых функций равно . Им соответствуют следующие таблицы истинности.
x y
f1 ()
f2 ()
f3 ()
f4 ()
f5 ()
f6 ()
f7 ()
f8 ()
0 0 0 0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 x y f9 f10 f11 f12 f13 f14 f15 f16 0 0 0 0 1 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 1 0
Здесь:
f1 (x, y) – конъюнкция (обозначения: x&y, ),
f2 (x, y) – дизъюнкция (обозначение: ),
f3 (x, y) – эквивалентность (обозначения: ),
f4 (x, y) – исключающее «или» (сложение по модулю 2; обозначения: ),
f5 (x, y) – импликация от y к x (обозначения: ),
f6 (x, y) – импликация от x к y (обозначения: ),
f7 (x, y) – стрелка Пи́рса (функция Да́ггера, функция Ве́бба, антидизъюнкция; обозначение: ),
f8 (x, y) – штрих Ше́ффера (антиконъюнкция; обозначение: ),
f9 (x, y) – отрицание импликации f6 (x, y),
f10 (x, y) – отрицание импликации f5 (x, y),
f11 (x, y) = g1 (x),
f12 (x, y) = g1 (y),
f13 (x, y) = g2 (x),
f14 (x, y) = g2 (y),
f15 (x, y), f16 (x, y) – тождественная истина и тождественная ложь.
Дизъюнктивная нормальная форма (ДНФ)
Простой конъюнкцией, или конъюнктом, называется конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречается не более одного раза. ............
