Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Полные системы. Примеры полных систем (с доказательством полноты)





Определение. Множество функций алгебры логики A называется полной системой (в P2), если любую функцию алгебры логики можно выразить формулой над A.

Система функций A={ f1, f1,…, fm }, являющаяся полной, называется базисом.

Минимальным базисом называется такой базис, для которого удаление хотя бы одной функции f1 , образующей этот базис, превращает систему функций (f1, f1,…, fm) в неполную.

Теорема. Система A = {∨, &, ¬} является полной.

Доказательство. Если функция алгебры логики f отлична от тождественного нуля, то f выражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишь дизъюнкция, конъюнкция и отрицание. Если же f ≡ 0, то f = x & ¬x . Теорема доказана.

Лемма. Если система A — полная, и любая функция системы A может быть выражена формулой над некоторой другой системой B, то B — также полная система.

Доказательство. Рассмотрим произвольную функцию алгебры логики f (x1, …, xn) и две системы функций: A = {g1, g2, …} и B = {h1, h2, …}. В силу того, что система A полна, функция f может быть выражена в виде формулы над ней:

f (x1, …, xn) = ℑ[g1, g2,…]

где gi= ℜi[h1,h2,…]

то есть функция f представляется в виде

f (x1, …, xn)=ℑ[ℜ1,ℜ2,...]

иначе говоря, может быть представлена формулой над B. Перебирая таким образом все функции алгебры логики, получим, что система B также полна. Лемма доказана.

Теорема. Следующие системы являются полными в P2:

1) {V, ¬} ;

2) {&, ¬} ;

3) { | };

4) {&, ⊕ , 1}базис Жегалкина.

Доказательство.

1) Известно (теорема 3), что система A = {&, V, ¬} полна. Покажем, что полна система B = { V, ¬ . Действительно, из закона де Моргана ¬(x& y) = (¬x ∨ ¬y) получаем, что x & y =¬ (¬x ∨ ¬y) , то есть конъюнкция выражается через дизъюнкцию и отрицание, и все функции системы A выражаются формулами над системой B. Согласно лемме система B полна.

2) Аналогично пункту 1: ¬( x ∨ y) = x & y ⇔ x ∨ y =¬( ¬x & ¬y) и из леммы 2 следует истинность утверждения пункта 2.

3) x | y=¬(x&y), x | x = ¬x ; x & y = ¬(x | y) = (x | y) | (x | y) и согласно лемме 2 система полна.

4) ¬x = x ⊕1 и согласно лемме 2 система полна.

Теорема доказана.





Дата добавления: 2014-01-03; Просмотров: 2729; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.018 сек.