Автор: Гость 4.04.2007 20:27
как преобразовать AB+AC+^A^B в совершенную конъюнктивную нормальную форму??
и как потом установить выполнимость формулы??
^A^B это не А*не В
спасибо
Автор: КМА 8.04.2007 3:30
Один из метод, это построение таблиц истиности:
A B C Значение формулы
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Теперь если это СКНФ, то нас интересуют только 0. Соответственно, если они есть, значит формула приводима к СКНФ, если же нет, значит не приводима. Далее, чтобы ее составить, необходимо, посмотреть на строчку где встречается ноль. Если значение у данной переменной ноль, значит просто пишем ее, если же один, то пишем ее отрицание. Т. е. смотрите:
A B C
0 1 0 0
Встретили ноль, значит, записываем элементарный дизъюнкт A+^B+С, тут ^B потому что у B еденичка, соответственно у А и С нолики, поэтому их не отрицаем.
Смотрим следующую строчку:
A B C
0 1 1 0
Опять смотрим и опять записываем элементраный дизъюнкт: А+^B+^C.
Последнее попробуй проделайте сами.
Теперь, когда записаны все элементарные дизъюнкты, то нужно построить их конъюнкцию, в итоге получим:
(A+^B+С)(А+^B+^C)(^A+B+C) - СКНФ.
Есть и еще один способ через эквивалентные преобразования, если хотите могу рассказать, но таблицами истиности намного проще все далается.
Автор: -Екатерина- 8.04.2007 18:52
очень хочу чтобы рассказали!!!
заранее спасибо
Автор: КМА 9.04.2007 3:08
Цитата
очень хочу чтобы рассказали!!!
Раз очень хотите, то расскажу. Только * это у меня отрицание.
Итак, я дам универсальный алгоритм, как это делается.
1. С помощью равносильностей (А => В) = ( *А + В) и (А <=>В) =((*А) + В)(А + *В) формулу приводят к равносильной формуле, не содержащей импликации и эквивалентности.
2. С помощью равносильностей **A=A, *(А + В) = (*А)(*В), *(АВ) = (*А)+(*В) формулу приводят к виду, в котором отрицание может присутствовать только непосредственно перед пропозициональной переменной.
3. Используя равносильность А+(ВС) = (А+С)(А+С), приводят формулу к КНФ.
4. С помощью равносильностей А + А = А, АА = А, А+0=А, А0=0, А1=1, А+1=1 удаляют повторные вхождения переменных, повторные вхождения одинаковых элементарных дизъюнктов и вхождения тождественно ложных элементарных дизъюнктов.
Если в результате получим пустое знакосочетание, то исходная формула тождественно истинная; ее преобразовать в СКНФ нельзя. Действие алгоритма в этом случае завершено.
5. По правилу расщепления (A = (A + B)(A + *B)) в каждый элементарный дизъюнкт, который содержит не все переменные, добавляют недостающие. В результате каждый дизъюнкт будет совершенным.
6. С помощью равносильности АА = А удаляют повторные вхождения одинаковых элементарных дизъюнктов. В результате приходим к СДНФ формулы.
В твоем случае это будет выглядеть так:
AB+AC+*A*B.
1. Можно опустить, т. к. от импликаций мы избавились.
2. Так же можно опустить, т. к. отрицание находиться непосредственно перед пропозициональной переменной.
3. [AB]+(AC)+*A*B=( (AB) +[A] )( (AB) + [C] )+*A*B=[(A+A)(A+B)(A+C)(B+C)]+(*A*B)={(A+A)[(A+B)(A+C)(B+C)]+*A }{ (A+A)[(A+B)(A+C)(B+C)]+*B };
Это не все, сейчас я рассмотрю первую скобку, а затем вторую, просто, чтобы было удобнее воспринять. Тут стоить отметить, что [] я просто выделял отдельную формулу (т. е. читаем ее как одну букву). А в {} чисто для удобства чтения, несут смысл обыкновенных скобок. Итак первая скобка (то что в {}).
(A+A)[(A+B)(A+C)(B+C)]+*A=(A+A+*A) ((A+B)[(A+C)(B+C)]+*A)= {A+A+*A}{A+B+*A}{(A+C)[(B+C)]+*A}=
(A+A+*A)(A+B+*A)(A+C+*A)(B+C+*A)
Можно заметить, что для второй скобки разложение будет аналогичным, только вместо *А будет стояить *В, т. е. вторая скобка преобразуется к виду: (A+A+*В)(A+B+*В)(A+C+*В)(B+C+*В).
Теперь мы видим, что у нас есть КНФ.
4. (A+A+*A)(A+B+*A)(A+C+*A)(B+C+*A)(A+A+*В)(A+B+*В)(A+C+*В)(B+C+*В)=(A+*A)(1+B)
(1+C)(*A+B+C)(A+*B)(A+1)(A+*B+C)(C+1)=111(*A+B+C)(A+*B)1(A+*B+C)1=(*A+B+C)(A+*B)
(A+*B+C)
Видим что получилось не пустое знакосочетание, значит продолжаем. Расчепляем.
5. (*A+B+C)[(A+*B)](A+*B+C)=(*A+B+C)(A+*B+С)(A+*B+*С)(A+*B+C)
6. Удаляем повторяющиеся: (*A+B+C)(A+*B+С)(A+*B+*С)(A+*B+C)=(*A+B+C)(A+*B+*С)(A+*B+C)
Как видим получили то же самое. Но путь более длителен. Правда, бывают случае, когда он и короче. Если что непонятно, то могу все уточнить.
Автор: Lapp 9.02.2010 7:36
Тема разделена, ответвление тут: http://forum.pascal.net.ru/index.php?showtopic=25415