Файл: Алгебра высказываний.doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 17.03.2019

Просмотров: 2128

Скачиваний: 5

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Решение. Для этого по определению следует заменить операции на двойственные. Тогда получим, что двойственной будет формула


Элементарными логическими выражениями (элементарными формулами, высказываниями) называются логические переменные и их отрицания. Например, A, B, – элементарные формулы, а формула не является элементарной, т.к. отрицается формула .

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

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

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

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


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

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

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

Чтобы из ДНФ получить КНФ нужно воспользоваться II дистрибутивным законом:

Полученное выражение уже является КНФ, однако его также можно упростить: в первом, пятом, шестом и восьмом множителях в качестве слагаемых представлены повторяющиеся элементы, третий и четвертый множители тождественно равны 1.

Полученная формула также является КНФ.


Критерий тождественной истинности формулы

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

Критерий тождественной ложности формулы

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


Пример 8. Проверить будет ли формула тождественно истинной.

Решение. Для решения этой задачи можно построить таблицу истинности и уже по значениям, которые принимает формула сделать вывод, а можно привести эту формулу к КНФ и проверить выполнение критерия.

Найдем КНФ формулы:

И в первом, и во втором множителе есть слагаемые, из которых одно есть переменная, а другое – ее отрицание, следовательно, по критерию тожественной истинности формулы, формула тождественно истинна.


Совершенной ДНФ (СДНФ) формулы , содержащей n различных переменных, называется ДНФ, обладающая следующими свойствами:

  1. в ней нет двух одинаковых слагаемых;

  2. ни одно слагаемое не содержит двух одинаковых множителей;

  3. никакое слагаемое не содержит переменной вместе с ее отрицанием;

  4. в каждом слагаемом содержится в качестве множителей либо переменная , либо ее отрицание, где .

Совершенной КНФ (СКНФ) формулы , содержащей n различных переменных, называется КНФ, обладающая следующими свойствами:

  1. в ней нет двух одинаковых множителей;

  2. ни один множитель не содержит двух одинаковых слагаемых;

  3. ни один множитель не содержит переменной вместе с ее отрицанием;

  4. каждый множитель содержит в качестве слагаемого либо переменную , либо ее отрицание, где .

Замечание: У тождественно истинных формул существует только СДНФ, а у тождественно ложных – только СКНФ.

Найти СКНФ и СДНФ формул можно при помощи равносильных преобразований и таблицы истинности.


Пример 9.

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

        2. Найти СКНФ и СДНФ этой же формулы по таблицы истинности.

Решение

1. Для получения совершенных форм удобнее брать соответствующие нормальные формы, т.е. для получения СДНФ брать ДНФ, для СКНФ – КНФ.

Для получения СДНФ в качестве начальной возьмем следующую ДНФ: В этой формуле в каждом слагаемом не хватает множителей: в первом – С (или ), во втором – В (или ), в третьем – А (или ). Чтобы после преобразований значения слагаемых не изменились, в качестве множителей в них можно добавить только тождественно истинные формулы. Например, используя равносильность (3):

Применение I дистрибутивного закона даст:

.

После группировки и использования закона идемпотентности получим:

.

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

Рассмотрим алгоритм получения СКНФ. Для этого возьмем КНФ формулы α: . Здесь в множителях в качестве слагаемых не хватает: в первом – С (или ), во втором – А (или ), в третьем – В (или ). Чтобы в результате преобразований значение формулы не изменилось, мы можем в качестве слагаемого в каждый множитель добавить соответствующие выражение вида: (по закону непротиворечия оно тождественно равно 0). Т.е.

.

Произведя необходимые преобразования по II дистрибутивному закону,
получим:

В этой форме имеются одинаковые множители: 1-й и 3-й, 4-й и 5-й. Применив закон идемпотентности, окончательно получим СКНФ:

.

2. Построим таблицу истинности формулы .

Номер
комбинации

А

В

С

1

1

1

1

1

1

1

2

1

1

0

1

0

0

3

1

0

1

1

1

1

4

1

0

0

1

0

0

5

0

1

1

1

1

1

6

0

1

0

1

1

1

7

0

0

1

0

1

0

8

0

0

0

0

1

0


Чтобы получить СДНФ, рассмотрим комбинации значений переменных, которые дают истинное значение формулы

Номер
комбинации

А

В

С

1

1

1

1

1

3

1

0

1

1

5

0

1

1

1

6

0

1

0

1


Для каждой положительной комбинации выпишем конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию следует включить саму эту переменную, если равно 0, то ее отрицание. Таким образом: построчно получим следующие конъюнкции: 1 строка – ; 3 строка – ; 5 строка – ; 6 строка – .

Затем необходимо все конъюнкции связать в дизъюнкцию. Полученная таким образом формула и будет СДНФ:

.

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

Номер
комбинации

А

В

С

2

1

1

0

0

4

1

0

0

0

7

0

0

1

0

8

0

0

0

0


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

.


Используя аппарат алгебры высказываний можно решать текстовые логические задачи. Причем некоторые задачи для их решения необходимо привести к виду КНФ или СДНФ.


Пример 10

Алеша, Боря и Гриша нашли в земле сосуд. Рассматривая удивительную находку, каждый высказал по два предложения:

Алеша. Это сосуд греческий и изготовлен в V веке.

Боря. Это сосуд финикийский и изготовлен в III веке.

Гриша. Это сосуд не греческий и изготовлен в IV.

Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предложений.

Где и в каком веке изготовлен сосуд?

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

Запишем условие задачи (формализуем ее), используя символы алгебры логики. Для этого примем следующие обозначения:

G = Это сосуд греческий;

F = Это сосуд финикийский;

V3 = Сосуд изготовлен в III в.;

V4 = Сосуд изготовлен в IV в.;

V5 = Сосуд изготовлен в V в.

Тогда со слов учителя следует, что Алешка прав только в чем-то одном: или G=1, или V5=1. Таким образом, тождественно истинным будет высказывание

Аналогично, из слов Бори и учителя следует:

а из слов Гриши и учителя:

Кроме того, ясно, что сосуд может быть изготовлен только в одном из веков и только в одной из сторон. Эти условия можно записать так:

.

Итак, мы получили пять тождественно истинных высказываний. Их нужно логически перемножить. Результат должен быть также тождественно истинным высказыванием:

=|учитывая, что |=

То есть

Таким образом, сосуд финикийский и изготовлен в V веке.


Пример 11

В одном королевстве были незамужние принцессы, голодные тигры и приговоренный к казни узник. Но король всякому узнику, осужденному на смерть, давал последний шанс спастись. Ему предлагалось угадать, в какой из двух комнат находится тигр, а в какой принцесса. Хотя вполне могло быть, что король в обеих комнатах разместил принцесс или, что хуже, в обеих тигров. Выбор надо было сделать на основании табличек на дверях комнат. Причем, узнику было известно, что утверждения на табличках либо оба истинны, либо оба ложны. Надписи гласили:


По крайней мере
в одной из этих комнат находится принцесса


Тигр
в другой комнате


Какую дверь должен выбрать узник?

Решение

Введем обозначения.

П1 = В первой комнате находится принцесса.

= В первой комнате находиться тигр.

П2 = Во второй комнате находится принцесса.

= Во второй комнате находится тигр.

А – утверждение на первой двери: .

В – утверждение на второй двери: .

Условия задачи о том, что утверждения на табличках либо одновременно истинные, либо одновременно ложные, записываются так:

.

Следовательно, имеем

То есть , первой комнате находится тигр, во второй принцесса.


Пример 12

Известно, что если Андрей и Володя пойдут в кино, то Сережа в кино не пойдет. Известно также, что если Володя не пойдет в кино, то в кино пойдут Андрей и Сережа. Надо узнать, кто при этих условиях может пойти в кино.

Решение

Введем обозначения:

А = «Андрей пойдет в кино»

В = «Володя пойдет в кино»

С = «Сережа пойдет в кино»

Запишем условие задачи в символьной форме и сразу упростим, полученные выражения:

;

.

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

.

Условия задачи свелись к формуле , которая должна быть истинной. Но дизъюнкция истинна, если истинным будет хотя бы один из ее членов. Значит, для того, чтобы условия задачи были выполнены, достаточно, чтобы имел место один из трех случаев:

1. , т.е. в кино может пойти Володя без Андрея.

2. , т.е. в кино может пойти Володя без Сергея.

3. , т.е. в кино могут пойти Андрей с Сережей, но без Володи.

Задача как будто решена. Но на самом деле это решения нельзя признать окончательным, т.к. в первом и во втором случаях ответ получился неполным (в первом – неизвестна судьба Сергея, а во втором – Андрея).

Чтобы получить полный ответ, надо ранее полученную ДНФ преобразовать к виду СДНФ:

Теперь мы действительно получили полный перечень всех случаев, при которых выполняются условия задачи.


Пример 13

В школе решили организовать секцию атлетической гимнастики. Надо было разработать правила приема в эту секцию. Ребята внесли ряд предложений:

1. Если ученик не отличник и не здоров, то он может быть принят.

2. Если ученик является отличником, то не может быть, чтобы он был здоров и его не приняли.

3. Если ученик не принят, то он не отличник.

4. Если ученик не здоров, то он не отличник и не будет принят.

Учитель физкультуры сказал, что четыре правила – это слишком много. К тому же формулировки правил должны быть более простыми, более лаконичными. Поэтому, сказал учитель, возникает следующая задача: надо совокупность всех четырех правил заменить новыми правилами – и надо это сделать так, чтобы число новых правил было минимальным, чтобы каждое новое правило было сформулировано кратчайшим образом и чтобы совокупность новых правил была равносильная совокупности четырех исходных правил.

Через некоторое время эту задачу действительно удалось решить. Какие правила получились?

Решение

Обозначим элементарные высказывания: ученик является отличником – О, ученик здоров – З, ученик принят – П. Теперь мы можем записать исходные правила в символьной форме. Полученные формулы сразу же упростим, воспользовавшись таблицей основных равносильностей. Мы получим следующие выражения:

1) ;

2) ;

3) ;

4) .

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

Мы получили формулу, в которой симметрия нарушена только по переменной П. Для исправления этого, произведем следующие действия:

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

Следовательно, для решения задачи необходимо полученную форму представить в виде КНФ.

.

Опять нарушена симметрия относительно переменной П. Тогда далее

.

Таким образом, задача решена. Получились два правила приема в секцию:

  1. Если ученик является отличником, то он будет принят .

  2. Если ученик принят, то необходимо, чтобы он был здоров .


ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ:

1. Переведите на язык алгебры логики следующие высказывания:

        1. Если светит солнце, то для того, чтобы не было дождя, достаточно, чтобы дул ветер.

        2. Неверно, что если дует ветер, то солнце светит только тогда, когда нет дождя.

        3. Чтобы погода была солнечной, достаточно, чтобы не было ни ветра, ни дождя.

        4. Если ветра нет, то для дождя необходима пасмурная погода.

        5. Если погода пасмурная и дует ветер, то дождя нет. Но дождь идет. Значит, нет ветра.

        6. Неверно, что если погода пасмурная и дует ветер, то дождя нет. Но дождь идет. Значит, нет ветра.

        7. Если для солнечной погоды необходимо отсутствие дождя, то для того, чтобы пошел дождь, достаточно, чтобы погода была пасмурной и безветренной.

        8. Будет ветреная погода, разве то пойдет дождь.

        9. Дождь идет только тогда, когда погода пасмурная и безветренная. Но дождя нет. Значит, погода либо солнечная, либо пасмурная и ветреная.

        10. Погода не только солнечная, но и безветренная. Значит, дождя не будет, если не поднимется ветер.

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

        12. Погода будет не только пасмурной, но и дождливой, несмотря на ветер. Значит, солнечной погоды не будет, разве что прекратится дождь.

        13. Если пойдет дождь, Ваня, Петя и Коля останутся дома.

        14. Коля решит задачу, если он вспомнит нужную теорему.

        15. Хотя бы один из мальчиков (Ваня, Петя, Коля) – ошибается.

        16. Ни один из мальчиков (Ваня, Петя, Коля) не опоздали в школу.

        17. В кино пойдет либо Коля, либо Петя.

        18. Если урок будет интересным, никто из мальчиков – Петя и Ваня – не пойдем в лес.

        19. Учитель рассказал смешную историю, но никто из учеников – Петя и Ваня – не засмеялся.

        20. Погода будет пасмурной, и Ваня пойдет в лес тогда и только тогда, когда в лес пойдет Коля.

        21. Петя будет купаться только при солнечной погоде, если будет жарко.

Смотрите также файлы