lec09_1
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса.
Объем курса.
16 лекционных и 8 практических занятий.
Темы лекционных занятий.
1.Элементы теории множеств. Булева алгебра.
2.Булевы вектора и булевы функции.
3.ДНФ, СДНФ, КНФ, СКНФ.
4.Минимизация ДНФ.
5.Метод Карно и метод Квайна.
6.Двойственные функции.
7.Функциональная полнота. Полные классы. Алгебра Жегалкина. Интегрирование и дифференцирование БФ.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста. k-значные логики.
10.Исчисление высказываний.
11.Исчисление предикатов. Основные. положения. Кванторы
12.Нормальные формы. Доказательства.
13.Конечные автоматы.
14.Соединения и синтез автоматов.
15.Машина Тьюринга.
16.ЧРФ и НАМ.
2
Лекция 9.
Теорема Поста о ФПС. k-значные логики.
9.1.Теорема Поста.
9.2.Доказательство теоремы о функциональной полноте.
9.3.k-значные логики.
Часть 1.
Теорема Поста.
Теорема 9.1. Поста о функциональной полноте.
Система булевых функций = {f1, f2, … fn}, является функционально полной она не содержится целиком ни в одном из основных замкнутых классах функций.
Другими словами: для каждого из основных классов: T0, T1, L, M, S – найдется из хотя бы одна функция которая в нем не лежит.
!!! fi может быть одна и та же.
|
|
T0 |
T1 |
L |
M |
S |
|
1 |
- |
+ |
- |
+ |
- |
fi, |
2 |
+ |
+ |
|
- |
+ |
|
|
|
|
|
|
|
|
i |
|
- |
|
|
|
n |
+ |
+ |
+ |
+ |
- |
5
Лемма 9.1. О булевой функции, не сохраняющей константу «0».
Если булева функция не сохраняет константу «0», то из нее подстановкой вместо каждого аргумента xi можно получить либо константу «1», либо .
Доказательство:
Булева функция f (x1,x2,…xn) не сохраняет константу «0».
Заменяем каждый ее аргумент xi на x (такая подстановка допустима по условию леммы) и получим функцию одного аргумента
(x) = f (x,x,…x).
Исследуем ее. Т.к. f (x1,x2,…xn) T0
(0) = f (0,0,…0) = 1.
Если (1)=1, то (x) – константа «1». Если (1)=0, то (x)= .
Пример 9.1. Рассмотрим функции, не сохраняющие константу «0»: ↓,| и →, ←. Подставляя в них вместо аргументов переменную x, получаем:
x ↓ x = x | x = ?; x → x = x ← x = 1.
6
Лемма 9.2. О несамодвойственной функции.
Если булева функция f (x1,x2,…xn) не самодвойственна (f S), то, подставляя в нее вместо x1,x2,…xn переменную x или , можно получить БФ – (x),
тождественно равную const (0 или 1). (x) = 10 .
Доказательство:
Введем |
, |
если α = 1; |
= 1 |
|
||
α |
, |
если α = 0; |
= 0 |
Из 0 = 0; 1 = = 1. 0 = α , 1 = . |
||
Рассмотрим (x) = ( |
|
|
|
|
||
|
1, 2 , …, ). |
|
||||
|
|
1 |
2 |
|
|
|
Поскольку (x1,x2, … xn) несамодвойственная, то Вn, =( 1, 2,…, n):*( ) ( ), иначе бы эта функция была бы самодвойственной.
Другими словами (α1, α2, … α ) ( 1, 2 …, n) два значения:(α1, α2, … α ) = ( 1, 2, …, n), хотя бы на одном наборе.
Покажем, что (0) = (1).
(0) = (0 1,0 2,…,0 ) = (α1, α2, … α ) = ( 1, 2…, n) = (1 1,1 2,…,1 ) = (1).
7
Пример 9.1. Проверка несамодвойственности.
(x1,x2,x3) = (10110100).
Проверим, что S (не является самодвойственной).
S : (α1, α2, α3) = ( 1, 2, 3).= (010). ( ) = ( , , ).
Покажем, что (0) = (1).
(0) = (0 1,0 2,0 3) = ( , , ) = (010) = 1
(1) = (1 1,1 2,1 3) = ( , , ) = (101) = 1
S.
x1 |
x2 |
x3 |
|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
8
Лемма 9.3. О немонотонной функции.
Если БФ f (x1,x2,…xn) – немонотонная ( M), то, подставив в нее вместо одного из переменных x, а вместо остальных некоторые const (0 или 1), можно получить функцию (x) = .
Доказательство: конструктивно
(x1,x2, … xn) – немонотонная ( M) ( , ) Вn, где =( 1,…, n); =( 1,…, n):
; ( ) ( ).
Соединим две вершины , Вn куба некоторым путем (в направлении упорядоченности), проходящим по ребрам, т.е. Вn:
1 2 … k< , и .
i, i+1 – соседние вершины в кубе Вn они отличаются лишь одной координатой.
9
Лемма 9.3. О немонотонной функции.
Доказательство (продолжение):
Имеется ( ) = 1, ( ) = 0.
Пусть вариация значения функции происходит на паре соседних вершин i и i+1, отличающихся одной координатой хj. Т.е. ( i) = 1, ( i+1) = 0.
i = ( 1, 2, … j-1, 0, j+1, … n) i+1 = ( 1, 2, …, j-1, 1, j+1, … n)
(х) = ( 1, 2, …, j-1, х, j+1, … n).
Проверим, что (x) = :
(0) = ( 1, 2, …, j-1, 0, j+1, … n) = ( i) = 1 = x;
(1) = ( 1, 2, …, j-1, 1, j+1, … n) = ( i+1) = 0 = .
Ч.т.д.
10