- •Введение.
- •Назначение курса.
- •1.2 Логические представления
- •1.3 История развитая математической логики
- •1.4 Вопросы для самопроверки.
- •2. Основы математической логики
- •2.1 Логика высказываний. Основные понятия и определения.
- •2.2 Предикаты и кванторы
- •2.3 Булевы функции, булевы константы.
- •2.4 Основные логические связи.
- •Отрицание (логическая связь "не")
- •Конъюнкция
- •Дизъюнкция
- •Импликация.
- •Эквиваленция или равнозначность
- •2.5 Вопросы для самопроверки.
- •3. Алгебра логики.
- •3.1 Понятие алгебры.
- •3.2 Основные логические функции
- •3.3 Основные законы алгебры логики
- •Постулаты алгебры логики
- •Законы алгебры логики. Теоремы одной переменной
- •Теоремы для двух и трех переменных
- •3.4 Тавтологии. Равносильные формулы
- •3.5 Полнота системы логических функций. Базис
- •Критерии полноты Поста-Яблонского
- •3.6 Вопросы для самопроверки
- •4. Введение в формальные (аксиоматические) системы
- •4.1 Формальные модели.
- •4.2 Принципы построения формальных теорий. Аксиоматические системы, формальный вывод.
- •4.3. Формальные теории. Основные понятия и определения
- •Выводимость
- •Полнота, независимость и разрешимость
- •Метатеория формальных систем.
- •4.5 Вопросы для самопроверки.
- •6.3 Метод резолюции для логики предикатов первого порядка
- •6.5Формы представления логических формул.
- •7. Неклассические логики
- •7.2 Нечетная логика
- •7.3 Модальная и пороговая логика
- •Пороговая логика
- •Машина Тьюринга
- •8.3 Рекурсивные функции
- •8.5 Алгоритмически неразрешимые проблемы.
- •8.6 Меры сложности алгоритмов. Классы задач р, ехр и np. Np полные задачи
3.5 Полнота системы логических функций. Базис
При использовании аналитических форм представления логических функции широко используется принцип суперпозиции, заключающийся в замене одних аргументов данной функции другими. Например, если аргументы функции Z = Z(X, Y) являются в свою очередь функциями других аргументов X = Х(a, b) и Y = Y(c, d), то можно записать Z = Z(a, b, c, d).
Система S логических функций f0, f1, f2, … , fk называется функционально полной, если любую функцию алгебры логики можно представить в аналитической форме через эти функции. Как известно, любое сложное высказывание можно представить в виде выражения, в которое входят простые высказывания (переменные хi), операции дизъюнкции, конъюнкции, отрицания и, быть может, скобки (,). Рассмотрим, каким свойствам должны удовлетворять операции, с помощью которых можно выражать любое сложное высказывание.
Система S называется полной в Pk, если любая функция f, fPk представима в виде суперпозиции этой системы, и минимальным базисом, если теряется полнота S при удалении хотя бы одной функции, где Pk – k-значная логика.
В общем случае для установления полноты системы S булевых функций используется критерий полноты Поста-Яблонского.
Дадим предварительно классификацию булевых функций.
Все булевы функции подразделяются на следующие типы:
1. Функция, сохраняющая константу нуль. (Если функция на "0" наборе аргументов равна 0, то она называется сохраняющей константу нуль. ).
2. Функция, сохраняющая константу 1. (Если функция на "1" наборе аргументов равна 1, то она называется сохраняющей константу "1". ).
3. Самодвойственные функции.
Два набора аргументов называются противоположными, если значения всех аргументов у них противоположны.
Функция называется самодвойственной, если на каждой паре противоположных наборов аргументов она принимает противоположные значения.
4. Монотонная функция
Набор аргументов является возрастающим, если он является старшим, хотя бы в одном из разрядов.
Функция называется монотонной, если. она возрастает при, любом возрастании значений аргументов.
Пример: 01 – старший 11 - старший 1011 - старший
00 - младший 10 - младший 0011 - младший
несравнимый набор
5. Линейная функция
Функция называется линейной, если она может быть представлена многочленом первой степени, т.о.
могут принимать только два значения
- знак сложения по модулю 2.
mod 2, M2, таблица сложения по модулю 2.
Определим теперь пять классов булевых функций:
1. Классом K0 булевых функций сохраняющих константу 0, называется множество функций вида
2. Классом K1 булевых функций сохраняющих константу 1, называется множество функций вида .
3. Классом Kл линейных булевых функций называется множество функций вида , где С0, Сi = (0,1); - знак операции «сложение по модулю 2»; 1 0 = 1, 0 1 = 1, 1 1 = 0.
- линейные функции.
4. Классом Kс самодвойственных булевых функций называется множество булевых функций вида .
Ф ункция самодвойственная, если на любой паре противоположных наборов функция принимает противоположные значения.
- самодвойственные функции.
5. Классом Км монотонных булевых функций называется множество булевых функций вида: