- исследование рассуждений;
- получение логических следствий из данных формул и посылок для данных логических следствий;
- необходимые и достаточные условия;
- анализ и синтез релейно-контактных схем.
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. Решение задач с помощью алгебры высказываний
Yandex.RTB R-A-252273-3- Введение
- - логические операции над высказываниями;
- - равносильные формулы алгебры высказываний;
- 1.2 Равносильные формулы алгебры высказываний
- 1.3 Нормальные формы
- 1.4 Логические следствия
- - исследование рассуждений;
- 2.1 Исследование рассуждений
- - получение логических следствий из данных формул и посылок для данных логических следствий;
- 2.2 Получение логических следствий из данных формул и посылок для данных логических следствий
- - необходимые и достаточные условия;
- 2.3 Необходимые и достаточные условия
- - анализ и синтез релейно-контактных схем.
- 2.4 Анализ и синтез релейно-контактных схем
- Заключение:
- Заключение:
- Заключение:
- Заключение