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

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

Примеры

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

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

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

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

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

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

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

Решение вопроса воспитания толерантности в современных концепциях воспитания ребенка
Последнее десятилетие привнесло радикальные изменения в систему отечественного дошкольного образования. На смену типовой программе пришли вариативные, на смену унифицированному «детскому саду» – разные типы и виды дошкольных образовательных учреждений. Последние 10 лет ДОУ официально работали по 12 ...

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

Методика работы с детьми по зрительному восприятию
Дети с нарушениями зрения ограничены в непосредственном зрительном восприятии окружающего мира, они плохо видят отдаленные объекты: дома, движущиеся предметы, птиц на деревьях, самолет в небе и т.д. поэтому, чтобы обеспечить детям обстановку, благоприятствующую процессу обучения, необходимо: создат ...