1- 9_Математическая логика и теория алгоритмов

Министерство образования РФ

Томский государственный университет

систем управления и радиоэлектроники (ТУСУР)

ТМЦ ДО

Контрольная работа №1

по дисциплине «Математическая логика и теория алгоритмов »

авторы: В. М. Зюзьков

А. А. Шелупанов

V9

Выполнил:

студент ТМЦДО

специальности 075500

№1. Вставьте между множествами символ или , так чтобы получилось истинное высказывание:

{1,2} ?{1,2,{1,2}};

В данном случае можно поставить оба знака, так как каждый эл-т множества {1,2} т.е. 1 и 2 есть элемент множества {1,2,{1,2}}, и само множество {1,2} принадлежит {1,2,{1,2}}.

№2. №3. Перечислить все элементы из следующих множеств:

{0}

Если х есть включение в пустое множество то и множество х - пустое.

№3. Приведите пример множеств А, В и С таких, чтобы выполнялись условия АВ, ВС, АС.

А={1}

В={{1},3}

С= {1,2,4}

№4. Для бинарного отношения р={<x, y>|x<1} найдите D и R

D=(-1;+1)

R=(-;1)

№5. Докажите тождество (A\B)*C=(A*C)\(B*C).

Докажем на примере.

Пусть А={1;0}, B={3;1},C={4}

(A\B)={0}

(A\B)*C={<0.4>}

Ответ левой стороны.

(A*C)={<1;4>,<0,4>}

(B*C)={<3,4>,<1,4>}

(A*C)\(B*C)= {<0.4>}.

Ответы совпали ч.т.д.

№6. Пусть А={a- конечное множество. Определим отображение

f: P(A) следующим образом

f(B)= <a, где =0, если В, и =1, если В.

Докажите что f- биекция.

=0, если В-свидетельствует о том, что отображение иньективно, а =1, если В о ее сюрьективности.

f осуществляет взаимнооднозначное соответствие между множествами А и В, а значит биективно.

№7. Какие отображения иньективны, сюрьективны?

F:R;

Отображение, иньективно но не сюрьективно.

№8. Пусть отношение р определено на множестве (N- множество натуральных чисел {1,2,3,…}: <x,y> p <u,v> x+v=y+u. Доказать, что р- отношение эквивалентности.

Доказательство:

Отношение рефлексивно: <x,y>p<x, y>, так как x+y=y+x.

Отношение симметрично: если <x,y> p <u,v>, то <u,v>р<x,y>, так как из x+v=y+u следует что и u+y=v+x

Отношение транзитивно: если <x,y> p <u,v>, <u,v>p<w,z>, так как прибавив левые и правые части x+v=y+u u+z=v+w, получаю x+z=y+w.

Значит по определению отношение эквивалентно ч.т.д.

№9.Построить линейный порядок: а) на множестве ; б) на множестве N{все конечные последовательности из натуральных чисел}.

А){1,4,9,16}

Б){4,16,64}

№10. Если р - частичный порядок на Х, то р также частичный порядок на Х.

Это утвержден верно так как свойства порядка от этого не изменятся, а это значит что он так же будет частичным.