Курсовая работа: Представление булевых функций в СКНФ
В курсе дискретной математики изучаются функции, область определения которых – дискретное множество. Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов.
Теоретическая часть
В теории дискретных функциональных систем булевой функцией называют функцию типа 
, где 
– булево множество, а 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) – тождественная истина и тождественная ложь.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--