lec07_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
Лекция 7.
Функциональная полнота.
Часть 1.
Функциональная полнота системы функций.
Рассмотрим некоторую конечную совокупность булевых функций :
= {f1, f2, … fS} : Вn В1.
Если некоторую другую БФ (x1,x2, … xn): Вn В можно выразить через функции системы и представить ее в виде суперпозиций этих функций, то говорят, что представляется формулой над системой .
Система называется функционально полной (ФПС), если любую булеву функцию можно представить формулой над .
Исходя из определения СДНФ, СКНФ – система с |
? |
|
какими операциями будет функционально полна |
||
|
5
Пример 7.1. Доказательство ФПС для булева базиса – = { ,&, }.
= { ,&, }
Докажем, что функционально полна.
Согласно теореме 3.1 о КНФ и ДНФ БФ
иследствии из нее о СДНФ:
БФ можно представить в виде СДНФ, а любая СДНФ есть суперпозиция БФ из (считаем 0 x & ).
еще функционально полные системы.
Наша цель: найти их и получить теорему о полноте.
6
Теорема 7.1. О системе сравнения ФПС.
Теорема 7.1.
Пусть заданы две системы функций и 1, причем известно, что1 функционально полная. Если функции из 1 можно выразить через функции из , то тоже функционально полная.
Система 1 называется системой сравнения.
Доказательство: (от противного)
Пусть (x1,x2, … xn), = {f1, f2, … fS}, 1 = {g1, g2, … gr}.
(x1,x2, … xn) из полноты 1 следует, что представляется формулой над 1. Заменим в этой функции каждую gi формулой над , получим для формулу над . ч.т.д.
7
Теорема 7.2. О функциональной полноте системы двойственных функций.
Теорема 7.2.
Пусть = {f1, f2, … fS} – функционально полна. Тогда система, составленная из двойственных функций * = {f1*, f2*, … fr*} также функционально полна.
Доказательство:
(x1,x2, … xn) из функциональной полноты
представима формулой F над системой : =F .
Пусть f* - функция из *, тогда (согласно определения двойственности 6.1)
*(x1,x2, … xn) ( 1, 2, … )
и * представима какой-то формулой F над системой : *=F
(f*)* представима какой-то формулой F над системой *: (f*)* = F *. Согласно теореме 6.2: (f*)* = f, т.е. =F *.
Т.е. представима формулой над системой * * функционально полна.
8
Часть 2.
Важнейшие полные классы.
= {f1, f2, … fS} называется полной, если их суперпозиция дает любую булеву функцию.
α= { , &, }
–функционально полная система (булев базис), при 0 = x & .
ФПС является избыточной, если из нее можно удалить одну из функций без нарушения функциональной полноты. Иначе – неизбыточна (минимальна), т.е. удаление ее из нарушает ФПС.
α – избыточная ?
Да! - из нее можно удалить одну из функций (& или ) без нарушения функциональной полноты.
10