ĐỀ KIỂM TRA TOÁN RỜI RẠC

ĐỀ KIỂM TRA TOÁN RỜI RẠC

Câu 1:
a) Chứng minh $((p\to q \wedge (q\to r)))\to(p\to r)$ là hằng đúng.
b) Chứng minh suy luận sau \[\begin{array}{l}
t \to u\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left( 1 \right)\\
r \to \left( {s \vee t} \right)\,\,\,\,\,\,\,\,\,\left( 2 \right)\\
\left( {\neg p \vee q} \right) \to r\,\,\,\,\left( 3 \right)\\
\underline {\neg \left( {s \vee u} \right)\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left( 4 \right)} \\
\therefore p
\end{array}\]
Câu 2: Chứng minh $3^n$ là $O(5^n)$ nhưng $5^n$ không là $O(3^n)$.
Giải
Do $3^n<5^n$ với mọi $n>0,n\in N$ suy ra $3^n$ là $O(5^n)$
Nếu $5^n$ là $O(3^n)$ thì đối với một C nào đó $5^n\le C3^n$ với mọi $n$ đủ lớn, tức $C\ge (\frac{5}{3})^n$ với mọi n đủ lớn.
Điều này không thể xảy ra nên $5^n$ không là $O(3^n)$.

Câu 3: Đếm chuỗi 8bits thỏa bit đầu là 1 hay 2 bit cuối là 0.