Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Полные системы




Читайте также:
  1. C2 Покажите на трех примерах наличие многопартийной политической системы в современной России.
  2. II. Системы, развитие которых можно представить с помощью Универсальной Схемы Эволюции
  3. III. Требования к организации системы обращения с медицинскими отходами
  4. NP-полные задачи
  5. Oсoбеннoсти и прoблемы функциoнирoвaния вaлютнoй системы Республики Белaрусь
  6. А). Системы разомкнутые, замкнутые и комбинированные.
  7. А. Оппозиция логичных и нелогичных действий как исходноеотношение социальной системы. Теория действия Парето и теория действия Вебера
  8. Авиационно-транспортной системы
  9. Автоматизированные системы обработки данных
  10. Автоматизированные системы обработки экономической и финансовой информации

1. P2 – полная система.

2. Система M={x1&x2, x1Úx2, } – полная система, т.к. любая функция алгебры логики может быть записана в виде формулы через эти функции.

Пример 1. Неполные системы: { }, {0,1}.

 

Лемма (достаточное условие полноты)

 

Пусть система U = {f1, f2, ..., fs, ...} полна в Р2. Пусть B = {g1, g2, ..., gk, ...} – некоторая система из Р2, причем любая функция fi Î U может быть выражена формулой над B, тогда система B полна в Р2.

Доказательство. Пусть h(x1, ..., xn) Î P2, т.к. U полна в Р2, то h(x1, ..., xn) = =N[f1, ..., fs, ...] = N[L1[g1, ..., gk], ..., Ls[g1, ..., gk], ...] = U[g1, ..., gk]. Здесь мы воспользовались тем, что для любого i n fi может быть выражена формулой над B, поэтому fi=Li[gi, ..., gk].

3. Система {x1Úx2, } – полна в P2.

Возьмем в качестве полной в Р2 системы U={x1Úx2, , x1&x2}, B={x1Úx2, }. Надо показать, что x1&x2 представляется формулой над B. Действительно, по правилу Де Моргана получим: x1&x2= .

С помощью этой леммы докажем полноту еще ряда систем.

4. Система {x1&x2, } – полна в Р2.

5. Система {x1|x2} полна в Р2. Для доказательства возьмем в качестве полной в Р2 системы U = {x1&x2, } и выразим х1&х2 и через х1|x2 :

= x1 | x1, x1 & x2 = = (x1|x2)|(x1|x2).

6. Система {x1 x2} полна в Р2. U = {x1Úx2, }, = x1 x1, x1Úx2 = = (x1 x2) (x1 x2).

7. Система {x1&x2, x1Åx2, 0, 1}, U = {x1&x2, }, = x1Å1.

Следствие. Полином Жегалкина.

f(x1, ..., xn) Î P2, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как {x1&x2, x1Åx2, 0, 1} полна в Р2. В силу свойства x & (yÅz) = xy Å xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х х ...х , соединенных знаком Å. Такой полином называется полиномом Жегалкина.

Общий вид полинома Жегалкина:

где , s = 0, 1, ..., n, причем при s = 0 получаем свободный член а0.

 


Дата добавления: 2014-11-13; просмотров: 10; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты