математика. Учебник для сопровождения лекций и практических занятий
 Скачать 0.78 Mb.
|
|
Какие высказывания можно поставить в соответствие числу 𝑥? 58 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Каждой логической операции, оперирующей высказываниями, соответствует булева функция, оперирующая с логическими значениями. Справедливо и обратное, поскольку по логическому значению 𝑥 нетрудно восстановить исходное высказывание 𝑋: 𝑥 = 1. (отождествляем логически эквивалентные высказывания !) Какие высказывания можно поставить в соответствие числу 𝑥? 59 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Булева функция упорядоченной 𝑛-ке нулей и единиц сопоставля- ет 0 или 1. 60 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Булева функция упорядоченной 𝑛-ке нулей и единиц сопоставля- ет 0 или 1. По булевой функции восстанавливается соответствующая логи- ческая функция, поскольку высказывание 𝐵 восстанавливается по его логическому значению 𝑏: 61 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Булева функция упорядоченной 𝑛-ке нулей и единиц сопоставля- ет 0 или 1. По булевой функции восстанавливается соответствующая логи- ческая функция, поскольку высказывание 𝐵 восстанавливается по его логическому значению 𝑏: 𝐵 ∼ (здесь ∼ — символ эквивалентности высказываний) 62 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Булева функция упорядоченной 𝑛-ке нулей и единиц сопоставля- ет 0 или 1. По булевой функции восстанавливается соответствующая логи- ческая функция, поскольку высказывание 𝐵 восстанавливается по его логическому значению 𝑏: 𝐵 ∼ 𝑏 = 1. (здесь ∼ — символ эквивалентности высказываний) 63 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». 64 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Отметим, что высказывание ¬𝑋 логически эквивалент- но высказываниям «неверно, что 𝑋», «высказывание 𝑋 ложно», «высказывание 𝑋 неверно». 65 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 66 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 67 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 Если высказывание 𝑋 ложно, то высказывание «неверно, что 𝑋» 68 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 Если высказывание 𝑋 ложно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ , то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание « » 69 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 Если высказывание 𝑋 ложно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ , то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание « » Надо какое-нибудь неверное утверждение... 70 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 Если высказывание 𝑋 ложно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ 4 > 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание « » Надо какое-нибудь неверное утверждение... 71 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 Если высказывание 𝑋 ложно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ 4 > 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 > 5» 72 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 Если высказывание 𝑋 ложно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ 4 > 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 > 5» Истинно или ложно? 73 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 Если высказывание 𝑋 ложно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ 4 > 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 > 5» истинно. Истинно или ложно? 74 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 Если высказывание 𝑋 ложно, то высказывание «неверно, что 𝑋» истинно. Например, если 𝑋 ∼ 4 > 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 > 5» истинно. Истинно или ложно? 75 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 Если высказывание 𝑋 ложно, то высказывание «неверно, что 𝑋» истинно. Например, если 𝑋 ∼ 4 > 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 > 5» истинно. Истинно или ложно? 76 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 77 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 Если высказывание 𝑋 истинно, то высказывание «неверно, что 𝑋» 78 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 Если высказывание 𝑋 истинно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ , то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что » 79 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 Если высказывание 𝑋 истинно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ , то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что » Надо какое-нибудь верное утверждение... 80 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 Если высказывание 𝑋 истинно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ 4 < 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что » Надо какое-нибудь верное утверждение... 81 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 Если высказывание 𝑋 истинно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ 4 < 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 < 5» Надо какое-нибудь верное утверждение... 82 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 Если высказывание 𝑋 истинно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ 4 < 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 < 5» Истинно или ложно? 83 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 Если высказывание 𝑋 истинно, то высказывание «неверно, что 𝑋» Например, если 𝑋 ∼ 4 < 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 < 5» ложно. Истинно или ложно? 84 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 Если высказывание 𝑋 истинно, то высказывание «неверно, что 𝑋» ложно. Например, если 𝑋 ∼ 4 < 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 < 5» ложно. Истинно или ложно? 85 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 0 Если высказывание 𝑋 истинно, то высказывание «неверно, что 𝑋» ложно. Например, если 𝑋 ∼ 4 < 5, то высказывание ¬𝑋 ∼ 𝑋, т.е. высказывание «неверно, что 4 < 5» ложно. Истинно или ложно? 86 III.1. Отрицание Логическая функция отрицание высказыванию 𝑋 сопоставля- ет высказывание ¬𝑋, обозначаемое также 𝑋, логически экви- валентное высказыванию «не 𝑋». Логической операции «отрицание» соответствует од- ноименная булева функция отрицание, которую можно задать таблицей истинности: 𝑥 ¬𝑥 = 𝑥 0 1 1 0 Это стоит записать и запомнить! 87 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». 88 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Отметим, что высказывание 𝑋 ∨𝑌 логически эквивалентно вы- сказываниям «𝑋, а 𝑌 », «𝑋, но 𝑌 », «и 𝑋, и 𝑌 ». 89 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Логической операции «конъюнкция» соответ- ствует одноименная булева функция конъ- юнкция, которую можно задать таблицей истин- ности: 𝑥 𝑦 𝑥&𝑦 = 𝑥 ∧ 𝑦 90 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Логической операции «конъюнкция» соответ- ствует одноименная булева функция конъ- юнкция, которую можно задать таблицей истин- ности: 𝑥 𝑦 𝑥&𝑦 = 𝑥 ∧ 𝑦 0 0 91 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Логической операции «конъюнкция» соответ- ствует одноименная булева функция конъ- юнкция, которую можно задать таблицей истин- ности: 𝑥 𝑦 𝑥&𝑦 = 𝑥 ∧ 𝑦 0 0 Если высказывания 𝑋 и 𝑌 ложны, то высказывание «𝑋 и 𝑌 » 92 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Логической операции «конъюнкция» соответ- ствует одноименная булева функция конъ- юнкция, которую можно задать таблицей истин- ности: 𝑥 𝑦 𝑥&𝑦 = 𝑥 ∧ 𝑦 0 0 Если высказывания 𝑋 и 𝑌 ложны, то высказывание «𝑋 и 𝑌 » Например, если 𝑋 ∼ , и 𝑌 ∼ , то высказывание 𝑋 ∧ 𝑌 ∼ 𝑋&𝑌 , т.е. высказывание « и » 93 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Логической операции «конъюнкция» соответ- ствует одноименная булева функция конъ- юнкция, которую можно задать таблицей истин- ности: 𝑥 𝑦 𝑥&𝑦 = 𝑥 ∧ 𝑦 0 0 Если высказывания 𝑋 и 𝑌 ложны, то высказывание «𝑋 и 𝑌 » Например, если 𝑋 ∼ , и 𝑌 ∼ , то высказывание 𝑋 ∧ 𝑌 ∼ 𝑋&𝑌 , т.е. высказывание « и » Надо какое-нибудь неверное утверждение... 94 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Логической операции «конъюнкция» соответ- ствует одноименная булева функция конъ- юнкция, которую можно задать таблицей истин- ности: 𝑥 𝑦 𝑥&𝑦 = 𝑥 ∧ 𝑦 0 0 Если высказывания 𝑋 и 𝑌 ложны, то высказывание «𝑋 и 𝑌 » Например, если 𝑋 ∼ 4 > 5, и 𝑌 ∼ , то высказывание 𝑋 ∧ 𝑌 ∼ 𝑋&𝑌 , т.е. высказывание «4 > 5 и » Надо какое-нибудь неверное утверждение... 95 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Логической операции «конъюнкция» соответ- ствует одноименная булева функция конъ- юнкция, которую можно задать таблицей истин- ности: 𝑥 𝑦 𝑥&𝑦 = 𝑥 ∧ 𝑦 0 0 Если высказывания 𝑋 и 𝑌 ложны, то высказывание «𝑋 и 𝑌 » Например, если 𝑋 ∼ 4 > 5, и 𝑌 ∼ , то высказывание 𝑋 ∧ 𝑌 ∼ 𝑋&𝑌 , т.е. высказывание «4 > 5 и » Надо ещ¨е какое-нибудь неверное утверждение... 96 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Логической операции «конъюнкция» соответ- ствует одноименная булева функция конъ- юнкция, которую можно задать таблицей истин- ности: 𝑥 𝑦 𝑥&𝑦 = 𝑥 ∧ 𝑦 0 0 Если высказывания 𝑋 и 𝑌 ложны, то высказывание «𝑋 и 𝑌 » Например, если 𝑋 ∼ 4 > 5, и 𝑌 ∼ 2 2 = 5, то высказывание 𝑋 ∧ 𝑌 ∼ 𝑋&𝑌 , т.е. высказывание «4 > 5 и 2 2 = 5 » Надо ещ¨е какое-нибудь неверное утверждение... 97 III.2. Конъюнкция Логическая функция конъюнкция паре высказываний 𝑋 и 𝑌 сопоставляет высказывание 𝑋&𝑌 , обозначаемое также 𝑋 ∧ 𝑌 , логически эквивалентное высказыванию «𝑋 и 𝑌 ». Логической операции «конъюнкция» соответ- ствует одноименная булева функция конъ- юнкция, которую можно задать таблицей истин- ности: 𝑥 𝑦 𝑥&𝑦 = 𝑥 ∧ 𝑦 0 0 Если высказывания 𝑋 и 𝑌 ложны, то высказывание «𝑋 и 𝑌 » Например, если 𝑋 ∼ 4 > 5, и 𝑌 ∼ 2 2 = 5, то высказывание 𝑋 ∧ 𝑌 ∼ 𝑋&𝑌 , т.е. высказывание «4 > 5 и 2 2 = 5 » |