Минимизация логической функции Опции

[Tenshi]

День добрый, Уважаемые программисты
Прошу помощи в данном вопросе: "составить программу минимизации логической функции произвольной длины".
На данном этапе мне нужна теория и желательно алгоритм действий. У кого есть ссылки на источники или знания помогите

[volvo]

Поиск по форуму (ну, скажем по слову СДНФ) выдаст тебе кое-что интересное... Посмотри...

[Tenshi]

Благодарю Вас, Сударь

[Tenshi]

Что бы разобраться в принципе работы, просьба объясните (если можно комменты в код), что и какая функция и процедура здесь делает на этом примере (с данного форума), с логическими функциями еще не работал до этого момента (а будет еще курсовая). И еще вопрос: здесь происходит минимизация или просто вывод в таблицу? Заранее благодарю.

 program Minimization;
  function fromdec(n,m : longint): string;
	var
	  s: string;
	const
	  digit: string[16] = '0123456789ABCDEFQ';
  begin
	s := '';
	repeat
	s := digit[(n mod m) + 1] + s;
	n := n div m;
	until n = 0;
	while length(s) < 2 do s := '0' + s;
	fromdec := s;
  end;

  const
	s: string = 'A*/B+/A*/C*/D+B*/C*D';
  type
	tmatrix = array[0 .. 3, 0 .. 3] of 0 .. 1;
  var
	mx: tmatrix;
	p, i: integer;
	mask, sub_s: string;

  function matches(s, mask: string): boolean;
	var i: integer;
	begin
	  matches := true;
	  for i := 1 to length(s) do begin
		  if (mask[i] = 'X') or (s[i] = mask[i]) then {}
		  else matches := false

	end;
  end;

  procedure print_mx(const mx: tmatrix);
	 var i, j: integer;
	 begin
		for i := 0 to 3 do begin
		for j := 0 to 3 do write(mx[i, j]:3);
		writeln;
	 end;
  end;

  procedure fill_mx(var mx: tmatrix;
			first, second: string);
	 var i, j: integer;
	 begin
		for i := 0 to 3 do
		for j := 0 to 3 do
		if matches(fromdec(i, 2), first) and matches(fromdec(j, 2), second)
		then mx[i, j] := 1;
	 end;

begin
   write ('function: '); readln(s);
   s := s + '+';
   repeat
	 p := pos('+', s);
	 if p > 0 then begin
		sub_s := copy(s, 1, p-1);
		mask := '';
		for i := 1 to 4 do mask := mask + 'X';
		for i := 1 to length(sub_s) do begin
			if sub_s[i] in ['A' .. 'D'] then
			if (i > 1) and (sub_s[i - 1] = '/') then
			mask[ord(sub_s[i]) - ord('A') + 1] := '0'
			else
			mask[ord(sub_s[i]) - ord('A') + 1] := '1';
		end;
	 fill_mx(mx, copy(mask, 1, 2), copy(mask, 3, 2));
	 delete(s, 1, p);
	 end;
   until p = 0;
   print_mx(mx);
   readln;
end. 

[volvo]

И еще вопрос: здесь происходит минимизация или просто вывод в таблицу?

Здесь - просто вывод в таблицу - (поскольку такое было задание там, откуда скопирована данная программа:
переход от ДНФ к табличному виду

Написать программу, которая осуществляет переход от ДНФ к табличному заданию.

, собственно, это и делается...).

Минимизация происходит здесь: Булевские ф-ции

(
результат работы: на функции "a*\a*b+a*\b+b"

the result: a*\b + b

, а на функции "a+b+a*\b+a"

the result: a + b + a*\b

)

Сообщение отредактировано: volvo - 26.06.2008 10:04

[Tenshi]

Хмм, а из табличного вида произвести минимизацию, помоему это будет проще. Во всяком случае та прога на которую ты дал ссылку для меня вообще как темный лес =)
З.ы. Поделись пожалуйста как работают процедуры в приведении к табличному виду, мб тогда смогу дописать и минимизацию сам
Кстате, нет случаем ссылок на источники с минимизацией (и желательно примерами в паскале) остальные методы (кроме Карно) мне так же интересны =)

Сообщение отредактировано: Tenshi - 26.06.2008 13:04

[volvo]

а из табличного вида произвести минимизацию, помоему это будет проще.

Думаешь? Попробуй, скажем, на бумаге (методом карт Карно) минимизировать функцию... Ну, например, из 6-ти переменных... Не из 2-х или 3-х, и не 4-х. А именно больше 4-х. Проще?

Кстате, нет случаем ссылок на источники с минимизацией

Что касается других методов - это Квайн-МакКласки: http://sevntu.com.ua/conference/virt/Mater...tema3/kvain.htm (по-русски)

Здесь в PDF-файле: http://www.ece.umd.edu/class/enee644.S2004...o_level_Q_M.pdf (англ.)
Еще одна страничка (англ., если сможешь разобраться - прекрасно, там есть даже исходник, правда на Бейсике): http://www.seattlerobotics.org/encoder/200106/qmccmin.htm

как работают процедуры в приведении к табличному виду

Только попозже, вечером...

[Tenshi]

Думаешь? Попробуй, скажем, на бумаге (методом карт Карно) минимизировать функцию... Ну, например, из 6-ти переменных... Не из 2-х или 3-х, и не 4-х. А именно больше 4-х. Проще?
Что касается других методов - это Квайн-МакКласки: http://sevntu.com.ua/conference/virt/Mater...tema3/kvain.htm (по-русски)

Здесь в PDF-файле: http://www.ece.umd.edu/class/enee644.S2004...o_level_Q_M.pdf (англ.)
Еще одна страничка (англ., если сможешь разобраться - прекрасно, там есть даже исходник, правда на Бейсике): http://www.seattlerobotics.org/encoder/200106/qmccmin.htm

Только попозже, вечером...

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

[volvo]

Вот программа с комментариями (кодировка - Win1251):
 minimization.txt ( 3.68 килобайт ) Кол-во скачиваний: 758

[Tenshi]

Спасибо

[Гость]

Как осуществляется процесс нахождения минтермов из вот этой найденной таблицы?

[volvo]

А я, собственно, предупреждал, что не все так просто, как кажется, однако поскольку автор темы утверждал, что

смогу дописать и минимизацию сам

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

[Tenshi]

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

в этом и заключался мой вопрос,спасибо.
постил йа просто браузер пользователя отказывается запоминать
з.Ы. Сделать "не сам" я всегда успею, хочу просто увидеть как работает минимизация даже просто на бумаге (первый раз встречаюсь с этим понятием и собственно в логических функциях никогда не копался) если бы мне не было интересно и не нужно это, то не задавал бы столько вопросов
з.з.Ы хорошо что есть добрые люди вроде тебя которые так хорошо шарят в этих вопросах и тратят время на на нубоф вроде меня