Сокращенная конъюнктивная нормальная форма

Мы видели, что с помощью СКНФ можно получить обзор всех таких следствий из данных посылок, которые сами имеют СКНФ. Однако нас обычно интересуют лишь наиболее сильные^[3] следствия данных посылок. С этой точки зрения представляют интерес так называемые простые следствия. Следствие В из посылок A ₁, А ₂,..., A_n называют простым, если В есть такая не содержащая повторений и не тождественно-истинная элементарная дизъюнкция, которая не «поглощается» (в смысле «закона поглощения» — равносильности (19)) никаким другим более сильным следствием из посылок A ₁, А ₂,..., A_n такого же вида. Простые следствия из данных посылок можно найти, приводя их конъюнкцию к сокращенной КНФ.

Определение. Сокращенной КНФ данной формулы называется такая ее КНФ, которая удовлетворяет следующим условиям:

а) ни в одном конъюнктивном члене нет двух одинаковых дизъюнктов;

б) ни в одном конъюнктивном члене нет таких двух дизъюнктов, из которых один есть переменная, а другой отрицание этой переменной;

в) нет таких пар конъюнктивных членов, что каждый дизъюнкт из одного имеется в другом, т.е., во-первых, нет двух одинаковых конъюнктивных членов, а во-вторых, нет таких двух конъюнктивных членов, из которых один поглощается другим;

г) если имеются такие два конъюнктивных члена, из которых один содержит некоторую переменную, а другой — ее отрицание (при условии, что другой переменной, для которой это же имеет место, в данных конъюнктах нет), то в той же КНФ имеется конъюнктивный член, который является элементарной дизъюнкцией, построенной из всех дизъюнктов данной пары, отличных от упомянутой переменной и ее отрицания.

Для того чтобы привести формулу к сокращенной КНФ, нужно:

1) привести ее к КНФ;

2) из всех одинаковых конъюнктивных членов КНФ оставить только один и в элементарных дизъюнкциях также устранить все повторения;

3) устранить из КНФ все тождественно-истинные конъюнктивные члены;

4) если среди конъюнктивных членов КНФ имеются два таких, что один содержит некоторую переменную, а другой — ее отрицание, то на основании закона выявления, т. е. равносильности (21), добавить новый конъюнктивный член, представляющий собой дизъюнкцию остальных дизъюнктов этих двух конъюнктивных членов, но лишь при условии, что новый конъюнктивный член не тождественно-истинный и отличается от уже имеющихся. Например, если в КНФ имеются конъюнктивные члены (p Ú q Ú r) и (~ r Ú s), но нет конъюнктивного члена (p Ú q Ú s), то следует добавить его. Но если в КНФ имеются конъюнктивные члены (p Ú r Ú ~ s) и (~ р Ú q Ú s), то не следует добавлять конъюнктивного члена (r Ú ~ s Ú q Ú s), поскольку он тождественно-истинный, а таких согласно п. б) в сокращенной КНФ не должно быть.

В качестве законов выявления мы будем также использовать равносильности:

С Ù (В Ú ~ С) равносильно С Ù (В Ú ~ С) Ù В, (21а)

(А Ú С) Ù ~ С равносильно (А Ú С) Ù ~ С Ù А, (21б)

которые можно рассматривать как такие частные случаи равносильности (21), в которых отсутствуют либо формула А, либо формула В. Так, если в КНФ имеются конъюнктивные члены q и (p Ú ~ q), то припишем новый конъюнктивный член р, а если имеются конъюнктивные члены (p Ú q Ú r) и ~ r, то припишем новый конъюнктивный член (р Ú q).

5) если в новых (добавленных) конъюнктивных членах КНФ имеются повторения, то устранить их;

6) если конъюнкты КНФ с помощью равносильностей (2) и (4) можно перестроить так, что к ним будет применим закон поглощения, т. е. равносильность (19), то, применяя правило замены по этой равносильности, устраняем все поглощаемые конъюнктивные члены.

Приводя формулу к сокращенной КНФ, бывает удобно чередовать применение законов выявления и поглощения.

Формула, получившаяся в результате применения пп. 1 — 6, имеет сокращенную конъюнктивную нормальную форму и каждый ее конъюнкт есть простое следствие исходной формулы.

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

Рассмотрим следующие примеры.

1. Даны посылки p ® ~ q, ~ p ® r и ~(q Ù r). Найти все их простые следствия.

Приводим конъюнкцию посылок к КНФ:

(р ® ~ q) Ù (~ p ® r) Ù (~(q Ù r));

(~ р Ú ~ q) Ù (р Ú r) Ù (~ q Ú ~ r).

Производим все выявления:

(~ р Ú ~ q) Ù (р Ú r) Ù (~ q Ú ~ r) Ù (~ q Ú r) Ù (p Ú ~ q) Ù (~ q Ú ~ q).

Устраняем повторения в новых конъюнктах:

(~ р Ú ~ q) Ù (р Ú r) Ù (~ q Ú ~ r) Ù (~ q Ú r) Ù (p Ú ~ q) Ù ~ q.

Производим все поглощения:

(р Ú r) Ù ~ q.

Формулы (р Ú r) и ~ q являются простыми следствиями данных посылок, т. е. если посылки истинны, то формула (р Ú r) истинна, а формула q — ложна.

2. В совершении некоторого поступка подозревают только одного из четырех лиц: К, L, М и N; К утверждает, что поступок совершил L, L — что поступок совершил N, М — что он этого поступка не совершал, N тоже говорит, что он этого поступка не совершал. Кто же совершил поступок, если известно, что только одно из этих утверждений истинно?

Пусть высказыванию Поступок совершил К соответствует переменная р; высказыванию Поступок совершил L — переменная q; высказыванию Поступок совершил М — переменная r; высказыванию Поступок совершил N — переменная s. Тогда условие, что поступок мог совершить только один из четырех, можно записать в виде формулы, которая выражает, что никакие два из четырех высказываний не могут быть оба истинными;

~(p Ù q) Ù ~(p Ù r) Ù (р Ù s) Ù ~(q Ù r) Ù ~(q Ù s) Ù ~(r Ù s).

Утверждения каждого из четырех означают последовательно: q, s, ~ r и ~ s. Но так как истинно только одно из них, то никакие два из этих утверждений не являются одновременно истинными. Это условие можно записать следующим образом:

~(q Ù s) Ù ~(q Ù ~ r) Ù ~(q Ù ~ s) Ù ~(s Ù ~ r) Ù ~(s Ù ~ s) Ù ~(~ r Ù ~ s).

Конъюнкцию двух последних формул приводим к КНФ:

~(p Ù q) Ù ~(p Ù r) Ù (р Ù s) Ù ~(q Ù r) Ù ~(q Ù s) Ù ~(r Ù s) Ù ~(q Ù s) Ù ~(q Ù ~ r) Ù ~(q Ù ~ s) Ù ~(s Ù ~ r) Ù ~(s Ù ~ s) Ù ~(~ r Ù ~ s);

(~ р Ú ~ q) Ù (~ p Ú ~ r) Ù (~ p Ú ~ s) Ù (~ q Ú ~ r) Ù (~ q Ú ~ s) Ù (~ r Ú ~ s) Ù(~ q Ú ~ s) Ù (~ q Ú r) Ù (~ q Ú s) Ù (~ s Ú r) Ù (~ s Ú s) Ù (r Ú s).

Далее, устраняя повторения и вычеркивая тождественно-истинный конъюнктивный член, получаем формулу

(~ р Ú ~ q) Ù (~ p Ú ~ r) Ù (~ p Ú ~ s) Ù (~ q Ú ~ r) Ù (~ q Ú ~ s) Ù (~ r Ú ~ s) Ù(~ q Ú r) Ù (~ q Ú s) Ù (~ s Ú r) Ù(r Ú s).

Применяем закон выявления сначала к 5-му и 8-му конъюнктивным членам, затем к 6-му и 9-му, затем к 9-му и 10-му и, наконец, ко 2-му и вновь выявленному 13-му. После сокращения повторений в выявленных конъюнктивных членах получаем формулу:

(~ р Ú ~ q) Ù (~ p Ú ~ r) Ù (~ p Ú ~ s) Ù (~ q Ú ~ r) Ù (~ q Ú ~ s) Ù (~ r Ú ~ s) Ù(~ q Ú r) Ù (~ q Ú s) Ù (~ s Ú r) Ù(r Ú s) Ù ~ q Ù ~ s Ù r Ù ~ р.

Производим все поглощения и получаем сокращенную КНФ

~ q Ù ~ s Ù r Ù ~ р,

из которой видно, что р, q и s ложны, а r, т. е. высказывание Поступок совершил М — истинно.

3. Семья, состоящая из отца, матери, сына, а также старшей и младшей дочерей, купила телевизор. Условились, что в первый вечер будут смотреть передачи в таком порядке: 1) когда отец смотрит передачу, мать тоже смотрит передачу; 2) дочери, обе или одна из них, смотрят передачу; 3) из двух членов семьи — мать и сын —смотрит передачу один и только один; 4) сын смотрит передачу тогда и только тогда, когда ее смотрит старшая дочь, 5) если младшая дочь смотрит передачу, то отец и старшая дочь делают то же. Кто из членов семьи смотрел в этот вечер передачу?

Пусть высказыванию Отец смотрит высказыванию передачу соответствует переменная р; высказыванию Мать смотрит передачу — переменная q; высказыванию Сын смотрит передачу — переменная r; высказыванию Старшая дочь смотрит передачу — переменная s; высказыванию Младшая дочь смотрит передачу — переменная t. Тогда условия задачи выражают формулы:

1) р ® q;

2) s Ú t;

3) q «r,

4) r «s;

5) t ® (p Ù s).

Конъюнкцию этих формул приводим к КНФ:

(р ® q) Ù (s Ú t) Ù (q «r) Ù (r «s) Ù (t ® (p Ù s));

(~ p Ú q) Ù (s Ú t) Ù (q Ú r) Ù (~ q Ú ~ r) Ù (~ r Ú s) Ù

Ù (~ s Ú r) Ù (~ t Ú р) Ù (~ t Ú s).

Применяя закон выявления ко 2-му и последнему конъюнктам, получаем формулу

(~ p Ú q) Ù (s Ú t) Ù (q Ú r) Ù (~ q Ú ~ r) Ù (~ r Ú s) Ù

Ù (~ s Ú r) Ù (~ t Ú р) Ù (~ t Ú s) Ù s.

Затем производим поглощения — последний конъюнктивный член s поглощает 2-й, 5-й и 8-й конъюнктивные члены, а к 6-му и последнему конъюнктам вновь применяем закон выявления. Получаем формулу

(~ p Ú q) Ù (q Ú r) Ù (~ q Ú ~ r) Ù (~ s Ú r) Ù (~ t Ú р) Ù s Ù r.

Производим поглощения: последний конъюнкт поглощает 2-й и 4-й, а к 3-му и последнему конъюнктам применяем закон выявления. Получаем формулу

(~ p Ú q) Ù (~ q Ú ~ r) Ù (~ t Ú р) Ù s Ù r Ù ~ q.

Вновь производим поглощения: последний конъюнкт поглощает 2-й, а к последнему и 1-му конъюнктам применяем закон выявления. Получаем формулу

(~ p Ú q) Ù (~ t Ú р) Ù s Ù r Ù ~ q Ù ~ p.

Опять производим поглощения: последний конъюнкт поглощает 1-й, а к последнему и 2-му применяем закон выявления. Получаем формулу

(~ t Ú р) Ù s Ù r Ù ~ q Ù ~ p Ù ~ t.

Наконец, еще раз производим поглощения и получаем сокращенную КНФ конъюнкции посылок

s Ù r Ù ~ q Ù ~ p Ù ~ t.

Из последней формулы видно, что старшая дочь и сын смотрят передачу, а мать, отец и младшая дочь не смотрят.

Процедуру приведения к сокращенной КНФ можно использовать для упрощения формул.

Рассмотрим, например, следующую задачу: В ходе анализа химических свойств некоторого класса веществ экспериментатор обнаруживает последовательно следующие закономерности:

1) если вещество обладает свойством А и свойством В, то оно обладает также и свойством С;

2) если имеют место свойства В и D, то имеет место также или свойство А, или свойство С;

3) если вещество обладает свойством В, но не обладает свойством А, то оно обладает также или свойством С, или свойством D;

4) если свойство В имеет место, а свойство С отсутствует, то свойство А также отсутствует.

Требуется упростить эту информацию.

Пусть высказыванию Вещество обладает свойством А соответствует переменная р; высказыванию Вещество обладает свойством В — переменная q; высказыванию Вещество обладает свойством С — переменная r; высказыванию Вещество обладает свойством D — переменная s. Тогда обнаруженные закономерности можно записать следующими формулами:

1) (p Ù q) ® r; 2) (q Ù s) ® (p Ú r);

3) (q Ù ~ p) ® (r Ú s); 4) (q Ù ~ r) ® ~ p.

Приводим конъюнкцию этих формул к сокращенной КНФ.

((p Ù q) ® r) Ù ((q Ù s) ® (p Ú r)) Ù ((q Ù ~ p) ® (r Ú s)) Ù

Ù ((q Ù ~ r) ® ~ p);

(~(p Ù q) Ú r) Ù (~(q Ù s) Ú (р Ú r)) Ù (~(q Ù ~ p) Ú r Ú s) Ù

Ù (~(q Ù ~ r) Ú ~ p);

(~ p Ú ~ q Ú r) Ù (~ q Ú ~ s Ú р Ú r) Ù (~ q Ú p Ú r Ú s) Ù

Ù (~ q Ú r Ú ~ p);

(~ p Ú ~ q Ú r) Ù (~ q Ú ~ s Ú р Ú r) Ù (~ q Ú p Ú r Ú s);

(~ p Ú ~ q Ú r) Ù (~ q Ú ~ s Ú р Ú r) Ù (~ q Ú p Ú r Ú s) Ù

Ù (~ q Ú p Ú r) Ù (~ q Ú r);

~ q Ú r.

Таким образом, конъюнкция формул 1, 2, 3 и 4 равносильна формуле — ~ q Ú r, которая в свою очередь согласно равносильности (13) равносильна формуле q ® r. Следовательно, информация, заключенная в формулах 1 — 4 равносильна высказыванию Если вещество обладает свойством В, то оно обладает свойством С.

Упражнения

I. Найти все простые следствия из посылок:

1) p Ú q, q Ú r и ~р Ù r;

2) p ® q, p ® r и ~ q Ú ~ r.

II. Используя условия из примера 2 (с. 54), узнать, кто совершил поступок, если известно, что по крайней мере одно из этих утверждений ложно.

III. Методом приведения к сокращенной КНФ решить следующую задачу. Рабочий должен следить за деталями, движущимися мимо него по конвейеру, он должен снимать с ленты некоторые детали и пропускать остальные. Бригадир сказал ему, чтобы сегодня он снимал детали, которые удовлетворяют одновременно ряду условий, а именно:

а) обладают по крайней мере одной из следующих характеристик — искривлены, заржавлены или не окрашены;

б) или нестандартны, или заржавлены, или то и другое вместе;

в) или искривлены, или не заржавлены, или то и другое вместе;

г) или нестандартны, или не заржавлены, или то и другое вместе;

д) обладают хотя бы одной из следующих характеристик: искривлены, заржавлены или окрашены.

Предложенную в столь неудобной форме инструкцию рабочий упростил до двух характеристик объектов. Какие это характеристики?

IV. Один из А и В — рыцарь (всегда говорит правду), другой — лжец (всегда говорит ложь). А говорит: «По крайней мере, один из нас — лжец». Кто из них рыцарь, а кто — лжец?

V. Путник спросил у А: «Сколько рыцарей среди вас?» А ответил неразборчиво. Тогда путник обратился к В: «Что сказал А?». В ответил: «А сказал, что среди нас один рыцарь». Тогда С закричал: «Не верьте В! Он лжет!». Кто из В и С рыцарь и кто лжец?

VI. В одной из восточных стран был знаменитый оракул. Его устами вещало три божества: Бог Правды, Бог Лжи и Бог Дипломатии. Эти божества выглядели одинаково и одинаково охотно отвечали на вопросы. Но они были так похожи друг на друга, что никто не мог определить, отвечает всегда правдивый Бог Правды, Бог Лжи, говорящий только неправду, или Бог Дипломатии, который может либо солгать, либо сказать правду. Однажды нашелся смельчак, решивший опознать богов.

Он спросил Бога, стоявшего слева:

— Кто стоит рядом с тобой?

— Бог Правды, — ответил тот.

Тогда смельчак спросил Бога в центре:

— Кто ты?

— Бог Дипломатии, — был ответ.

— Кто стоит рядом с тобой? — спросил смельчак Бога справа.

— Бог Лжи, — ответило божество.

— Теперь все понятно, — сказал смельчак. Что же он понял из ответов богов?

Не нашли, что искали? Воспользуйтесь поиском: