Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 17
Текст из файла (страница 17)
Пусть А = (П, сз, О,ш,г,з, Ь,*). Отношение Л на А определено, как: Л= ((П П),(~,~1),(0,0),(ш,ш),(Г,1),(з,з),(Ь,Ь),(*,*),(П,О), (О,з),(ш,й), (С,*),(П, ),(,П),(з,О),(Ь,ш),(*,С),(О,П)). а) покажите, что Л является отношением эквивалентности на А; 442 ГЛЯВА 2. Теория множеств б) постройте все классы эквивалентности по отношению Л. Пусть 1(х) = хз + 1, где х 6 [ — 2,4] = (х: х действительное число и — 2 < х < 4) = А.
Определим отношение Л на А х А следующим образом: (а, Ь) е Л тогда и только тогда, когда 1(а) = 1(Ь) . а) покажите, что Л является классом эквивалентности на А = [ — 2,4]; б) определите классы эквивалентности: [1], (2], [0], [3], [ — 1/2], и [4] . 6. Для Х Ф ы определим отношение 1 как 1 = (х: х = (а,а) для некоторого а 6 Х) = ((а,а) 6 Х х Х: а 6 Х). 1 представляет собой отношение эквивалентности на Х и называется отношением тождества на Х. Пусть Л вЂ” отношение на Х. Докажите, что а) Л рефлексивно тогда и только тогда, когда 1 С Л; б) Л симметрично тогда и только тогда, когда Л = Л в) Л транзитивно тогда и только тогда, когда Л с Л ' ~ Л. 7.
Установите, какие из приведенных ниже совокупностей элементов составля ют разбиение множества А = (1,2,3,4,5,6,7). Если некоторая из совокупностей не входит в разбиение, объясните, почему. Для всех совокупностей, входящих в разбиение, перечислите элементы соответствующего отношения Л, и если это перечисление представляется слишком длинным, опишите множество упорядоченных пар, не перечисляя их.
а) И1, 2), И, (3, 4, 5)(6, 7Ц; б) ((1, 2), (3, 4, 5)(6, 7Ц; в) ((1,7),(3,4,6Ц; г) ((1,5),(3,4,5)(2,6,7Ц; д) ((1,2,3,4,5,6,7Ц. 8. Установите, какие из приведенных ниже совокупностей элементов составля ют разбиение множества А = (1,2,3,4,5,6,7). Если некоторая совокупность не входит в разбиение, объясните, почему. Для совокупностей, входяших в разбиение, перечислите элементы соответствующего отношения Л, и если это перечисление представляется слишком длинным, опишите множество упорядоченных пар, не перечисляя их. а) ((Ц,(2),(3),(4),(5),(6),(7Ц; б) ((1,4),(3,5,8)(6,2,7Ц; в) ((1,6),(3,4),(5,2Ц; г) ((1,7),(3,5),(2,4),(6Ц; д) ((1,2,3,4),(4,5,6,7Ц. 9.
Пусть А — множество неотрицательных целых чисел,  — множество по ложительных целых чисел. Определим отношение Л на А х В следуюшим образом; (а, Ь)Л(с, Н), если ад = Ьс. Является ли это отношением эквивалентности? Если это так, докажите. Если нет, объясните почему. Какие элементы множества А х В находятся в отношении с (1,2)Р 114 ГЛАВА 3. логика, целые числа и йоказатапьгтаа Некоторые предикаты истинны для каждого возможного набора значений переменных, взятых из данного множества.
Среди примеров, приведенных выше, Я(х) — предикат — 1 < з(п(х) < 1, где х принадлежит множеству действительных чисел. Тот факт, что для любого значения х — 1 < з(п(х) < 1, дает основание сказать, что для любого х истинно Я(х), что символически изображается как ЧхЯ(х) или Чх( — 1 < гйп(х) < 1) . Символ Чх называется универсальным квантором, или квантором всеобщности, и читается "для любого х" или "для всех х". Множество значений, которое может принимать х, называется универсом, или предметной областью. В частности, предметной областью может являться множество действительных чисел, множество целых чисел или другие подобные множества.
Вообще говоря, истинность утверждения с квантором всеобщности зависит от предметной области. Например, высказывание Чх(х > 5) не истинно, если универсом (предметной областью) является множество целых чисел; однако, оно было бы истинным, если в качестве предметной области взять множество целых чисел, больших чем 2. Точно так же высказывание ~х(хз > 0) истинно, если предметная область — множество действительных чисел, но ложно, если предметная область содержит комплексное число 1, т.к.
1~ = — 1. Квантифицированный предикат 'чхР(х), где Р(х): 3+х = 5, не является истинным, если предметная область — множество целых чисел, потому что имеются значения х из этой области (например,х = 4) такие, что Р(х) ложно. Для истинности УхР(х) Р(х) должно быть истинным для каждого значения х из предметной области. Таким образом, УхР(х) имеет конкретное истинностное значение, поэтому является высказыванием. Предикат Чх'чуРг(х,у) читается как "для каждого х, для каждого у имеет место 1г(х, у) или "для каждого х и для каждого у имеет место 1г(х, у)".
Предикат ЧхЧуЛ(х,у) истинный только тогда, когда для любого набора значений х и у из соответствующей предметной области хз + уз > О истинно. Если предметной областью для х и для у является множество действительных чисел, то Чх Чу В(х, у) Ряздел Зль исчисление предикетое 115 истинно. Рассматривая приведенный выше предикат с„(х,у,х): х +у > х~, мы находим, что (чх) (Чу) (чх) Я(х, у, г) не является истинным, когда предметная область для х, у и х — множество целых чисел, поскольку высказывание Я(1, 2, 3) ложно. Для ясности будем иногда заключать квантор в скобки, записывая (Мх)Р(х) вместо ЧхР(х) и (Чх)(чу)В(х, у) вместо ЧтМуй(х, у).
Хотя МхР(х), вообще говоря, не истинно, Р(х) истинно по крайней мере для одного значения х, а именно, х = 2. Поэтому существует х такой, что Р(х) истинно. Символически это записывается как ЗхР(х) . Символ Зх называется квантаром существования. Здесь, как и в случае ех, выражение Зх относится к значению х из предметной области. Высказывание Зх(*~ = 4) истинно, если предметной областью есть множество действительных чисел, т.к. хз = 4 истинно для х = 2. Высказывание Зх(х~ = 5) также истинно, если предметной областью есть множество действительных чисел; однако, оно не является истинным, если предметная область есть множество целых чисел, так как не существует целого числа, квадрат которого равен 5.
Поскольку для предиката Я(х,у,х) высказывания Я(1,2,0) и Я( — 3,4,5) истинны, то высказывание Зх Зу хх Я(х, у, х) истинно. Чтобы предикат был высказыванием, все его переменные должны иметь конкретные значения или быть связаны соответствующим квантором. Например, (Лх)(чх)Я(х, у, г) не является высказыванием, т.к. переменная у не связана никаким квантором. Если Р(х) — предикат, то высказывание чхР(х) истинно только тогда, когда высказывание Р(х) истинно для любого х. Когда же высказывание УхР(х) будет ложным? Отрицание УхР(х) может быть записано как 'ехР(х) .
Чтобы доказать ложность высказывания чхР(х), достаточно найти только одно значение х, для которого Р(х) ложно (или, что равносильно, Р(х) истинно). Таким образом, МхР(х) ложно тогда и только тогда, когда Зх( Р(х)) 116 ГлкВл 3, погика, целые числа и доказательства истинно, т.е. существует такое значение х (из предметной области), что -зз(х) истинно (или Р(х) ложно). Например, высказывание Чх(х > 0) не является истинным, если предметная область — множество целых чисел, т.к. хз не больше, чем О, если х = О.
Таким образом, Чх(хз > 0) ложно, потому что Зх(хз ~г 0) истинно. Но это означает, что Чх(хз > 0) ложно, потому что Бх( (х > 0)) истинно. Аналогично, если С(х) — предикат, отрицание существования такого х, что С(х) истинно, записывается в виде -РхС( )) Очевидно, если не существует значения х, при котором С(х) истинно, то С(х) ложно для любого х. В этом случае -С(х) будет истинным для всех значений х или, что равносильно, ~ (-С(х)) Результат проведенных рассуждений может быть сформулирован в виде тождеств: -Чх(В(х)) =— хх(-.0(х)); Бх(С(х)) е— э 'чх( С(х)) .
Для образования отрицания с навешенным квантором всеобщности нужно заменить Чх на Зх и взять отрицание предиката, следующего за квантором. А для формирования отрицания предиката с навешенным квантором существования нужно заменить Вх на Чх и взять отрицание предиката, следующего за квантором.
Отрицание высказывания, содержащего более одного квантара, осуществляется путем последовательного рассмотрения каждого квантора, начиная с первого. Например, для отрицания (Чх)(Чу)Л(х, у) имеем (Чх)(иу)Л(х, у) = Зх-(иу)Л(х, у) = = (Вх)(Ву) Л(х, у) . Аналогично, (Зх)(чу) (Зг) Я(х, у, г) = (чх) (чу) (Вг) Я(х, у, г) = = — (~г ПЫ-Р )я(х у ) =— — : (Чх)(лу)(чг) чг(х, у, 2) .
Следовательно, для отрицания высказывания, содержащего кванторы, В заменяется на Ч и наоборот, после чего берется отрицание предиката, связанного с этой последовательностью кванторов. Существует связь между квантифицированными предикатами и предикатами, в которых используются конкретные значения переменных. Рассмотрим, например, предикат вида ЧхЯ(х) РАЗДЕЛ ЗЛ. Исчисление лредикетое 117 в форме высказывания для каждого х верно, что — 1 < з)п(х) < 1. Предположим, что это высказывание истинно. Применим это к конкретному зна- чению х, равному 8. Тогда Я(8).
Если ЧхЯ(х) истинно и а — конкретное значение х (из предметной области), то Я(а) истинно. Таким образом, для случая х равно 8 истинным является — 1 < з(п(8) < 1. Обратно, если 6 — произвольно выбранное значение из универса (т.е. единственным известным и допускаемым свойством Ь есть принадлежность предметной области), и мы покажем, что Я(Ь) истинно, то для любого х имеем Я(х) или ЧхЯ(х) . Следующие два правила устанавливают связь между предикатами с навешенным квантором всеобщности и предикатами, примененными к произвольным константам (элементам) из универса. Из истинности ЧхЯ(х) следует, что Я(а) истинно для произвольного (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
