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

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

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

Введение

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

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

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

Алгоритм

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

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++)

{

cout << «Vvedite znachenie funkcii na dannom nabore» << endl;

cin >> b[0] [j];

while (! (b[0] [j] == 1 || b[0] [j] == 0))

cout << endl << «Fatal error!!! Please input only 0 or 1» << endl, cin >> 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 fnn»;

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]<<»nn»;

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();

}

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

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

результат:

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать