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

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

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

Введение

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

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

В теории дискретных функциональных систем булевой функцией называют функцию типа $\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)

Нульарные функции

При n = 0 количество булевых функций сводится к двум, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами.

При n = 1 число булевых функций равно $2^{2^1} = 4$ . Им соответствуют следующие таблицы истинности.

x	g1 ( $\lnot$ )	g2 (=)	g3 (1)	g4 (0)
0	1	0	1	0
1	0	1	1	0

Здесь:

g1 (x) – отрицание (обозначения: $\neg x,\,\overline{x},\,x'$ ),

g2 (x) – тождественная функция,

g3 (x) и g4 (x) – соответственно, тождественная истина и тождественная ложь.

Бинарные функции

При n = 2 число булевых функций равно $2^{2^2} = 16$ . Им соответствуют следующие таблицы истинности.

x	y	f1 ( $\land$ )	f2 ( $\lor$ )	f3 ( $\equiv$ )	f4 ( $\oplus$ )	f5 ( $\leftarrow$ )	f6 ( $\rightarrow$ )	f7 ( $\downarrow$ )	f8 ( $\mid$ )
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, $x\cdot y, x y, x\land y$ ),

f2 (x, y) – дизъюнкция (обозначение: $x \lor y$ ),

f3 (x, y) – эквивалентность (обозначения: $x\sim y, x\equiv y, x\leftrightarrow y$ ),

f4 (x, y) – исключающее «или» (сложение по модулю 2; обозначения: $x \oplus y, x+y$ ),

f5 (x, y) – импликация от y к x (обозначения: $x\leftarrow y, x \subset y$ ),

f6 (x, y) – импликация от x к y (обозначения: $x\rightarrow y, x\supset y$ ),

f7 (x, y) – стрелка Пи́рса (функция Да́ггера, функция Ве́бба, антидизъюнкция; обозначение: $x\downarrow y$ ),

f8 (x, y) – штрих Ше́ффера (антиконъюнкция; обозначение: $x \mid 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) – тождественная истина и тождественная ложь.

Дизъюнктивная нормальная форма (ДНФ)

Простой конъюнкцией, или конъюнктом, называется конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Например $a \overline{b} c\lor b c\lor\overline{a}$ – является ДНФ.

Совершенной дизъюнктивной нормальной формой, или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: $a \overline{b} c\lor a b c\lor\overline{a} b\overline{c}$ .

Легко убедится, что каждой булевой функции соответствует некоторая ДНФ, и даже СДНФ. Для этого достаточно взять таблицу истинности этой функции и найти все булевы векторы, на которых её значение равно 1. Для каждого такого вектора $b=(b_1,b_2,\ldots,b_n)$ строится конъюнкция $x_1^{b_1} x_2^{b_2}\ldots x_n^{b_n}$ , где $x_i^0 = \overline{x_i}$ . Если взять дизъюнкцию этих конъюнкций, то результатом очевидно будет СДНФ. Поскольку на всех булевых векторах её значения совпадают со значениями исходной функции, она будет СДНФ этой функции. Например, для импликации $x\to y$ , результатом будет $\overline{x} y \lor \overline{x}\, \overline{y}\lor x y$ , что можно упростить до $\overline{x}\lor y$ .

Конъюнктивная нормальная форма (КНФ)

Конъюнктивная нормальная форма (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ – это конъюнкция простых дизъюнкций.

Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С) КНФ и (С) ДНФ взаимодвойственны, свойства (С) КНФ повторяют все свойства (С) ДНФ, грубо говоря, «с точностью до наоборот».

КНФ может быть преобразована к эквивалентной ей ДНФ, путём раскрытия скобок по правилу:

$a (b\lor c)\to a b\lor a c$

которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого, необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом, результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также, можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило

$a\lor b c\to (a \lor b)(a \lor c)$

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать способом, описанным выше, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

Алгоритм

Алгоритм получения СКНФ:

1. Получить таблицу истинности для определенного количества переменных;

2. Заполнить значения функции для каждого из наборов таблицы истинности;

3. Отметить те строки таблицы истинности, на которых функция приняла значение 0;

4. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму переменную, если =1, то ее отрицание;

5. Все полученные дизъюнкции связать в конъюнкцию;

Листинг программы

#include <iostream.h>

#include <conio.h>

int OutputABC (int a, int b, int c, int x, int y)

{

cout << «(»;

if (a == 1) cout << «~Av»; else cout << «Av»;

if (b == 1) cout << «~Bv»; else cout << «Bv»;

if (c == 1) cout << «~C»; else cout << «C»;

cout <<»)»;

if (y<x-1) cout << «*»,

y++;

return(y);

};

void main ()

{const int K=8; const int N=3;

int i, j, b[N] [K], x(0), y(0);

i=0;

for (j=0; j<K; j++)

>> b[0] [j];

cout << endl;

i=1;

for (j=0; j<K; j+=2)

b[i] [j]=0;

for (j=1; j<K; j+=2)

b[i] [j]=1;

i=2;

for (j=0; j<K; j+=4)

b[i] [j]=0;

for (j=1; j<K; j+=4)

b[i] [j]=0;

for (j=2; j<K; j+=4)

b[i] [j]=1;

for (j=3; j<K; j+=4)

b[i] [j]=1;

i=3;

for (j=0; j<4; j++)

b[i] [j]=0;

for (j=4; j<K; j++)

b[i] [j]=1;

for (j=0; j<K; j++)

if (b[0] [j] == 0) x++;

cout<< «A B C f\n\n»;

cout<<«0 0 0 «<<b[0] [0]<<»\n0 0 1 «<<b[0] [1]<<»\n0 1 0 «<<b[0] [2]

<<»\n0 1 1 «<<b[0] [3]<<»\n1 0 0 «<<b[0] [4]<<»\n1 0 1 «<<b[0] [5]

<<»\n1 1 0 «<<b[0] [6]<<»\n1 1 1 «<<b[0] [7]<<»\n\n»;

cout<< «F=»;

for (j=0; j<K; j++)

if (b[0] [j] == 0)

y=OutputABC (b[3] [j], b[2] [j], b[1] [j], x, y);

getch();

}

Тестирование программы

входные данные:

результат:

входные данные:

результат:

Заключение

булева функция программа переменная

В курсовой работе был реализован алгоритм представления булевых функций в СКНФ.

По данному алгоритму на языке С++ была написана программа, результат которой был продемонстрирован.

Список использованной литературы

1. Яблонский С.В. Введение в дискретную математику. – М.: Наука. – 1986

2. Н.А. Ахметова, З.М. Усманова Дискретная Математика Функции алгебры логики учебное электронное издание – Уфа – 2004