Замечание: Обратим внимание, что одно определение получается из другого заменой друг другом слов «слагаемое» и «сомножитель».
Примеры
— СДНФ некоторой формулы двух переменных
- СКНФ функции трех переменных
Допустимыми для СДНФ (СКНФ) являются только некоторые полные конъюнкции (дизъюнкции): содержащие — без повторений — все переменные этой функции — с отрицаниями или без них.
Опишем два способа приведения к совершенным нормальным формам.
1-Й СПОСОБ — АНАЛИТИЧЕСКИЙ
Алгоритм приведение к СДНФ:
1.Приводят к ДНФ с помощью равносильных преобразований;
2. Умножают на единицы, представленные в виде дизъюнкций каждой недостающей переменной, с ее отрицанием;
3.Раскрывают скобки — по первому распределительному закону;
4.Исключают повторения слагаемых.
Пример:
Алгоритм приведение к СКНФ:
1. Формулу приводят к КНФ;
2. Прибавляют нули, представленные в виде конъюнкций каждой недостающей переменной с ее отрицанием;
3. С помощью второго распределительного закона приводят эти сомножители к суммам первой степени, т. е. не содержащим произведений;
4. Исключают повторения сомножителей.
Пример:
2-Й СПОСОБ — ТАБЛИЧНЫЙ
Составим таблицу истинности для функции :
x |
y |
z |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Алгоритм приведение к СДНФ:
1. Строим таблицу истинности;
2. Рассматриваем только те строки таблицы, в которых формула принимает значение 1;
3. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 — без отрицания;
4. Образуем дизъюнкцию всех полученных конъюнкций.
Пример: В нашей таблице первую строку опускаем: функция принимает значение 0. Второй строке соответствует конъюнкция третью строку опускаем и т. д.
СДНФ:
Приведение к СКНФ:
1.Строим таблицу истинности;
2.Рассматриваем только те строки таблицы, где функция принимает значение 0;
3.Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Аргумент, принимающий значение 0, берется без отрицания, значение 1 — с отрицанием;
4.Образуют конъюнкцию полученных дизъюнкций.
В нашем примере первой строке таблицы соответствует дизъюнкция
вторую строку опускаем и т. д.
СКНФ:
Замечания:
Если условиться из двух совершенных форм, СДНФ и СКНФ, отдавать предпочтение той, которая содержит меньше букв, то СДНФ предпочтительнее, если в столбце значений функции таблицы истинности меньше единиц; СКНФ — если в этом столбце меньше нулей.
В обычной, школьной алгебре мы знаем, что нет общего метода перехода от табличного задания функции к аналитическому. В алгебре высказываний, как видим, такой метод существует /5,7/.
Решение логических задач с помощью логики высказываний
Статьи по теме:
Рекомендации по работе с детьми-сиротами и детьми, оставшимися без попечения
родителей на уроках естественно-географического цикла
Исходя из изученного и представленного в данной работе теоретического материала и результатов диагностики, можно определить ряд рекомендаций для учителя по работе с детьми-сиротами и детьми, оставшимися без попечения родителей на уроках естественно-географического цикла. Повышение мотивации обучени ...
Методические приемы, используемые в обучении решению текстовых
задач
Методика обучения текстовых задач, которая ориентирована на формирование у учащихся обобщенных умений:читать задачу, выделять условия и вопрос, известные и неизвестные величины, установить взаимосвязь между ними и на этой основе выбирать те математические действия, выполнение которых позволяет отве ...
Особенности социально-экономического развития и политического положения
Восточной Сибири в конце XIX - начале ХХ вв
Проводимые Россией реформы 60-70-х гг. XIX в. начали оказывать все возрастающее влияние на социально- экономическое и культурное развитие Восточной Сибири. Отсутствие помещичьего землевладения способствовало росту капитализма в сельском хозяйстве Сибири, но остававшиеся в нем докапиталистические пе ...