Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Логические операции над высказываниямиСтр 1 из 9Следующая ⇒ Задачи по математической логике Элементы алгебры высказываний Логические операции над высказываниями Равносильные формулы алгебры высказываний Нормальные формы Логические следствия Решение задач с помощью алгебры высказываний Исследование рассуждений Получение логических следствий из данных формул и посылок для данных логических следствий Необходимые и достаточные условия Анализ и синтез релейно-контактных схем Элементы алгебры высказываний Логические операции над высказываниями
Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание X ложно, и ложным, если высказывание X истинно. Отрицание высказывания X обозначается и читается «не X» или «неверно, что X». Логические значения высказывания можно описать с помощью таблицы
Таблицы такого вида принято называть таблицами истинности. Конъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если оба высказывания X, Y истинны, и ложным, если хотя бы одно из них ложно. Конъюнкция высказываний X, Y обозначается символом X&Y или (XÙY), читается «X и Y». Высказывания X и Y называются членами конъюнкции или конъюнктивными элементами. Логические значения конъюнкции описываются следующей таблицей истинности:
Например, для высказываний «6 делится на 2», «6 делится на З» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на З», которое, очевидно, истинно. Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания далеких друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний. Дизъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если хотя бы одно из высказываний X, Y истинно, и ложным, если они оба ложны. Дизъюнкция высказываний X, Y обозначается символом X Y, читается «X или Y», где «или» используется в неразделительной форме. Высказывания X и Y называются членами дизъюнкции. Логические значения дизъюнкции описываются следующей таблицей истинности:
Например, высказывание «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол Е острый». Импликацией двух высказываний X,Y называется высказывание, которое считается ложным, если X истинно, а Y - ложно, и истинным во всех остальных случаях. Импликация высказываний X, Y обозначается символом X Y, читается «если X, то Y» или «из X следует Y». Высказывание X называют посылкой, высказывание Y – заключением. Логические значения операции импликации описываются следующей таблицей истинности:
Например, высказывание «Если число 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 называются членами эквиваленции. Логические значения операции эквиваленции описываются следующей таблицей истинности:
Например, эквиваленция «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда P= Q» является истинной, так как высказывания «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ P= = Q» либо одновременно истинны, либо одновременно ложны. Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности. Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция «Штрих Шеффера». Эта операция обозначается символом и определяется следующей таблицей истинности:
Штрих Шеффера - функция, принимающая значение ложь, если X – истинно и Y – истинно. Очевидно, имеют место равносильности: 1) 2) Из этих двух равносильностей следует, что всякая формула алгебры логики может быть заменена равносильной формулой, содержащей только операцию «Штрих Шеффера». Отметим, что . Стрелка Пирса (функция Вебба) X Y – функция, принимающая значение истина, когда X – ложно и Y – ложно.
Отметим, что X Y = Функция сложение по модулю 2 (функция разноименности, или сумма Жегалкина) - функция, принимающая значение истинно, когда X и Y принимают противоположные значения.
Отметим, что = . С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний 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 – количество переменных. Например, для формулы таблица истинности имеет вид:
Легко видеть, что, если формула содержит n элементарных высказываний, то она принимает 2n значений, состоящих из нулей и единиц, или, что тоже, таблица содержит 2n строк.
|