выполнимость формул Опции

[Гость]

как преобразовать AB+AC+^A^B в совершенную конъюнктивную нормальную форму??
и как потом установить выполнимость формулы??
^A^B это не А*не В

спасибо

[КМА]

Один из метод, это построение таблиц истиности:

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) - СКНФ.

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

[-Екатерина-]

очень хочу чтобы рассказали!!!
заранее спасибо

[КМА]

очень хочу чтобы рассказали!!!

Раз очень хотите, то расскажу. Только * это у меня отрицание.

Итак, я дам универсальный алгоритм, как это делается.

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]

Тема разделена, ответвление тут: Как переводить из десятичной системы в восьмеричную?