Теорема 1

Над алфавитом мощностью m можно создать ровно mⁿ слов длиною n.

Доказательство:

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

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

Дата добавления: 2014-12-07