1. (10 баллов) докажите, что формула (p or q) and (-p or r) - > (q or r) является тавтологией.
2. (10 баллов) убедитесь, что следующие отношения, указанные в множестве всех функций из множества Z к множеству Z, являются соотношениями эквивалентности. Перечислите, какие условия отношения эквивалентности выполняются, а какие нет. Если отношение является отношением эквивалентности, опишите его классы абстракции.
а) {(f, g) : f(0) = g(0) и f (1) = g(1)}
b) {(f, g): f(x) - g(x) = 1 для каждого x ? Z}
3. (10 баллов) примените математическую индукцию, чтобы доказать, что n! < n^n, где n - натуральное число, большее 1.
4. (10 баллов) найдите f (n) если f - это рекурсивно определенная строка следующим образом f (0) =6, f(1) = 2 и для n >0, f(n + 1) = - 2f(n)+3f(n-1).
5. (10 баллов) какое наименьшее количество городских кодов, необходимых для обеспечения того, чтобы 25 миллионам телефонов в вашем регионе могли быть назначены отдельные 10-значные номера телефонов? (Предположим, что номера телефонов имеют формат NXX-NXX-XXXX, где первые три цифры образуют код города, N-цифра от 2 до 9 включительно, а X - любая цифра.) Примените правило ящика Дирихле.
6. (10 очков) на сколько способов можно разложить 5 шариков в 7 коробках, если каждая коробка может содержать не более одного шарика и
а) и шарики, и коробки различимы (помечены)?
б) шарики различимы, а коробки неразличимы?
в) шарики неразличимы, а коробки различимы?
d) и шарики, и коробки неразличимы?
