Форум «Всё о Паскале» _ Задачи _ Минимизация логической функции
Автор: Tenshi 24.06.2008 16:53
День добрый, Уважаемые программисты Прошу помощи в данном вопросе: "составить программу минимизации логической функции произвольной длины". На данном этапе мне нужна теория и желательно алгоритм действий. У кого есть ссылки на источники или знания помогите
Автор: volvo 24.06.2008 16:59
Поиск по форуму (ну, скажем по слову СДНФ) выдаст тебе кое-что интересное... Посмотри...
Автор: Tenshi 25.06.2008 12:40
Благодарю Вас, Сударь
Автор: Tenshi 26.06.2008 12:58
Что бы разобраться в принципе работы, просьба объясните (если можно комменты в код), что и какая функция и процедура здесь делает на этом примере (с данного форума), с логическими функциями еще не работал до этого момента (а будет еще курсовая). И еще вопрос: здесь происходит минимизация или просто вывод в таблицу? Заранее благодарю.
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 26.06.2008 13:12
Цитата
И еще вопрос: здесь происходит минимизация или просто вывод в таблицу?
Здесь - просто вывод в таблицу - (поскольку такое было задание там, откуда скопирована данная программа: http://forum.pascal.net.ru/index.php?s=&showtopic=15866&view=findpost&p=92850
Цитата
Написать программу, которая осуществляет переход от ДНФ к табличному заданию.
, собственно, это и делается...).
Минимизация происходит здесь: http://forum.pascal.net.ru/index.php?s=&showtopic=6976&view=findpost&p=50614
( результат работы: на функции "a*\a*b+a*\b+b"
Цитата(Console)
the result: a*\b + b
, а на функции "a+b+a*\b+a"
Цитата(Console)
the result: a + b + a*\b
)
Автор: Tenshi 26.06.2008 17:03
Хмм, а из табличного вида произвести минимизацию, помоему это будет проще. Во всяком случае та прога на которую ты дал ссылку для меня вообще как темный лес =) З.ы. Поделись пожалуйста как работают процедуры в приведении к табличному виду, мб тогда смогу дописать и минимизацию сам Кстате, нет случаем ссылок на источники с минимизацией (и желательно примерами в паскале) остальные методы (кроме Карно) мне так же интересны =)
Автор: volvo 26.06.2008 17:19
Цитата
а из табличного вида произвести минимизацию, помоему это будет проще.
Думаешь? Попробуй, скажем, на бумаге (методом карт Карно) минимизировать функцию... Ну, например, из 6-ти переменных... Не из 2-х или 3-х, и не 4-х. А именно больше 4-х. Проще?
Цитата
Кстате, нет случаем ссылок на источники с минимизацией
Что касается других методов - это Квайн-МакКласки: http://sevntu.com.ua/conference/virt/Materials/Shkil/text2/tema3/kvain.htm (по-русски)
Здесь в PDF-файле: http://www.ece.umd.edu/class/enee644.S2004/lectures/two_level_Q_M.pdf (англ.) Еще одна страничка (англ., если сможешь разобраться - прекрасно, там есть даже исходник, правда на Бейсике): http://www.seattlerobotics.org/encoder/200106/qmccmin.htm
Цитата
как работают процедуры в приведении к табличному виду
Только попозже, вечером...
Автор: Tenshi 26.06.2008 18:07
Цитата(volvo @ 26.06.2008 14:19)
Думаешь? Попробуй, скажем, на бумаге (методом карт Карно) минимизировать функцию... Ну, например, из 6-ти переменных... Не из 2-х или 3-х, и не 4-х. А именно больше 4-х. Проще? Что касается других методов - это Квайн-МакКласки: http://sevntu.com.ua/conference/virt/Materials/Shkil/text2/tema3/kvain.htm (по-русски)
Здесь в PDF-файле: http://www.ece.umd.edu/class/enee644.S2004/lectures/two_level_Q_M.pdf (англ.) Еще одна страничка (англ., если сможешь разобраться - прекрасно, там есть даже исходник, правда на Бейсике): http://www.seattlerobotics.org/encoder/200106/qmccmin.htm
Только попозже, вечером...
спасибо а про большое количество переменных я осведомлен, мне хватит и 3
Автор: volvo 27.06.2008 0:54
Вот программа с комментариями (кодировка - Win1251): minimization.txt ( 3.68 килобайт )
Кол-во скачиваний: 1008
Автор: Tenshi 27.06.2008 1:29
Спасибо
Автор: Гость 27.06.2008 18:00
Как осуществляется процесс нахождения минтермов из вот этой найденной таблицы?
Автор: volvo 27.06.2008 18:18
А я, собственно, предупреждал, что не все так просто, как кажется, однако поскольку автор темы утверждал, что
Цитата
смогу дописать и минимизацию сам
, то это теперь его проблема... Для того, чтобы понять, как это делается - достаточно вручную минимизировать несколько выражений (находится минимальное число прямоугольников максимальной площади, накрывающее все единичные значения в таблице, и по координатам этих прямоугольников строятся минтермы). Это несложно. Но вот сделать это программно - уже сложнее.
Автор: Tenshi 27.06.2008 20:14
Цитата(volvo @ 27.06.2008 15:18)
(находится минимальное число прямоугольников максимальной площади, накрывающее все единичные значения в таблице, и по координатам этих прямоугольников строятся минтермы).
в этом и заключался мой вопрос,спасибо. постил йа просто браузер пользователя отказывается запоминать з.Ы. Сделать "не сам" я всегда успею, хочу просто увидеть как работает минимизация даже просто на бумаге (первый раз встречаюсь с этим понятием и собственно в логических функциях никогда не копался) если бы мне не было интересно и не нужно это, то не задавал бы столько вопросов з.з.Ы хорошо что есть добрые люди вроде тебя которые так хорошо шарят в этих вопросах и тратят время на на нубоф вроде меня