Представление булевых функций в СКНФ
Краткое сожержание материала:
Размещено на
16
Размещено на
Курсовая работа
«Представление булевых функций в СКНФ»
Введение
В курсе дискретной математики изучаются функции, область определения которых - дискретное множество. Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов.
Теоретическая часть
В теории дискретных функциональных систем булевой функцией называют функцию типа , где - булево множество, а 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) - тождественная истина и тождественная ложь.
Дизъюнктивная нормальная форма (ДНФ)
Простой конъюнкцией, или конъюнктом, называется конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречает...
Полные системы булевых функций
Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геомет...
Основы теории булевых функций
Изложены основы теории булевых функций. Основное внимание уделено представлениям булевых функций термами. Рассмотрены разделы: разложения и каноническ...
Полином Жегалкина
Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования,...
Функционально полные системы булевых функций
Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полином...
Булевы функции
Описание: Брошюра знакомит читателя с булевыми функциями — одним из важнейших классов дискретных функций. В ней излагаются основные понятия теории бул...
