Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

В этой теме рассматриваются всюду определенные функции, заданные на множестве B={0,1}. Такие функции называются булевыми. Основная цель темы – доказать критерий полноты класса функций – теорему Поста.

§1. Замкнутость и полнота

§2. Самодвойственные функции

§3. Монотонные функции

§4. Линейные функции

Определение. Функция f(x1,…,xn) называется линейной, если существует a0,a1,…,anÎB такие, что


f(x1,…,xn)=a0+a1×x1+…+an×xn.


Примерами линейных функций являются q(x), i(x), n(x), x+y. Функции x×y, xÚy, x®y линейными не являются. Докажем, например, нелинейность импликации f(x,y)=x®y. Предположим противное. Пусть f(x,y) – линейная функция. Это означает, что x®y=a0+a1×x+a2×y для некоторых a0,a1,a2ÎB. Составим таблицу, задающую функции, стоящие в левой и правой части последнего равенства (см. таблицу 2.5).


Таблица 2.5

x y x® y a0+a1×x+a2×y Следствие
0 0 1 a0 a0=1
0 1 1 1+a2 a2=0
1 0 0 1+a1 a1=1
1 1 1 0 Противоречие

Противоречие показывает, что x® y – нелинейная функция.


Класс всех линейных функций обозначим буквой L. Класс L является замкнутым. Действительно, тождественная функция является линейной. Далее очевидно, что замена аргументов у линейной функции дает линейную и суперпозиция линейных функций линейна.


Следующее утверждение называется леммой о нелинейной функции.


Лемма. Пусть f(x1,…,xn) – нелинейная функция. Тогда замыкание класса K={f(x1,…,xn), q(x), i(x), n(x)} содержит произведение x×y.


Доказательство. Как отмечалось в §1 каждая функция может быть задана полиномом Жегалкина. Это означает, что


f(x1,…,xn)=åai1,…,ik xi1×xi2××xik, (1)


где {i1,…,ik} Í {1,…,n}, ai1,…,ikÎB и суммирование ведется по всем подмножествам множества {1,…,n}. Так как f(x1,…,xn) – нелинейная функция, то хотя бы одно слагаемое имеет степень большую или равную двум. Без ограничения общности можно считать, что это слагаемое содержит произведение x1×x2. Слагаемое правой части равенства (1) разделим на 4 группы: содержащие x1×x2; содержащие x1 и не содержащие x2; не содержащие x1 и содержащие x2, не содержащие x1 и x2. В первой группе вынесем за скобки х1×х2, во второй – х1, в третьей – х3, получим, что


f(x1,…,xn)= x1×x2×f0(x3,…,xn)+x1×f1(x3,…,xn)+x2×f2(x3,…,xn)+f3(x3,…,xn).


Если f0(x3,…,xn) есть тождественный нуль, то выделим произведение переменных в одном из оставшихся слагаемых и проведем аналогичную группировку. Будем поэтому считать, что существуют a3,…,anÎB такие, что f0(a3,…,an)=1. Пусть c1=f1(a3,…,an), c2=f2(a3,…,an), c3=f3(a3,…,an). Рассмотрим функции


g(x1,x2)=f(x1,x2,a3,…,an)=x1×x2+c1×x1+c2×x2+c3 и

h(x1,x2)=g(x1+c2, x2+c1)+c1×c2+c3


Если c=1, то c×x=i(x)×x, x+c=n(x); если же с=0, то c×x=q(x), x+c=x. Отсюда следует, что функции g(x1,x2) и h(x1,x2) принадлежат замыканию класса K. В то же время


h(x1,x2)=(x1+c2)( x2+c1)+c1(x1+c2)+ c2(x2+c1)+c3+c1×c2+c3=

x1×x2+c2×x2+c1×x1+c1×c2+c1×x1+c1×c2+c2x2+c1c2+c3+c1×c2+c3=x1x2


поскольку сложение на множестве B удовлетворяет тождеству u+u=0. Итак, замыкание класса K содержит произведение х×y.


Лемма доказана.

§5. Критерий полноты

Задачи

Ответы, указания и решения

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru