Практическое задание по дискретной математике

Практическое задание по дискретной математике

Вариант 13

1. Описать математическую модель заданного объекта. Степень детализации – произвольная:

а) трапеция;

б) тетрадь.

2. Дана матрица чисел А(3,3). Найти сумму всех четных чисел. Описать инвариантную, аналитическую, алгоритмическую и схемную модель решения задачи.

3. Задать различными способами множество M всех чисел, являющихся степенями двойки: 2, 4, 8, 16, …, не превышающих 300.

4. Задать в явном виде (списком) булеан  множества U, если U = {a₁, a₂, a₃, a₄}. Какова будет его мощность?

5. Пусть U = {1, 2, 3, 4, 5, 6}, A = {1, 3, 4}, B = {2, 3}, C = {1, 4, 6}.

Найти:  а) A È B;  б) A Ç B;  в) A \ B;  г) B \ A; д); е) ; ж)  з) ; и) АÇ;  к) (B\A)È .

6. Составить матрицы отношений, заданных на системе множеств , М = {a, b, c}: R – «являться нестрогим включением». Определить D(R) и Q(R).

7. Задать различными способами отношение R на множестве M × M. Определить свойства данного отношения.

R – «быть больше». M = {3, 7, 8, 12, 15, 16}

8. Пусть R₁ и R₂ – отношения на N:

R₁ = {(a, b): b = a + 1; a, b Î N}

R₂ = {(a, b): b = a² + 1; a, b Î N}

Определить составные отношения R₁°R₂, R₁°R₁ = R₁⁽²⁾, R₂°R₂=R₂⁽²⁾.

9. Определить пошагово значение истинностной функции при следующих заданных значениях переменных.

( x₁ Ú ( x₂ => x₁ )) & (x₁ => x₂)

10. Имеет ли место равносильность?

11. Привести к ДНФ и СДНФ:

( Ú )( Ú )

12. Привести к КНФ и СКНФ:

13. Построить КНФ по заданной ДНФ:

( Ú )( Ú )

14. Построить СДНФ и СКНФ для функции f (x₁,x₂,x₃) со следующей таблицей истинности:

15 . Пусть P₁ и P₂ обозначают высказывания:

P₁ –эти прямые перпендикулярны, 

P₂ –эти прямые имеют точку пересечения.

Записать, как читаются следующие символические выражения:

а) Ø P₁

б) P₁ Ú P₂

в) P₁ & P₂

г) P₁ Þ P₂

д) P₁ Û P₂

е) P₁ Å P₂

Определить истинность выражения, если это возможно.

16. Следующие сложные высказывания расчленить на простые и записать с помощью математической символики:

а) на улице идет дождь, значит надо взять зонт

б) на каникулы Лена поедет либо в Испанию, либо в Италию,

в) кот Вася любит есть рыбу и играть в мячик.

17. Связать свободную переменную квантором так, что бы получить истинное высказывание (предметная область – множество действительных чисел):

18. Пусть P(x, y) – двухместный предикат «окружность x вписана в треугольник y». Записать высказывания, определить значения их истинности, построить отрицания данных высказываний:

.

19. Записать высказывания в предикатной форме, используя кванторы. Построить отрицания, а затем перевести обратно в литературное высказывание так, что бы отрицание не начиналось со слов «не» или «неверно, что»:

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

РЕШЕНИЕ

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

С помощью данной математической модели решаются задачи построения крыш домов, где необходимо знать размер основания, боковых сторон и высоты.

б) Тетрадь – четырехугольник, у которого все углы прямые и противолежащие стороны попарно параллельны. Данную модель используют в магазинах канцтоваров. Необходимо знать количество листов, в клетку или линию, с толстым или тонким переплетом.

2. Инвариантная модель решения задачи:

   Дано: матрица А (3,3)

   Найти: Ʃ четных чисел S:S+A[I, J] mod2 = 0

   Аналитическая модель:                                               Алгоритмическая модель:       

   S=S+A[i,j] mod 2=0                                                      Присвоим: S=0;

                                                                                          Задаем цикл:  for i=1 to 3 do

                                                                                          for j=1 to 3 do

                                                                                          If A[I, J] mod2 = 0,

                                                                                          S=S+A[I, J]

 Схемная модель:

3. Перечислением: M = {2, 4, 8, 16, ..., 300}      2⁸ = 256, т.е. больше 300

Порождающей процедурой: а) 2ⁿÎM; б) если nÎN, то 2ⁿ; в) n ≤ 8;

Характеристическим свойством элементов: M = {n:n – целое положительное число, не    превышающее 8} или M = {n:nÎN и 2ⁿÎN, n ≤ 8}

4. U = {a₁,a₂,a₃,a₄}

 = {Æ, {a₁}, {a₂}, {a₃}, {a₄}, {a₁,a₂}, {a₁,a₃}, {a₁,a₄}, {a₂,a₃}, {a₂,a₄}, {a₃,a₄}, {a₁,a₂,a₃}, {a₁,a₂,a₄}, {a₂,a₃,a₄}, {a₁,a₃,a₄}, {a₁,a₂,a₃,a₄}}

|| =2⁴=16

5. U = {1, 2, 3, 4, 5, 6}, A = {1, 3, 4}, B = {2, 3}, C = {1, 4, 6}.

а) A È B = {1,2,3,4}; 

б) A Ç B = {3}; 

в) A \ B = {1,4}; 

г) B \ A = {2};

д) = U \ A = {2,5,6};

е)  = U \ B = {1,4,5,6};

ж)= (A \ B) È (B \ A) = {1,4}È {2}= {1,2,4};  

з) = U \ (A Ç B) = {1,2,3,4,5,6} \ {3} = {1,2,4,5,6,};

и) АÇ = A Ç (U \ B) = {1,3,4} Ç {1,4,5,6} = {1,4}; 

к) (B\A)È  = (B \ A) È (U \ C) = {2} È {2,3,6} = {2,3,6}.

 = {a,b}, {a,a}, {a,c}, {b,b}, {c,c}, {b,c}

D (R) = {a,b,c}

Q (R) = {a,b,c}

7. R – «быть больше». M = {3, 7, 8, 12, 15, 16}

R  M × M

R = {{a,b}: a, bÎM; a > b} – антирефлексивно, транзитивно

R = {(7,3), (8,3), (8,7), (12,3), (12,7), (12,8), (15,3), (15,7), (15,8), (15,12), (16,3), (16,7), (16,8), (16,12), (16,15)}

8. R₁ = {(a, b): b = a + 1; a, b Î N}

R₂ = {(a, b): b = a² + 1; a, b Î N}

R₁°R₂ = {(a,b): (a,c) ÎR₁; (c,b) ÎR₂; a,b,c Î N} = {(a,b): c = a+1; c²+1=b; a,b,c ÎN} = {(a,b):     

(a+1)²+1=b; a,b ÎN} = {(1,5), (2,10), (3,17),..}

R₁⁽²⁾ =R₁°R₁ = {(a,b): a+1=b; a,b ÎN} = {(1,2), (2,3), (3,4), (4,5),..}

R₂⁽²⁾=R₂°R₂ = {(a,b): a⁴+1=b; a,b ÎN} = {(1,2), (2,17), (3,82),..}

9. ( x₁ Ú ( x₂ => x₁ )) & (x₁ => x₂)

10.

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

Левая часть. x® yz=x Ú (y ˄ z)

Правая часть. ( x®y)( x®y)=( x ˅y) ˄ ( x ˅ z) =    x ˅ (y ˄ z)

Равносильность доказана

11. ( Ú ₃)( Ú ₃) = ₃)

Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности.

Далее, рассматриваются значения переменных, при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

Т.о. СДНФ запишется в виде:. ₃)= 

12. =()()

СКНФ запишем в виде:

=

13. ( Ú ₂)( Ú ) =

( Ú ₂)( Ú ) =.

Левая часть равенства – форма, записанная в КНФ, а правая – в ДНФ

14.  

f (x₁, x₂, x₃) = (,,x₃ ) Ú (, x₂, x₃) Ú (x₁,, x₃) Ú (x₁, x₂, x₃) – CДНФ

f (x₁, x₂, x₃) = (x₁, x₂, x₃)( x₁,, x₃)(, x₂, x₃)(,,x₃) – СКНФ

15. а) эти прямые не перпендикулярны

 б) прямые перпендикулярны или имеют точку пересечения

 в) эти прямые перпендикулярны и имеют точку пересечения

 г) если прямые перпендикулярны, то прямые имеют точку пересечения

 д) эти прямые перпендикулярны тогда и только тогда, когда имеют точку пересечения

 е) если эти прямые перпендикулярны, то они не имеют общую точку. Если эти прямые не перпендикулярны, то они имеют точку пересечения.

16. а) на улице идет дождь, значит надо взять зонт.

 А – на улице идет дождь;

 В – надо взять зонт;

 А Þ В

б) на каникулы Лена поедет либо в Испанию, либо в Италию.

А – На каникулы Лена поедет;

В – Либо в Испанию;

С  - Либо в Италию.

А ® (B Å C)

в) кот Вася любит есть рыбу и играть в мячик.

А – кот Вася любит;

В – есть рыбу;

С – играть в мячик.

А ® (В & С)

17. а) |x| = x ; ( – Данное высказывание истинно.

б)  ;  – Данное высказывание является истинным. [ – область           значения.

в) ;  – Данное высказывание верно.[- область значения.

г) ;  - Данное высказывание является истинным.

18.

а)  - для любой окружности  и треугольника , окружность  вписана в треугольник . Данное высказывание ложно. Построим отрицание:

б)  - есть такая окружность , которая вписана в любой треугольник . Данное высказывание ложно. Построим отрицание:

в)  - для любой окружности , существует треугольник , описанный около него. Данное высказывание является истинным. Построим отрицание:

г)  - существует такая окружность  и треугольник, что окружность  вписана в треугольник .  Данное высказывание является истинным.

19. В каждом городе хотя бы одна улица застроена только такими домами, в которых есть однокомнатные квартиры.

 A – город;  B – улица;  D – дом;  Q(F) – однокомнатные квартиры.

 – высказывание, удовлетворяющее нашему условию.

 Построим отрицание: