dysk (2)

MDiL KOLOKWIUM GRUPA B

Zadanie 1.(8 ptk) (a) Czy następujące zdanie jest tautologią?

(CP A Q) *> rj (p =► (q ■> r)j

(b) Korzystając z reguły podstawiania (a) w prawie zaprzeczenia implikacji P zastąp zmienną q przez (r => a) i zapisz zdanie P* logicznie równoważne z P.

Zadanie 2.(8 ptk) Dana jest relacja R określona na zbiorze A — {1,3,6,9,18,27,30,5,10} w następujący sposób:

(x, y) € R wtedy i tylko wtedy gdy x jest dzielnikiem y

(a)    Wykaż iż jest to relacja częściowego porządku

(b)    Narysuj diagram Hassego

(c)    Podaj element: największy, najmniejszy, minimaly i maksymalny

adanie 3.(8 ptk) Dany jest alfabet A = {x, y, z}. Podaj wzór rekurencyjny na liczbę słów Łn długości n utworzonych z alfabetu A, które zawierają parzystą liczbę liter z. Zamień wzór rekurencyjny na wzór jawny oraz wykaż, że wzór jawny jest poprawny.

wtenie i S ptk) Stosując metodę Rabina dla n = 31 19 odszyfruj liczbę 225.

Powodzenia}.