Файл: Учебное пособие по изучению курса Дискретная математика для студентов направления 230100 Информатика и вычислительная техника.pdf

53
3.4.3. Функциональная полнота
Класс функций F называется полным, если его замыкание совпадает с
P
n
:
Другими словами, множество функций F образует полную систему,
если любая функция реализуема в виде формулы над F.
Теорема.
Пусть заданы две системы функций и
Тогда, если система F – полная и все функции из F реализуемы формулами над G, то система G тоже полная.
Доказательство. Пусть h – произвольная функция,
. Тогда
[F]=P
n
, следовательно, h реализуема формулой
, базисом которой является
F (
). Если выполнить замену подформулы fi на подформулу в
формуле
, то мы получим формулу над G.
Следовательно, функция h реализуется формулой
Примеры.
1. Система {
} – полная, т. к. любая логическая операция может быть выражена через дизъюнкцию, конъюнкцию и отрицание;
2. Система {
} – полная, т. к.
3. Система {
} – полная, т. к.
4. Система {|} – полная, т. к.
, а {
}и{
} – полные системы.
5. Система {
} – полная, т. к.
Представление логической операции системой{
}называется полиномом Жегалкина. Таким образом, всякая логическая операция представима в виде где
- сложение по модулю 2, знак · обозначает конъюнкцию,
Теорема Поста: Система логических операций полна тогда и только тогда, когда она содержит хотя бы одну функцию, не сохраняющую 0, одну функцию, не сохраняющую 1, хотя бы одну несамодвойственную функцию,
хотя бы одну нелинейную функцию и хотя бы одну немонотонную функцию.
Пример.
Докажем полноту системы {
⊕
,
∨
,1}.
f
T
0
T
1
T*
T
L
T
M
В
каждом столбце должен быть хотя бы один
«-»
x
⊕
y
+
-
-
+
- x
∨
y
+
+
-
-
+
1
-
+
-
+
+
1.
Проверка на принадлежность классу T
0

54 2.
Проверка на принадлежность классу T
1 3.
Проверка на принадлежность классу T*.
4.
Проверка на принадлежность классу T
L
5.
Проверка на принадлежность классу T
M
f(0,0)=0
f(0,1)=1
f(1,0)=1
f(1,1)=0
f(0,0)=0
f(0,1)=1
f(1,0)=1
f(1,1)=1

55
Контрольные вопросы
1. Что такое высказывание? Привести примеры простых и сложных высказываний.
2. С помощью каких логических операций можно получать сложные логические высказывания?
3. Привести примеры булевых функций.
4. Что такое формула? Привести примеры формул.
5. Каким образом связаны между собой формулы и функции?
6. Что такое базис формулы?
7. Какие формулы называются равносильными? Привести примеры равносильных формул.
8. Какими способами можно получать новые правильно построенные функции?
9. Привести примеры ДНФ, КНФ, СДНФ, СКНФ.
10.Сформулировать алгоритмы получения:
a. СДНФ из ДНФ;
b. СКНФ из КНФ;
c. СДНФ из СКНФ;
d. СКНФ из СДНФ.
11.Какие формулы не имеют СДНФ? Какие формулы не имеют СКНФ?
12. Как доказать, что всякую булеву функцию можно представить некоторой формулой логики высказываний?
13.Сформулировать алгоритм минимизации функций.
14.Что такое замыкание системы булевых функций?
15.Привести примеры замкнутых классов булевых функций.
16.Какой класс функций называется полным? Привести примеры.
17.Используя теорему Поста, доказать, что следующие системы булевых функций являются полными:
a.
;
b.
;
c.
F:\пособие\Д М (П особие)2.doc
F:\пособие\Теория автоматов и формальные грамматики.doc

56
Список литературы
1. Соловьев А. Е., Галкин В. С. Основы дискретной математики.
Учебное пособие. Изд. Пермского ун-та, 1977, 80с.
2. Новиков Ф. А. Дискретная математика для программистов.
СПб.:Питер, 2004.-302с.
3. Шапорев С. Д. Дискретная математика. Курс лекций и практических занятий. СПб.:БХВ-Петербург, 2006.-400с.
4. Капитонова Ю. В. и др. Лекции по дискретной математике.
СПб.:БХВ-Петербург, 2004.-624с.
5. Нефедов В.Н. , Осипова В. А. Курс дискретной математики: Учебное пособие. – М.:Изд-во МАИ, 1992.-264с.
6. Аляев Ю. А. , Тюрин С. Ф. Дискретная математика и математическая логика. М.:Финансы и статистика, 2006.-368с.