IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Минимизация логической функции
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской
Реальное имя: Artem

Репутация: -  0  +


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


Гость






Поиск по форуму (ну, скажем по слову СДНФ) выдаст тебе кое-что интересное... Посмотри...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской
Реальное имя: Artem

Репутация: -  0  +


Благодарю Вас, Сударь smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской
Реальное имя: Artem

Репутация: -  0  +


Что бы разобраться в принципе работы, просьба объясните (если можно комменты в код), что и какая функция и процедура здесь делает на этом примере (с данного форума), с логическими функциями еще не работал до этого момента (а будет еще курсовая). И еще вопрос: здесь происходит минимизация или просто вывод в таблицу? Заранее благодарю.
 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.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






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

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

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

, а на функции "a+b+a*\b+a"
Цитата(Console)
the result: a + b + a*\b

)

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской
Реальное имя: Artem

Репутация: -  0  +


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

Сообщение отредактировано: Tenshi -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






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

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

Что касается других методов - это Квайн-МакКласки: 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

Цитата
как работают процедуры в приведении к табличному виду
Только попозже, вечером...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской
Реальное имя: Artem

Репутация: -  0  +


Цитата(volvo @ 26.06.2008 14:19) *

Думаешь? Попробуй, скажем, на бумаге (методом карт Карно) минимизировать функцию... Ну, например, из 6-ти переменных... Не из 2-х или 3-х, и не 4-х. А именно больше 4-х. Проще? smile.gif
Что касается других методов - это Квайн-МакКласки: 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

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

спасибо smile.gif а про большое количество переменных я осведомлен, мне хватит и 3 smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Вот программа с комментариями (кодировка - Win1251):
Прикрепленный файл  minimization.txt ( 3.68 килобайт ) Кол-во скачиваний: 839
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской
Реальное имя: Artem

Репутация: -  0  +


Спасибо good.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Как осуществляется процесс нахождения минтермов из вот этой найденной таблицы?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






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


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Мужской
Реальное имя: Artem

Репутация: -  0  +


Цитата(volvo @ 27.06.2008 15:18) *

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

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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 31.10.2020 16:00
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name