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

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

Примеры

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

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

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

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

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

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

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

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

Компоненты творческих способностей
Творческие способности представляют собой сплав многих качеств. И вопрос о компонентах творческого потенциала человека остается до сих пор открытым, хотя в настоящий момент существует несколько гипотез, касаю­щихся этой проблемы. Многие психологи связывают способности к творческой деятельно­сти, пр ...

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