Практические приложения алгебры высказываний

дипломная работа

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

- необходимые и достаточные условия;

- анализ и синтез релейно-контактных схем.

1. Элементы алгебры высказываний

1.1 Логические операции над высказываниями

Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание X ложно, и ложным, если высказывание X истинно.

Отрицание высказывания X обозначается и читается «не X» или «неверно, что X».

Логические значения высказывания можно описать с помощью таблицы

X

1

0

0

1

Таблицы такого вида принято называть таблицами истинности.

Конъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если оба высказывания X, Y истинны, и ложным, если хотя бы одно из них ложно.

Конъюнкция высказываний X, Y обозначается символом X&Y или (XY), читается «X и Y». Высказывания X и Y называются членами конъюнкции или конъюнктивными элементами.

Логические значения конъюнкции описываются следующей таблицей истинности:

X

Y

XY

1

1

1

1

0

0

0

1

0

0

0

0

Например, для высказываний «6 делится на 2», «6 делится на З» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на З», которое, очевидно, истинно.

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

Дизъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если хотя бы одно из высказываний X, Y истинно, и ложным, если они оба ложны.

Дизъюнкция высказываний X, Y обозначается символом XY, читается «X или Y», где «или» используется в неразделительной форме. Высказывания X и Y называются членами дизъюнкции.

Логические значения дизъюнкции описываются следующей таблицей истинности:

X

Y

XY

1

1

1

1

0

1

0

1

1

0

0

0

Например, высказывание «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол Е острый».

Импликацией двух высказываний X,Y называется высказывание, которое считается ложным, если X истинно, а Y - ложно, и истинным во всех остальных случаях.

Импликация высказываний X, Y обозначается символом X Y, читается «если X, то Y» или «из X следует Y». Высказывание X называют посылкой, высказывание Y - заключением.

Логические значения операции импликации описываются следующей таблицей истинности:

X

Y

XY

1

1

1

1

0

0

0

1

1

0

0

1

Например, высказывание «Если число 12 делится на 6, то оно делится на З», очевидно, истинно, так как здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».

Употребление слов «если ..., то ...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание X ложно, то высказывание «Если X, то Y» вообще не имеет смысла. Кроме того, строя предложение вида «если X, то Y» в обыденной речи, мы всегда подразумеваем, что предложение Y вытекает из предложения X. Употребление слов «если ..., то ...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.

Эквиваленцией (или эквивалентностью) двух высказываний X, Y называется высказывание, которое считается истинным, когда оба высказывания X, Y либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.

Эквиваленция высказываний X, Y обозначается символом X Y, читается «для того, чтобы X, необходимо и достаточно, чтобы Y» или «X тогда и только тогда, когда Y». Высказывания X, Y называются членами эквиваленции.

Логические значения операции эквиваленции описываются следующей таблицей истинности:

X

Y

XY

1

1

1

1

0

0

0

1

0

0

0

1

Например, эквиваленция «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда P= Q » является истинной, так как высказывания «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ P= =Q» либо одновременно истинны, либо одновременно ложны.

Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция «Штрих Шеффера». Эта операция обозначается символом и определяется следующей таблицей истинности:

X

Y

1

1

0

1

0

1

0

1

1

0

0

1

Штрих Шеффера - функция, принимающая значение ложь, если X - истинно и Y - истинно.

Очевидно, имеют место равносильности:

1)

2)

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

Отметим, что .

Стрелка Пирса (функция Вебба) XY - функция, принимающая значение истина, когда X - ложно и Y - ложно.

X

Y

XY

1

1

0

1

0

0

0

1

0

0

0

1

Отметим, что XY =

Функция сложение по модулю 2 (функция разноименности, или сумма Жегалкина) - функция, принимающая значение истинно, когда X и Y принимают противоположные значения.

X

Y

1

1

0

1

0

1

0

1

1

0

0

0

Отметим, что = .

С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний X, Y, Z можно построить высказывания

(X&Y)Z и X .

Первое из них есть дизъюнкция конъюнкции X, Y и отрицания выказывания Z, а второе высказывание есть импликация, посылкой которой является высказывание X, а заключением - отрицание дизъюнкции высказывания Y и конъюнкции высказываний X, Z.

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

Высказывания обозначаются большими буквами латинского алфавита А, В, С, …

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

В связи с этим формулы

(X&Y)Z и X

могут быть записаны так:

X&YZ и X .

Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логическим значением формулы в случае, если X = 1, Y = 1, Z=0 будет истина, то есть = 1.

Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности. Эта таблица будет содержать 2n строк, где n - количество переменных.

Например, для формулы таблица истинности имеет вид:

X

Y

1

1

0

0

1

0

0

1

0

0

1

0

1

1

0

1

1

0

1

0

0

0

0

1

1

1

0

0

Легко видеть, что, если формула содержит n элементарных высказываний, то она принимает 2n значений, состоящих из нулей и единиц, или, что тоже, таблица содержит 2n строк.

1.2 Равносильные формулы алгебры высказываний

Две формулы алгебры высказываний А и В называются равносильными или эквивалентными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы элементарных высказываний.

Равносильность формул будем обозначать знаком , а запись А В означает, что формулы А и В равносильны.

Например, равносильны формулы:

Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тожественно истинны формулы

Формула А называется тождественно ложной (или противоречием), если она принимает значение 0 при всех значениях входящих в нее высказываний.

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

Формула А называется выполнимой, если она принимает значение 1 при всех значениях входящих в нее высказываний.

Например, выполнима формула .

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.

Между понятиями равносильности и операцией существует следующая связь: если формулы А и В равносильны, то формула АВ - тавтология, и обратно, если формула АВ - тавтология, то формулы А и В равносильны.

Важнейшие равносильности алгебры высказываний можно разбить на следующие группы.

1.Равносильности алгебры Буля:

1.Закон двойного отрицания:

2. Коммутативность:

3. Ассоциативность:

4. Дистрибутивность & относительно:

5. Дистрибутивность относительно &:

6. Законы де Моргана:

7. Законы поглашения:

8. Законы идемпотентности:

9. Свойства констант:

10. Закон противоречия:

11. Закон исключения третьего:

2. Равносильности, выражающие одни логические операции через другие:

12.

13.

14.

15.

16.

17.

1.3 Нормальные формы

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

Определение 1. Элементарной конъюнкцией п высказываний называется конъюнкция высказываний или их отрицаний.

Определение 2. Элементарной дизъюнкцией п высказываний называется дизъюнкция высказываний или их отрицаний.

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

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

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

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

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

1. Все логические операции можно заменить тремя: конъюнкцией, дизъюнкцией и отрицанием.

2. Знак отрицания с помощью законов де Моргана можно отнести к пропозициональным переменным.

3. С помощью дистрибутивных законов формула преобразовывается в конъюнкцию элементарных дизъюнкций или дизъюнкцию элементарных конъюнкций.

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

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

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

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

в) ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;

г) в каждой элементарной конъюнкции содержится либо Xi, либо , где i=.

Условие а) - г) являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:

1) если какая-нибудь элементарная конъюнкция не содержит высказывание Xi, то заменим выражением ;

2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;

3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.

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

Определение 6. Совершенная конъюнктивная нормальная форма - это ее КНФ обладающая свойствами:

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

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

в) ни одна элементарная дизъюнкция не содержит какой-нибудь переменной с ее отрицанием;

г) каждая элементарная дизъюнкция содержит либо Xi, либо , где i=.

В свою очередь эти условия дают возможность составить алгоритм получения СКНФ из КНФ:

1) если какая-нибудь элементарная дизъюнкция не содержит высказывание Xi, то заменим выражением ;

2) если в полученном выражении окажутся одинаковые элементарные дизъюнкции, то лишние опускаются;

3) если в некоторых элементарных дизъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4) удаляем элементарные дизъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Для тождественно истинных формул СКНФ не существует.

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

1.4 Логические следствия

Определение 1. Формула B называется логическим следствием формул A1, A2, …, An, если при любых значениях, входящих в них, элементарных высказываний формула B принимает значение истинно всякий раз, когда формулы A1, A2, …, An принимают значение истинно. Обозначается A1, A2, …, An ¦ B

Из определения логического следования вытекает:

Тавтология логически следует из любой формулы.

Из противоречия логически следует любая формула.

Теорема 1. Из A логически следует B тогда и только тогда, когда тавтологией является AB.

Теорема 2. A1, A2,…, An¦ B тогда и только тогда, когда является тавтологией

A1&A2& …& An B.

Теорема 3. Из формул A1, A2,…, An , B логически следует C тогда и только тогда, когда из формул A1, A2, …, An логически следует BC.

Следствие 1. Из A и B логически следует C тогда и только тогда, когда тавтологией является

A (BC).

Следствие 2. Из формул A1, A2, …, An логически следует B тогда и только тогда, когда тавтологией является

A1 (A2 … (AnB)…).

Отношение логического следования играет в математике большую роль.

Если из A¦B, то A называется достаточным условием для B, а B - необходимым условием для A.

Если вместе с A¦B из B¦A, то A называется необходимым и достаточным условием для B, а B - необходимым и достаточным условием для A.

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

2.1 Исследование рассуждений

Отношение логического следования используется при исследовании рассуждений.

Задача 1. Если 6 - составное число (S), то 12 - составное число (W). Если 12 - составное число, то существует простое число, больше чем 12 (P). Если существует простое число больше 12, то существует составное число больше 12 (C). Если 6 делится на 2 (D), то 6 - составное число. Число 12 составное. Следовательно, 6 - составное число.

Посылки: , , , , W

Заключение: S

Решение:

Данное высказывание тавтологией не является, значит из указанных посылок не следует высказывание «6 - составное число».

Задача 2. Я пойду в кино на новую комедию (A) или на занятия по математической логике (B). Если я пойду в кино, то я от всей души посмеюсь (C). Если я пойду на занятия по математической логике, то испытаю удовольствие от логических рассуждений (D). Следовательно, или я от всей души посмеюсь или испытаю удовольствие от логических рассуждений.

Посылки: , ,

Заключение:

Решение:

Значит из данных посылок следует .

Задача 3. Я пойду домой (H) или останусь здесь и выпью стаканчик (S). Я не пойду домой. Следовательно, я останусь и выпью.

Посылки: ,

Заключение: S

Решение:

Значит, высказывание «я останусь и выпью» является логическим следствием из данных посылок.

Задача 4. Если Джон ляжет сегодня поздно (S), он будет утром в отупении (D). Если он ляжет не поздно, то ему будет казаться, что не стоит жить (L). Следовательно, или Джон будет завтра в отупении, или ему будет казаться, что не стоит жить.

Посылки: ,

Заключение:

Решение:

Значит из данных посылок следует .

Задача 5. Или Сэлли и Боб одного возраста (S), или Сэлли старше Боба (O). Если Сэлли и Боб одного возраста, то Нэнси и Боб не одного возраста (N). Если Сэлли старше Боба, то Боб старше Уолтера (W). Следовательно, или Нэнси и Боб не одного возраста, или Боб старше Уолтера.

Решение:

Посылки: , ,

Заключение:

Значит из данных посылок следует .

Делись добром ;)