Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста (стр. 5 из 5)

Оскільки

, а , серед наборів знайдуться два сусідні і , такі що і . Нехай вони відрізняються в r-му розряді: , . Тоді визначимо функцію так: . Справді, тоді , і . Лема доведена.

Лема 4(про нелінійну функцію.) [1, ст. 11]. З будь-якої нелінійної функції алгебри логіки

, підставляючи замість усіх змінних , можна отримати або .

Доведення. Нехай

. Розглянемо поліном Жегалкіна цієї функції.

З її нелінійності випливає, що в ньому присутні складові виду

. Будемо вважати, що існує добуток . Таким чином, поліном Жегалкіна цієї функції виглядає так

,

Причому

Інакше кажучи,

такі, що .

Розглянемо допоміжну функцію

.

Тоді функція

Лему доведено.

Теорема 11

Cистема функцій алгебри логіки

є повною в тоді і тільки тоді, коли вона не міститься цілком в жодному із класів: .

Доведення

Необхідність. Нехай

– повна система, – будь-який з класів і нехай

Тоді

Отримане протиріччя завершує обґрунтування необхідності.

Достатність. Нехай

Тоді в

існують функції

Достатньо показати, що

Розіб’ємо доведення на три частини: отримання заперечення, констант і кон’юнкції.

1. Отримання

. Розглянемо функцію і введемо функцію . Так як функція не зберігає 0, . Можливі два випадки: або . Розглянемо функцію і аналогічним способом введемо функцію . Так як функція не зберігає одиницю, . Можливі також два випадки: або . Якщо хоч в одному випадку отримали шукане значення, то пункт завершений. Якщо ж в обидвох випадках отримали константи, то згідно з лемою 3(про немонотонну функцію), підставляючи функцію замість усіх змінних константи і тотожні функції, можна отримати заперечення. Отже, заперечення отримане.

2. Отримання константи 0 та 1. Маємо

. Згідно з лемою 2(про несамодвоїсту функцію), підставляючи замість усіх змінних функції заперечення(отримане в попередньому пункті) і тотожну функцію, можна отримати константи

Константи отримані.

3. Отримання кон’юнкції

. Маємо функцію . Згідно з лемою4(про нелінійну функцію), підставляючи у функцію замість усіх змінних константи і заперечення(які були отримані у попередніх пунктах доведення), можна отримати кон’юнкцію або заперечення кон’юнкції. Проте на першому етапі заперечення вже отримано, отже, завжди можна отримати кон’юнкцію

Кон’юнкція отримана.

Отже,

Остання рівність випливає з другого пункту теореми 2. Враховуючи лему 1 достатність доведена.

Розділ 4. Постановка і реалізація задачі

Постановка задачі.

Контрольні приклади виконання програми

Висновки

Список використаної літератури

1. Алексеев В.Б., Поспелов А.Д. Дискретная математика. – М., 2002. – 44с.

2. Белоусов А.И., Ткачев С.Б. Дискретная математика. –М.,2004. – 743с .

3. Мартинюк О.М. Основи дискретної математики. – Одеса: Наука і техніка, 2008.-300с.

4. Борисенко О.А. Лекції з дискретної математики (множини і логіка): навчальний посібник. – 3-є вид., випр. і доп. – Суми: ВДТ «Університетська книга», 2002. – 180 с.

5. Плотников А.Д. Дискретная математика: учебное пособие. – М.: Новое знание, 2005. – 288 с.

6. Основи дискретної математики Капітонова Ю.В., Кривий С.Л., Летичевський О.А. та ін.– К.: Наукова думка, 2002. – 580 с.