Формы записи высказываний. Алгоритмические способы решения логических задач

Замечание: Обратим внимание, что одно определение получается из другого заменой друг другом слов «слагаемое» и «сомножитель».

Примеры

— СДНФ некоторой формулы двух переменных

- СКНФ функции трех переменных

Допустимыми для СДНФ (СКНФ) являются только некоторые полные конъюнкции (дизъюнкции): содержащие — без повторений — все переменные этой функции — с отрицаниями или без них.

Опишем два способа приведения к совершенным нормальным формам.

1-Й СПОСОБ — АНАЛИТИЧЕСКИЙ

Алгоритм приведение к СДНФ:

1.Приводят к ДНФ с помощью равносильных преобразований;

2. Умножают на единицы, представленные в виде дизъюнкций каждой недостающей переменной, с ее отрицанием;

3.Раскрывают скобки — по первому распределительному закону;

4.Исключают повторения слагаемых.

Пример:

Алгоритм приведение к СКНФ:

1. Формулу приводят к КНФ;

2. Прибавляют нули, представленные в виде конъюнкций каждой недостающей переменной с ее отрицанием;

3. С помощью второго распределительного закона приводят эти сомножители к суммам первой степени, т. е. не содержащим произведений;

4. Исключают повторения сомножителей.

Пример:

2-Й СПОСОБ — ТАБЛИЧНЫЙ

Составим таблицу истинности для функции :

Алгоритм приведение к СДНФ:

1. Строим таблицу истинности;

2. Рассматриваем только те строки таблицы, в которых формула принимает значение 1;

3. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 — без отрицания;

4. Образуем дизъюнкцию всех полученных конъюнкций.

Пример: В нашей таблице первую строку опускаем: функция принимает значение 0. Второй строке соответствует конъюнкция третью строку опускаем и т. д.

СДНФ:

Приведение к СКНФ:

1.Строим таблицу истинности;

2.Рассматриваем только те строки таблицы, где функция принимает значение 0;

3.Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Аргумент, принимающий значение 0, берется без отрицания, значение 1 — с отрицанием;

4.Образуют конъюнкцию полученных дизъюнкций.

В нашем примере первой строке таблицы соответствует дизъюнкция

вторую строку опускаем и т. д.

СКНФ:

Замечания:

Если условиться из двух совершенных форм, СДНФ и СКНФ, отдавать предпочтение той, которая содержит меньше букв, то СДНФ предпочтительнее, если в столбце значений функции таблицы истинности меньше единиц; СКНФ — если в этом столбце меньше нулей.

В обычной, школьной алгебре мы знаем, что нет общего метода перехода от табличного задания функции к аналитическому. В алгебре высказываний, как видим, такой метод существует /5,7/.

Решение логических задач с помощью логики высказываний

Статьи по теме:

Принципы отбора содержания системы самостоятельных работ тематического контроля знаний учащихся
Предлагаемая система самостоятельных работ предназначена для осуществления контроля за знаниями учащихся 8 классов. Ее содержание ориентировано на учебник Ю.Н. Макарычева, Н.Г. Миндюк, К.И. Нешкова, С. Б Суваровой; под редакцией С.А. Теляковского "Алгебра. Учебник для 8 класса средней школы&qu ...

Развитие культуры и образования в период феодальной раздробленности и культурной изоляции
В XIV—XV вв. в среде посадского населения Новгорода, Пскова, а затем и Москвы появляются еретические движения, получившие название движения стригольников и жи-довствующих. Основателем первого являлся дьякон Карп, бывший, по-видимому, одновременно цирюльником. О взглядах стригольников можно судить п ...

Методические рекомендации для коррекционно – педагогической работы по формированию сенсорных эталонов
сенсорный эталон дошкольник интеллектуальный В методике сенсорного воспитания дошкольников можно выделить несколько этапов. Целью первого этапа является привлечение внимания детей к тому сенсорному признаку, который должен быть освоен. Для этого воспитатель предлагает детям что-нибудь нарисовать, с ...