Лемма о несамодвойственной функции

 

Подстановкой функций и в несамодвойственную функцию можно получить одну из констант.

Доказательство. Пусть – несамодвойственная функция. Тогда существует набор , для которого . Построим функцию , заменив единицы в на , а нули – на . Так как , то . Заметим, что .

Тогда , т.е. . Следовательно, функция есть одна из констант.

Разложение булевой функции по переменным

Обозначим x^s=

Посмотрим, чему равно x^s при разных значениях x и s.

x\s

Из таблицы следует: x^s=1 тогда и только тогда, когда x=s.

Теорема о разложении функции по переменным

 

Пусть f(x₁, ..., x_n) Î P₂. Тогда для любого m: 1 ≤ m ≤ n допустимо представление:

f(x₁, ..., x_m, x_m+1, ..., x_n) = ,

где дизъюнкция берется по всем наборам из 0 и 1, которое называется разложением функции f по переменным x₁, ..., x_n.

Прежде чем доказать утверждение, рассмотрим примеры.

Пример 1. m = 1, запишем разложение по переменным х:

f(x₁, ..., x_n) = = f(0, x₂ , …, x_n)Ú x₁f(1, x₂, ..., x_n). (1)

Пример 2. m=2, запишем разложение по переменным х и :

f(x₁, x₂, …x_n) = =

.

Если f(x₁, x₂) = x₁ Å x₂, то последняя формула дает x₁ Å x₂ = x₂Ú x₁ .

Доказательство. Для доказательства возьмем произвольный набор (a₁, ..., a _n) и покажем, что левая и правая части формулы (1) принимают на этом наборе одинаковые значения. Слева имеем f(a₁, ..., a_n). Cправа: .

Дизъюнкция берется по всевозможным наборам (s₁, ..., s_m). Если в этих наборах хотя бы одно s_i ¹ a_i (1≤ i≤ m), то = 0 и , следовательно, ненулевой член будет только на наборе (s₁, ..., s_m) = (a₁, ..., a_m), тогда f(a₁, ..., a_n).

Следствие 1. Любую функцию f(x₁, ..., x_n) не равную тождественно нулю можно представить в виде: , причём единственным образом. Этот вид называется совершенной дизъюнктивной нормальной формой функции f(x₁, ..., x_n) и записывается СДНФ.

Доказательство. Существование СДНФ для функции не равной тождественно нулю вытекает из предыдущей теоремы. Покажем, что эта СДНФ единственная. В самом деле, имеется n-местных функций, не равных нулю тождественно. Подсчитаем число различных СДНФ от n переменных. Путь означает число сочетаний из n элементов по k. Тогда число одночленных СДНФ равно . Число k-членных СДНФ равно . Число n-членных СДНФ равно . Число всех различных СДНФ

Итак, функций реализуются посредством СДНФ, т.е. каждой функции соответствует единственная СДНФ.

Замечание. – элементарная конъюнкция ранга n по числу входящих переменных, предполагается, что при i ¹ j, х_i ¹ х_j. СДНФ для f(x₁, ..., x_n) –дизъюнкция элементарных конъюнкций ранга n. Если функция представлена в виде дизъюнкций элементарных конъюнкций, где ранг хотя бы одной элементарной конъюнкции меньше n, то такая форма называется дизъюнктивной нормальной формой ( ДНФ ).

Cледствие 2. Любая функция алгебры логики может быть представлена в виде формулы через отрицание, & и Ú.

а) Если f ≡ 0, то f(x₁, ..., x_n) = & .

б) Если f(x₁, ..., x_n) ¹ 0 тождественно, тогда ее можно представить в виде СДНФ, где используются только связки , &, Ú. СДНФ дает алгоритм представления функции в виде формулы через &, Ú, .

Пример 3. Пусть функция f(x₁, x₂, x₃) задана таблицей истинности. Запишем ее в виде СДНФ. Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и

(1, 1, 1), поэтому f(x₁, x₂, x₃) = x₁⁰ & x₂¹ & x₃⁰ Ú x₁¹ & x₂⁰ & x₃⁰ Ú x₁¹& x₂¹ & x₃¹=

= & x₂& Ú x₁& & Ú x₁& x₂& x_3.

x1	x2	x3	f

Следствие 3. Мы умеем представлять функцию в виде . Нельзя ли представить ее в виде . Пусть функция f(x₁, ..., x_n) ¹ 1 тождественно. Тогда функция f* ¹ 0 тождественно, и ее можно представить в виде СДНФ:

.

По принципу двойственности заменим & на Ú и наоборот, получим

(2)

называется элементарной дизъюнкцией ранга n. Представление функции в виде (2) называется совершенной конъюнктивной нормальной формой или в краткой записи – СКНФ. СКНФ для f(x₁, ..., x_n) – конъюнкция элементарных дизъюнкций ранга n. КНФ для f(x₁, ..., x_n) – конъюнкция элементарных дизъюнкций, где ранг хотя бы одной элементарной дизъюнкции меньше n.

Пример 4. Пусть f(x₁, x₂, x₃) = x₁ (x₂ (x₃ ~ x₁)). Представим ее в виде СКНФ, для этого получим таблицу истинности.

x1	x2	x3	x3~x1	x2 (x3~x1)	f
1	1	1	1 1	1	1

Функция равна нулю только на наборе (1, 1, 0), поэтому

f(x₁ x₂ x₃)=x₁ Ú x₂ Ú x₃ =x₁⁰Ú x₂⁰Ú x₃¹= Ú Ú x₃.

 

2.5. Полнота, примеры полных систем

Определение. Система функций {f₁, f₂, ..., f_s, ...}Ì P₂ называется полной в Р₂, если любая функция f(x₁, ..., x_n) Î P₂ может быть записана в виде формулы через функции этой системы.

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

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

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

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

 

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

 

Пусть система U = {f₁, f₂, ..., f_s, ...} полна в Р₂. Пусть B = {g₁, g₂, ..., g_k, ...} – некоторая система из Р₂, причем любая функция f_i Î U может быть выражена формулой над B, тогда система B полна в Р₂.

Доказательство. Пусть h(x₁, ..., x_n) Î P₂, т.к. U полна в Р₂, то h(x₁, ..., x_n) = =N[f₁, ..., f_s, ...] = N[L₁[g₁, ..., g_k], ..., L_s[g₁, ..., g_k], ...] = U[g₁, ..., g_k]. Здесь мы воспользовались тем, что для любого i n f_i может быть выражена формулой над B, поэтому f_i=L_i[g_i, ..., g_k].

3. Система {x₁Ú x₂, } – полна в P₂.

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

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

4. Система {x₁& x₂, } – полна в Р₂.

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

= x₁ | x₁, x₁ & x₂ = = (x₁|x₂)|(x₁|x₂).

6. Система {x₁ x₂} полна в Р₂. U = {x₁Ú x₂, }, = x₁ x₁, x₁Ú x₂ = = (x₁ x₂) (x₁ x₂).

7. Система {x₁& x₂, x₁Å x₂, 0, 1}, U = {x₁& x₂, }, = x₁Å 1.

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

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

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

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

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. III. Полномочия и функции Комиссии
2. Аналитические абстрактные функции и ряды Тейлора.
3. Банковская система. Центр. и ком-кие банки, их задачи и функции.
4. Билет 1. Сущность финансов, их функции
5. Билет № 5. Рынок в системе общественного производства: природа и функции.
6. Биологические мембраны клетки их строение химический состав и функции.
7. Биосфера. Экологические функции.
8. Бюджетный дефицит: понятие, функции, виды, пути сокращения
9. ВЗЯТИЕ ЖЕЛУДОЧНОГО СОДЕРЖИМОГО ДЛЯ ИССЛЕДОВАНИЯ СЕКРЕТОРНОЙ ФУНКЦИИ ЖЕЛУДКА
10. Виды РНК. Строение и функции РНК
11. ВНУТРЕННИЕ ФУНКЦИИ ГОСУДАРСТВА
12. Возникновение и сущность денег. Функции денег. Виды денег.