Курсовая работа
«Представление булевыхфункций в СКНФ»
Введение
В курседискретной математики изучаются функции, область определения которых –дискретное множество. Простейшим (но нетривиальным) таким множеством являетсямножество, состоящее из двух элементов.
Теоретическаячасть
В теориидискретных функциональных систем булевой функцией называют функцию типа />, где />– булевомножество, а n – неотрицательное целое число, которое называют арностью илиместностью функции. Элементы 0 (ноль) и 1 (единица) стандартно интерпретируюткак истину и ложь, хотя в общем случае их смысл может быть любым. Элементы />называют булевыми векторами. В случае n = 0 булева функцияпревращается в булеву константу.
Каждая булевафункция арности n полностью определяется заданиемсвоих значений на своей области определения, то есть на всех булевых векторахдлины n. Число таких векторов равно 2n. Поскольку на каждом векторе функцияможет принимать значение либо 0, либо 1, количество всех n-арных булевыхфункций равно />. То, что каждаябулева функция задаётся конечным массивом данных, позволяет представлять их ввиде таблиц. Такие таблицы носят название таблиц истинности и в общем случаеимеют вид:
x1
x2
…
xn
f(x1, x2,…, x1) … f (0,0,…, 0) 1 … f (1,0,…, 0) 1 … f (0,1,…, 0) 1 1 … f (1,1,…, 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) 1 1 1 1 1
Здесь:
g1 (x) – отрицание(обозначения: />),
g2 (x) – тождественнаяфункция,
g3 (x) и g4 (x)– соответственно, тождественная истина и тождественная ложь.
/>Бинарные функции
При n = 2число булевых функций равно />. Имсоответствуют следующие таблицы истинности.x y
f1 (/>)
f2 (/>)
f3 (/>)
f4 (/>)
f5 (/>)
f6 (/>)
f7 (/>)
f8 (/>) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 x y f9 f10 f11 f12 f13 f14 f15 f16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Здесь:
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) – тождественная истина и тождественная ложь.
Дизъюнктивнаянормальная форма (ДНФ)
Простойконъюнкцией, или конъюнктом, называется конъюнкция некоторого конечного наборапеременных, или их отрицаний, причём каждая переменная встречается не болееодного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкцияпростых конъюнкций. Например /> – является ДНФ.
Совершеннойдизъюнктивной нормальной формой, или СДНФ относительно некоторого заданногоконечного набора переменных называется такая ДНФ, у которой в каждую конъюнкциювходят все переменные данного набора, причём в одном и том же порядке.Например: />.
Легкоубедится, что каждой булевой функции соответствует некоторая ДНФ, и даже СДНФ.Для этого достаточно взять таблицу истинности этой функции и найти все булевывекторы, на которых её значение равно 1. Для каждого такого вектора />строится конъюнкция />, где />/>. Если взять дизъюнкцию этих конъюнкций, торезультатом очевидно будет СДНФ. Поскольку на всех булевых векторах её значениясовпадают со значениями исходной функции, она будет СДНФ этой функции.Например, для импликации />, результатом будет />, что можноупростить до />.
Конъюнктивнаянормальная форма (КНФ)
Конъюнктивнаянормальная форма (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией илидизъюнктом называется дизъюнкция одной или нескольких переменных или ихотрицаний, причём каждая переменная входит в неё не более одного раза. КНФ – этоконъюнкция простых дизъюнкций.
Совершеннойконъюнктивной нормальной формой (СКНФ), относительно некоторого заданногоконечного набора переменных, называется такая КНФ, у которой в каждуюдизъюнкцию входят все переменные данного набора, причём в одном и том жепорядке. Поскольку (С) КНФ и (С) ДНФ взаимодвойственны, свойства (С) КНФповторяют все свойства (С) ДНФ, грубо говоря, «с точностью до наоборот».
КНФ можетбыть преобразована к эквивалентной ей ДНФ, путём раскрытия скобок по правилу:
/>
котороевыражает дистрибутивность конъюнкции относительно дизъюнкции. После этого,необходимо в каждой конъюнкции удалить повторяющиеся переменные или ихотрицания, а также выбросить из дизъюнкции все конъюнкции, в которыхвстречается переменная вместе со своим отрицанием. При этом, результатом необязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также, можновсегда перейти от ДНФ к КНФ. Для этого следует использовать правило
/>
выражающеедистрибутивность дизъюнкции относительно конъюнкции. Результат нужнопреобразовать способом, описанным выше, заменив слово «конъюнкция» на«дизъюнкция» и наоборот.
Алгоритм
Алгоритмполучения СКНФ:
1. Получитьтаблицу истинности для определенного количества переменных;
2. Заполнитьзначения функции для каждого из наборов таблицы истинности;
3. Отметитьте строки таблицы истинности, на которых функция приняла значение 0;
4. Выписатьдля каждой отмеченной строки дизъюнкцию всех переменных следующим образом: еслизначение некоторой переменной в данной строке =0, то в дизъюнкцию включают самупеременную, если =1, то ее отрицание;
5. Всеполученные дизъюнкции связать в конъюнкцию;
/>
/>
/>
/>
/>
/>
/>
Листингпрограммы
#include
#include
intOutputABC (int a, int b, int c, int x, int y)
{
cout
if(a == 1) cout
if(b == 1) cout
if(c == 1) cout
cout
if(y
y++;
return(y);
};
voidmain ()
{constint K=8; const int N=3;
inti, j, b[N] [K], x(0), y(0);
i=0;
for(j=0; j
{
cout
cin>> b[0] [j];
while(! (b[0] [j] == 1 || b[0] [j] == 0))
cout> b[0] [j];
}
cout
i=1;
for(j=0; j
b[i][j]=0;
for(j=1; j
b[i][j]=1;
i=2;
for(j=0; j
b[i][j]=0;
for(j=1; j
b[i][j]=0;
for(j=2; j
b[i][j]=1;
for(j=3; j
b[i][j]=1;
i=3;
for(j=0; j
b[i][j]=0;
for(j=4; j
b[i][j]=1;
for(j=0; j
if(b[0] [j] == 0) x++;
cout
cout
cout
for(j=0; j
if(b[0] [j] == 0)
y=OutputABC(b[3] [j], b[2] [j], b[1] [j], x, y);
getch();
}
Тестированиепрограммы
входныеданные:
/>
результат:
/>
входныеданные:
/>
результат:
/>
Заключение
булева функция программа переменная
В курсовойработе был реализован алгоритм представления булевых функций в СКНФ.
По данномуалгоритму на языке С++ была написана программа, результат которой былпродемонстрирован.
Списокиспользованной литературы
1. Яблонский С.В. Введениев дискретную математику. – М.: Наука. – 1986
2. Н.А. Ахметова,З.М. Усманова Дискретная Математика Функции алгебры логики учебноеэлектронное издание – Уфа – 2004