Замечание: Обратим внимание, что одно определение получается из другого заменой друг другом слов «слагаемое» и «сомножитель».
Примеры
— СДНФ некоторой формулы двух переменных
- СКНФ функции трех переменных
Допустимыми для СДНФ (СКНФ) являются только некоторые полные конъюнкции (дизъюнкции): содержащие — без повторений — все переменные этой функции — с отрицаниями или без них.
Опишем два способа приведения к совершенным нормальным формам.
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/.
Решение логических задач с помощью логики высказываний
Статьи по теме:
Разработка тембрального диапазона
Сначала используются так называемые “кричалки". Работа с ними требует соблюдения основных правил гигиены голоса. Нельзя, не подготовив голос дыхательными и артикуляционными упражнениями, сразу включать максимальную громкость. Это приведет к срыву голоса. Во время произнесения “кричалки" в ...
Организация и методы диагностики нарушений письма у учащихся начальных
классов общеобразовательной школы
На современном этапе развития логопедии как науки все большее значение приобретают нейропсихологические методы диагностики речевых нарушений школьников. Комплексное нейропсихологическое обследование, охватывающее как речевые, так и неречевые возможности ребенка, позволяет провести качественную функ ...
Требования к учителю географии органов
народного образования
Из года в год российское образование совершенствуется. Становится оно лучшим или худшим, покажет только время, но за новинками в школьном образовании, как по цепочке, меняется и многое другое. Растут требования к детям, а следовательно к учителям, следовательно меняется и подготовка будущих педагог ...