XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 4
Текст из файла (страница 4)
Ошрццанце .: высказывание Р (читается: „не Р") истинно тогда и только тогда, когда Р ложно. 4. Импликаццл =ь: высказывание Р~ Я (читается: „если Р, то Я" или „Р влечет Я") истинно тогда и только тогда, когда истинно высказывание Я или оба высказывания ложны.
5. Эквцваленшность (или раеносильноспьь) еь: высказывание Р СФ Я (читается: „Р, если и только если ь1") истинно тогда и только тогда, когда оба высказывания Р и Я либо одновременно истинны, либо одновременно ложны. Любые два высказывания Р и Щ такие, что истинно Р сФ Я, называют лоеически зкенеалеюинымц или раеносильнымн. Записывая высказывания с помощью логических операций, мы предполагаем, что очередность выполнения всех операций определяется расстановкой скобок. Для упрощения записи скобки зачастую опускают, принимал при этом определенный порядок вьшолнения операций („соглашение о приоритетах").
Операция отрицания всегда выполняется первой, и потому ее в скобки не заключают. Второй выполняется операция коньюнкции, затем диэъюнкции и, наконец, импликации и эквивалентности. Например, высказывание ( Р) Ч Я записывают так: — Р Ч Я. Это высказывание есть дизъюнкция двух высказываний: первое является отрицанием Р, а второе — Я. В отличие от него высказывание -(РЧ Я) есть отрицание дизъюнкции высказываний Р и Я.
Например, высказывание 26 1. МНОЖЕСТВА И ОТНОШЕНИЯ после расстановки скобок в соответствии с приоритетами при- мет вид (((-1Р) л Я) ч ((- Я) л Р)) ь ( Я). Сделаем некоторые комментарии по поводу введенных вьппе логических связок. Содержательная трактовка дизъюнкции, конъюнкции и отрицания не нуждается в специальных разъяснениях. Импликация Р ~ Я истинна, по определению, всякий раз, когда истинно высказывание Я (независимо от истинности Р) или Р и Я одновременно ложны. Таким образом, если импликация Р =ь Я истинна, то при истинности Р имеет место истинность ф но обратное может и не выполняться, т.е. при ложности Р высказывание Я может быть как истинным, так и ложным.
Это и мотивирует прочтение импликации в виде „если Р, то Я". Нетрудно также понять, что высказывание Р =~ 1~ равносильно высказыванию - Р Ч Я и тем самым содержательно „если Р, то Я" отождествляется с „не Р или Я". Равносильность сь есть не что иное, как „двусторонняя импликация", т.е. Р с~ Я равносильно (Р =~ Я) Л Я ~ Р). Это означает, что из истинности Р следует истинность Я и, наоборот, из истинности Я следует истинность Р. Пример 1.1. Для определения истинности или ложности сложного высказывания в зависимости от истинности или ложности входящих в него высказываний используют пзаблицы псшимиостпи. В первых двух столбцах таблицы записывают все-возможные наборы значений, которые могут принимать высказывания Р и Ч. Истинность высказывания обозначают буквой „И", а ложность — буквой „Л".
Остальные столбцы заполняют слева направо. Так для каждого набора значений Р и Я находят соответствующие значения высказываний. Наиболее простой вид имеют таблицы истинности логических операций (табл. 1.1 — 1.5). 27 1.1. Мло:кеегва Таблица 1.1 Таблица 1.3 Таблица 1.8 Л И И Л Таблица 1.5 Таблица 1.4 Рассмотрим сложное высказывание ( РЛЯ) =~ (- ЯЛР).
Для удобства вычислений обозначим высказывание - Р Л Я че- рез А, высказывание -Я Л Р через В, а исходное высказывание запишем в виде А =: В. Таблица истинности этого высказыва- ния состоит из столбцов Р, ф А, В и А =~ В (табл. 1.6). Таблица 1.6 Сложные высказывания образуются не только посредством логических связок, но и с помощью предикатов и кванторов. Предикая есть высказывание, содержащее одно или несколько индивидных переменных.
Например, ех есть четное 28 К МНОЖЕСТВА И ОТНОШЕНИЯ число" или „х есть студент МГТУ им. Баумана, поступивший в 1999 г.". В первом предикате я есть целочисленное переменное, во втором — переменное, пробегающее множество „человеческих индивидов". Примером предиката, содержащего несколько индивидных переменных, может служить: „я есть сын у", „я, у и л учатся в одной и той же группе", „х делится на у", «к меньше у" и т.п. Предикаты будем записывать в виде Р(х), Я(я, у), В(я,у, х), полагая, что в скобках перечислены все переменные, входящие в данный предикат.
Подставляя вместо каждого переменного, входюцего в предикат Р(хм...,я„), конкретное значение, т.е. фиксируя значения х1 = ам..., х„= а„, где ам..., а„— некоторые константы с соответствующей областью значений, получаем высказывание, не содержащее переменных. Например, „2 есть четное число", „Исаак Ньютон есть студент МГТУ им. Баумана, поступивший в 1999 г.", „Иванов есть сын Петрова", „5 делится на 7" и т.п. В зависимости от того, истинно или ложно полученное таким образом высказывание, говорят, что предикат Р выполняется или не выполняется на наборе значений переменных я1 = ам..., я„= а„.
Предикат, выполняющийся на любом наборе входящих в него переменных, называют пюждесшеенно псгпиннььм, а предикат, не выполняющийся ви на одном наборе значений входящих в него переменных, — шождесшвенно вожным. Высказывание из предиката можно получать не только подстановкой значений его переменных, но и посредством кванторов. Вводят два нваншора — сущесщвованил и всеобщносши, обозначаемые 3 и Ч соответственно. Высказывание (Чх Н А)Р(х) („для каждого элемента я, принадлежащего множеству А, истинно Р(х)", иля, более коротко, „для всех я Н А истинно Р(х) ") истинно, по определению, тогда и только тогда, когда предикат Р(х) выполняется для каждого значения переменного х. Высказывание (Зх Е А) Р(х) („существует, или найдется кой элемент х множества А, что истинно Р(х)", также „для 29 1.1. Мяежествв некоторого х Е А истинно Р(х) ") истинно, по определению, тогда и только тогда, когда на некоторых значениях переменного х выполняется предикат Р(х).
При образовании высказывания из предиката посредством квантора говорят, что переменное предиката связывается кван- тором. Аналогично связываются переменные в предикатах, содержащих несколько переменных. В общем случае используют формы высказываний вида (Я1х1 Е А1)(~Ьхг Е Аг) . " (Ювхв Е А„)Р(х1,хз,..., х„), где вместо каждой буквы Я с индексом может быть подставлен любой из кванторов Ч или 3. Например, высказывание (Чх Е А)(зр Е В)Р(х,р) читаетсл так: „для всякого х Е А существует р Е В, такой, что истинно Р(х, у) ".
Если множества, которые пробегают переменные предикатов, фиксированы (подрззумеваются „по умолчанию"), то кванторы записываются в сокращенной форме: (Чх)Р(х) или (Зх) Р(х). Заметим, что многие математические теоремы можно записать в форме, подобной только что приведенным высказываниям с кванторами, например: вдля всех ~ и для всех а истинно: если у — функция, дифференцируемая в точке а, то у непрерывна в точке а". Обсудив особенности употребления логической символики, вернемся к рассмотрению множеств. Два множества А и В считают равмымп, если любой элемент х множества А является элементом множества В и наоборот.
Из приведенного определения равных множеств следует, что множество полностью определяется своими элементами. Рассмотрим способы задания конкретных множеств. Для конечного множества, число элементов которого относительно невелико, может быть использован способ непосредственного перечисления элементов. Элементы конечного множества пере- 30 1.
МНОЖЕСТВА И ОТНОШЕНИЯ числяют в фигурных скобках в произвольном фиксированном порядке (1, 3, 5). Подчеркнем, что поскольку множество полностью определено своими элементами, то при задании конечного множества порядок, в котором перечислены его элементы, не имеет значения. Поэтому записи (1, 3, 5), (3, 1, 5), (5, 3, Ц и т.д. все задают одно и то же множество. Кроме того, иногда в записи множеств используют повторения элементов. Будем считать, что запись (1, 3, 3, 5, 5) задает то же самое множество, что и запись (1, 3, 5).
В общем случае для конечного множества используют форму записи (ам..., а„). Как правило, при этом избегают повторений элементов. Тогда конечное множество, заданное записью (ам ...,а„), состоит из и элементов. Его называют также п-элементпным множестпвам. Однако способ задания множества путем непосредственного перечисления его элементов применим в весьма узком диапазоне конечных множеств. Наиболее общим способом задания конкретных множеств является указание некоторого свойства, которым должны обладать все элементы описываемого множества, и только они.
Эта идея реализуется следующим образом. Пусть переменное х пробегает некоторое множество У, называемое универсальным множестпвом. Мы предполагаем, что рассматриваются только такие множества, элементы которых являются и элементами множества У. В таком случае свойство, которым обладают исключительно элементы данного множества А, может быть выражено посредством предиката Р(х), выполняющегося тогда и только тогда, когда переменное х принимает произвольное значение иэ множества А. Иначе говоря, Р(х) истинно тогда и только тогда, когда вместо х подставляется индивидная константа а Е А. Предикат Р называют в этом случае характперистпическим предикатпом множества А, а свойство, выражаемое с помощью этого предиката, — характперистпическим свойстпвом или кол ьектпивиэируютаим свойстпвом ~1].
1.1. Множества Множество, заданное через характеристический предикат, записывается в следующей форме: А=1х: Р(х)). (1.1) Например, А = (х: х есть четное натуральное число) означает, что „А есть множество, состоящее нз всех таких элементов х, что каждое из них есть четное натуральное число Термин вколлективизирующее свойство" мотивирован тем, что это свойство позволяет собрать разрозненные элементы в единое целое.
Так, свойство, определяющее множество С = 1х: х есть студент 2-го курса специальности ИУ5 МГТУ им. Баумана, поступивший в 1999 г.), Замечание 1.1. Конкретное содержание понятия универсального множества определяется тем конкретным контекстом, в котором мы применяем теоретико-множественные идеи. Например, если мы занимаемся только различными числовыми в буквальном смысле слова формирует некий „коллектив". Если мы вернемся к канторовскому определению множества, то характеристический предикат множества и есть тот закон, посредством которого совокупность элементов соединяется в единое целое.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
