Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Дизъюнктивные нормальные формы




 

Формулы логики высказываний наряду с КНФ могут иметь дизъюнктивную нормальную форму (ДНФ).

Условимся называть элементарной конъюнкцией формулу, которая имеет вид

A 1 Ù А 2 Ù...Ù An,

где n ³ 1, a Ai, (i £ n) либо переменная, либо отрицание переменной. Например, формула

р Ù q Ù ~ r Ù p Ù~ q Ù r

является элементарной конъюнкцией, формула же

(p Ú q) Ù r Ù р

элементарной конъюнкцией не является, так как ее 1-й конъюнктивный член не есть ни переменная, ни отрицание переменной.

Теорема. Элементарная конъюнкция тождественно-ложна тогда и только тогда, когда в нее входит хотя бы одна пара конъюнктивных членов, из которых один есть некоторая переменная, а другой — ее отрицание.

Доказательство. В самом деле, элементарная конъюнкция, содержащая такую пару, либо имеет вид

Е Ù ~ Е Ù К,

где Е — переменная, а подформула К — элементарная конъюнкция (которой может и не быть), либо ей можно придать этот вид в результате применения правила замены по равносильности (2). Так как подформула Е Ù ~ Е тождественно-ложна, то согласно (48') и вся элементарная конъюнкция

Е Ù ~ Е Ù К

тождественно-ложная формула, независимо от того, истинна или ложна подформула К.

Наличие переменной и ее отрицания не только достаточное, но и необходимое условие тождественной ложности элементарной конъюнкции. Действительно, допустим, что в элементарной конъюнкции такой пары нет. Придадим каждой переменной, не стоящей под знаком отрицания, логическое значение «истина», а каждой переменной, стоящей под знаком отрицания, — значение «ложь». Тогда каждый из конъюнктивных членов получает значение «истина», а значит, вся элементарная конъюнкция имеет значение «истина» и не является тождественно-ложной формулой.

Определение. Формула логики высказываний имеет дизъюнктивную нормальную форму, если она имеет вид

В 1 Ú В 2Ú...Ú Вm,

где В 1, В 2,..., Вm —элементарные конъюнкции и m ³ 1. Например, формула

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

имеет дизъюнктивную нормальную форму.

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

Для того чтобы привести формулу к ДНФ, необходимо вначале привести ее к нормальной форме. Затем каждую подформулу вида (А Ù (В Ú С)) согласно равносильности (7) и каждую подформулу вида ((B Ú C) Ù A) согласно равносильности (7') заменить формулой ((А Ù В) Ú (А Ù C)).

Рассмотрим процесс приведения формулы к ДНФ на следующем примере. Пусть дана формула

(р ® ~ q) «(~ r Ù s).

Приводим ее к ДНФ:

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

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

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

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

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

Например, пусть дана формула

~((p ® q) ® ((p Ú r) ® (q Ú r))).

Приводим ее к ДНФ:

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

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

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

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

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

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

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

Каждая не тождественно-ложная формула имеет ДНФ, которая называется совершенной.

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

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

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

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

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

Для того чтобы привести формулу к СНДФ, необходимо:

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

2) на основании равносильностей (2), (4) и (9) устранить из ДНФ повторяющиеся дизъюнкты, т. е. из всех имеющихся одинаковых дизъюнктов оставить один и вычеркнуть остальные;

3) на основании равносильностей (2) и (8) устранить все повторения в дизъюнктивных членах ДНФ, т. е. из всех имеющихся одинаковых конъюнктов оставить один и вычеркнуть остальные;

4) на основании равносильностей (2), (4) и (50) устранить из формулы те дизъюнктивные члены, которые являются тождественно-ложными элементарными конъюнкциями;

5) ко всем тем дизъюнктивным членам, в которых отсутствует какая-нибудь из содержащихся в данной формуле переменных Е, на основании равносильности (47) приписать знак конъюнкции, вслед за ним—тождественно-истинную дизъюнкцию (Е Ù ~ Е) и применить правило замены по равносильности (7). Эту процедуру повторять до тех пор, пока не окажется, что в каждый дизъюнктивный член входят все переменные, содержащиеся в данной формуле;

6) если в получившейся ДНФ снова появились одинаковые дизъюнктивные члены, то надо устранить повторения.

Пусть, например, требуется привести к СДНФ формулу

(р ® q) Ù (~ q ® р).

Вначале приведем ее к ДНФ:

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

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

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

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

Пополняем 2-й дизъюнкт недостающей переменной p:

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

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

Устраняем возникшие повторения и получаем СДНФ данной формулы:

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

В конце § 7 главы I рассматривались формулы, однозначно определяющие таблицы логических функций. Легко убедиться в том, что каждая такая формула имеет СДНФ.

Гипотезой формулы В называют такую формулу А, что формула А ® В тождественно-истинна. Если А — гипотеза формулы В, то А Ù С — тоже гипотеза формулы В; если А и С — гипотезы формулы В, то A Ú С —тоже гипотеза В. Дизъюнктивные члены СДНФ данной формулы есть различные гипотезы, при истинности которых данная формула истинна.

С помощью СДНФ можно получить обзор всех гипотез данной формулы, которые имеют СДНФ. Но нас обычно интересуют лишь самые слабые гипотезы. С этой точки зрения представляют интерес так называемые простые гипотезы. Гипотеза А формулы В называется простой, если А есть элементарная конъюнкция, которая не тождественно-ложна, не содержит повторений и не поглощается никакой другой, более слабой, гипотезой формулы В такого же вида. Простые гипотезы данной формулы можно найти, приводя ее к сокращенной ДНФ.

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

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

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

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

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

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

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

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

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

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

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

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

которые можно рассматривать как такие частные случаи равносильности (22), в которых отсутствуют либо формула А, либо формула В;

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

6) если среди дизъюнктивных членов ДНФ имеются такие, которые поглощаются другими, то, применяя правило замены по равносильности (20), устранить все поглощаемые дизъюнктивные члены.

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

Рассмотрим следующий пример. Пусть дана формула

((p Ù q) Ú r) ® r.

Приводим ее к сокращенной ДНФ:

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

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

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

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

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

r Ú ~ p Ú ~ q.

Таким образом, данная формула логически следует из гипотезы r, или гипотезы ~ p, или гипотезы ~ q.

Упражнения:

I. Привести к ДНФ формулу

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

2) (p «~ q) ® ~((p «r) ® ~(q «r));

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

4) (p «r) ® (~(q «~ r) ® p));

5) (p Ù q) «(~ q ® (p Ú r));

6) (p Ú r) ® ~(q ® (q Ù r)).

II. Привести к СДНФ формулу

1) ((p ® q) «(r «s)) ®(~ p Ù s);

2) (p «q) ® ((p «r) ® (q «r));

3) ((p Ú ~ qr) ® (p Ù r);

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

5) (p ® q) ® (~ q ® (p Ú r));

6) (p ® r) ® ~(q ® (q ® r)).

III. Найти все простые гипотезы формул

1) (р «q) Ú (p Ù q);

2) ((p ® q) ® r) ® (r Ú q).

IV. Алхимик, посаженный в тюрьму за ересь, последовательно получил шесть секретных сообщений, которые были закодированы с помощью овощей, вложенных в суп; они касались его намерения превратить свинец в золото.

Первое сообщение: «Ваше намерение превратить свинец в золото будет осуществлено; королева утвердит вашего зятя настоятелем к 1 апреля 1457 г.; ваше обвинительное заключение будет передано настоятелю к этому времени».

Второе сообщение: «Ваше намерение превратить свинец в золото не будет осуществлено; королева не утвердит вашего зятя настоятелем к 1 апреля 1457 г.; обвинительное заключение не будет передано настоятелю».

Третье сообщение: «Ваше намерение превратить свинец в золото будет осуществлено; королева утвердит вашего зятя настоятелем к 1 апреля 1457 г.; обвинительное заключение не будет передано настоятелю».

Четвертое сообщение: «То что следует далее, неверно. Или ваше намерение превратить свинец в золото будет осуществлено, или королева утвердит вашего зятя настоятелем к 1 апреля 1457 г.; или обвинительное заключение не будет передано».

Пятое сообщение: «По крайней мере, одно из предыдущих сообщений истинно».

Шестое сообщение: «Полученная вами информация абсолютно надежна».

Как мог бы алхимик методом приведения к сокращенной ДНФ наилучшим образом упростить всю полученную им информацию? Выразить ответ формулой, содержащей знак эквивалентности (см.: Калбертсон Дж. Т. Математика и логика цифровых устройств. М., 1965. С. 215—216).

V. Крутой Докер, Шито-Крыто и Золотая Ручка работают в банке в качестве кассира, юриста и охранника.

Если Золотая Ручка — юрист, Шито-Крыто — охранник.

Если Золотая Ручка — охранник, то Шито-Крыто — кассир.

Если Шито-Крыто — не юрист, то Крутой Докер — не охранник.

Если Крутой Докер — кассир, то Золотая Ручка — охранник.

Кто кем работает?

VI. Незадачливый брокер в самый разгар торгов прислал своему партнеру сообщение: «Если нам удастся продать акции по указанной шефом цене, то мы хорошо заработаем. Но если нам не удастся этого сделать, то либо придется сбавить цену, либо вовсе отказаться от продажи. Однако если мы откажемся от продажи, то нам грозит разорение или шеф нас уволит. С другой стороны, если нам грозит разорение или увольнение с работы, то мы должны продать акции по указанной шефом цене».

Упростить сообщение при помощи сокращенной ДНФ.

 


[1] Равносильности (1) – (50¢) см. в главе I данного учебника.

[2] См.: Гильберт Д., Аккерман В. Основы теоретической логики. М., 1947. С. 47.

[3] Говорят, что формула А сильнее формулы В, а формула В слабее формулы А, если тождественно-истинна формула А ® В, но не формула В ® А.






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

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных