алгоритм

Лень много думать, но есть подозрение, что задачу можно решить только полным перебором. Ну то есть перебираешь разные варианты «склеивания» функций и выбираешь самый короткий результат.

быстрее будет построить таблицу истинности и потом по таблице свять функцию

Не совсем понял, что ты написал, и вникать как-то лень было. Но вообще человек по имени Квайн как бы ж доказал, что если в ДНФ/КНФ провести все возможные операции неполного склеивания, а потом поглощения, то полученная ДНФ/КНФ будет минимальной по количеству аргументов.

Неполное склеивание - Ax || A!x == A || Ax || A!x

Поглощение - Ax || A == A, A!x || A == A

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

P.S. Я так понял, речь идет именно о минимизации нормальных форм, раз уж карты Карно прозвучали, правильно?

да. например, с помощью СДНФ. Но это будет не самая короткая запись.

Лень много думать, но есть подозрение, что задачу можно решить только полным перебором. Ну то есть перебираешь разные варианты «склеивания» функций и выбираешь самый короткий результат.

слишком большое кол-во входных данных

быстрее будет построить таблицу истинности и потом по таблице свять функцию

таблицу истинности для неупрощённой фал? так, и как сваять упрощённую ф-цию?

это я позже сообразил 8)

Слушай. Опиши ты условие по человечески. Нихрена не понял.

Что значит «смысл в том, чтобы из списка a при помощи b получить минимальный список.»?

Не совсем понял, что ты написал, и вникать как-то лень было. Но вообще человек по имени Квайн как бы ж доказал, что если в ДНФ/КНФ провести все возможные операции неполного склеивания, а потом поглощения, то полученная ДНФ/КНФ будет минимальной по количеству аргументов.

смотри ф-цию join-bb :) спасибо, что напомнил про поглощение, надо добавить его.
Проблема в том, что в ДНФ/КНФ есть необязательные фал, которые могут помочь минимизировать обязательные, но просто воткнуть в ДНФ все, и обязательные, и необязательные, а потом эту кашу минимизировать нельзя. или я не правильно вас понял?

>с тем что нужно замечательно справляется метод карт Карно, но это больше графический метод и реализовывать его полностью на компе мне кажется плохой идеей. http://ru.wikipedia.org/wiki/Карта_Карно

не судьба была в английскую вики глянуть? так есть ссылка на метод Мак-Класки. собственно он и в русской есть, только ссылки на него в статье о карте Карно нет.

так, попытаюсь.
есть набор фал, назовём его A:

 (list "0101" "1111" "1000" "1011") 

A --> (list "0101" "1~11" "1000") 

 (list "0100" "1010" "1110") 

 (list "010~" "1~1~" "1000") 

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

;;генерим все варианты + разделяем их на отдельные списки,
;;соответствующие разному кол-ву переменных

(defun gen-l-variants (l)
  (let ((len (length l))
	(all-variants))
    (loop for el in l
       for i from 0 below (1- len)
       do (loop for j from (1+ i) below len 
	     do (let* ((el-2 (elt l j))
		       (joined (join-bb (car el) (car el-2))))
		  (when (and joined (not (equal (car el) (car el-2))))
		    (push (append (list joined) 
				  (del-nils (append (list (car el))
						    (list (car el-2))
						    (cdr el) (cdr el-2))))
			  all-variants)))))
    all-variants))

(defun del-nils (l) (loop for i in l when i collect i)) 

(defun gen-variants (l)
  (let ((razr '())
	(l-tmp l))
    (loop for i = (gen-l-variants l-tmp)
       when (equal i l-tmp) do (return)
       do (progn (push i razr)
		 (setf l-tmp i)))
    (append (list l) (del-nils razr))))


SINHR> (gen-variants '(("0101") ("1010") ("1111") ("0111") ("0110") ("1110")))
((("0101") ("1010") ("1111") ("0111") ("0110") ("1110"))
 (("~11~" "011~" "111~" "0111" "0110" "1111" "1110")
  ("~11~" "~110" "~111" "0110" "1110" "1111" "0111"))
 (("~110" "0110" "1110") ("011~" "0111" "0110") ("111~" "1111" "1110")
  ("~111" "1111" "0111") ("1~10" "1010" "1110") ("01~1" "0101" "0111")))

отобрать именно те, которые можно будет склеить

а если ещё и те, которые помогут склеить основные, вообще кавайно будет

>и список вспомогательных фал, пример

(011 101 000 001 ...)

Что за вспомогательный список?

Откуда он берется?

Maxima не поможет?

Метод Квайна-Мак-Класски.

$ apt-cache show qmc ... Description: Quine McClusky Simplification Tool This tool optimizes boolean expressions using the Quine McClusky process.

Кроме метода Куайна-МакКласки можно глянуть в исходники минимизатора Espresso, реализации которого, кстати, уже более 20ти лет.

это список неиспользуемых(простаивающих) состояний элементов памяти

спасибо, посмотрю

это некий аналог матлаба? всё равно прийдётся алгоритм писать.

Да, вы были правы, можно использовать его алгоритм. использовать все фал, но добавлять в простые импликанты только обязательные. Сейчас начал делать, результат напишу

собственно результат:

(defun mac-classki-alg (fal ~s)
  :documentation "input fal is list, that have '(xyz... t) as 1-state and '(xyz... nil) as ~-state"
  (let ((simply-implicants)
	(f-tmp (join-fal-and-~ fal ~s))
	(impls-tmp t))
    (loop for (f impls) = (multiple-value-list (mac-classki-iter f-tmp))
       ;;do (format t "~&f = ~a ; impls = ~a" f impls) 
       while f
       do (progn (setf impls-tmp impls)
		 (when impls (push impls simply-implicants))
		 (setf f-tmp f))
       finally (when impls (push impls simply-implicants)))
    ;;delete duplicates from finaly implicants
    (setf simply-implicants (loop for i in simply-implicants collect (delete-duplicates i :test #'equal)))))
     

(defun mac-classki-iter (f)
  (let* ((counted-table (count-ones f))
	 (len (length counted-table))
	 (fals)
	 (impls))
    (loop for i from 0 below (1- len)
       do (loop for j1 in (elt counted-table i)
	     for j1-simply? = t
	     ;; adding in fals
	     do (loop for j2 in (elt counted-table (1+ i))
		   do (let ((joined? (join-bb (car j1) (car j2))))
			;;(when joined? (format t "~&(~a ; ~a) --> ~a" j1 j2 joined?))
			(if joined? 
			    (progn (push (list joined? (or (second j1) (second j2)))
					 fals)
				   (setf j1-simply? nil))
			    (when (and (= i (1- len)) (second j2))   ; when j2 is last 
			      (push j2 impls)))))
	     ;; adding simply implicants
	     do (when (and j1-simply? (second j1)) 
		  (push j1 impls)))) 
    (values fals impls)))

(defun count-ones (fal)
  (flet ((how-much-1 (state) 
	   (loop for i across state 
	      count (equal i #\1))))
    (loop for pair in fal 
       with counted-table = (make-list (1+ (length (car (first fal)))))
       do (push pair
		(elt counted-table (how-much-1 (car pair))))
       finally (return (del-nils counted-table)))))
	      
(defun join-fal-and-~ (f ~s)
  (flet ((rewrite (states p)
	   (loop for st in states collect (list st p))))
    (append (rewrite f t) (rewrite ~s nil))))