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