- •Ахметова Наиля Абдулхамитовна
- •Введение
- •1. Элементы комбинаторики
- •1.1. Перестановки. Размещения. Сочетания
- •Теорема.
- •1.2. Задачи по комбинаторике
- •2. Функции алгебры логики
- •2.1. Элементарные функции алгебры логики
- •Пример 2.
- •2.2. Формульное задание функций алгебры логики
- •Упрощение записи формул:
- •Теорема о замене подформул на эквивалентные
- •Некоторые свойства элементарных функций
- •Следствия из свойств элементарных функций
- •Пример 3:
- •2.3 Принцип двойственности
- •Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:
- •Пример 3. Покажем, что функция х1х2 двойственна к x1&x2, функция х1х2 двойственна к функции x1|x2.
- •Принцип двойственности
- •Лемма о несамодвойственной функции
- •2.4 Разложение булевой функции по переменным
- •Теорема о разложении функции по переменным
- •2.5. Полнота, примеры полных систем
- •Полные системы
- •Представление функции в виде полинома Жегалкина
- •Теорема Жегалкина
- •2.6. Замыкание и замкнутые классы
- •Важнейшие замкнутые классы в р2
- •Теорема Поста о полноте
- •Примеры использования теоремы Поста.
- •3. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1,x1x2,x1x2}.
- •Теорема о достаточности четырех функций.
- •2.7. Функции k - значной логики
- •Теорема о полной в Рk системе функций
- •2.8. Задачи и упражнения по функциям алгебры логики
- •1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и :
- •2. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:
- •3. Минимизация булевых функций
- •3.1. Минимизация нормальных форм
- •Алгоритм Квайна построения сокращенной днф.
- •Метод Блейка
- •Алгоритм построения сокращенной днф с помощью кнф (метод Нельсона)
- •Построение всех тупиковых днф.
- •Алгоритм минимизации функций в классе днф
- •Алгоритм минимизации функций в классе кнф
- •Алгоритм минимизации функций в классе нормальных форм
- •3.2 Минимизация частично определенных функций
- •Алгоритм минимизации частично определенных функций в классе днф
- •Алгоритм минимизации частично определенных функций в классе кнф
- •Метод минимизирующих карт Карно
- •3.3 Задачи по минимизации и доопределению булевых функций
- •4. Логика высказываний
- •4.1. Введение в логику высказываний
- •4.2. Задачи по алгебре высказываний
- •Список литературы
Теорема Поста о полноте
Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T0,T1,L,S,M.
Доказательство.Докажем необходимость этого условия. Пусть система
N = {f1,f2, ...fs, ...} полна вР2, покажем, что тогда она не лежит целиком вQ, где черезQобозначим любой из классовT0,T1,L,S,M. Докажем от противного, пустьNQ, очевидно, [N][Q] =Q, но [N] =P2, т.к.N– полна вР2, отсюдаР2=Q, но это не так. Необходимость доказана.
Докажем достаточность. Пусть F= {f0,f1,fL,fm,fs}, гдеf0T0,f1T1,fLL,fsSиfmM. Покажем, что суперпозицией функций системыFможно получить полную системуG= {x1&x2, }.
1. Пусть g(x) =f0(x, …,x). Тогдаg(0) =f( 0, …, 0) = 1. Далее возможны два случая:
g(1) = 1. Тогдаg(x)1. Функцияh(x) =f1(g(x), …,g(x)) =f1(1, …, 1) = 0, т.е.h(x)0. Получили константы 0 и 1;
g(1) = 0. Тогдаg(x) =. По лемме о несамодвойственной функции суперпозицией над {fs, } можно получить одну из констант, например, 0. Тогдаf0(0, …, 0) = 1 есть другая константа.
В обоих случаях получили обе константы.
2. По лемме о немонотонной функции суперпозицией над {fm, 0, 1} можно получить отрицание.
3. По лемме о нелинейной функции суперпозицией над {fL, 1, } можно получить конъюнкцию. Теорема доказана.
Следствие.Всякий замкнутый класс функций изР2, не совпадающий сР2содержится, по крайней мере, в одном из замкнутых классовT0,T1,L,S,M. Действительно, еслиNне является подмножествомQ, то [N] =P2, что неверно.
Примеры использования теоремы Поста.
1. Покажем, что система функций {f1 =x1x2,f2 =0,f3 =1,f4 =x1x2x3} полна вР2. Составим таблицу, которая называется критериальной :
|
Т0 |
Т1 |
L |
M |
S |
x1x2 |
+ |
+ |
- |
+ |
- |
0 |
+ |
- |
+ |
+ |
- |
1 |
- |
+ |
+ |
+ |
- |
x1x2x3 |
+ |
+ |
+ |
- |
+ |
x1 x2 x3 |
x1x2x3 |
0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
0 0 0 0 1 0 0 1 |
Из таблицы видно, что какой бы класс мы ни взяли, всегда есть функция из данной системы , которая в этот класс не входит. Можно сформулировать следующее правило: для того чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце критериальной таблицы был хотя бы один «минус».
Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f2,f3,f4}L, {f1,f3,f4}T1, {f1,f2,f4}T0, {f1,f2,f3}M.
2. Мы знаем, что система {x1|x2} – полна вР2. Какова для нее критериальная таблица?x1|x2= =x1x21.
|
Т0 |
Т1 |
L |
M |
S |
x1|x2 |
- |
- |
- |
- |
- |
3. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1,x1x2,x1x2}.
|
Т0 |
Т1 |
L |
M |
S |
0 |
+ |
- |
+ |
+ |
- |
1 |
- |
+ |
+ |
+ |
- |
x1x2 |
+ |
+ |
- |
+ |
- |
x1x2 |
+ |
- |
+ |
- |
- |
Согласно критериальной таблице, полной является и система {1, x1x2,x1x2}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, гдеаравны 0, если членыхх...х, в полиноме отсутствуют.
4. Выясним, полна ли система . Составим критериальную таблицу, очевидно. Чтобы показать, что, достаточно найти одну функциюи. Возьмем, удовлетворяющую требуемым условиям. ЕслиfS\T0, тоf(0, ..., 0) = 1,f(1, ..., 1)=0, следовательно,fM,fT1. Рассмотрим функциюh=x1x2x2x3x1x3=1, набор ее значений (11101000),hS\T0, ноhL. Следовательно, критериальная таблица имеет вид:
|
Т0 |
Т1 |
L |
M |
S |
LT1 |
- |
+ |
+ |
- |
- |
S\T0 |
- |
- |
- |
+ |
- |
и А – полная система функций.
Определение. Система функций {f1, ...,fs, ...} называется базисом вР2,если она полна вР2, но любая ее подсистема не будет полной. Например, система функций {x1&x2, 0, 1,x1x2x3} – базис.