![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Полные системы1. P2 – полная система. 2. Система M={x1&x2, x1Úx2, Пример 1. Неполные системы: {
Лемма (достаточное условие полноты)
Пусть система Доказательство. Пусть h(x1, ..., xn) Î P2, т.к. U полна в Р2, то h(x1, ..., xn) = =N[f1, ..., fs, ...] = N[L1[g1, ..., gk], ..., Ls[g1, ..., gk], ...] = U[g1, ..., gk]. Здесь мы воспользовались тем, что для любого i 3. Система {x1Úx2, Возьмем в качестве полной в Р2 системы U={x1Úx2, С помощью этой леммы докажем полноту еще ряда систем. 4. Система {x1&x2, 5. Система {x1|x2} полна в Р2. Для доказательства возьмем в качестве полной в Р2 системы U = {x1&x2,
6. Система {x1 7. Система {x1&x2, x1Åx2, 0, 1}, U = {x1&x2, Следствие. Полином Жегалкина. f(x1, ..., xn) Î P2, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как {x1&x2, x1Åx2, 0, 1} полна в Р2. В силу свойства x & (yÅz) = xy Å xz можно раскрыть все скобки, привести подобные члены, и получится полином от n переменных, состоящий из членов вида х Общий вид полинома Жегалкина: где
|