Сервер Методического Обеспечения вгуэс

Вид материала

Реферат

Содержание Индуктивный переход.

Подобный материал:

• Дипломная работа студента 545 группы, 334.18kb.
• Т. Н. Коржавина Принципы организации службы научного и методического обеспечения колледжа, 47.35kb.
• «sql*net», 239.02kb.
• Генезис развития теории и методики программно-методического обеспечения обучения, 145.89kb.
• Прозрачный прокси сервер на базе squid, ipfw и Freebsd, 8.5kb.
• Доклад «Три кита школьного образования: стандарты, учебники, егэ», 116.02kb.
• Справка по результатам самоаттестации методического объединения учителей русского языка, 447.26kb.
• Большой Сервер Недвижимости 31. 05. 2008: программа, 1328.13kb.
• Т. Г. Римская научный редактор, к и. н., доцент, директор филиала вгуэс в г. Находке, 2476.8kb.
• Владивосток: Изд-во вгуэс, 2005., 1071.2kb.

Тем не менее, в дальнейшем мы будем придерживаться принципа "разумной достаточности". То есть мы будем ставить скобок столько, чтобы выражение легко прочитывалось, но не так много, чтобы запутаться в них. В каждом конкретном случае будет ясно, что мы понимаем под принципом разумной достаточности.

Если высказывание F построено из логических переменных , то мы будем обозначать это так: .

Первая основная задача, которая здесь возникает, это вычислить значения истинности F, когда переменным придаются конкретные значения . В этом случае мы пишем: значение равно , где принимают значения 0 или 1. Пример был приведен в §1, поэтому сейчас мы поставим вопрос другой – на каком количестве наборов вообще надо считать значения . Другими словами – сколько существует наборов длины n из 0 и 1.

1. Теорема 3

Наборов длины n из 0 и 1 существует .

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

Обозначим это количество буквой и докажем ММИ, что .

Пусть n=1. Наборов длины 1 из 0 и 1 существует 2: (0) и (1), поэтому . Базис индукции заложен.

Индуктивное предположение. Допустим, что .

Индуктивный переход. Докажем, что . В самом деле, рассмотрим какой-нибудь набор из 0 и 1 длины k, скажем . Тогда из него можно получить ровно два набора длины k+1, а именно и . Значит, наборов длины k+1 в два раза больше, чем наборов длины k, то есть . Теорема доказана.

Существует общепринятый порядок выписывания наборов длины n из 0 и 1. Начинается этот список с нулевого набора – (0,0,..,0,0). Каждый следующий набор получается из предыдущего прибавлением 1 в двоичной арифметике. Заканчивается список единичным набором – (1,1,..,1,1). Тем, кто забыл или не знает двоичной арифметики, сообщаем необходимые и самые простые равенства: 0+0=0, 0+1=1+0=1, 1+1=10.

Составим списки наборов из 0 и 1 длины 3 и длины 4:

1) 0 0 0 2) 0 0 0 0

0 0 1 0 0 0 1

0 1 0 0 0 1 0

0 1 1 0 0 1 1

1 0 0 0 1 0 0

1 0 1 0 1 0 1

1 1 0 0 1 1 0

1 1 1 0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

1. Задача

Составьте список наборов длины пять.

1. Определение 4

Таблица истинности для высказывания имеет вид:


... 00...00 00...01 .................. ... ..................11...10 11...11

По сути дела, пример таблицы истинности был приведен в §1. Здесь же мы лишь дали необходимые обозначения и теоретические обоснования. В дальнейшем нам неоднократно придется строить таблицы истинности.