Представление булевых функций в СДНФ и её программная реализация
Секция: Физико-математические науки
![](https://nauchforum.ru/themes/mix_and_match/images/logo.jpg)
XXXIX Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»
Представление булевых функций в СДНФ и её программная реализация
В курсе дискретной математики изучаются функции, область определения которых – дискретное множество. Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов. Цель статьи – написание программы построения СДНФ для функций алгебры логики на языке высокого уровня С++.
Булева функция (или логическая функция, или функция алгебры логики) от n аргументов — в дискретной математике – это отображение Bn → B, где B = {0,1} – булево множество.
Арность функции алгебры логики – это количество её аргументов.
Каждая булева функция арности n полностью определяется своими значениями на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно . Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно
.
ДНФ (Дизъюнктивная Нормальная Форма) — нормальная форма, где булева функция имеет вид дизъюнкции нескольких простых конъюнктов.
СДНФ (Совершенная Дизъюнктивная Нормальная Форма) – это такая ДНФ, которая удовлетворяет условиям:
· в ней нет одинаковых простых конъюнкций;
· каждая простая конъюнкция полная (если в неё каждая переменная (или её отрицание) входит только 1 раз).
Теорема.
Если булева функция не равна тождественному нулю, то ее можно представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборы переменных (х1,х2, …,хn), для которых f(х1,х2, …,хn) =1, и составляем простую конъюнкцию для этого набора так: если хi = 0, то берем в этой конъюнкции отрицание xi, если хi = 1, то берем хi. Составляя дизъюнкцию этих простых конъюнкций, придем к СДНФ.
Пример построения СДНФ.
Таблица 1.
Таблица истинности со значениями функции от трех переменных
X |
Y |
Z |
F(x, y, z) |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
Тогда СДНФ:
F(x, y, z )= -x-yz v –xy-z v xyz
Программная реализация СДНФ.
Для написания программы, воспользуемся следующим алгоритмом:
1. Создаём динамическую матрицу для таблицы истинности произвольного размера (размер задаём сами), и значениями функции.
2. Находим строки, где значение функции принимает 1.
3. Выпишем для этой строки конъюнкцию всех переменных: если значение переменной в данной строке равно 1, то в конъюнкцию включаем саму переменную, если 0, то включаем отрицание этой переменной.
4. Все полученные конъюнкции свяжем в дизъюнкцию.
Код программы:
#include <iostream>
#include <locale.h>
using namespace std;
int main()
{
int n,m,i,j,k=0; float **bul; int *p;
setlocale( LC_ALL,"Russian" );
cout<<"Введите m, n и таблицу истинности из расчета n=2^m, где n-столбцы, m-строки."<< endl;
cout<<"m="; cin>>m; cout<<"n="; cin>>n;
m=m+1;
bul=new float *[n];
for(i=0;i<n;i++)
bul[i]=new float(m);
p=new int[m];
cout<<"Ввод таблицы, где последний столбец значение функции:"<<endl;
for(j=0;j<m-1;j++)
{ cout<<"X"<<j+1<<" ";}
for(j=m-1;j<m;j++)
cout<<"F "<<endl;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>bul[i][j];
cout<<"СДНФ для этой функции:\n "<<endl;
for(i=0;i<n;i++)
{ if (bul[i][m-1]==1)
{ for(j=0;j<m-1;j++)
if(bul[i][j]==0)
{ cout<<"-X"<<j+1;}
else
cout<<"X"<<j+1;
if (i<n-1)
cout<<" v "; }
}
cout<< endl;
for(i=0;i<n;i++)
delete [ ] bul[i]; delete [ ] bul;
return 0;
}
Тестирование программы:
Рисунок 1. СДНФ для ФАЛ от двух переменных
Рисунок 2. СДНФ для ФАЛ от двух переменных
![](/sites/default/files/publ_rinc.png)