Соответствие, обратное данному

Пусть Р – соответствие между элементами множеств Х и У. Соответствие между элементами множеств У и Х называется обратным данному, если у вступает в отношение с элементом х (у х) тогда и только тогда, когда х вступает в отношение Р с элементом у (хРу).

( Обратное р)  ( у х  хРу)

Пример.

На множествах Х=3,7,5 и У=9,15,21 задано соответствие Р: «х делитель у».

Р=(3;9), (3;15), (3;21), (7;21), (5;15).

: «х кратно у».

=(9;3), (15;3), (21;3), (21;7), (15;5).

Графики обратных соответствий симметричны биссектрисе 1 и 3 координатных углов.

Постройте графики Р и и убедитесь в вышесказанном.

Взаимно однозначное соответствие

Соответствие Р между элементами множеств Х и У называется взаимно однозначным если каждому элементу из множества Х соответствует единственный элемент из множества У и каждому элементу из множества У соответствует единственный элемент из множества Х. Пример: В данных случаях между множествами Х и У установлены взаимно однозначные соответствия.

В данных случаях между множествами Х и У не установлены взаимно однозначные соответствия.

Равномощные множества

Два множества Х и У называются равномощными, если между ними можно установить взаимно однозначное соответствие.

Обозначение: ХУ.

В данных случаях множества Х и У равномощны.

Если множества конечные и обладают одинаковым количеством элементов, то они равномощны.

Пример. Х=1, 2, 3 и У=2, 3, 4, 5 - множества не равномощны. Х=1, 2, 3 и У=2, 3, 4 - множества равномощны.

Для бесконечных множеств справедливо, что множество может быть равномощно своему подмножеству. Пример:

1. Множество натуральных чисел равномощно множеству чётных чисел, так как каждому чётному числу можно присвоить номер: 1-2, 2-4, 3-6, 4-8, 5-10, 6-12 и т.д.

2. Равномощными могут быть множества точек двух отрезков.

Вопрос 19. Теоретико-множественное определение произведения целых неотрицательных чисел. Определение произведения через сумму. Законы умножения (с доказательством).

Если а и в – целые неотрицательные числа (а,bЄ Zо), то произведением а*b называется число, удовлетворяющее следующим условиям:

1.а*b=а+а+…+а; если b >1 и в число слагаемых

(это сумма b слагаемых, каждое из которых равно а, при условии, что b>1)

2.аb=а*1=а, если в=1

3.аb=а*0=0, если в=0

Определение 2: Произведением двух целых неотрицательных чисел а и в называется число элементов декартова произведения множеств а и в, таких, что во множестве А-а элементов, во множестве B-b элементов.

Теорема: Произведение любых двух целых неотрицательных чисел существует и оно единственное.

а,bЄ Zо,۷а*b. (перевернутая А۷

Докажем используя определение №1

1) в>1, а*в = а + а + а…+а (в слагаемое), т.к. сумма существует и единственная => существует и единственное произведение

2) в=1, а*в = а, произведение существует и единственное

3) в=0, а*в = 0 ,произведение существует и единственное

Законы умножения

Сочетательный закон

Правило. Чтобы произведение двух множителей умножить на третий множитель, можно первый множитель умножить на произведение второго и третьего множителей.

• Например:

• (7 * 6) * 5 = 7 * (6 * 5) = 210

• (a * b) * c = a * (b * c)

Переместительный закон

Правило. От перестановки множителей произведение не изменяется.

• Например:

• 7 * 6 * 5 = 5 * 6 * 7 = 210

• а * Ь * с = с * Ь * а

Распределительным закон

Правило. Чтобы умножить число на сумму, можно умножить это число на каждое из слагаемых и полученные произведения сложить.

• Например:

• 7 * (6 + 5) = 7 * 6 + 7 * 5 = 77

• a * (b + c) = ab + ac

Распределительный закон распространяется и на действие вычитания.

• Например:

• 7 * (6 — 5) = 7 * 6 — 7 * 5 = 7

Законы умножении распространяются на любое количество множителей в числовом или буквенном выражении. Распределительный закон умножения используется для вынесения общего множителя за скобки.

Правило. Чтобы преобразовать сумму (разность) в произведение, достаточно вынести за скобки одинаковый множитель слагаемых, а оставшиеся множители записать в скобках суммой (разностью).

• Например:

• 7 * 8 — 7 * 5 = 7 * (8 — 5)

• аЬ + ас = а * (Ь + с)

Вынесение множителя за скобки для больших числовых или буквенных выражений можно производить по группам слагаемых.

• Например:

• 3 * 6 + 9 * 6 — 4 * 8 = 6 * (3 + 9) — 4 * 8

• ab + bc — df -af = b * (a + c) — f * (d + a)

• c * (a + b) — d * (a + b) = (a + b) * (c — d)

Вопрос 23. Понятие высказывательной формы (предиката). Область определения и множество истинности предиката. Обращение предикатов в высказывания с помощью кванторов общности и существования. Построение отрицаний таких высказываний.

Высказывательные формы (предикаты), так же как и высказывания, бывают элементарными и составными. Составные высказывательные формы образуются из элементарных при помощи тех же логических связок, которые используются в составных высказываниях. Пусть на множестве Х задана высказывательная форма А(х). Отрицанием высказывательной формы (предиката) А(х), заданной на множестве Х, называется высказывательная форма Ā(х), заданная на том же множестве, которая истинна при тех значениях хÎХ, при которых данная форма А(х) ложна, и, наоборот, ложна при тех значениях хÎХ, при которых данная форма А(х) истинна. Обозначение Ā(х) читаем: «Неверно, что А от х» или «Не А от х». Если предложение содержит одну переменную, оно называется одноместным предикатом. Для обозначения одноместных предикатов используют символы: А(х), В(х), Р(х), Q2(х) и так далее. Слово «предикат» происходит от латинского «ргеdicate» (сказуемое). П р и м е р 2. Рассмотрим предложение: «2х–4 > 0». Истинно оно или ложно? Мы не можем ответить на этот вопрос. Это не есть высказывание. Но если вместо х поставить некоторое число, например 3, то мы получим истинное высказывание: «2 ∙ 3 – 4 > 0». Если вместо х поставить 1, то мы получим ложное высказывание: «2 ∙ 1 – 4 > 0». Исходное предложение содержит букву х и при подстановке вместо х некоторого числа, получаем высказывание. Данное предложение является одноместным предикатом. Множество значений X которое принимает переменная х, называется областью определения предиката А(х). Совокупность Т значений переменной х, при которых предикат А(х),   принимает истинные значения, называется множеством истинности предиката А(х). В примере 2 область определения X = R, а область истинности 

Высказывания «для всех х» (для любого х, для каждого х) называется квантором общности и обозначается  х. Высказывание «существует х» (для некоторых х, хотя бы для одного х, найдется такое х) называется квантором существования и обозначается  х. Высказывание «существует одно и только одно х» (для единственного значения х) называется квантором единственности:  ! х.

Например: «Все кустарники являются растениями». Это высказывание содержит квантор общности («все»). Высказывание «существуют числа, кратные 5» содержит квантор существования («существуют»).

Если не каждая переменная связывается квантором, то получается не высказывание, а предикат, зависящий от той переменой, которая не связана квантором. Так, если перед предикатом Р(х; у) поставить квантор  у, то получим предикат ( у Y) Р(х; у), зависящий от переменной х.

Если какое-либо предметное переменное в формуле не связано квантором, то его называют свободным переменным. Например: ( х) ху=ух. Здесь переменное у не связано каким-либо квантором, поэтому оно свободно. От него не зависит истинность данного высказывания.

Кванторы   ( х) ( х) называются двойственными друг другу.

В связи с введением кванторов необходимо учесть следующее:

1. Формула логики предикатов не может содержать одно и то же  предметное переменное, которое было бы связано в одной части формулы и свободно в другой.

2. Одно и то же переменное не может находиться в области двойственных друг другу кванторов.

Нарушение этих условий называют коллизией переменных. Для доказательства утверждения с квантором общности необходимо убедиться в том, что при подстановке каждого из значений х в предикат Р(х) последний обращается в истинное высказывание. Если множество  Х конечно, то это можно сделать путем перебора всех случаев; если же множество Х бесконечно, то необходимо провести рассуждения в общем виде.

Высказывание ( х) Р(х) ложно, если можно указать такое значение  а Х, при котором  Р(х) обращается в ложное высказывание Р(а). Поэтому, для опровержения высказывания с квантором общности достаточно привести пример.

Высказывание ( х) Р(х) истинно, если можно указать такое значение а Х, при котором Р(х) обращается в истинное высказывание Р(а). Поэтому, чтобы убедиться в истинности высказывания квантором существования, достаточно привести пример и таким образом доказать.

Для того чтобы убедиться в ложности высказывания с квантором существования ( х) Р(х), необходимо убедиться в ложности каждого высказывания Р(х ), Р(х ), …, Р(х ). Если множество Х конечно, то это можно сделать перебором. Если же множество Х бесконечно, то необходимо провести рассуждения в общем виде. Примеры:

1. Найти значение истинности высказывания «среди чисел  1, 2, 3, 4 найдется простое число».

Решение: Высказывание содержит квантор существования и поэтому может быть представлено в виде дизъюнкции высказываний: «1 – простое  число» или «2 – простое число» или «3 – простое число» или «4 – простое число». Для доказательства истинности дизъюнкции достаточно истинности хотя бы одного высказывания, например, «3 – простое число», которое истинно. Следовательно, истинно и исходное высказывание.

Для построения отрицания высказывания с кванторами надо:

1)    квантор общности заменить квантором существования, а квантор существования – квантором общности;

2)    предикат заменить его отрицанием.

Пример. Сформулируем отрицание для следующих высказываний:

а) все элементы множества Z четные; b) некоторые глаголы отвечают на вопрос «что делать?».

Решение: а) Заменим квантор общности  квантором существования, а высказывание его отрицанием: некоторые элементы множества Z нечетные.

b) Заменим квантор существования квантором общности, а выражение его отрицанием: все глаголы не отвечают на вопрос «что делать?».