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

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

Примеры

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

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

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

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

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/.

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

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

Особенности изменений и нововведений
Анализ всех сторон функционирования организации, в частности, анализ руководства, принятия решений и коммуникаций показывают, что организации не являются чем-то застывшим, а имеют динамический характер, вызванный определенными организационными изменениями. Изменения в организациях могут происходить ...

Организация учебного процесса
В 70 – первой половине 90-х гг. XIX в. наиболее распространенный методом обучения был так называемый «догматический метод», когда обучение в основном сводилось к простому «спрашиванию - заданию». Учитель как правело, начинает урок с проверки домашнего задания. К моменту объяснения нового материала ...

Специфика изучения ИЯ на старшей ступени
Специфики иностранного языка как учебного предмета на старшей ступени обучения в средней общеобразовательной школе включает следующие положения: - роль ИЯ как учебного предмета в современной образовательной системе; - специфика обучения ИЯ на старшей ступени средней общеобразовательной школы, основ ...