Замечание: Обратим внимание, что одно определение получается из другого заменой друг другом слов «слагаемое» и «сомножитель».
Примеры
— СДНФ некоторой формулы двух переменных
- СКНФ функции трех переменных
Допустимыми для СДНФ (СКНФ) являются только некоторые полные конъюнкции (дизъюнкции): содержащие — без повторений — все переменные этой функции — с отрицаниями или без них.
Опишем два способа приведения к совершенным нормальным формам.
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/.
Решение логических задач с помощью логики высказываний
Статьи по теме:
Решение вопроса воспитания толерантности в современных концепциях
воспитания ребенка
Последнее десятилетие привнесло радикальные изменения в систему отечественного дошкольного образования. На смену типовой программе пришли вариативные, на смену унифицированному «детскому саду» – разные типы и виды дошкольных образовательных учреждений. Последние 10 лет ДОУ официально работали по 12 ...
Сравнительный анализ педагогических подходов по работе с беспризорными детьми
на основании исследований А.В. Гоголевой «Беспризорность»
песталоцци беспризорность педагогический Макаренко Антон Семёнович (1.03.1888 – 1.04.1939) родился в городе Бесполье, ныне в Сумской области Украины. Педагог и русский писатель. По окончании Кременчугского городского училища и пед. курсов при нём учительствовал в посёлке Крюков и на станции Долинск ...
Теоретическое изучение коррекции речи детей
старшего дошкольного возраста с нарушениями слуха
Речь является основным средством человеческого общения. Без нее люди не имели бы возможности получать и передавать большое количество информации. По мнению А.Н.Леонтьева, речь человека, человеческое слово и история его развития выступают «во – первых, как предмет лингвистики…во – вторых, как предме ...