Лабораторная работа 2 Множества, задание множества с помощью предиката

1. Цель работы

Целью лабораторной работы является получение навыков определения поэлементный состав конечного множества по предикату (логическому условию на универсуме).

2. Задание

Дан универсум всех возможных элементов множеств _U и одноместный предикат , определенный на нем. Определить состав множества, порожденного предикатом, то есть множества, состоящего из тех элементов универсума, для которых значение предикатаистинно, то есть равно 1. Выполнить 10 пунктов задания для следующих одноместных предикатов:

3. Краткие теоретические положения

Пусть   универсум, то есть совокупность всех возможных объектов данной задачи. Предикатом , где , называется функция , определенная на универсуме и принимающая два значения: 1  истина и 0  ложь. Множеством , порожденным данным предикатом, называется множество , то есть множество таких объектов, для которых данный предикат истинен.

Пример 3.1. Пусть   множество студентов вуза, универсум данной задачи. Универсум состоит из объектов вида , где   некоторый студент данного вуза. Объект обладает рядом характеристик, полей. Например, имеется поле .возраст  возраст данного студента. Рассмотрим предикат , то есть предикат принимает значение «истина» для студентов не младше 18 лет и только для таких студентов. Тогда множество   это множество студентов данного вуза, которые не младше 18 лет. То есть .

При построении необходимых предикатов используюся логические функции, то есть функции, принимающие значения в множестве {0,1}.

Основными в двузначной логике являются следующие функции:

Отрицание – функция , принимающая значения 1, когда , и значение 0, когда .

Дизъюнкция – функция , принимающая значение 0 тогда и только тогда, когда оба аргумента имеют значение 0.

Конъюнкция – функция , принимающая значение 1 тогда и только тогда, когда оба аргумента имеют значение 1.

Импликация – функция , равная 0 тогда и только тогда, когда,, то есть посылка выполняется, а заключение нет. В остальных случаях импликация равна 1, то есть не нарушается.

Равносильность это функция , равная 1 тогда и только тогда, когда значения ее аргументов совпадают, то есть оба равны 0 или оба равны 1. При разных значениях аргументов равносильность равна 0.

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

Рассмотрев выражение для P(x) определяем, что , еслиx  натуральное число, которое больше 10, не больше 20 и которое делится на 5. Получаем . То есть данному набору требований удовлетворяет только одно число 15. Множество {15}и служит ответом в данной задаче.

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

Предикатом (n-местным) от n переменных называется функция, принимающая значения 0 и 1.

Например,  двуместный предикат, определенный на , означающий, то есть тот факт, что первый аргумент данного предиката не меньше второго. ТакQ(3,4) = 0, так как высказывание ложно,Q(5,1) = 1, так как высказывание истинно.

Предикат становится высказыванием, если вместо n его аргументов подставить определенные значения. Предикат называется 0-местным, если он вообще не имеет аргументов, то есть является просто высказыванием.

Из n-местного предиката стандартным образом образуются (n-1)-местные путем использования специальных знаков называемых кванторами, «» квантор всеобщности и «_»  квантор существования.

Например, применение знака «_» к аргументу x в вышеописанном предикате Q приводит к образованию одноместного предиката , определенного на множествеN натуральных чисел, причем  верно, а , то есть неверно, так как не для всехвыполняется свойство,

Например, если не выполняется. Поэтому построенный одноместный предикат характеризуется значениямиQ₁(1) = 1, Q₁(y) = 0, при y = 1.

К двуместному предикату Q(x,y) можно применить также квантор «» квантор существования. Тогда получаем другой одноместный предикат . ПредикатQ₂(y) равен 1 при всех значениях y, так как для любого числа у всегда найдется такое х, что . Таким образом, Q₂(y) = 1 при всех у.

И так, применение кванторов, существования () и всеобщности () приводит к уменьшению местности предиката на 1. Переменная, которая стоит под знаком квантора, называетсясвязанной (в предыдущих примерах это х), от неё полученный новый предикат (кванторный предикат) не зависит. Остальные переменные – свободные.

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

Пусть, например,  0-местный предикат, в котором все переменные связаны, то есть это высказывание и Q₃ имеет определенное значение 0 или 1, ложь или истина. В словесной форме читается как «существует натуральное число у такое, что для всех натуральных чисел х выполняется неравенство ». Ясно, что значениемQ₃ является 1, истина, так как можно взять у = 1, то есть указать тот элемент, о существовании которого утверждается.

Пример 3.3.  универсум данной задачи, то есть отрезок множества натуральных чисел от 3 до 20, включающий все натуральные числа в указанном промежутке, включая данные. Дан двухместный предикат, определенный на , имеющий вид, то есть предикатистинен на паре чиселтогда и только тогда, когда числа различны и первое число в данной паре делится нацело на второе, Дан предикат, получаемый применением квантора существования по переменнойк исходному предикату. Требуется найти множество , то есть множество истинности предиката . Для этого заметим, чтотогда и только тогда, когда для данного числасуществует число, которое является делителем числа x. То есть в множество необходимо включать те числа, которые имеют делители в этом же множестве, отличные от данного числа. К таким относятся: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20. Таким образом, получаем ответ: ={4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}.

4. Пример выполнения задания

{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 17, 18, 19, 20}.

_. x принадлежит , больше 3, меньше или равно 8 и четно.

Ответ: ={4,6,8};

Упростим второе условие:

, так как  целое

принадлежит , больше 1, меньше или равно 5 и четно.

Ответ: ={2, 4};

Упростим первое условие: ;

Упростим второе условие:

принадлежит , больше 4, меньше или равно 6 и нечетно.

Ответ: ={5};

Упростим первое условие:

Упростим второе условие:

;

принадлежит , больше или равно 4, меньше или равно 6 и при делении на 3 дает остаток 1.

4 = 31+1 = 1;

5 = 3∙1 + 2, 2  1;

6 = 3∙2 + 0, 0  1.

Ответ: ;

принадлежит и таков, что существует, причем, такое, чтоделится нацело на.

Проверяем каждое число.

{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 17 ,18, 19, 20}.

2  нет; 3  нет; 4 = 2∙2, 2 да, 5  нет, 6 = 2∙3, 2 да, 7  нет, 8 = 2∙4, 4 да, 9 = 3∙3, 3 да, 10 = 2∙5, 2 да, 11  нет, 12 = 2∙6, 2 да, 13  нет, 17  нет, 18 = 2∙9, 2 да, 19  нет, 20 = 2∙10, 2 да.

Ответ: {4, 6, 8, 10, 12, 18, 20}.

принадлежит , четно и или больше 8 или меньше или равно 4.

Ответ: {2, 4, 10, 12, 18, 20}.

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

Ответ: {2, 3}.

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

Проверяем каждое число.

{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,17,18,19,20}.

2  нет, 3  нет, 4 = 2+2  да, 5 = 2+3  да, 6 = 2+4  да, 7 = 2+5  да, 8 = 2+6  да, 9 = 2+7  да, 10 = 2+8  да, 11 = 2+9  да, 12 = 2+10  да, 13 = 2+11  да, 17 = 4+13  да, 18 = 6+12  да, 19 = 6+13  да, 20 = 2+18  да.

Ответ: {4, 5, 6, 7, 8, 9,10, 11, 12, 13, 17, 18, 19, 20}.

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

Проверяем каждое число.

{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 17, 18, 19, 20}.

2  да, 3  да, 4 = 2∙2  нет, 5  да, 6 = 2∙3  нет, 7  да, 8 =2∙4  нет, 9 = 3∙3  нет, 10 =2∙5  нет, 11  да, 12 = 2∙6  нет, 13  да, 17  да, 18 = 2∙9  нет, 20 = 2∙10  нет.

Ответ: {2, 3, 5, 7, 11, 13, 17, 19}.

принадлежит и таков, что существуют, такие, что выполняется условие, то есть элементможно представить в виде произведения каких либо элементов из множества, причем должно выполняться также дополнительное условие, что эти элементы должны быть больше 1.

Проверяем каждое число.

{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,17,18,19,20}.

2  нет, 3  нет, 4 = 2∙2  да, 5  нет, 6 = 2∙3  да, 7  нет, 8 = 2∙4  да, 9 = 3∙3  да, 10 = 2∙5  да, 11  нет, 12 = 2∙6  да, 13  нет, 17  нет, 18 = 2∙9  да, 20 = 2∙10  да.

Ответ: {4, 6, 8, 9, 10, 12, 20}.

5. Индивидуальные задания

   № вар.	U
   	{2 5 8 4 3 19 23 18 11 30}
   	{10 2 3 5 9 4 19 6 18 7}
   	{19 13 14 10 8 15 16 5 12 3}
   	{10 2 3 5 8 4 19 6 18 7}
   	{11 2 3 5 9 4 19 6 18 7}
   	{10 2 3 4 13 5 19 6 18 7}
   	{10 2 3 14 13 5 19 6 18 7}
   	{1 2 3 5 9 4 19 6 18 7}
   	{1 2 3 5 9 4 19 6 18 7}
   	{19 13 14 10 8 15 16 6 12 3}
   	{2 4 3 14 8 5 19 6 18 7}
   	{9 4 3 14 8 5 19 6 18 7}
   	{9 4 3 11 8 5 19 6 18 7}
   	{9 10 3 11 8 5 19 6 18 7}
   	{9 10 3 11 8 5 16 6 18 7}
   	{9 10 4 11 8 5 16 6 18 7}
   	{17 2 3 5 9 4 19 6 1 7}
   	{9 10 4 11 8 5 16 6 12 7}
   	{19 10 4 11 8 5 16 6 12 7}
   	{19 13 4 11 8 5 16 6 12 7}
   	{19 13 4 11 18 5 16 6 12 7}
   	{19 13 14 11 18 5 16 6 12 7}
   	{19 13 14 11 18 15 16 6 12 7}
   	{19 13 14 10 18 15 16 6 12 7}
   	{19 13 14 10 18 15 16 6 12 3}
   	{17 2 3 5 9 4 19 6 8 7}
   	{17 2 12 5 9 4 19 6 8 7}
   	{17 2 12 5 9 14 19 6 8 7}
   	{11 2 12 5 9 14 19 6 8 7}
   	{11 2 12 5 9 14 19 6 10 7}
   	{11 2 12 5 9 14 19 6 10 3}
   	{11 2 7 5 9 14 19 6 10 3
   	{11 2 7 5 12 14 19 6 10 3}
   	{11 2 7 9 12 14 19 6 10 3}
   	{11 5 7 9 12 14 19 6 10 3}
   	{11 5 7 9 12 14 19 16 10 3}
   	{1 5 7 9 12 14 19 16 10 3}
   	{15 5 7 9 12 14 19 16 10 3}
   	{15 5 7 9 2 14 19 16 10 3}
   	{15 5 7 9 12 14 19 16 10 3}
   	{15 5 17 9 12 14 19 16 10 3}

6. Контрольные вопросы

1. Дать определение одноместного предиката.

2. Дать определение двухместного предиката.

3. Как определяется множество , соответствующее одноместному предикату .

4. Как используется квантор существования .

5. Как используется квантор всеобщности .