Статья:

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

Конференция: XXXIX Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Секция: Физико-математические науки

Выходные данные
Короткова Д.А. Представление булевых функций в СДНФ и её программная реализация // Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XXXIX междунар. студ. науч.-практ. конф. № 10(39). URL: https://nauchforum.ru/archive/MNF_tech/10(39).pdf (дата обращения: 18.08.2018)
Лауреаты определены. Конференция завершена
Эта статья набрала 0 голосов
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

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

Короткова Дарья Алексеевна
студент, Ульяновский государственный университет, РФ, г. Ульяновск

 

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

Булева функция (или логическая функция, или функция алгебры логики) от n аргументов — в дискретной математике – это отображение Bn → B, где B = {0,1} – булево множество.

Арность функции алгебры логики – это количество её аргументов.

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

ДНФ (Дизъюнктивная Нормальная Форма) — нормальная форма, где булева функция имеет вид дизъюнкции нескольких простых конъюнктов.

СДНФ (Совершенная Дизъюнктивная Нормальная Форма) – это такая ДНФ, которая удовлетворяет условиям:

·     в ней нет одинаковых простых конъюнкций;

·     каждая простая конъюнкция полная (если в неё каждая переменная (или её отрицание) входит только 1 раз).

Теорема.

Если булева функция не равна тождественному нулю, то ее можно представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборы переменных (х12, …,хn), для которых f(х12, …,х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. СДНФ для ФАЛ от двух переменных

 

Список литературы: 
1. Гаврилов С.П. Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1978.
2. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 1992.
3. Яблонский С.В. Введение в дискретную математику. – М.: Наука. – 1986.