математика. Учебник для сопровождения лекций и практических занятий
 Скачать 0.78 Mb.
|
|
Министерство образования и науки РФ Уральский государственный экономический университет Ю. Б. Мельников Алгебра высказываний: ло- гические и булевы функции Электронный учебник для сопровождения лекций и практических занятий Изд. 4-е, испр. и доп. Екатеринбург 2012 e-mail: melnikov@k66.ru, melnikov@r66.ru сайты: http://melnikov.k66.ru, http://melnikov.web.ur.ru 1 I. Инструкция к пособию 4 II. Алгебра высказываний 13 II.1. Что такое высказывание . . . . . . . . . . . . . . . . . . 14 II.2. Логическая эквивалентность высказываний . . . . . . . 30 III. Логические и булевы операции 46 III.1. Отрицание . . . . . . . . . . . . . . . . . . . . . . . . . 64 III.2. Конъюнкция . . . . . . . . . . . . . . . . . . . . . . . . 88 III.3. Дизъюнкция . . . . . . . . . . . . . . . . . . . . . . . . 129 III.4. Импликация . . . . . . . . . . . . . . . . . . . . . . . . 170 III.5. Эквиваленция . . . . . . . . . . . . . . . . . . . . . . . 196 III.6. Элементарные булевы и логические функции . . . . . . 208 IV. Отрицания к базовым логическим функциям 209 2 V. Предикаты и кванторы 210 V.1. Предикат-высказывание и предикат-функция . . . . . . 215 V.2. Кванторы . . . . . . . . . . . . . . . . . . . . . . . . . . 231 VI. Построение отрицаний к формулам с предикатами и кванторами 256 3 I. Инструкция к пособию Данная работа представлена в формате pdf и, следовательно, мо- жет использоваться на различных аппаратных и программных плат- формах. 4 I. Инструкция к пособию Данная работа представлена в формате pdf и, следовательно, мо- жет использоваться на различных аппаратных и программных плат- формах. Для просмотра файлов pdf желательно использовать программу Adobe Reader версии 8 или 9, но для операционной системы Android желательно применять Smart Office. Можно использовать другую программу, поддерживающую выполнение скриптов, включенных в файл pdf. Следует проследить, чтобы было разрешено выполнение скриптов. Это необходимо для выполнения переходов по гиперссыл- кам. 5 I. Инструкция к пособию Для просмотра файлов pdf настоятельно рекомендуем использо- вать программу Adobe Reader версии 8 или 9. Электронный учебник представляет собой систему файлов, кото- рые следует просматривать с помощью программы Adobe Reader. Основным из этих файлов является 0000Spisok.pdf, содержащий гиперссылки на файлы с представлениями лекций и практических занятий. Вернуться из презентации любой лекции и практического занятия к файлу 0000Spisok.pdf можно двумя способами: 6 I. Инструкция к пособию Для просмотра файлов pdf настоятельно рекомендуем использо- вать программу Adobe Reader версии 8 или 9. Электронный учебник представляет собой систему файлов, кото- рые следует просматривать с помощью программы Adobe Reader. Основным из этих файлов является 0000Spisok.pdf, содержащий гиперссылки на файлы с представлениями лекций и практических занятий. Вернуться из презентации любой лекции и практического занятия к файлу 0000Spisok.pdf можно двумя способами: во-первых, с титульного листа с помощью гиперссылки, отмеченной словосочетанием «электронного учебника» во фразе «Раздел элек- тронного учебника»; 7 I. Инструкция к пособию Для просмотра файлов pdf настоятельно рекомендуем использо- вать программу Adobe Reader версии 8 или 9. Электронный учебник представляет собой систему файлов, кото- рые следует просматривать с помощью программы Adobe Reader. Основным из этих файлов является 0000Spisok.pdf, содержащий гиперссылки на файлы с представлениями лекций и практических занятий. Вернуться из презентации любой лекции и практического занятия к файлу 0000Spisok.pdf можно двумя способами: во-первых, с титульного листа с помощью гиперссылки, отмеченной словосочетанием «электронного учебника» во фразе «Раздел элек- тронного учебника»; во-вторых, с последней страницы, по гиперссылке «Вернуться к спис- ку презентаций». 8 I. Инструкция к пособию Для просмотра файлов pdf настоятельно рекомендуем использо- вать программу Adobe Reader версии 8 или 9. В презентациях, предназначенных для проведения практических занятий, имеется два вида учебных заданий: примеры, предназна- ченные для иллюстрации теоретического материала, демонстрации методов решения задач и т. п., и задачи, предназначенные для само- стоятельного решения. 9 I. Инструкция к пособию Для просмотра файлов pdf настоятельно рекомендуем использо- вать программу Adobe Reader версии 8 или 9. В программе Adobe Reader переход в полноэкранный режим и воз- вращение к режиму работы в окне осуществляется комбинацией кла- виш Ctrl+L (т.е. одновременным нажатием клавиш «Ctrl» и «L»). Пе- реход к следующему слайду или возвращение к предыдущему слайду осуществляется клавишами «Page Up» или «Page Down». 10 I. Инструкция к пособию Для просмотра файлов pdf настоятельно рекомендуем использо- вать программу Adobe Reader версии 8 или 9. Для перехода по гиперссылке, как обычно, следует навести ука- затель мыши на текст, выделенный красным (но не пурпурным) или синим цветом и нажать на левую кнопку мыши или левую кнопку та- чпада (для ноутбука). «Откат», т.е. отмена предыдущей команды (на- пример, перехода по гиперссылке) осуществляется одновременным нажатием клавиш Alt и ← (в Adobe Reader X может не работать). 11 I. Инструкция к пособию Для просмотра файлов pdf настоятельно рекомендуем использо- вать программу Adobe Reader версии 8 или 9. В случае, если два соседних слова выделены, допустим, синим цве- том, но одно набрано обычным, а другое — полужирным шрифтом, то это означает, что переход по гиперссылкам осуществляется на раз- личные мишени. 12 II. Алгебра высказываний Мы рассмотрим несколько основных понятий математической ло- гики, во многом обобщающих так называемую формальную логику, разработанную Аристотелем. Просим прощения у искушенных читателей за некоторые погреш- ности изложения, обусловленные необходимостью максимально упро- стить изложение. 13 II.1. Что такое высказывание 14 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. 15 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Примерами высказываний являются фразы: 16 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Примерами высказываний являются фразы: на улице идет дождь; 17 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Примерами высказываний являются фразы: на улице идет дождь; 𝐴𝑀 — медиана треугольника 𝐴𝐵𝐶; 18 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Примерами высказываний являются фразы: на улице идет дождь; 𝐴𝑀 — медиана треугольника 𝐴𝐵𝐶; 𝑥 2 − 2𝑥 < 0 ; 19 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Примерами высказываний являются фразы: на улице идет дождь; 𝐴𝑀 — медиана треугольника 𝐴𝐵𝐶; 𝑥 2 − 2𝑥 < 0 ; {︂ 𝑥 + 2𝑦 = 2; 𝑥 − 𝑦 = 1; 20 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Примерами высказываний являются фразы: на улице идет дождь; 𝐴𝑀 — медиана треугольника 𝐴𝐵𝐶; 𝑥 2 − 2𝑥 < 0 ; {︂ 𝑥 + 2𝑦 = 2; 𝑥 − 𝑦 = 1; 𝑥 < 𝑦 < 0 ⇒ 𝑥 2 > 𝑦 2 21 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Не являются высказываниями фразы: 22 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Не являются высказываниями фразы: 𝑥 2 − 5𝑥 + 4 ; 23 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Не являются высказываниями фразы: 𝑥 2 − 5𝑥 + 4 ; закройте дверь! 24 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Не являются высказываниями фразы: 𝑥 2 − 5𝑥 + 4 ; закройте дверь! Является ли треугольник 𝐴𝐵𝐶 равнобедренным? 25 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Отметим, что мы можем не знать ответ на вопрос: «верно ли вы- сказывание...?», важно, что ответ существует в принципе. 26 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Отметим, что мы можем не знать ответ на вопрос: «верно ли вы- сказывание...?», важно, что ответ существует в принципе. Например, в настоящий момент нам не известно, верно ли выска- зывание «на марсе есть живые существа». 27 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Отметим, что мы можем не знать ответ на вопрос: «верно ли вы- сказывание...?», важно, что ответ существует в принципе. Например, в настоящий момент нам не известно, верно ли выска- зывание «на марсе есть живые существа». На этот вопрос мы когда-то получим ответ. Но возможны выска- зывания, ответ на которые мы, возможно, не найдем однозначный ответ никогда. 28 II.1. Что такое высказывание Под высказыванием мы будем понимать фразу, относительно ко- торой осмысленным является вопрос, верна эта фраза или нет. Отметим, что мы можем не знать ответ на вопрос: «верно ли вы- сказывание...?», важно, что ответ существует в принципе. Например, в настоящий момент нам не известно, верно ли выска- зывание «на марсе есть живые существа». На этот вопрос мы когда-то получим ответ. Но возможны выска- зывания, ответ на которые мы, возможно, не найдем однозначный ответ никогда. Важно лишь, что ответ в принципе существует! 29 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: 30 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; 31 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; Сравните фразы: «мамаша с детенышем пытается перейти дорогу» и «мама с ребенком пробует перейти дорогу». 32 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; Сравните фразы: «мамаша с детенышем пытается перейти дорогу» и «мама с ребенком пробует перейти дорогу». В первой из этих фраз чувствуется пренебрежение: использование слова «мамаша», ребенка обозвали «детенышем» (этот термин обыч- но относят к животным). 33 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; Сравните фразы: «мамаша с детенышем пытается перейти дорогу» и «мама с ребенком пробует перейти дорогу». В первой из этих фраз чувствуется пренебрежение: использование слова «мамаша», ребенка обозвали «детенышем» (этот термин обыч- но относят к животным). Вторая фраза более нейтральная, во всяком случае, о ситуации сообщается более уважительно. 34 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; Сравните фразы: «этот компьютер деш¨евый, но мощный», «этот ком- пьютер деш¨евый и мощный» и «этот компьютер и деш¨евый, и мощ- ный». 35 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; Сравните фразы: «этот компьютер деш¨евый, но мощный», «этот ком- пьютер деш¨евый и мощный» и «этот компьютер и деш¨евый, и мощ- ный». В первой фразе явно ощущается оттенок удивления, вторая фраза совершенно нейтральна, а в третьей фразе сделан упор на наличие обоих качеств (например, последняя фраза очень органично смотре- лась бы в рекламе компьютера). 36 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; Сравните фразы: «этот компьютер деш¨евый, но мощный», «этот ком- пьютер деш¨евый и мощный» и «этот компьютер и деш¨евый, и мощ- ный». В первой фразе явно ощущается оттенок удивления, вторая фраза совершенно нейтральна, а в третьей фразе сделан упор на наличие обоих качеств (например, последняя фраза очень органично смотре- лась бы в рекламе компьютера). Однако, логически эти фразы равносильны, поскольку ответ на вопрос «верна ли эта фраза» будет одинаков в любой конкретной ситуации. 37 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; грамматическая сложность; 38 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; грамматическая сложность; Например, сравните фразы «этот автомобиль является громоздким, к тому же данная машина имеет красный цвет, однако рассчитана только на двух пассажиров» и «этот двухместный красный авто- мобиль является громоздким». 39 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; грамматическая сложность; Например, сравните фразы «этот автомобиль является громоздким, к тому же данная машина имеет красный цвет, однако рассчитана только на двух пассажиров» и «этот двухместный красный авто- мобиль является громоздким». Другой пример: 3(2𝑥 − 2) + 2(4 − 4(𝑥 + 2)) = 0 и 𝑥 = −7 верны одновременно, но вторая фраза, очевидно, гораздо короче, проще и понятнее. 40 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; грамматическая сложность; используемый язык и т.д. 41 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; грамматическая сложность; используемый язык и т.д. Например, фразы «переменная 𝑥 равна 3», «the variable 𝑥 is equal to 3» и 𝑥 = 3 означают одно и то же, но сформулированы на разных языках. 42 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; грамматическая сложность; используемый язык и т.д. Например, фразы «переменная 𝑥 равна 3», «the variable 𝑥 is equal to 3» и 𝑥 = 3 означают одно и то же, но сформулированы на разных языках. Более того, если известно, что через 𝑥 обозначена длина отрезка, то фраза 𝑥 ⏟ ⏞ 3 , сформулированная на языке геометрических чертежей, равносильна предыдущим тр¨ем фразам. 43 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; грамматическая сложность; используемый язык и т.д. Но в логике нас интересует только истинность или ложность выска- зывания, от остальных его характеристик мы абстрагируемся. 44 II.2. Логическая эквивалентность высказываний У высказывания есть множество характеристик: эмоциональный окрас; грамматическая сложность; используемый язык и т.д. Но в логике нас интересует только истинность или ложность выска- зывания, от остальных его характеристик мы абстрагируемся. Поэтому мы будем считать высказывания (логически) эквива- лентными или (логически) равносильными, если истинность одного из них влечет истинность другого. 45 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. 46 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. 47 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. 48 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Мы рассматриваем единственную характеристику высказывания: его истинность или ложность. 49 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Мы рассматриваем единственную характеристику высказывания: его истинность или ложность. Если 𝑋 — это высказывание, то через 𝑥 будем обозначать его логическое значение: 50 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Мы рассматриваем единственную характеристику высказывания: его истинность или ложность. Если 𝑋 — это высказывание, то через 𝑥 будем обозначать его логическое значение: 𝑥 = 1 тогда и только тогда, когда высказывание 𝑋 истинно; 51 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Мы рассматриваем единственную характеристику высказывания: его истинность или ложность. Если 𝑋 — это высказывание, то через 𝑥 будем обозначать его логическое значение: 𝑥 = 1 тогда и только тогда, когда высказывание 𝑋 истинно; 𝑥 = 0 тогда и только тогда, когда высказывание 𝑋 ложно. 52 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Если, например, 𝑍 — результат применения некоторой логической операции к упорядоченной паре высказываний 𝑋 и 𝑌 , то логическое значение 𝑧 зависит только от логических значений 𝑥 и 𝑦, поскольку 53 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Если, например, 𝑍 — результат применения некоторой логической операции к упорядоченной паре высказываний 𝑋 и 𝑌 , то логическое значение 𝑧 зависит только от логических значений 𝑥 и 𝑦, поскольку при замене высказываний на логически эквивалентные значения их логических значений сохраняются. Поэтому... 54 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Каждой логической операции, оперирующей высказываниями, соответствует булева функция, оперирующая с логическими значениями. 55 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Каждой логической операции, оперирующей высказываниями, соответствует булева функция, оперирующая с логическими значениями. Справедливо и обратное, поскольку по логическому значению 𝑥 нетрудно восстановить исходное высказывание 𝑋: 56 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Каждой логической операции, оперирующей высказываниями, соответствует булева функция, оперирующая с логическими значениями. Справедливо и обратное, поскольку по логическому значению 𝑥 нетрудно восстановить исходное высказывание 𝑋: (отождествляем логически эквивалентные высказывания !) 57 III. Логические и булевы операции Мы отождествляем логически эквивалентные высказывания. Высказывание будем задавать с помощью конкретной фразы, но она может быть заменена любой логически эквивалентной. Логическая операция (логическая функция) высказыва- нию 𝑋 или упорядоченной паре высказываний (𝑋, 𝑌 ) сопоставля- ющая некоторое высказывание, которое может быть заменено на ло- гически эквивалентное. Каждой логической операции, оперирующей высказываниями, соответствует булева функция, оперирующая с логическими значениями. Справедливо и обратное, поскольку по логическому значению 𝑥 нетрудно восстановить исходное высказывание 𝑋: (отождествляем логически эквивалентные высказывания !) |