Разложение Шеннона Рассмотрим разложение булевой функции f (x 1, x 2, . . . , xn) по переменной xi. Разложение Шеннона: f (x 1, x 2, . . . , xn)= xi f(x 1, . . . , xi 1, 1, xi+1, . . . , xn) xi f(x 1, . . . , xi 1, 0, xi+1, . . . , xn). Доказательство (не умоляя общности, для i =1). Если x 1 = 0, то f(0, x 2, . . . , xn) = 0 f (1, x 2, . . . , xn) 1 f(0, x 2, . . . , xn) = f (0, x 2, . . . , xn). Если x 1 = 1, то f(1, x 2, . . . , xn) = 1 f(1, x 2, . . . , xn) 0 f(1, x 2, . . . , xn) = f(0, x 2, . . . , xn). ЧТД Пример. Булеву функцию f (x, y, z) = x y / y z , разложим по переменной z: f (x, y, z) = z(x y / y 1) z (x y / y 0)= [по свойствам 0 и 1] = z z (x y / y). Сомножитель f (x 1, . . . , xi -1, 1, xi+1, . . . , xn) в формуле Шеннона называется коэффициентом разложения функции f (x 1, x 2, . . . , xn) по переменной xi при xi, а сомножитель f (x 1, . . . , xi -1, 0, xi+1, . . . , xn) - коэффициентом разложения функции f (x 1, x 2, . . . , xn) по xi при xi. Пример. f (x, y, z) = x y / y = y (x 1 / 0) y (x 0 / 1). x 1 / 0 - коэффициент разложения функции f (x, y, z) по y при y ; x 0 / 1 - коэффициент разложения функции f (x, y, z) по y при y.

Разложение функции по k переменным Доказательство. Подставим в левую и правую части равенства произвольный набор a 1 a 2. . . an: Упростим правую часть, рассуждая следующим образом. Нетрудно проверить, что 1, если и только если ai = 0 = 1, 11 = 1, но 0 1 = 0 и 10 = 0), ci (в самом деле: 0 поэтому конъюнкция равна единице лишь в единственном случае, когда наборы a 1 a 2. . . ak и с1 с2. . . сk совпадают. А это значит, что она не обращает в ноль лишь одно слагаемое правой части - то, для которого a 1 a 2. . . ak = с1 с2. . . сk и в котором сама обращается в единицу. Подставив в ставшееся слагаемое a 1 a 2. . . ak вместо с1 с2. . . сk , получим

Совершенная дизъюнктивная нормальная форма (Сов. ДНФ) Применив формулу разложения булевой функции f (x 1, x 2, . . . , xn) по k переменным при k = n, получим: Поскольку коэффициентами разложения f (c 1, c 2, . . . , cn) в этой формуле являются значения функции f (x 1, x 2, . . . , xn) на всевозможных наборах c 1 c 2. . . cn, то возможны два случая: если набор c 1 c 2. . . cn M 0 (f), то f (c 1, c 2, . . . , cn) = 0 и поэтому обращается в 0 соответствующее слагаемое правой части; если набор c 1 c 2. . . cn M 1 (f), то f(c 1, c 2, . . . , cn)=1 и слагаемое упрощается. В результате имеем: Совершенная дизъюнктивная нормальная форма булевой функции, или Сов. ДНФ, - это формула вида:

Утверждение о единственности Сов. ДНФ Любая булева функция, кроме константы 0, представима cовершенной дизъюнктивной нормальной формой, и она единственна для данной функции. Алгоритм построения Сов. ДНФ (по таблице истинности) вытекает из определения Сов. ДНФ и состоит в циклическом выполнении следующего шага: в векторе столбце значений функции выбирается очередная 1 и по набору значений аргументов этой строки формируется конъюнкция всех аргументов с соблюдением следующего правила: если i‑я компонента набора равна 0, то переменная xi входит в конъюнкцию в степени 0 (с инверсией), иначе в степени 1 (без инверсии); полученная конъюнкция добавляется в формулу как очередное слагаемое. Пример. Обратим внимание на тот факт, что нам впервые удалось от табличного способа задания функции перейти к формульному!

Утверждение о единственности Сов. КНФ Любая булева функция, кроме константы 1, представима cовершенной конъюнктивной нормальной формой, и она единственна для данной функции. Алгоритм построения Сов. КНФ по таблице истинности вытекает из определения Сов. КНФ и состоит в циклическом выполнении следующего шага: в векторе столбце значений функции выбирается очередной 0 и по набору значений аргументов этой строки формируется дизъюнкция всех аргументов с соблюдением следующего правила: если i‑я компонента набора равна 0, то переменная xi входит в дизъюнкцию в степени 1 (без инверсии), иначе в степени 0 (с инверсией); полученная дизъюнкция добавляется в Сов. КНФ как очередной сомножитель. Пример.

Элементарная конъюнкция и ДНФ Рассмотрим множество переменных x 1, x 2, . . . , xn. Элементарной конъюнкцией назовем конъюнкцию, в которую каждая переменная входит не более одного раза (с инверсией или без инверсии). Примеры. x 1 x 2 x 3 x 4, x 1 x 2 x 4 , x 3 - элементарные конъюнкции, x 1 x 2 x 4, x 1 x 3 - неэлементарные. В частности, 1 - это элементарная конъюнкция, не содержащая ни одной переменной. Число переменных, образующих элементарную конъюнкцию, назовем ее рангом. Пример. Ранг элементарной конъюнкции x 1 x 2 x 4 равен трем. Полной конъюнкцией назовем элементарную конъюнкцию, состоящую из всех переменных, т. е. конъюнкцию ранга n. Пример. При n = 4 конъюнкция x 1 x 2 x 3 x 4 - полная. Дизъюнктивной нормальной формой (ДНФ) назовем дизъюнкцию различных элементарных конъюнкций. Пример. x 1 x 2 x 4 x 1 x 2 x 3 x 4 x 3 - ДНФ. Очевидно, что совершенная ДНФ является частным случаем ДНФ. Длиной ДНФ назовем число конъюнкций в данной ДНФ. Рангом ДНФ назовем сумму рангов ее конъюнкций. Пример. Длина ДНФ из предыдущего примера равна трем, а ранг - восьми.

Связь между алгеброй множеств и алгеброй логики заключается в том, что есть 2 изоморфные системы.

БИЛЕТ 25

Понятие двойственности. Принцип двойственности.

Опр. Для заданной булевой функции двойственной к ней называют: ).

Замечания.

Пусть задана булева функция .

Замечание. В функциях f i , i=1,…,m некоторые переменные могут быть фиктивными.

= = = =

Следствие. Если задана булева функция формулой F в базисе Б 0 =(x&y,x˅y,-,0,1), то для получения двойственной функции достаточно сделать замену:

БИЛЕТ 26

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

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

Для любой булевой функции f=f(x 1 ,…,x n) и V 1≤k≤n справедливо представление f(x1,…,xn)=, где x 1 =x, x 0 = ̚ x.

Возьмем произвольный набор Z=(α1,…,αn) и подставим в левую и правую части формулы:

Л.Ч.=f(α1,…,αn)

П.Ч.= =

{ 1 0 ==0; 0 1 =0; 1 1 =1; 0 0 ==1; }

Правая часть совпала с левой.

Следствие1. Формула разложения булевой функции по переменным:

Положим k=1. Возьмем разложение по последней переменной.

Следствие2. Разложение функции в совершенную дизъюнктивную нормальную формулу (СДНФ).

V справедливо =.

=1.

Возьмем в теореме случай k=n, т.е. разложение по всем переменным.

Следствие3. О представимости любой функции в классическом базисе.

Любую булеву функцию можно представить в виде формулы над базисом.

Б 0= {x&y,x˅y,}

Замечание. Для любой булевой функции существует представление в виде СДНФ и это представление является единственной.

БИЛЕТ 27

Совершенные дизъюнктивные нормальные формы (СДНФ)[сумма произведений ˅&].

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

включает следующие действия:

·для каждого набора значений переменных x 1 , x 2 ,..., x n , на котором функция f (x 1 , x 2 ,..., x n) равна 1, выписываются конъюнкции всех переменных;

·над теми переменными, которые на этом наборе равны 0, ставятся отрицания;

·все такие конъюнкции соединяются знаками дизъюнкции.

Полученная таким образом формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции.

Для каждой функции СДНФ единствена.

Таким образом, СДНФ функции f (x 1 , x 2 ,..., x n) представляет собой дизъюнкцию элементарных конъюнкций: D = K 1 ˅ K 2 ˅ ... ˅ K m , где все конъюнкции имеют одинаковое число сомножителей, равное числу логических переменных, а число конъюнкций равно числу наборов значений переменных x 1 , x 2 ,..., x n , на которых функция f (x 1 , x 2 ,..., x n) равна 1. Любые другие записи логической функции, вида D = K 1 ˅ K 2 ˅ ... ˅ K m , не отвечающие этим условиям, называются

дизъюнктивными нормальными формами (ДНФ) этой функции.

БИЛЕТ 28

Совершенные конъюнктивные нормальные формы (СКНФ)[произведение сумм &˅].

Утверждение. Для любой булевой функции f=f(x1,…,xn),f≠ 1 справедливо представление

Имеем: f*≠ 0. Теперь построим СДНФ для f*.

Возьмем двойственную от обеих частей уравнения.

Делаем замены: .

= .

Замечание. Для каждой булевой функции ≠ 1 существует представление в виде СКНФ и это представление является единственным.

БИЛЕТ 29

Полиномы Жегалкина.

В алгебре логики обычно выделяют 3 кононические формы представления функции в виде формулы:

Полиномы Жегалкина

Моном – формула вида 0,1, .

Полином Жегалкина:

P=M 1 ⊕M 2 ⊕…⊕M k , M i – моном.

Все мономы попарно различны.

Теорема. Любую булеву функцию можно представить в виде полинома Жегалкина и это представление является единственным.

I . Доказываем представимость функции в виде полинома Жегалкина.

Рассмотрим 2 случая

1. f ≠ 0, тогда

Можем заменить ˅ на ⊕, т.к. никакие два слагаемых в СДНФ≠1.

Значит, существует j ()

Сделаем преобразования

Раскрываем скобки, приводим подобные по правилу АА=0.

В итоге получим полином Жегалкина для каждой функции существует полином Жегалкина.

II . Доказываем единственность.

Воспользуемся принципом Дирихле.

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

. То есть 2 n отличных от нуля.

Пустой моном=1.

Образуем полином:

Мономов = N=2 n

Полиномов = 2 N =

Если ничего не включили, то 0.

БИЛЕТ 30

Понятие функциональной полноты системы булевых функций. Полнота системы {И, ИЛИ, НЕ}.

Определение. Множество функций алгебры логики А называется полной системой (в Р2), если любую функцию алгебры логики можно выразить формулой над А. Теорема. Система А = {v, &, ─} является полной.

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

БИЛЕТ 31

Замыкание и замкнутые классы.

1°. Понятие замкнутого класса.

Определение 1. Пусть A ⊆ P2. Тогда замыканием A называется множество всех функций алгебры логики, которые можно выразить формулами над A.

Обозначение: [A].

Имеют место следующие свойства:

2) A ⊇ B ⇒ [A] ⊇ [B], причём, если в левой части импликации строгое вложение, то из него вовсе не следует строгое вложение в правой части - верно лишь A ⊃ B ⇒ [A] ⊇ [B];

Определение 2. Система функций алгебры логики A называется полной, если [A] = P2.

Определение 3. Пусть A ⊆ P2. Тогда система A называется замкнутым классом, если замыкание A совпадает с самим A: [A] = A.

2°. Примеры замкнутых классов.

Класс T 0 = {f (x 1 , …, x n) | f (0, …, 0) = 0}.

Классу T 0 принадлежат, например, функции 0, x, xy, x ∨ y, x ⊕ y.

Классу T 0 не принадлежат функции 1, x , x → y, x | y, x ↓ y, x ~ y.

Класс T 1 = {f (x 1 , …, x n) | f (1, 1, …, 1) = 1}.

Классу T 1 принадлежат функции 1, x, xy, x ∨ y, x → y, x ~ y.

Классу T 1 не принадлежат функции 0, x , x ⊕ y, x | y, x ↓ y.

Класс L линейных функций.

Определение 4. Функция алгебры логики f (x 1 , …, x n) называется линейной, если

f (x 1 , …,x n) = a 0 ⊕ a 1 x 1 ⊕ … ⊕ a n x n , где a i ∈ {0, 1}.

Иными словами, в полиноме линейной функции нет слагаемых, содержащих конъюнкцию.

Классу L принадлежат функции 0, 1, x = x⊕1, x ~ y, x ⊕ y.

Классу L не принадлежат функции xy, x ∨ y, x → y, x | y, x ↓ y.

Класс S самодвойственных функций.

Определение 2. Функция алгебры логики f (x 1 , …, x n) называется самодвойственной, если f (x 1 ,…, x n) = f* (x 1 ,…,x n).

Иначе говоря, S = {f | f = f*}.

Определение 2. Функция алгебры логики f (x 1 ,…,x n) называется монотонной, если для любых двух сравнимых наборов ~α и ~β выполняется импликация ~α≤ ~ β ⇒f(~α) ≤ f (~ β)

Класс M всех монотонных функций.

Классу M принадлежат функции 0 , 1 , x , xy , x ∨ y, m (x, y, z) = xy ∨ yz ∨ zx.

Классу M не принадлежат функции x , x | y , x ↓ y , x ⊕ y , x ~ y , x → y

БИЛЕТ 32

Классы Поста.

Критерий Поста - одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.

Булева функция - это функция типа , где , а - арность. Количество различных функций арности равно , общее же количество различных булевых функций бесконечно. Вместе с тем, очевидно, что многие функции могут быть выражены через другие с использованием оператора суперпозиции. Например, давно известно, что из дизъюнкции и отрицания можно, используя законы де Моргана, получить конъюнкцию. Кроме того, любая булева функция (за исключением тождественного нуля) может быть представлена в виде ДНФ, то есть, в терминах конъюнкции, дизъюнкции и отрицания. Возникает естественный вопрос: как определить, будет ли данный набор функций достаточным, чтобы представить любую булеву функцию? Такие наборы называются функционально полными . Теорема Поста даёт ответ на этот вопрос. Поскольку условие теоремы является необходимыми и достаточным, её называют также критерием .

Идея теоремы состоит в том, чтобы рассматривать множество всех булевых функций как алгебру относительно операции суперпозиции. Сейчас она носит имя алгебра Поста . Эта алгебра содержит в качестве своих подалгебр множества функций, замкнутых относительно суперпозиции. Их называют ещё замкнутыми классами . Пусть - некоторое подмножество .Замыканием множества называется минимальная подалгебра , содержащая . Иными словами, замыкание состоит из всех функций, которые являются суперпозициями . Очевидно, что будет функционально полно тогда и только тогда, когда . Таким образом, вопрос, будет ли данный класс функционально полон, сводится к проверке того, совпадает ли его замыкание с .

БИЛЕТ 33

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

Теорема 12 (теорема Поста). Система функций алгебры логики A = {f1, f2, …} является полной в P2 тогда и только тогда, когда она не содержится целиком ни в одном из следующих классов: T0, T1, S, L, M.

Доказательство. Необходимость. Пусть A - полная система, N - любой из классов T 0 , T 1 , S, L, M и пусть A ⊆ N. Тогда [A] ⊆ [N] = N ≠ P2 и [A] ≠ P2. Полученное противоречие завершает обоснование необходимости.

Достаточность. Пусть A ⊄ T 0 , A ⊄ T 1 , A ⊄ M, A ⊄ L, A ⊄ S. Тогда в A существуют функции f 0 ∉ T 0 , f 1 ∉ T 1 , f m ∉ M,

f l ∉ L, f s ∉ S. Достаточно показать, что [A] ⊇ = P2. Разобьём доказательство на три части: получение отрицания, констант и конъюнкции.

a) Получение ─x . Рассмотрим функцию f 0 (x 1 , …, x n) ∉ T0 и введём функцию φ 0 (x) =f 0 (x, x, …, x). Так как функция f 0 не сохраняет нуль, φ 0 (0) = f (0, 0, …, 0) = 1. Возможны два случая: либо ϕ 0 (x) = ─x , либо φ0 (x) ≡ 1. Рассмотрим функцию f 1 (x 1 , …, x n) ∉ T 1 и аналогичным образом введём функцию φ 1 (x) = f 1 (x, x, …, x). Так как функция f 1 не сохраняет единицу, φ 1 (1) = f (1, 1, …, 1) = 0. Возможны также два случая: либо ϕ 1 (x) = ─x , либо φ1 (x) ≡ 0. Если хотя бы в одном случае получилось искомое отрицание, пункт завершён. Если же в обоих случаях получились константы,

то согласно лемме о немонотонной функции, подставляя в функцию f m ∉ M вместо всех переменных константы и тождественные функции, можно получить отрицание.

Отрицание получено.

b) Получение констант 0 и 1. Имеем f s ∉ S. Согласно лемме о несамодвойственной функции, подставляя вместо всех переменных функции f s отрицание (которое получено в пункте a) и тождественную функцию, можно получить константы: ∋ . Константы получены.

c) Получение конъюнкции x · y. Имеем функцию f l ∉ L. Согласно лемме о нелинейной функции, подставляя в функцию f l вместо всех переменных константы и отрицания (которые были получены на предыдущих шагах доказательства), можно получить либо конъюнкцию, либо отрицание конъюнкции. Однако на первом этапе отрицание уже получено, следовательно, всегда можно получить конъюнкцию:

∋ . Конъюнкция получена.

В результате получено, что ⊇ [ ─x,xy] = P 2 . Последнее равенство следует из пункта 2 теоремы 4. В силу леммы 2 достаточность доказана.

БИЛЕТ 34

Реализация булевых функций схемами из функциональных элементов.

*учебник*

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

Соединяя функциональные элементы вместе, мы получаем функциональную схему. С ее помощью можно реализовать любую булеву функцию.

Сложностью схемы из функциональных элементов называется число функциональных элементов в схеме.

Дизъюнктор, инвектор.

СФЭ – схемы из функциональных элементов.

F=(f 1 , f 2 , …, f m)

L(S) – сложность – количество функциональных элементов в схеме.

L(S) = minL(S) – наименьшее количество элементов, с помощью которых можно построить схему.

L A (f) = L(S A (f)) – сложность схемы.

L A (n) = maxL A (f), f ϵ . Макс.берется по всем переменным.

Функция Шеннона для А.

Пусть в СДНФ l (эль) слагаемых.

f = k 1 ˅k 2 ˅…˅k l

Обозначим полученную схему S, тогда

L(S) = L(Dn)+L(Vl )

L(Dn) = 2*2 n + n – 4

l ≤ 2 n

L(Vl )=l - 1≤ 2 n – 1

L(S) ≤ (2*2 n + n - 4) + (2 n - 1) = 3*2 n + n – 5.

БИЛЕТ 35

Реализация дешифратора в классе схем из функциональных элементов (схема для выборки элементов).

*учебник*

Дешифратором Qn порядка n называется схема из функциональных элементов с n входами x 1 , x 2 , …, x n и 2 n выходами z0, z 1 ,…, такая, что если |x1x2…xn| = i, то zi = 1 и zj = 0 при i ≠ j.

Заметим, что если i = (i 1 , i 2 , …, i n) 2 , то z i (x 1 ,…,x n) = .

Лемма. Существует дешифратор Qn с числом элементов, не превосходящим n2 n+1 .

Доказательство. Для реализации каждой z i достаточно взять ровно n–1 конъюнкций и не более n отрицаний, то есть всего менее, чем 2n функциональных элементов. Всего различных конъюнкций ровно 2 n , и сложность дешифратора не превосходит n 2n+1 .

Тривиальные методы основаны на автономной реализации элементарных конъюнкций.

БИЛЕТ 36

Универсальные методы синтеза схем из функциональных элементов.

Теорема. Существует метод синтеза схем из функциональных элементов такой, что для любой булевой функции f(x1,…,xn) строится ее реализующая схема S, такая, что

L(S) ≤ 3*2 n + n – 5 , отсюда:

Следствие. L(n) ≤ 3*2 n + n – 5

Замечание.

БИЛЕТ 37

Реализация двоичного сумматора в классе схем из функциональных элементов.

*учебник*

Определение . Сумматором S n порядка n называется схема с 2n входами x 1 , x 2 , …, x n , y 1 , y 2 , …, y n и n + 1 выходом z 0 , z 1 , z 2 , …, z n такая, что |z | = |S n (x ,y )| = |x |+|y |.

Теорема . Существует схемный сумматор порядка n в базисе {˅, &, ̚ } с числом элементов 9n – 5. Доказательство . Построим искомый схемный сумматор. Для этого возьмём одну ячейку полусумматора, содержащую четыре элемента и n–1 ячейку сумматора, каждая из которых содержит девять элементов. Построим из этих частей сумматор.

Пусть имеются два числа, записанные в двоичном виде.

Сложность: L(Бi)=9.

Теорема. Существует метод синтеза n-разрядного двоичного сумматора такой, что L()=9n-5.

БИЛЕТ 38

Логика высказываний.

Логика высказываний - это определённая совокупность формул, т.е. сложных высказываний, записанных на специально сконструированном искусственном языке. Язык логики высказываний включает:

1. неограниченное множество переменных: А, В, С, …, А1 , В1 , С1 , …, представляющих высказывания;

2. особые символы для логических связок: & - «и», v - «или», V - «либо, либо», ? - «если, то», ? - «если и только если», ~ - «неверно, что»»

3. скобки, играющие роль знаков препинания обычного языка. Чтобы использовать меньшее количество скобок, условимся, что операция отрицания выполняется первой, затем идут конъюнкция и дизъюнкция, и только после этого импликация и эквивалентность.

Формулам логики высказываний, образованным из переменных и связок, в естественном языке соответствуют предложения. К примеру, если А есть высказывание «Сейчас день», В - высказывание «Сейчас светло» и С - высказывание «Сейчас холодно», то формула:

А? В v С, или со всеми скобками: (А? (В v С)) ,

представляет высказывание «Если сейчас день, то сейчас светло или холодно». Формула:

В & С? А, или ((В & С) ? А) ,

представляет высказывание «Если сейчас светло и холодно, то сейчас день». Формула:

~ В? ~ А, или ((~ В) ? (~ А)) ,

представляет высказывание «Если неверно, что сейчас светло, то неверно, что сейчас день» и т.п. Подставляя вместо переменных другие конкретные (истинные или ложные) высказывания, получим другие переводы указанных формул на обычный язык.

Формула, которой не соответствует осмысленное предложение, построена неправильно.

Таковы, в частности, формулы:

(А?), (& В), (A v ВС), (~ &) и т.п.

Каждой формуле логики высказываний соответствует таблица истинности, показывающая, при каких подстановках конкретных высказываний в данную формулу она даёт истинное сложное высказывание, а при каких ложное. Например, формула (~ В? ~ А) даст ложное высказывание, только если вместо В подставить ложное высказывание, а вместо А - истинное.

Всегда истинная формула логики высказываний, или тавтология, - это формула, дающая истинное высказывание при любых подстановках, в неё конкретных (т.е. истинных или ложных) высказываний.

Иными словами, внутренняя структура тавтологии гарантирует, что она всегда превратится в истинное высказывание, какими бы конкретными высказываниями мы ни заменяли входящие в неё переменные.

Пусть s принимает значения 0 или 1, т.е. s {0, 1}.

Введем обозначение:

x s = Øx , если s = 0, x s = x , если s = 1.

Т.е. x 0 = Øx , x 1 = x .

Очевидно, что x s = 1, если x = s и x s = 0, если x s .

Теорема 4.5 (о разложении булевой функции по переменным).

Каждая булева функция f (x 1 , x 2 , ... , x n ) может быть представлена в виде:

f (x 1 , x 2 , ... , x n ) = f (x 1 , x 2 , ... , x m , x m +1 , ... , x n ) =

V x 1 s 1 &x 2 s 2 &...&x m sm & f (s 1 , s 2 , ... s m , x m +1 , ... , x n ), (4.1)

m n , где дизъюнкция берется по всем наборам (s 1 , s 2 , ... , s m ) (их 2 m ).

Например, для m = 2, n = 4 разложение (4.1) включает в себя четыре (2 m = 2 2 =4) конъюнкции и имеет вид:

f (x 1 , x 2 , x 3 , x 4) = x &x &f (0, 0, x 3 , x 4) V x &x &f (0, 1, x 3 , x 4) V x & x &f (1, 0, x 3 , x 4) V x & x &f (1, 1, x 3 , x 4) = Øx 1 &Øx 2 &f (0, 0, x 3 , x 4) V Øx 1 &x 2 &f (0, 1, x 3 , x 4) V x 1 &Øx 2 &f (1, 0, x 3 , x 4) V x 1 &x 2 &f (1, 1, x 3 , x 4).

Доказательство теоремы 4.5.

Теорема будет доказана, если показать, что равенство (4.1) выполняется для произвольного набора переменных (y 1, y 2 , ... , y m , y m +1 , ... , y n ) .

Подставим этот произвольный набор переменных в левую и правую части равенства (4.1).

В левой части получим f (y 1, y 2 , ... , y n ) .

Т. к. y s = 1 только, когда y = s , то среди 2 m конъюнкций y 1 s 1 &y 2 s 2 &...&y m sm в правой части (4.1) только одна обратится в 1 – та, в которой y 1 = s 1 ,…, y m = s m . Все остальные конъюнкции равны 0. Поэтому в правой части (4.1) получим:

y 1 y 1 &y 2 y 2 &...&y m ym &f (y 1, y 2 , ... , y m , y m +1 , ... , y n ) = f (y 1, y 2 , ... , y n ) .

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

Теорема 4.6 (о представлении булевой функции формулой в СДНФ),

Всякая булева функция f (x 1 , x 2 , ... , x n ),не равная тождественно 0, может быть представлена формулой в СДНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.

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

При m = n получим важное следствие теоремы 4.5:

f (x 1 , x 2 , ... , x n ) = V x 1 s 1 &x 2 s 2 &...&x n sn , (4.2)

f (s 1 , s 2 , ... , s n ) = 1

где дизъюнкция берется по всем наборам (s 1 , s 2 , ... , s n ), на которых f = 1.

Очевидно, что разложение (4.2) есть не что иное, как СДНФ формулы f , которая содержит столько конъюнкций, сколько единиц в таблице значений f . Следовательно, СДНФ для всякой булевой функции единственна с точностью до перестановки ее дизъюнктивных членов.

Очевидно также, что для булевой функции f (x 1 , x 2 , ... , x n ), тождественно равной 0, разложение (2) не существует.

В силу изложенного для получения формулы булевой функции f (x 1 , x 2 , ... , x n ) в СДНФ можно воспользоваться следующим алгоритмом.

Алгоритм 4.3. (Алгоритм представления булевой функции, заданной таблицей, формулой в СДНФ).

Шаг 1. s 1 , s 2 , ... , s n , для которых значение f равно 1, т. е. f (s 1 , s 2 , ... , s n ) = 1.

Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию x 1 s 1 &x 2 s 2 &...&x n sn , где x i si = x i , если s i = 1 и x i si =Øx i , если s i = 0, i = 1, 2, ... ,n .

Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ.

Пример 4.15.

Найдем формулу в СДНФ для функции f (x 1 , x 2 , x 3), заданной таблицей 4.4.

f (x 1 , x 2 , x 3) =1. Это 4-ая, 5-ая. 6-ая и 8-ая строки.

2. Для каждой выбранной строки составляем конъюнкции по правилу, указанному в шаге 2. Получим соответственно для четырех выбранных строк:

x 1 0 &x 2 1 &x 3 1 = Øx 1 &x 2 &x 3 .

x 1 1 &x 2 0 &x 3 0 = x 1 &Øx 2 &Øx 3 .

x 1 1 &x 2 0 &x 3 1 = x 1 &Øx 2 &x 3 .

x 1 1 &x 2 1 &x 3 1 = x 1 &x 2 &x 3 .

3. Составляем дизъюнкцию всех полученных конъюнкций и находим СДНФ:

f (x 1 , x 2 , x 3) = Øx 1 &x 2 &x 3 V x 1 &Øx 2 &Øx 3 V x 1 &Øx 2 &x 3 V x 1 &x 2 &x 3 .

Убеждаемся, что это выражение совпадает с полученным ранее в примере 4.13 представлением нашей формулы в СДНФ.

Замечание. Если булева функция задана формулой в СДНФ, то, применяя алгоритм 4.3 в обратной последовательности, легко можем получить таблицу значений этой функции.

Теорема 4.7 (о представлении булевой функции формулой в СКНФ),

Всякая булева функция f (x 1 , x 2 , ... , x n ),не равная тождественно 1, может быть представлена формулой в СКНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.

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

Рассмотрим функцию Øf (x 1 , x 2 , ... , x n ). В соответствии с теоремой 4.6, если она не равна тождественно 0, существует ее формула в СДНФ. Обозначим эту формулу F 1 . Очевидно, условие, что функция Øf (x 1 , x 2 , ... , x n ) не равна тождественно 0, равносильно условию, что функция f (x 1 , x 2 , ... , x n ) не равна тождественно 1. Кроме того, по закону де Моргана формула F 2 º ØF 1 находится в СКНФ (отрицание конъюнкции есть дизъюнкция отрицаний). По закону двойного отрицания

F 2 º ØF 1 º ØØf (x 1 , x 2 , ... , x n ) º f (x 1 , x 2 , ... , x n ),

что и доказывает теорему.

Для получения формулы булевой функции f (x 1 , x 2 , ... , x n ) в СКНФ следует воспользоваться следующим алгоритмом.

Алгоритм 4.4. (Алгоритм представления булевой функции, заданной таблицей, формулой в СКНФ)

Шаг 1. Выбираем в таблице все наборы переменных s 1 , s 2 , ... , s n , для которых значение f (s 1 , s 2 , ... , s n ) = 0.

Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию

x 1 Ø s 1 Vx 2 Ø s 2 V...Vx n Ø sn , где x i Ø si = x i , если s i = 0 и x i Ø si = Øx i , если s i = 1, i = 1, 2, ... , n .

Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится СКНФ.

Пример 4.16.

Найдем формулу в СКНФ для функции f (x 1 , x 2 , x 3), заданной таблицей 4.4.

1. Выберем в таблице строки, где f (x 1 , x 2 , x 3) = 0. Это 1-ая, 2-ая и 3-я и 7-ая строки.

2. Для каждой выбранной строки составляем дизъюнкции по правилу, указанному в шаге 2. Получим соответственно для трех выбранных строк:

x 1 1 Vx 2 1 Vx 3 1 = x 1 Vx 2 Vx 3 .

x 1 1 Vx 2 1 Vx 3 0 = x 1 Vx 2 VØx 3 .

x 1 1 Vx 2 0 Vx 3 1 = x 1 VØx 2 Vx 3 .

x 1 0 Vx 2 0 Vx 3 1 = Øx 1 VØx 2 V x 3 .

3. Составляем конъюнкцию всех полученных дизъюнкций и находим СКНФ:

f (x 1 , x 2 , x 3) = (x 1 Vx 2 Vx 3)&(x 1 Vx 2 VØx 3)&(x 1 VØx 2 Vx 3)&(Øx 1 VØx 2 Vx 3).

Это выражение совпадает с полученным ранее в примере 4.14 представлением нашей формулы в СКНФ.

Замечание. Т. к. всего строк в таблице функции 2 n , то, если число дизъюнктивных членов в СДНФ равно p , а число конъюнктивных членов в СКНФ равно q , то p +q =2 n .

Так, для функции, рассмотренной в примерах 4.15 и 4.16, n = 3, p = 4, q = 4, p + q = 8 = 2 3 .

Задание булевых функций от переменных с помощью таблицы истинности, определение формулы, виды важнейших равносильностей (законов) алгебры логики. Равносильные формулы, законы равносильности, логические уравнения. Разложение булевых функций по переменным.

Нажав на кнопку "Скачать архив", вы скачаете нужный вам файл совершенно бесплатно.
Перед скачиванием данного файла вспомните о тех хороших рефератах, контрольных, курсовых, дипломных работах, статьях и других документах, которые лежат невостребованными в вашем компьютере. Это ваш труд, он должен участвовать в развитии общества и приносить пользу людям. Найдите эти работы и отправьте в базу знаний.
Мы и все студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будем вам очень благодарны.

Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку "Скачать архив"

Подобные документы

Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.

реферат , добавлен 06.12.2010


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

учебное пособие , добавлен 29.04.2009


Булевы алгебры – решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.

курсовая работа , добавлен 12.05.2009


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

контрольная работа , добавлен 26.04.2011


Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.

контрольная работа , добавлен 20.01.2011


Основные понятия алгебры логики. Дизъюнктивные и конъюнктивные нормальные формы. Сущность теоремы Шеннона. Булевы функции двух переменных. Последовательное и параллельное соединение двух выключателей. Свойства элементарных функций алгебры логики.

контрольная работа , добавлен 29.11.2010


Логическая переменная в алгебре логики. Логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Основные законы алгебры логики. Правила минимизации логической функции (избавление от операций импликации и эквивалентности).

курсовая работа , добавлен 16.01.2012

Обозначим через . Тогда

x s =

В частности, тогда и только тогда, когда .

С помощью “степенной функции” всякую булеву функцию можно представить в виде:

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

В самом деле, если , то , и

Если , то , и

Пример 4.

Разложим функцию по переменной . Для этого сначала построим таблицу функции :

Из таблицы видно, что и .

Используя формулу разложения по переменной , находим

Пример 5.

Разложим функцию из примера 4 по всем переменным. Так как функция принимает значение 1 на трех наборах: , то согласно следствию из теоремы о разложении, имеем

Определение 3.

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

называется совершенной дизъюнктивной нормальной формой (СДНФ).

Пример 6.

- СДНФ для функции (см. пример 5).

Теорема 2.

Всякая булева функция (кроме 0) имеет единственную СДНФ.

Доказательство. Согласно следствию из теоремы о разложении

Замечание. Если под дизъюнкцией одного слагаемого понимать само это слагаемое, то дизъюнкции нуля слагаемых не существует, поэтому не существует СДНФ для функции 0.

При построении СДНФ имеет место следующее

Правило единицы. принимает значение 1; для каждого такого набора в СДНФ делается заготовка слагаемого . Если в данном наборе аргументов , то над переменной в заготовленном слагаемом навешивается отрицание: .

Теорема 3.

Всякая булева функция может быть выражена через дизъюнкцию, конъюнкцию и отрицание:

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

Если , то . Если , то

Теорема 4.

Всякая булева функция (кроме 1) может быть единственным образом выражена в виде совершенной конъюнктивной нормальной форме (СКНФ):

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

Если , то и

Применив к последнему тождеству принцип двойственности, находим

При построении СКНФ имеет место следующее

Правило нуля. Рассматриваются только те наборы аргументов, на которых функция принимает значение 0; для каждого такого набора в СКНФ делается заготовка сомножителя . Если в данном наборе аргументов , то над переменной в заготовленном сомножителе навешивается отрицание: .

Пример 7.

Построим функцию для импликации: . Импликация принимает значение 0 на одном наборе:

Так как в этом наборе и , то по правилу нуля получаем

.

Итак, - искомая функция для импликации.

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

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

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

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

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

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

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

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

7. Система {x 1 &x 2 , x 1 Åx 2 , 0, 1} полна в Р 2 , U = {x 1 &x 2 , }, = x 1 Å1.

Полином Жегалкина

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

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

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

Представление функции в виде полинома Жегалкина

1. Представим любую функцию формулой над {x 1 &x 2 , } и сделаем замену =x Å1. Этот способ удобен, если функция задана формулой.

Пример 9 . (x 1 (x 2 x 3))(x 1 Ú x 2) x 3 = (x 1 Ú x 2 Ú x 3)(x 1 Ú x 2) x 3 = (`x 1 x 2 Ú x 1 x 3 Ú x 1 x 2 Ú x 2 Ú x 2 x 3)x 3 = (`x 1 x 3 Ú x 2)x 3 = x 1 x 3 x 2 x 3 = ((x 1 x 3 Å1)x 2 Å1)x 3 = x 1 x 2 x 3 Åx 2 x 3 Åx 3 .

Надо помнить, что четное число одинаковых слагаемых в сумме по mod 2 дает 0.

2. Метод неопределенных коэффициентов. Он удобен, если функция задана таблицей.

Пример 10 .

Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f (x 1 , x 2 , x 3) = (01101001) = а 0 Å а 1 х 1 Å а 2 х 2 Å а 3 х 3 Å b 1 x 1 x 2 Å b 2 x 2 x 3 Åb 3 x 1 x 3 Åcx 1 x 2 x 3 . Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) f (0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим f (0, 0, 0) = а 0 , отсюда а 0 = 0. f (0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: f (0, 0, 1) = а 0 Å а 3 , т.к. а 0 = 0, отсюда а 3 = 1. Аналогично, f (0, 1, 0) = 1 = а 2 , f(0, 1, 1) = 0 = а 2 Å а 3 Å b 2 b 2 = 0; а 1 = 1; 0 = а 1 Å а 3 Å b 3 , b 3 = 0; 0 = а 1 Å а 2 Å b 1 , b 1 = 0; 1 = 1 Å 1 Å 1 Å c ; c = 0; тогда полином Жегалкина для данной функции примет вид: f (x 1 , x 2 , x 3) = x 1 Å x 2 Å x 3 .

Многочлен Жегалкина можно получить также с помощью треугольника Паскаля по единицам его левой стороны по таблице следующим образом. Построим многочлен Жегалкина для функции f = (10011110). Верхняя сторона треугольника есть функция f . Любой другой элемент треугольника есть сумма по модулю для двух соседних элементов предыдущей строки. Левая сторона треугольника для функции f содержит шесть единиц. Многочлен Жегалкина будет содержать шесть слагаемых. Первая единица треугольника соответствует набору (000). Первое слагаемое многочлена есть 1. Третья снизу единица в левой стороне треугольника соответствует набору (101). В качестве слагаемого многочлена берем x 1 x 3 . Аналогично для других единиц треугольника. Слева от наборов показаны слагаемые многочлена Жегалкина.

Теорема Жегалкина

Каждая функция из может быть представлена в виде полинома Жегалкина единственным образом.

Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:

, s = 0, 1, ..., n .

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

Любая функция из Р 2 может быть представлена формулой над {x 1 & x 2 , x 1 Å x 2 , 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции f (x 1 , ..., x n ) от n переменных. Мы знаем, что всего таких функций, т.е. их таблиц истинности, 2 n . Подсчитаем число различных полиномов Жегалкина от n переменных, т.е. число вариаций вида: . Число наборов равно числу всех подмножеств множества { x 1 , ..., x n }, сюда входит и пустое множество (если s = 0). Число подмножеств множества из n элементов равно 2 n , а так как каждый набор входит с коэффициентом , принимающим два значения: 0 или 1, то число всевозможных полиномов будет . Так как каждому полиному соответствует единственная функция, число функций от n переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.

Определение.

Функция f (x 1 , ..., x n ), полином Жегалкина для которой имеет следующий линейный относительно переменных вид: f = а 0 Å а 1 х 1 Å а 2 х 2 Å ... Å а n х n , называется линейной.

Лемма о нелинейной функции .

Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.

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

Пусть f (x 1 , ..., x n ) – нелинейная функция. Тогда полином Жегалкина содержит для нее слагаемое, в котором присутствует произведение x i x j . Будем считать для простоты, что x 1 x 2 в многочлене Жегалкина является этим произведением. Произведя группировку слагаемых, функцию f представим в виде

Функция h 0 не есть тождественный нуль, иначе в полиноме Жегалкина отсутствует слагаемое с произведением x 1 x 2 . Тогда существует набор (a 3 , …, a n ) из 0 и 1, для которого h 0 (a 3 , …, a n ) = 1. Пусть h 1 (a 3 , …, a n ) = a , h 2 (a 3 , …, a n ) = b , h 3 (a 3 , …, a n ) = c . Тогда

Построим функцию:

Где d = ab Å c . Если d = 0, то h (x 1 , x 2) = x 1 x 2 . Если d = 1, то h (x 1 , x 2) = x 1 x 2 Å 1 и тогда Лемма доказана.

Функция f (x 1 , ..., x n) сохраняет константу a Î {0, 1}, если f (a , …, a ) = a .

Пример 11.

Функция xy сохраняет 0, сохраняет 1. Функция x ®y сохраняет 1 и не сохраняет 0.

Минимизация булевых функций

Минимизация нормальных форм

Минимальной ДНФ (МДНФ) функции f (x 1 , ... ,x n ) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими видами ДНФ, реализующими функцию f .

Если для всякого набора = (a 1 , ..., a n ) значений переменных условие g ()=1 влечёт , то функция g называется частью функции f (или функция f накрывает функцию g ). Если при этом для некоторого набора = (c 1 , ..., c n ) функция g ()=1, то говорят, что функция g накрывает единицу функции f на наборе (или что g накрывает конституенту единицы функции f ). Заметим, что конституанта единицы функции f есть часть функции f , накрывающая единственную единицу функции f .

Элементарная конъюнкция K называется импликантом функции f , если для всякого набора =(a 1 , ..., a n ) из 0 и 1 условие K ()=1 влечет f ()=1.

Импликант K функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f .

Ясно, что всякий импликант функции f есть часть функции f .

Теорема 5.

Всякая функция реализуется дизъюнкцией всех своих простых имликант (ПИ).

Следовательно, f = A . Теорема доказана.

Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f . Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

Пусть A и B – произвольные формулы. Из свойств булевых операций вытекают следующие обратимые правила преобразования ДНФ:

1) – полное склеивание (развертывание);

2) – неполное склеивание;

3) – обобщенное склеивание;

4) – поглощение;

5) – идемпотентность (удаление дублирующих членов).

Теорема Квайна. Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращения ДНФ функции f .

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

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