6826

Автоматизация минимизации булевых функций

Лабораторная работа

Информатика, кибернетика и программирование

Автоматизация минимизации булевых функций Номер зачётной книжки: Основные этапы минимизации методом Квайна-МакКласки: Сначала определяем основные конститутенты, далее подготавливаем к склеиванию термов. Склеиваим все ...

Русский

2013-01-08

181 KB

27 чел.

Автоматизация минимизации булевых функций

Номер зачётной книжки: 831910 =100000011111112;

 

Основные этапы минимизации методом Квайна-МакКласки:

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

Скриншот программы:

Листинг программы:

import java.util.ArrayList;

public class Function {

 private String funcName;

 

 private ArrayList<String> function;

 private ArrayList<String> argumentNames;

 private ArrayList<String> additionalConsts;

 

 public Function(String fName, ArrayList<String> argNames,

  ArrayList<String> func, ArrayList<String> addConsts){

 funcName = fName;

 function = func;

 argumentNames = argNames;

 additionalConsts = addConsts;

}

 public void prepare(){

 prepareForMin(function);

 prepareForMin(additionalConsts);

}

 

 private void prepareForMin(ArrayList<String> constList){

 boolean xFined = false;

 ArrayList<String> impToRemove = new ArrayList<String>();

 ArrayList<String> impToAdd = new ArrayList<String>();

 for(String impl: constList){

  for(int i = 0; i<impl.length(); i++) {

   if(impl.charAt(i)=='X'){

    impToAdd.add(impl.replaceFirst("X", "0"));

    impToAdd.add(impl.replaceFirst("X", "1"));

    impToRemove.add(impl);

    xFined = true;    }

  }

 }

 for(String impl:impToRemove){

  constList.remove(impl);

 }

 for(String impl:impToAdd){

  constList.add(impl);

 }

 if(xFined){

  prepareForMin(constList);

 }

}

 

 public void minimize(){

 Minimizator min = new Minimizator();

 function = min.minimize(function, additionalConsts);

}

// public String toStringKvain(){

//  String func = funcName+" = ";

//  for(String impl:function) {

//   String strImplicant = "(";

//   strImplicant += impl;

//   strImplicant += ")U";

//   func+=strImplicant;

//  }

//  return func.substring(0, func.length()-1);

// }

 

 public String toString(){

 String func = funcName+" = ";

 if(function.get(0).charAt(0)=='!'){

  return func+function.get(0).charAt(1);  }

 

 for(String impl:function) {

  String strImplicant = " (";

  for(int i = 0; i<impl.length(); i++) {

   if(impl.charAt(i)=='0'){

    strImplicant+="Not"+argumentNames.get(i)+" ";

    continue;

   }

   if(impl.charAt(i)=='1'){

    strImplicant+=argumentNames.get(i)+" ";

    continue;

   }

  }

  strImplicant += ") v";

  func+=strImplicant;

 }

 return func.substring(0, func.length()-1);

 }

}

import java.util.ArrayList;

public class Minimizator {

 

 private ArrayList<String> minImps;

 

 public Minimizator(){

 minImps = new ArrayList<String>();

}

 

 private String createImplicant(String s1, String s2) {//поглощение

 String implicant = "";

 for (int i = 0; i < s1.length(); i++) {

  if (s1.charAt(i) != s2.charAt(i)) {

   implicant += 'X';

  } else {

   implicant += s1.charAt(i);

  }

 }

 return implicant;

}

 

 private int differentBits(String s1, String s2) {

 int count = 0;

 for (int i = 0; i < s1.length(); i++) {  

  if (s1.charAt(i) != s2.charAt(i)) {

   count++;

  }

 }

 return count;

}

 

 private int getNumOf1(String s) {

 int k = 0;

 for (int i = 0; i < s.length(); i++)

  if (s.charAt(i) == '1') k++;

 return k;

}

 

 

 private int getMinimizationPhase(String s){

 int k = s.length();

 for(int i = 0; i<s.length();i++) {

  if(s.charAt(i)=='X'){

   k--;

  }

 }

 return k;

}

 private boolean impExists(String s){

 for(String imp:minImps){

  if(imp.equals(s)) return true;

 }

 return false;

}

 

 //checking if implicant exists in current list of implicants

 private boolean impExists(ArrayList<String> imps, String s){

 for(String imp:imps){

  if(imp.equals(s)) return true;

 }

 return false;

}

 

 //return number of entering into this constituant with all minimal implicants

 private int countEntering(int[] mas){

 int numOfEntering = 0;

 for(int i =0; i<mas.length; i++){

  numOfEntering+=mas[i];

 }

 return numOfEntering;

}

 

 //return pointer on the entering implicant

 private int getNumOfEntering(int[] mas){

 for(int i =0; i<mas.length; i++){

  if(mas[i]==1){

   return i;

  }

 }

 

 return 0;

}

 //checking if all constituant are covered

 private boolean allCovered(int[] mas){

 for(int i = 0; i<mas.length; i++) {

  if(mas[i]==0){

   return false;

  }

 }

 return true;

}

 

 

 public ArrayList<String> minimize(ArrayList<String> constits,ArrayList<String> notConsts ){

 if(constits.size()==0){

  ArrayList<String> zeroResult = new ArrayList<String>();

  zeroResult.add("!0");

  return zeroResult;

 }

 createMinImps(constits, notConsts);

 int[] coveredConst = new int[constits.size()];

 int[][] coveringTable = new int[constits.size()][minImps.size()];

 for(int i =0; i< coveringTable.length;i++){

  coveredConst[i] = 0;

  for(int j = 0; j<coveringTable[0].length;j++){

   coveringTable[i][j] = ifCover(constits.get(i),minImps.get(j));

   if(coveringTable[i][j]==1){

    //System.out.println(constits.get(i)+"  ->"+minImps.get(j));

   }

  }

 }

 

 ArrayList<String> minimalForm = new ArrayList<String>();

 

 for(int i = 0; i<coveringTable.length;i++){

  if(countEntering(coveringTable[i])==1){

   int pCoreImp = getNumOfEntering(coveringTable[i]);

   String coreImp =minImps.get(pCoreImp);

   if(impExists(minimalForm, coreImp)){

    continue;

   }

   minimalForm.add(coreImp);

   for(int j = 0; j < constits.size();j++) {

    if(coveringTable[j][pCoreImp]==1){

     coveredConst[j] = 1;

    }

   }

   

  }

 }

 //проверить все ли покрыты, и покрывать пока не покроет все

 while(!allCovered(coveredConst)){

  for(int i = 0; i< constits.size();i++){

   if(coveredConst[i]==0){

    int addImp =-1;

    for(int j = 0; j < coveringTable[0].length;j++){

     if(coveringTable[i][j]==1){

      coveredConst[i] = 1;

      minimalForm.add(minImps.get(j));

      addImp = j;

      break;

     }

    }

    for(int j = 0; j < coveringTable.length;j++){

     if(coveringTable[j][addImp]==1){

      coveredConst[j] = 1;

     }

    }

    break;

   }

  }

 }

 for(String s:minimalForm){

  //System.out.println(s);

 }

 return minimalForm;

}

 

 public int ifCover(String constit, String implic){

 for(int i = 0; i<constit.length();i++) {

  if((constit.charAt(i)!=implic.charAt(i))&&(implic.charAt(i)!='X')){

   return 0;

  }

 }

 return 1;

}

 

 

 public void createMinImps(ArrayList<String> implicants, ArrayList<String> xImplicants){

 

 

 int size = implicants.get(0).length();

 int numOfBits = getMinimizationPhase(implicants.get(0));

 

 ArrayList<ArrayList<String>> impTable= new ArrayList<ArrayList<String>>();

 ArrayList<String> newImps= new ArrayList<String>();

 for(int i = 0;i <numOfBits+1;i++){

  impTable.add(new ArrayList<String>());

 }

 for(String imp:implicants){

  int numOf1= getNumOf1(imp);

  impTable.get(numOf1).add(imp);

  if(numOfBits==size)

   minImps.add(imp);

 }

 if(xImplicants!=null){

  for(String imp:xImplicants){

   int numOf1= getNumOf1(imp);

   impTable.get(numOf1).add(imp);

  }

 }

 

 for(int i = 0;i<impTable.size()-1;i++){

  for(String imp1:impTable.get(i)){

   for(String imp2:impTable.get(i+1)){

    if(differentBits(imp1,imp2)==1){

     String newImp =createImplicant(imp1,imp2);

     minImps.remove(imp1);

     minImps.remove(imp2);

     if(!impExists(newImp)){

      minImps.add(newImp);

      newImps.add(newImp);

     }

    }

   }

  }

 }

 if(newImps.size()!=0){

  createMinImps(newImps, null);

 }

}

}

Выводы

В результате выполнения данной лабораторной работы я приобрёл навыки автоматизации процедуры минимизации булевых функций методом Квайна-МакКласки. Мной были реализованы процедуры построения функций переходов и функций возбуждения тригеров, минимизации этих функций. Все процедуры были реализованы на языке программирования Java.


 

А также другие работы, которые могут Вас заинтересовать

33520. Ведущие темы в лирике Есенина 22.6 KB
  Ведущие темы в лирике Есенина. Сложная и интересная судьба поэта множество путешествий смена мест и образа жизни в сочетании с творческим подходом к осмыслению действительности обусловили богатство и разнообразие тем и мотивов лирики Есенина. Время творчества Есенина время крутых поворотов в истории России. Есенина.
33521. Тема революции в поэме С. Есенина «Анна Снегина» 18.29 KB
  Есенина Анна Снегина. Поэма Анна Онегина написанная незадолго до смерти поэта в 1924 году явилась своеобразным обобщением размышлений Есенина об этом драматическом и противоречивом времени и вобрала в себя многие мотивы и образы его лирики. Это ощущение усиливается в поэме тем что на её страницах в качестве олицетворения его юности появляется Анна Снегина – первая любовь девушка в белой накидке которая ласково сказала: Нет Несмотря на былые воспоминания автор прекрасно понимает что прошлое вернуть невозможно:...
33522. Творчество В.Набокова (роман по выбору). Проблематика, конфликты, герои 16.5 KB
  Защита Лужина Роман Защита Лужина привлекает и своим заглавием и своим содержанием писатель неоднократно объяснял его замысел: Русское заглавие этого романа – Защита Лужина – относится к шахматной защите будто бы придуманной моим героем сочинять книгу было нелегко надо был ввести роковое предназначение в жизнь Лужина и придать очертанию сада поездки событиям подобие замысловатой игры а в последних главах – настоящей шахматной атаки разрушающей до основания здоровье моего героя. У Лужина неожиданно счастливая семейная жизнь...
33523. Особенности композиции и система образов в романе М. Булгакова «Мастер и Маргарита» 22.64 KB
  Особенности композиции и система образов в романе М. Булгакова Мастер и Маргарита Роман в романе М. Сожженное в печи произведение Мастера так называемый внутренний роман возрождается будто Феникс из пепла так как он связан с персонажами романа внешнего. С внешним романом его соединяет образ Алоизия Могарыча предателя которого Мастеру изображать неинтересно поэтому что уже был в его творчестве Иуда.
33524. Проблематика романа «Мастер и Маргарита» 16.97 KB
  Более всего тема угнетения преследования неординарной талантливой личности государством присутствует в судьбе Мастера. Маргарита громит квартиру критика Латунского погубившего Мастера но отвергает предложение уничтожить своего врага. После бала у Сатаны героиня в первую очередь просит за страдающую Фриду забывая о собственном страстном желании вернуть Мастера. Именно Воланд приводит Мастера и его подругу в их вечный дом даруя им покой.
33525. Тема репрессий в поэме А.Ахматовой «Реквием» 17.6 KB
  Ахматова начала писать свою поэму Реквием в 1935 году когда ее единственный сын Лев Гумилев был арестован. Как и другие матери жены сестры Ахматова много часов стояла в молчаливой очереди что вела к петербургской тюрьме Кресты. Только в 1940 году Ахматова завершила свое произведение опубликовано же оно было в 1987 году много лет спустя после смерит автора. Ахматова рассказывает об истории создания поэмы.
33526. Роман-антиутопия Е.Замятина «Мы» (жанровые и художественные особенности) 17.26 KB
  У Замятина мы не масса а социальное качество. Заветная идея сталинизма – не человек но винтик в гигантском государственном механизме который подчинен твердой руке машиниста у Замятина показана осуществленной. Особенности жанра При чтении толкования термина антиутопия все его особенности прослеживаются в романе Евгения Замятина Мы: это и изображение тоталитарного государства и острый конфликт Чтобы возникла художественность нужен романный конфликт. Он должен пережить это сомнение как кульминацию своей жизни пусть даже...
33527. «Чевенгур» Платонова как роман-предупреждение 14.06 KB
  Чевенгур Платонова как романпредупреждение. прочитав роман “Чевенгур†писал Платонову: “Человек вы талантливый это бесспорно бесспорно и то что вы обладаете очень своеобразным языком. Платонов же посылая Горькому рукопись “Чевенгура†писал что “в романе содержится честная попытка изобразить начало коммунистического обществаâ€. Роман “Чевенгур†это энциклопедия социальных инициатив в их взаимодействии с реальной плотью жизни.
33528. Проблематика романа Б. Пастернака «Доктор Живаго», значение лирического дневника в идейной концепции романа 20.46 KB
  Пастернака Доктор Живаго значение лирического дневника в идейной концепции романа. Пастернак начал писать роман “Доктор Живаго†в 1945 году и закончил его в декабре 1955 года.Лихачев уверен что автор Пастернак пишет о самом себе но пишет как о постороннем он придумывает себе судьбу в которой можно было бы наиболее полно раскрыть перед читателем свою внутреннюю жизнь что жизнь Юрия Андреевича Живаго – это альтернативный вариант жизни самого Пастернака. Доктор Живаго – выразитель сокровенного лирический герой Пастернака который...