Файл: Учебник для сопровождения лекций и практических занятий.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.01.2024
Просмотров: 45
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Министерство образования и науки РФ
Уральский государственный экономический университет
Ю. Б. Мельников
Алгебра высказываний: ло- гические и булевы функции
Электронный учебник для сопровождения лекций и практических занятий
Изд. 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