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