Равносильные формулы алгебры высказываний
Задачи по математической логике
Элементы алгебры высказываний
Логические операции над высказываниями
Равносильные формулы алгебры высказываний
Нормальные формы
Логические следствия
Решение задач с помощью алгебры высказываний
Исследование рассуждений
Получение логических следствий из данных формул и посылок для данных логических следствий
Необходимые и достаточные условия
Анализ и синтез релейно-контактных схем
Элементы алгебры высказываний
Логические операции над высказываниями
Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание X ложно, и ложным, если высказывание X истинно.
Отрицание высказывания X обозначается и читается «не X» или «неверно, что X».
Логические значения высказывания можно описать с помощью таблицы
X | |
1 | 0 |
0 | 1 |
Таблицы такого вида принято называть таблицами истинности.
Конъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если оба высказывания X, Y истинны, и ложным, если хотя бы одно из них ложно.
Конъюнкция высказываний X, Y обозначается символом X&Y или (XÙY), читается «X и Y». Высказывания X и Y называются членами конъюнкции или конъюнктивными элементами.
Логические значения конъюнкции описываются следующей таблицей истинности:
|
|
X | Y | X&Y |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 0 |
Например, для высказываний «6 делится на 2», «6 делится на З» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на З», которое, очевидно, истинно.
Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания далеких друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний.
Дизъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если хотя бы одно из высказываний X, Y истинно, и ложным, если они оба ложны.
Дизъюнкция высказываний X, Y обозначается символом X Y, читается «X или Y», где «или» используется в неразделительной форме. Высказывания X и Y называются членами дизъюнкции.
Логические значения дизъюнкции описываются следующей таблицей истинности:
X | Y | X Y |
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 | X Y |
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 | X Y |
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)
Из этих двух равносильностей следует, что всякая формула алгебры логики может быть заменена равносильной формулой, содержащей только операцию «Штрих Шеффера».
Отметим, что .
Стрелка Пирса (функция Вебба) X Y – функция, принимающая значение истина, когда X – ложно и Y – ложно.
X | Y | X Y |
1 | 1 | 0 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 1 |
Отметим, что X Y =
Функция сложение по модулю 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&Y Z и 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 при всех значениях входящих в нее переменных.
Например, тожественно истинны формулы
Формула А называется тождественно ложной (или противоречием), если она принимает значение 0 при всех значениях входящих в нее высказываний.
Например, тождественно ложна формула .
Формула А называется выполнимой, если она принимает значение 1 при всех значениях входящих в нее высказываний.
Например, выполнима формула .
Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.
Между понятиями равносильности и операцией существует следующая связь: если формулы А и В равносильны, то формула А В - тавтология, и обратно, если формула А В - тавтология, то формулы А и В равносильны.
Важнейшие равносильности алгебры высказываний можно разбить на следующие группы.
1.Равносильности алгебры Буля:
1.Закон двойного отрицания:
2. Коммутативность:
3. Ассоциативность:
4. Дистрибутивность & относительно :
5. Дистрибутивность относительно &:
6. Законы де Моргана:
7. Законы поглашения:
8. Законы идемпотентности:
9. Свойства констант:
10. Закон противоречия:
11. Закон исключения третьего:
2. Равносильности, выражающие одни логические операции через другие:
12.
13.
14.
15.
16.
17.
Нормальные формы
Основной из задач алгебры высказываний является проблема разрешения, т.е. является ли данная формула тавтологией или противоречием или выполнимой формулой. Эта проблема легко решается с помощью нормальных форм.
Определение 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. Формула B называется логическим следствием формул A1, A2, …, An, если при любых значениях, входящих в них, элементарных высказываний формула B принимает значение истинно всякий раз, когда формулы A1, A2, …, An принимают значение истинно. Обозначается A1, A2, …, An ╞ B
Из определения логического следования вытекает:
1. Тавтология логически следует из любой формулы.
2. Из противоречия логически следует любая формула.
Теорема 1. Из A логически следует B тогда и только тогда, когда тавтологией является A B.
Теорема 2. A1, A2,…, An╞ B тогда и только тогда, когда является тавтологией
A1&A2& …& An B.
Теорема 3. Из формул A1, A2,…, An , B логически следует C тогда и только тогда, когда из формул A1, A2, …, An логически следует B C.
Следствие 1. Из A и B логически следует C тогда и только тогда, когда тавтологией является
A (B C).
Следствие 2. Из формул A1, A2, …, An логически следует B тогда и только тогда, когда тавтологией является
A1 (A2 … (An B)…).
Отношение логического следования играет в математике большую роль.
Если из A╞B, то A называется достаточным условием для B, а B – необходимым условием для A.
Если вместе с A╞B из B╞A, то A называется необходимым и достаточным условием для B, а B – необходимым и достаточным условием для A.
Дата добавления: 2018-09-22; просмотров: 489; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!