Міністерство освіти і науки України Вінницький національний технічний університет Кафедра КН Лабораторна робота №4 з дисципліни «Дискретна математика» Тема: «Розробка алгоритму і програми мінімізації функцій алгебри логіки методом Квайна» Виконали: студент[ім’я автора приховано] Ільченко О.В. Ваховський В.М. Перевірила: Ваховська Л. М. Вінниця 2016 Мета роботи: Набути навиків мінімізації логічних функцій методом Квайна. Завдання: розробити алгоритм та програму для мінімізації логічної функції, задану у вигляді. Продемонструвати роботу програми на прикладі. 3. Завдання для виконання Варіант 41 V=(0,1,3,4,5,7,8,9,13) Варіант 37 V=(2,4,5,8,9,11,12,13) Схема алгоритму
Рисунок 1 – Блок-схема програми мінімізації функції алгебри логіки Результати роботи: Варіант 41 / Рисунок 3 – Результат роботи програми мінімізації функції алгебри логіки Варіант 37 / Рисунок 4 – Результат роботи програми мінімізації функції алгебри логіки Висновок Під час виконання лабораторної роботи було розроблено алгоритм застосування методу мінімізації функції алгебри логіки. Було розроблено програму для знаходження мінімізації функції алгебри логіки в якій було знайдено ДДНФ, скорочену та мінімальну форми функції. Додаток 1. Інструкція користувача Для запуску програми мінімізації функції необхідно запустити файл MininizationFAL.exe. Ввести вектор або функцію. Натиснути на кнопку «Минимизировать» для виконання пошуку мінімальної форми. Програма виведе ДДНФ, скорочену і мінімальну форми . Додаток 2. Лістинги програми //--------------------------------------------------------------------------- #include "Unit1.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; //--------------------------------------------------------------------------- #include <stdio.h> #include <stdlib.h> #include <iostream> #include <string.h> #include <math.h> #include <vcl.h> #pragma hdrstop //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ class minterm { public: int a[4]; int size; minterm(){ size=0; } minterm(int A,int B,int C,int D){ size=4; a[0]=A; a[1]=B; a[2]=C; a[3]=D; } void fill(int A,int B,int C,int D){ a[0]=A; a[1]=B; a[2]=C; a[3]=D; } bool operator == (const minterm &m){ for(int i=0;i<size;i++){ if(a[i]!=m.a[i]) return 0; } return 1; } bool operator != (const minterm &m){ for(int i=0;i<size;i++){ if(a[i]!=m.a[i]) return 1; } return 0; } bool not_void(){ for(int i=0;i<size;i++){ if(a[i]!=-1) return 1; } return 0; } bool include(const minterm &m) { for(int k=0;k<4;k++) { if(m.a[k]!=-1 && a[k]!=m.a[k]) return 0; } return 1; } int count_1() { int c=0; for(int i=0;i<4;i++) if(a[i]==1) c++; return c; } bool positions_coincide(const minterm &m) { for(int i=0;i<4;i++) if(a[i]==-1 && a[i]!=m.a[i]) return 0; return 1; } bool can_be_united(const minterm &m) { for(int k=0;k<4;k++) { if(a[k]!=m.a[k]) { for(int i=k+1;i<4 && k<3;i++) if(a[i]!=m.a[i]) return false; return true; } } return true; } void glue(const minterm &m) { for(int k=0;k<4;k++) { if(a[k]!=m.a[k]) { for(int i=k+1;i<4 && k<3;i++) if(a[i]!=m.a[i]) return; a[k]=-1; return; } } } AnsiString print(){ AnsiString s; if(!(a[0]==-1 && a[1]==-1 && a[2]==-1 && a[3]==-1)){ if(a[0]==1) s=s+"A"; if(a[0]==0) s=s+"!A"; if(a[1]==1) s=s+"B"; if(a[1]==0) s=s+"!B"; if(a[2]==1) s=s+"C"; if(a[2]==0) s=s+"!C"; if(a[3]==1) s=s+"D"; if(a[3]==0) s=s+"!D"; } return s; } }; //--------------------------------------------------------------------------- class fal{ public: minterm *mdnf; int size,param; class Table; fal(){ size=0; mdnf=0; param=0; } fal(const AnsiString s,int param_){ minterm table[16]={ minterm(0,0,0,0),minterm(0,0,0,1),minterm(0,0,1,0),minterm(0,0,1,1), minterm(0,1,0,0),minterm(0,1,0,1),minterm(0,1,1,0),minterm(0,1,1,1), minterm(1,0,0,0),minterm(1,0,0,1),minterm(1,0,1,0),minterm(1,0,1,1), minterm(1,1,0,0),minterm(1,1,0,1),minterm(1,1,1,0),minterm(1,1,1,1)}; int lenght=s.Length(); param=param_; char* f= s.c_str(); for(int i=0;i<lenght;i++){ f[i]=f[i]-48; } size=0; for(int i=0;i<lenght;i++){ if(f[i]==1){ ++size; } } mdnf=new minterm[size]; int j=0,koef=1; if(param==3) koef=2; if(param==2) koef=4; for(int i=0;i<lenght;i++){ if(f[i]==1){ mdnf[j]=table[koef*i]; for(int k=param;k<4;++k) mdnf[j].a[k]=-1; j++; } } } fal(const Table &t,int param_) { mdnf=new minterm[t.size]; size=t.size; param=param_; for (int i = 0; i < size; i++) { mdnf[i]=t.row[i]->m; } } ~fal(){ delete[] mdnf; } AnsiString print(){ int i; AnsiString s; for(i=0;!mdnf[i].not_void() && i<size;i++); s=s+mdnf[i].print(); for(i=i+1;i<size;i++) if(mdnf[i].not_void()){ s=s+" v "; s=s+mdnf[i].print(); } s=s+"\n"; return s; } int count(){ int n=0; for(int i=0;i<size;i++) if(mdnf[i].not_void()) n++; return n; } //--------------------------------------------------------------------------- class Row { public: int index; int index_arr[8]; minterm m; int n; bool united; Row() { index=n=0; } Row(int index_,minterm m_) { m=m_; united=0; index=index_+1; for(int i=1;i<8;i++) index_arr[i]=0; index_arr[0]=index; n=m.count_1(); } Row(const Row &r) { m=r.m; united=r.united; index=r.index; for(int i=0;i<8;i++) index_arr[i]=r.index_arr[i]; n=r.n; } Row *Unite(Row &r) { Row *new_row=new Row(r); united=r.united=true; new_row->united=0; new_row->m.glue(m); for(int i=0;i<8;i++) if(new_row->index_arr[i]==0) { for(int j=0;j<8 && index_arr[j]!=0;j++) new_row->index_arr[i++]=index_arr[j]; break; } new_row->n=new_row->m.count_1(); return new_row; } void print() { Form1->Label10->Caption=Form1->Label10->Caption+"| "+index+" | " +index_arr[0]+' '+index_arr[1]+' '+ index_arr[2]+' '+index_arr[3]+' '+index_arr[4]+' '+index_arr[5]+' '+ index_arr[6]+' '+index_arr[7]+' '+" | "+m.print()+" | "+n+" | " +(int)united+" | \n"; } bool find_in_index_arr(int n) { for(int i=0;i<8;i++) if(index_arr[i]==n) return 1; return 0; } }; //--------------------------------------------------------------------------- class Table { public: Row **row; int size,real_size; Table(int size) { this->size=size; real_size=size; row=new Row*[size]; } Table(const fal &sdnf) { size=sdnf.size; real_size=size; row=new Row*[size]; for(int i=0;i<size;i++) row[i]=new Row(i,sdnf.mdnf[i]); } ~Table() { delete[] row; } void print() { Form1->Label10->Caption=Form1->Label10->Caption+"size="+size+ " rs="+real_size+"\n"; for(int i=0;i<size;i++) row[i]->print(); Form1->Label10->Caption=Form1->Label10->Caption+"\n"; } Table &operator = (const Table &t) { if(&t==this) return *this; Row **n=new Row*[t.real_size]; for (int i = 0; i < t.real_size; i++) { n[i]=t.row[i]; } for(int i=0;i<real_size;i++) delete[] row; row=n; size=t.size; real_size=t.real_size; return *this; } bool shorten() { bool changes=false; Table *new_table; int new_size=0; new_table=new Table(3*size); for (int i=0; i < size; i++) { for (int j = 0; j < size; j++) { if((row[i]->index!=row[j]->index && row[i]->n==(row[j]->n+1) && row[i]->m.can_be_united(row[j]->m) && row[i]->m.positions_coincide(row[j]->m))) { new_table->row[new_size]=row[i]->Unite(*row[j]); new_table->row[new_size]->index=new_size; new_size=new_size+1; changes=true; } } } for (int i=0; i < size; i++) { if(!(row[i]->united)) { new_table->row[new_size]=row[i]; new_table->row[new_size]->index=new_size; ++new_size; } } *this=*new_table; size=new_size; return changes; } void remove_eq_rows() { for (int i=0; i < size; i++) for (int j = 0; j < size; j++) if(row[i]->index!=row[j]->index && row[i]->m==row[j]->m && !(row[i]->united)) row[j]->united=1; this->shorten(); } bool find(int n, int r) { for (int i=0; i < size; i++) if(r!=i) { if(row[i]->find_in_index_arr(n)) return true; } return false; } bool find_in_core(int n, int r) { for (int i=0; i < size; i++) if(r!=i && row[i]->united) { if(row[i]->find_in_index_arr(n)) return true; } return false; } Row *find_and_add_in_core(int n, int r) { for (int i=0; i < size; i++) if(r!=i && !row[i]->united) { if(row[i]->find_in_index_arr(n)) { row[i]->united=1; return new Row(*row[i]); } } return 0; } void minimize() { Table *new_table; Row *new_row=0; int new_size=0; new_table=new Table(size); for (int i=0; i < size; i++) { for (int n=0; n < 8; n++) if(!this->find(row[i]->index_arr[n],i)){ row[i]->united=1; new_table->row[new_size]=new Row(*row[i]); ++new_size; break; } } for (int i=0; i < size; i++) for (int n=0; n < 8; n++) if(row[i]->united!=1 && row[i]->index_arr[n]!=0) if(!this->find_in_core(row[i]->index_arr[n],i)) { new_row= this->find_and_add_in_core(row[i]->index_arr[n],i); if(new_row) { new_table->row[new_size]=new_row; ++new_size; } } *this=*new_table; size=new_size; } }; }; //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } void print_element_not(int x,int y){ Form1->Image1->Canvas->MoveTo(x,y); Form1->Image1->Canvas->LineTo(x,y+25); Form1->Image1->Canvas->LineTo(x-50,y+25); Form1->Image1->Canvas->LineTo(x-50,y-25); Form1->Image1->Canvas->LineTo(x,y-25); Form1->Image1->Canvas->LineTo(x,y); Form1->Image1->Canvas->Ellipse(x+5,y-5,x-5,y+5); } void print_dot(int x,int y){ Form1->Image1->Canvas->Brush->Color=0; Form1->Image1->Canvas->Ellipse(x+3,y-3,x-3,y+3); Form1->Image1->Canvas->FloodFill(x,y,0,fsBorder); Form1->Image1->Canvas->Brush->Color=clBtnFace; } void print_element_and(int x,int y,const minterm &m){ Form1->Image1->Canvas->MoveTo(x,y); Form1->Image1->Canvas->LineTo(x,y+25); Form1->Image1->Canvas->LineTo(x-50,y+25); Form1->Image1->Canvas->LineTo(x-50,y-25); Form1->Image1->Canvas->LineTo(x,y-25); Form1->Image1->Canvas->LineTo(x,y); Form1->Image1->Canvas->TextOut(x-25,y-10,"&"); Form1->Image1->Canvas->MoveTo(x,y); Form1->Image1->Canvas->LineTo(x+20,y); if(m.a[0]==1) { Form1->Image1->Canvas->MoveTo(x-50,y-15); Form1->Image1->Canvas->LineTo(10,y-15); print_dot(10,y-15); } if(m.a[0]==0) { Form1->Image1->Canvas->MoveTo(x-50,y-15); Form1->Image1->Canvas->LineTo(160,y-15); print_dot(160,y-15); } if(m.a[1]==1) { Form1->Image1->Canvas->MoveTo(x-50,y-5); Form1->Image1->Canvas->LineTo(30,y-5); print_dot(30,y-5); } if(m.a[1]==0) { Form1->Image1->Canvas->MoveTo(x-50,y-5); Form1->Image1->Canvas->LineTo(180,y-5); print_dot(180,y-5); } if(m.a[2]==1) { Form1->Image1->Canvas->MoveTo(x-50,y+5); Form1->Image1->Canvas->LineTo(50,y+5); print_dot(50,y+5); } if(m.a[2]==0) { Form1->Image1->Canvas->MoveTo(x-50,y+5); Form1->Image1->Canvas->LineTo(200,y+5); print_dot(200,y+5); } if(m.a[3]==1) { Form1->Image1->Canvas->MoveTo(x-50,y+15); Form1->Image1->Canvas->LineTo(70,y+15); print_dot(70,y+15); } if(m.a[3]==0) { Form1->Image1->Canvas->MoveTo(x-50,y+15); Form1->Image1->Canvas->LineTo(220,y+15); print_dot(220,y+15); } } //--------------------------------------------------------------------------- void __fastcall TForm1::Button1Click(TObject *Sender) { AnsiString s = Edit1->Text; int param_=(int)*ComboBox1->Text.c_str()-48; if(Edit1->Text=="1111111111111111" || Edit1->Text=="11111111" || Edit1->Text=="1111") { Label3->Caption=1; Label8->Caption=1; Label1->Caption=1; TRect tRect(0,0,Image1->Width,Image1->Height); Image1->Canvas->FillRect(tRect); return; } if(Edit1->Text=="0000000000000000" || Edit1->Text=="00000000" || Edit1->Text=="0000") { Label3->Caption=0; Label8->Caption=0; Label1->Caption=0; TRect tRect(0,0,Image1->Width,Image1->Height); Image1->Canvas->FillRect(tRect); return; } fal k(s,param_); fal::Table t(k); while(t.shorten()); t.remove_eq_rows(); fal f(t,param_); Label3->Caption=f.print(); //t.print(); t.minimize(); //t.print(); Label1->Caption=k.print(); fal l(t,param_); Label8->Caption=l.print(); int height=l.count()*70+500; Image1->Height=height; TRect tRect(0,0,Image1->Width,Image1->Height); Image1->Canvas->FillRect(tRect);