Типовик

Дискретная математика

1. Упростите и проинвертируйте заданное выражение:

P = A \ B [ A \ B [ A \ C [ B \ C

Затем найдите элементы множества P, выраженного через множества:

A= f0; 3; 4; 9g; B = f1; 3; 4; 7g; C = f0; 1; 2; 4; 7; 8; 9g; I = f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g:

2.Упростите следующее выражение с учетом того, что A B C D I; A 6=

A \ B \ C [ C \ D [ B \ C \ D

3. Определите, какими из свойств обладает следующее отношение на множестве f1; 2; 3; 4; 5g: aRb () (a + b) mod 2 = 0

4.Составьте таблицу истинности и проверьте, является ли формула тавтологией:

((P ! Q) _ R) $ (P ! (Q _ R))

5.Представьте функцию в СДНФ с обязательным учетом числа аргументов, от которых она зависит. Номера минтермов упорядочить по возрастанию.

f(A; B; C; D) = (A + B + C)(A + C + BD)(C + D)

6. Представьте булеву функцию, зависящую от аргументов A; B; C; D в виде полинорма Жегалкина:

f(A; B; C; D) = (1; 2; 3; 4; 5; 7; 8; 11; 12; 13; 14; 15)

7.Найдите минимальные ДНФ и КНФ. Укажите число вхождений аргументов для минимальных ДНФ и КНФ.

=[(ACD ! B)(BC D)] ! [(AB ! BC) ! (B + D)]

8.Дан набор функций F , который не является функционально полной системой. Дополните это набор пятью различными функциями так, чтоб получившйся набор оставался функционально неполным.

F = ff1(A; B) = A ^ B; f2(A; B) = (A ! B) ^ A; f3(A; B) = A $ Bg

9. Докажите, что система функций является полной: f ; _; g