Contribution to International Economy

Минимизация булевых функций методом неопределенных коэффициентов

ВВЕДЕНИЕ

В данной курсовой работе предложено создать Windows-приложение на языке C# реализующее минимизацию булевых функций методом неопределенных коэффициентов.

Разработчику ставится задача, при выполнении которой используются знания, полученные при изучении курса объектно-ориентированного анализа и программирования; навыки работы с операционными системами, программными оболочками, разнообразными служебными и сервисными средствами. А также навыки по алгоритмизации, программированию и решению в интегрированной визуальной среде программирования Visual C#.

 

1. ПОСТАНОВКА ЗАДАЧИ

В данной курсовой работе требуется создать Windows-приложение на языке C# реализующее метод неопределенных коэффициентов для минимизации булевых функций.

Графическая часть должна быть реализована на основе библиотеки WinForms.

В приложении должна присутствовать обработка ошибок, вывод промежуточных данных

 

2. АНАЛИЗ МЕТОДОВ РЕШЕНИЯ

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

Определение: Преобразование логических функций с целью упрощения их аналитического представления называются минимизацией.

Существуют два направления минимизации:

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

2. Получение минимальной формы записи (цель – получение минимального числа символов для записи всей функции сразу).

Существуют различные методы минимизации:

Метод непосредственных преобразований логических функций

При применении данного метода:

а) Записываются ДСНФ логических функций

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

 

По отношению к соседним min-термам применяется закон склейки, значит ранг min-терма понижается на единицу.

Определение: Min-термы, образованные при склеивании называются импликантами.

Полученные после склейки импликанты по возможности склеивают до тех пор, пока склеивание становится невозможным.

Определение: Несклеивающиеся импликанты называются прослойками.

Определение: Формула, состоящая из простых импликант – тупиковая.

Пример:

 

0 0 0 1

0 0 1 1

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 0

 

Если в процессе склейки образуется форма R, содержащая члены вида и то для нее справедливо выражение , что позволяет добавить к исходной форме R несколько членов вида пар и и после этого продолжить минимизацию.

 

Метод неопределенных коэффициентов.

Суть метода состоит в преобразовании ДСНФ в МДНФ.

На основании теоремы Жигалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных):

 

Алгоритм определения коэффициентов:

1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности.

2. Напротив каждого выражения поставить соответствующее значение функции.

3. Выбрать строку, в которой значение функции и приравнять все к нулю.

4. Просмотреть строки, где функция имеет единичное значение, и вычеркнуть все коэффициенты, встречающиеся в нулевых строках.

5. Проанализировать оставшиеся коэффициенты в единичных строках.

6. Используя правило, что дизъюнкция равна 1 если хотя бы один из , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно.

7. Записать исходный вид функции.

Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной.

 

3. РАЗРАБОТКА АЛГОРИТМА, СХЕМА АЛГОРИТМА И ЕГО ОПИСАНИЕ

На основе анализа методов решения поставленной задачи, составляем соответствующую блок схему алгоритма работы программы:

Рисунок 1. Алгоритм работы программы

Рассмотрим реализацию шагов алгоритма в коде:

1) Ввод булевой функции

Вводится в поле this.tb_boolean_func.Text

2)Разбор выражения записи функции и получение таблицы истинности для введенной функции:

int x1, x2, x3;

 

bool[] mas_rez = new bool[8];

 

int pos = 0;

 

for (x1 = 1; x1 >= 0; x1--)

for (x2 = 1; x2 >= 0; x2--)

for (x3 = 1; x3 >= 0; x3--)

{

string func = this.tb_boolean_func.Text;

func = func.Replace(" ", "");

bool f1 = false;

string[] parts = func.Split('+');

for (int i = 0; i < parts.Length; i++)

{

bool fp1 = true;

string[] xs = parts[i].Split('*');

for (int j = 0; j < xs.Length; j++)

{

if (xs[j][0] == '!')

{

string per = xs[j].Substring(1, xs[j].Length - 1);

switch (per)

{

case "x1":

{

bool x = x1 == 1;

fp1 = fp1 && !x;

break;

}

case "x2":

{

bool x = x2 == 1;

fp1 = fp1 && !x;

break;

}

case "x3":

{

bool x = x3 == 1;

fp1 = fp1 && !x;

break;

}

default:

{

throw new Exception("Недопустимое имя переменной ! :"+per);

break;

}

}

//fp1=fp1&&

}

else

{

string per = xs[j];

switch (per)

{

case "x1":

{

bool x = x1 == 1;

fp1 = fp1 && x;

break;

}

case "x2":

{

bool x = x2 == 1;

fp1 = fp1 && x;

break;

}

case "x3":

{

bool x = x3 == 1;

fp1 = fp1 && x;

break;

}

default:

{

throw new Exception("Недопустимое имя переменной ! :" + per);

break;

}

}

}

}

f1 = f1 || fp1;

}

mas_rez[pos] = f1;

pos++;

}

Здесь перебором возможных значений переменных x1,x2,x3 вычисляется таблица истинности и записывается в массив mas_rez.

3) Инициализация матрицы коэффициентов в соответствии с теоремой Жигалкина:

Обявляем класс

class Koefficient

{

public Koefficient()

{

up_part = "";

down_part = "";

value = false;

}

public string up_part;

public string down_part;

public bool value;

}

Осуществляем заполнение:

Koefficient[,] tabl_koeff = new Koefficient[8, 7];

 

pos = 0;

 

// формируем таблицу коэффициентов

for (x1 = 1; x1 >= 0; x1--)

for (x2 = 1; x2 >= 0; x2--)

for (x3 = 1; x3 >= 0; x3--)

{

tabl_koeff[pos, 0] = new Koefficient();

tabl_koeff[pos, 0].up_part = x1.ToString();

tabl_koeff[pos, 0].down_part = "1";

tabl_koeff[pos, 0].value = true;

 

tabl_koeff[pos, 1] = new Koefficient();

tabl_koeff[pos, 1].up_part = x2.ToString();

tabl_koeff[pos, 1].down_part = "2";

tabl_koeff[pos, 1].value = true;

 

tabl_koeff[pos, 2] = new Koefficient();

tabl_koeff[pos, 2].up_part = x3.ToString();

tabl_koeff[pos, 2].down_part = "3";

tabl_koeff[pos, 2].value = true;

 

tabl_koeff[pos, 3] = new Koefficient();

tabl_koeff[pos, 3].up_part = x1.ToString() + x2.ToString();

tabl_koeff[pos, 3].down_part = "12";

tabl_koeff[pos, 3].value = true;

 

tabl_koeff[pos, 4] = new Koefficient();

tabl_koeff[pos, 4].up_part = x1.ToString() + x3.ToString();

tabl_koeff[pos, 4].down_part = "13";

tabl_koeff[pos, 4].value = true;

 

tabl_koeff[pos, 5] = new Koefficient();

tabl_koeff[pos, 5].up_part = x2.ToString() + x3.ToString();

tabl_koeff[pos, 5].down_part = "23";

tabl_koeff[pos, 5].value = true;

 

tabl_koeff[pos, 6] = new Koefficient();

tabl_koeff[pos, 6].up_part = x1.ToString() + x2.ToString() + x3.ToString();

tabl_koeff[pos, 6].down_part = "123";

tabl_koeff[pos, 6].value = true;

 

pos++;

}

В результате в tabl_koeff получаем массив коеффициентов.

 

4) Определение нулевых коэффициентов на основе таблицы истинности функции:

// определеям нулевые коэффициенты, шаг 1

for (k = 0; k < 8; k++)

{

if (mas_rez[k] == false)

{

for (h = 0; h < 7; h++)

{

tabl_koeff[k, h].value = false;

for (w = 0; w < 8; w++)

for (y = 0; y < 7; y++)

{

if (w == k) continue;

if (mas_rez[w] == false) continue;

if (tabl_koeff[w, y].down_part == tabl_koeff[k, h].down_part &&

tabl_koeff[w, y].up_part == tabl_koeff[k, h].up_part)

{

tabl_koeff[w, y].value = false;

}

}

}

}

}

 

// формируем получившуюся систему уравнений

List<List<Koefficient>> lst_system = new List<List<Koefficient>>();

 

for (k = 0; k < 8; k++)

{

if (mas_rez[k])

{

List<Koefficient> lst_rivnanna = new List<Koefficient>();

for (h = 0; h < 7; h++)

if (tabl_koeff[k, h].value)

lst_rivnanna.Add(tabl_koeff[k, h]);

if (lst_rivnanna.Count > 0)

lst_system.Add(lst_rivnanna);

}

}

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

 

5) Выбор min-термов минимального ранга:

// определеям нулевые коэффициенты, шаг 2

for (k = 0; k < lst_system.Count; k++)

{

bool fl1 = true;

while (fl1)

{

fl1 = false;

for (h = 0; h < lst_system[k].Count && !fl1; h++)

for (w = h + 1; w < lst_system[k].Count; w++)

{

bool fl2 = true;

for (y = 0; y < lst_system[k][h].down_part.Length; y++)

{

if (!lst_system[k][w].down_part.Contains(lst_system[k][h].down_part[y]))

{

fl2 = false;

break;

}

}

 

if (fl2)

{

lst_system[k].RemoveAt(w);

fl1 = true;

break;

}

}

}

}

 

В результате в lst_system остаются коэффициенты, определябщие конюнкции наименьшего возможного ранга.

 

6) Запись результирующей функции

// находим МДНФ

List<Koefficient> lst_rez_koeff = new List<Koefficient>();

for (k = 0; k < lst_system.Count; k++)

for (h = 0; h < lst_system[k].Count; h++)

lst_rez_koeff.Add(lst_system[k][h]);

 

// удаляем повторяющиеся коэффициенты

bool fl3 = true;

while (fl3)

{

fl3 = false;

for (h = 0; h < lst_rez_koeff.Count && !fl3; h++)

for (w = h + 1; w < lst_rez_koeff.Count; w++)

if (lst_rez_koeff[h].down_part == lst_rez_koeff[w].down_part &&

lst_rez_koeff[h].up_part == lst_rez_koeff[w].up_part)

{

lst_rez_koeff.RemoveAt(w);

fl3 = true;

break;

}

}

 

// выводим МДНФ

 

string mdnf = "";

 

for (k = 0; k < lst_rez_koeff.Count; k++)

{

for (h = 0; h < lst_rez_koeff[k].down_part.Length; h++)

{

string add_s = "";

if (lst_rez_koeff[k].up_part[h] == '0') add_s = "!";

 

mdnf += add_s + "x" + lst_rez_koeff[k].down_part[h] + "*";

 

}

mdnf = mdnf.Remove(mdnf.Length - 1, 1);

mdnf += "+";

}

mdnf = mdnf.Remove(mdnf.Length - 1, 1);

 

this.tb_result.Text = mdnf;

 

В this.tb_result.Text выводится результирующая функция.

 

 

4. ФОРМАТ ВХОДНЫХ И ВЫХОДНЫХ ДАННЫХ. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

Входными данными является запись булевой функции от 1 до 3 переменных.

Для запуска необходимо запустить файл MinBoolean.exe

Выводом программы является минимизированная запись булевой функции и данные промежуточных шагов по минимизации.

5. РЕАЛИЗАЦИЯ АЛГОРИТМА, ЛИСТИНГ ПРОГРАММЫ

Рассмотрим программную реализацию блок-схемы алгоритмы работы программы, приведенного на Рис.1:

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

 

namespace MinBoolean

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

 

class Koefficient

{

public Koefficient()

{

up_part = "";

down_part = "";

value = false;

}

public string up_part;

public string down_part;

public bool value;

}

 

private void button1_Click(object sender, EventArgs e)

{

 

try

{

int x1, x2, x3;

 

bool[] mas_rez = new bool[8];

 

int pos = 0;

 

for (x1 = 1; x1 >= 0; x1--)

for (x2 = 1; x2 >= 0; x2--)

for (x3 = 1; x3 >= 0; x3--)

{

string func = this.tb_boolean_func.Text;

func = func.Replace(" ", "");

bool f1 = false;

string[] parts = func.Split('+');

for (int i = 0; i < parts.Length; i++)

{

bool fp1 = true;

string[] xs = parts[i].Split('*');

for (int j = 0; j < xs.Length; j++)

{

if (xs[j][0] == '!')

{

string per = xs[j].Substring(1, xs[j].Length - 1);

switch (per)

{

case "x1":

{

bool x = x1 == 1;

fp1 = fp1 && !x;

break;

}

case "x2":

{

bool x = x2 == 1;

fp1 = fp1 && !x;

break;

}

case "x3":

{

bool x = x3 == 1;

fp1 = fp1 && !x;

break;

}

default:

{

throw new Exception("Недопустимое имя переменной ! :"+per);

break;

}

}

//fp1=fp1&&

}

else

{

string per = xs[j];

switch (per)

{

case "x1":

{

bool x = x1 == 1;

fp1 = fp1 && x;

break;

}

case "x2":

{

bool x = x2 == 1;

fp1 = fp1 && x;

break;

}

case "x3":

{

bool x = x3 == 1;

fp1 = fp1 && x;

break;

}

default:

{

throw new Exception("Недопустимое имя переменной ! :" + per);

break;

}

}

}

}

f1 = f1 || fp1;

}

mas_rez[pos] = f1;

pos++;

}

 

/*

x1,x2,x3

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

*/

 

this.listBox1.Items.Clear();

 

this.listBox1.Items.Add("0 0 0 = " + mas_rez[7].ToString());

this.listBox1.Items.Add("0 0 1 = " + mas_rez[6].ToString());

this.listBox1.Items.Add("0 1 0 = " + mas_rez[5].ToString());

this.listBox1.Items.Add("0 1 1 = " + mas_rez[4].ToString());

this.listBox1.Items.Add("1 0 0 = " + mas_rez[3].ToString());

this.listBox1.Items.Add("1 0 1 = " + mas_rez[2].ToString());

this.listBox1.Items.Add("1 1 0 = " + mas_rez[1].ToString());

this.listBox1.Items.Add("1 1 1 = " + mas_rez[0].ToString());

 

 

Koefficient[,] tabl_koeff = new Koefficient[8, 7];

 

pos = 0;

 

// формируем таблицу коэффициентов

for (x1 = 1; x1 >= 0; x1--)

for (x2 = 1; x2 >= 0; x2--)

for (x3 = 1; x3 >= 0; x3--)

{

tabl_koeff[pos, 0] = new Koefficient();

tabl_koeff[pos, 0].up_part = x1.ToString();

tabl_koeff[pos, 0].down_part = "1";

tabl_koeff[pos, 0].value = true;

 

tabl_koeff[pos, 1] = new Koefficient();

tabl_koeff[pos, 1].up_part = x2.ToString();

tabl_koeff[pos, 1].down_part = "2";

tabl_koeff[pos, 1].value = true;

 

tabl_koeff[pos, 2] = new Koefficient();

tabl_koeff[pos, 2].up_part = x3.ToString();

tabl_koeff[pos, 2].down_part = "3";

tabl_koeff[pos, 2].value = true;

 

tabl_koeff[pos, 3] = new Koefficient();

tabl_koeff[pos, 3].up_part = x1.ToString() + x2.ToString();

tabl_koeff[pos, 3].down_part = "12";

tabl_koeff[pos, 3].value = true;

 

tabl_koeff[pos, 4] = new Koefficient();

tabl_koeff[pos, 4].up_part = x1.ToString() + x3.ToString();

tabl_koeff[pos, 4].down_part = "13";

tabl_koeff[pos, 4].value = true;

 

tabl_koeff[pos, 5] = new Koefficient();

tabl_koeff[pos, 5].up_part = x2.ToString() + x3.ToString();

tabl_koeff[pos, 5].down_part = "23";

tabl_koeff[pos, 5].value = true;

 

tabl_koeff[pos, 6] = new Koefficient();

tabl_koeff[pos, 6].up_part = x1.ToString() + x2.ToString() + x3.ToString();

tabl_koeff[pos, 6].down_part = "123";

tabl_koeff[pos, 6].value = true;

 

pos++;

}

 

int k = 0, h, w, y;

 

// определеям нулевые коэффициенты, шаг 1

for (k = 0; k < 8; k++)

{

if (mas_rez[k] == false)

{

for (h = 0; h < 7; h++)

{

tabl_koeff[k, h].value = false;

for (w = 0; w < 8; w++)

for (y = 0; y < 7; y++)

{

if (w == k) continue;

if (mas_rez[w] == false) continue;

if (tabl_koeff[w, y].down_part == tabl_koeff[k, h].down_part &&

tabl_koeff[w, y].up_part == tabl_koeff[k, h].up_part)

{

tabl_koeff[w, y].value = false;

}

}

}

}

}

 

// формируем получившуюся систему уравнений

List<List<Koefficient>> lst_system = new List<List<Koefficient>>();

 

for (k = 0; k < 8; k++)

{

if (mas_rez[k])

{

List<Koefficient> lst_rivnanna = new List<Koefficient>();

for (h = 0; h < 7; h++)

if (tabl_koeff[k, h].value)

lst_rivnanna.Add(tabl_koeff[k, h]);

if (lst_rivnanna.Count > 0)

lst_system.Add(lst_rivnanna);

}

}

 

// выводим получившуюся систему уравнений

this.listBox2.Items.Clear();

for (k = 0; k < lst_system.Count; k++)

{

string item1 = "";

for (h = 0; h < lst_system[k].Count; h++)

item1 += "K(" + lst_system[k][h].up_part + "," + lst_system[k][h].down_part + ") V";

item1 = item1.Remove(item1.Length - 2, 2);

item1 += " = 1";

listBox2.Items.Add(item1);

}

 

 

 

// определеям нулевые коэффициенты, шаг 2

for (k = 0; k < lst_system.Count; k++)

{

bool fl1 = true;

while (fl1)

{

fl1 = false;

for (h = 0; h < lst_system[k].Count && !fl1; h++)

for (w = h + 1; w < lst_system[k].Count; w++)

{

bool fl2 = true;

for (y = 0; y < lst_system[k][h].down_part.Length; y++)

{

if (!lst_system[k][w].down_part.Contains(lst_system[k][h].down_part[y]))

{

fl2 = false;

break;

}

}

 

if (fl2)

{

lst_system[k].RemoveAt(w);

fl1 = true;

break;

}

}

}

}

 

// выводим получившуюся систему уравнений

this.listBox3.Items.Clear();

for (k = 0; k < lst_system.Count; k++)

{

string item1 = "";

for (h = 0; h < lst_system[k].Count; h++)

item1 += "K(" + lst_system[k][h].up_part + "," + lst_system[k][h].down_part + ") V";

item1 = item1.Remove(item1.Length - 2, 2);

item1 += " = 1";

listBox3.Items.Add(item1);

}

 

 

// находим МДНФ

List<Koefficient> lst_rez_koeff = new List<Koefficient>();

for (k = 0; k < lst_system.Count; k++)

for (h = 0; h < lst_system[k].Count; h++)

lst_rez_koeff.Add(lst_system[k][h]);

 

// удаляем повторяющиеся коэффициенты

bool fl3 = true;

while (fl3)

{

fl3 = false;

for (h = 0; h < lst_rez_koeff.Count && !fl3; h++)

for (w = h + 1; w < lst_rez_koeff.Count; w++)

if (lst_rez_koeff[h].down_part == lst_rez_koeff[w].down_part &&

lst_rez_koeff[h].up_part == lst_rez_koeff[w].up_part)

{

lst_rez_koeff.RemoveAt(w);

fl3 = true;

break;

}

}

 

// выводим МДНФ

 

string mdnf = "";

 

for (k = 0; k < lst_rez_koeff.Count; k++)

{

for (h = 0; h < lst_rez_koeff[k].down_part.Length; h++)

{

string add_s = "";

if (lst_rez_koeff[k].up_part[h] == '0') add_s = "!";

 

mdnf += add_s + "x" + lst_rez_koeff[k].down_part[h] + "*";

 

}

mdnf = mdnf.Remove(mdnf.Length - 1, 1);

mdnf += "+";

}

mdnf = mdnf.Remove(mdnf.Length - 1, 1);

 

this.tb_result.Text = mdnf;

 

}

catch (Exception ex)

{

MessageBox.Show("Возникла ошибка ! Проверьте правильность записи введенной функции!");

}

}

}

}

 

6. РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ

ВЫВОД

В ходе выполнения курсовой работы разработано Windows приложение на языке C# реализующее минимизацию булевых функций методом неопределенных кофициентов.

Также были углублены и закреплены знания по алгоритмизации, программированию в интегрированной визуальной среде программирования Visual C#.

 

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Керниган Б., Ритчи Д. Язык программирования Cи C programming language. — 2-е изд. — М.: «Вильямс», 2007. С. 304. — ISBN 0-13-110362-8

Шилдт Г. Полный справочник по C = C: The Complete Reference. — 4-е изд. — М.: «Вильямс», 2004. — С. 704. — ISBN 0-07-212124-6

Джонсон М. Харт Системное программирование в среде Microsoft Windows. - 3-е издание. 592 стр., с ил.; ISBN 5-8459-0879-5, 0-321-25619-0;

http://support.microsoft.com

 

ПРИЛОЖЕНИЯ

К данному курсовому проекта прилагается магнитный носитель информации (дискета 3,5’’, 1,44Mb) с электронной версией пояснительной записки, полученным Windows-приложением и исходными текстами программы.

 


Переплет дипломов
Главная Новости О компании Наши услуги Цены Способы оплаты Авторам Вопрос-ответ Карта сайта Контакты
Партнеры: "ЦОДНТИ" "Первая Переплетная Мастерская""ЮТЭК"
Academic Journal Catalogue (AJC)