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

Связь между алгеброй множеств и алгеброй логики заключается в том, что есть 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 ВС), (~ &) и т.п.

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

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

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

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


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


аранов Виктор Павлович. Дискретная математика.

Раздел 4. Функциональные системы с операциями. Алгебра логики.

Лекция 21. Принцип двойственности. Разложение функций по переменным. Совершенные ДНФ и КНФ

Лекция 21. ПРИНЦИП ДВОЙСТВЕННОСТИ. РАЗЛОЖЕНИЕ БУЛЕВЫХ

ФУНКЦИЙ ПО ПЕРЕМЕННЫМ. СОВЕРШЕННЫЕ ДИЗЪЮНКТИВНАЯ И

КОНЪЮНКТИВНАЯ НОРМАЛЬНЫЕ ФОРМЫ

План лекции:

  1. Принцип двойственности.
  2. Разложение булевых функций по переменным. Совершенные дизъюнктивная и конъюнктивная нормальные формы.
  1. Принцип двойственности

Функция, равная, называется двойственной функцией к функции .

Очевидно, что таблица истинности для двойственной функции получается из таблицы истинности для функции инвертированием (т. е. заменой 0 на 1 и 1 на 0) значений переменных и функции. Например, .

Легко установить для функций 0, 1, что

  1. функция 0 двойственна 1;
  2. функция 1 двойственна 0;
  3. функция двойственна;
  4. функция двойственна;
  5. функция двойственна;
  6. функция двойственна.

Из определения двойственности следует, что

т. е. функция является двойственной к (свойство взаимности).

Принцип двойственности. Если формула реализует функцию, то формула, т. е. формула, полученная из заменой функций соответственно на, реализует функцию.

Формулу будем называть формулой, двойственной к.

Для доказательства этого утверждения необходимо проверить его справедливость для элементарных шагов суперпозиции и.

Пусть, например, функция получается из функции в результате следующей подстановки переменных:

Тогда

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

Доказательство справедливости принципа двойственности для шага проведем на примере. Пусть

Тогда

т. е. функция получается из и так же, как функция из и.

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

Пример 1. Из тождества следует тождество.

Действительно,

;; .

Пример 2. Построение формулы для отрицания функции.

Из определения двойственной функции следует

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

Найдем отрицание для функции.

Так как, то.

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

Дизъюнктивная и конъюнктивная нормальные формы

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

где – параметр, равный либо 0, либо 1. Очевидно, что

Легко видеть, что 1 тогда и только тогда, когда.

Теорема о разложении функций по переменным. Каждую функцию алгебры логики при любом () можно представить в следующей форме:

, (1)

где дизъюнкция берется по всевозможным наборам значений переменных.

Это представление называется разложением функции по переменным .

Доказательство. Рассмотрим произвольный набор значений переменных и покажем, что левая и правая части соотношения (1) принимают на нем одно и то же значение. Левая часть дает. Правая –

В качестве следствий из теоремы рассмотрим два специальных случая разложения.

  1. Разложение по переменной:

Функции и называются компонентами разложения. Данное разложение полезно, когда какие-либо свойства устанавливаются по индукции.

  1. Разложение по всем переменным:

При тождественно не равной 0 оно может быть преобразовано:

В результате окончательно получим

. (2)

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

Непосредственно к понятию совершенной д. н. ф. примыкает следующая теорема.

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

Доказательство.1) Пусть. Тогда, очевидно,

  1. Пусть тождественно не равна 0. Тогда ее можно представить формулой (2).

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

Пример 3. Найти совершенную д. н. ф. для функции.

Совершенная д. н. ф. есть выражение типа П. Покажем, что при тождественно не равной 1 ее можно представить в виде. Запишем для двойственной функции (очевидно не равной тождественно 0) разложение в виде совершенной д. н. ф.:

Из принципа двойственности следует

Таким образом, получаем разложение, которое называется совершенной конъюнктивной нормальной формой (совершенной к. н. ф.):

. (3)

Пример 4. Построить совершенную к. н. ф. для функции.

Имеем.

Другие похожие работы, которые могут вас заинтересовать.вшм>
200. Нормальные формы логических функций 63.53 KB
Нормальные формы логических функций Представление булевой функции в форме дизъюнкции конъюнктивных термов конституент единицы Ki 2.7 называется дизъюнктивной нормальной формой ДНФ этой функции. содержат в точности по одной все логические переменные взятые с отрицаниями или без них то такая форма представления функции называется совершенной дизъюнктивной нормальной формой СДНФ этой функции. Как видно при составлении СДНФ функции нужно составить дизъюнкцию всех минтермов при которых функция принимает значение 1.
9015. МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ 81.74 KB
ДНФ и схемы из ФЭ. Минимизация булевых функций на основе построения тупиковых ДНФ. Минимизация булевых функций на основе построения тупиковых ДНФ Сокращенная тупиковая и минимальная ДНФ находятся в следующем соотношении. Тупиковая ДНФ получается из сокращенной путем удаления некоторых членов.
9017. ПРОБЛЕМА МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ 109.86 KB
ДНФ и схемы из ФЭ. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ План лекции: Понятие дизъюнктивной нормальной формы ДНФ. Понятие ДНФ. Выражение при где – элементарная конъюнкция ранга называется дизъюнктивной нормальной формой ДНФ.
14731. Разложение сигналов в обобщенный ряд Фурье по системам ортогональных функций. Функции Уолша 38.95 KB
Разложение сигналов в обобщенный ряд Фурье по системам ортогональных функций. Ознакомить с основными характеристиками сигналов и помех. Изучить представление сигналов в виде обобщенного ряда Фурье по системам ортогональных функций. Разложение сигналов в обобщенный ряд Фурье по системам ортогональных функций.
6707. Проектирование реляционных баз данных. Проблемы проектирования в классическом подходе. Принципы нормализации, нормальные формы 70.48 KB
Что такое проект реляционной базы данных Это набор взаимосвязанных отношений в которых определены все атрибуты заданы первичные ключи отношений и заданы еще некоторые дополнительные свойства отношений которые относятся к принципам поддержки целостности. Поэтому проект базы данных должен быть очень точен и выверен. Фактически проект базы данных это фундамент будущего программного комплекса который будет использоваться достаточно долго и многими пользователями.
4849. Формы и методы осуществления функций государства 197.3 KB
Термин «функция» имеет в отечественной и зарубежной научной литературе далеко не одинаковое значение. В философском и общесоциологическом плане, он рассматривается, как «внешнее проявление свойств какого-либо объекта в данной системе отношений»; как совокупность обычных или же специфических действий отдельных лиц или органов
1790. Разложение на слагаемые 180.15 KB
Саме слово алгоритм походить від algorithmi – латинської форми написання імені великого математика ІХ ст. аль-Хорезмі, який сформулював правила виконання арифметичних дій. Спочатку під алгоритмами і розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами.
2690. Изучение работоспособности сверл с переменным шагом винтовой линии 18.85 KB
Модели процесса резания могут быть представлены системой математических уравнений, определяющих в каждом конкретном случае оценочную функцию или критерии работоспособности режущих инструментов, а также технические ограничения по кинематике станка, жесткости режущих инструментов и в целом технологической системы
17088. УГОЛОВНАЯ ОТВЕТСТВЕННОСТЬ ЗА ПРЕСТУПЛЕНИЯ, СОВЕРШЕННЫЕ В СОСТАВЕ ОРГАНИЗОВАННОЙ ПРЕСТУПНОЙ ГРУППЫ 50.97 KB
Ломтев ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы исследования обуславливается потребностью в дальнейшем развитии и совершенствовании теории и практики реализации уголовной ответственности за преступления совершаемые в составе организованной преступной группы. Исследования в сфере противодействия организованной преступности показывают что именно в составе организованных преступных групп совершаются наиболее опасные и трудно раскрываемые преступления. В рамках решения задачи повышения эффективности уголовного закона в части борьбы с...
11576. Понятие, виды и формы сделок. Последствия несоблюдения требуемой формы сделок 49.82 KB
Признание сделки недействительной виды недействительной сделки. Прикладная ценность курсовой работы заключается в упрощении понятия сделки то есть публичного его представления в более доступной форме.

Множество В, на котором определены две бинарные операции (конъюнкция и дизъюнкция) и одна унарная операция (отрицание) и выделены два элемента 0 и 1 называется булевой алгеброй.

Причем для этих операций необходимо выполнение следующих свойств:

Ассоциативность

Коммутативность

Дистрибутивность конъюнкции относительно дизъюнкции

Дистрибутивность дизъюнкции относительно конъюнкции

Идемпотентность

Двойное отрицание

Свойства констант

Правила де Моргана

Закон противоречия

Закон исключенного третьего

В алгебре логики эти законы называются равносильностями.

Совершенные нормальные формы

Совершенная дизъюнктивная нормальная форма

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

; А А =1; Х А =1, если Х=А, Х А =0, если ХА.

Формула Х А 1…… Х А n , где А=- какой-либо двоичный набор, а среди переменных Хi могут быть совпадающие называется элементарной конъюнкцией.

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

Элементарная конъюнкция называется правильной, если в нее каждая переменная входит не более одного раза (включая ее вхождение под знаком отрицания).

Например: 1) (значок конъюнкции в данном случае опущен).

1),4) - правильные элементарные конъюнкции;

2)- переменная х входит один раз сама и второй раз под знаком отрицания;

Переменная y входит трижды: один раз сама и два раза под знаком отрицания.

Правильная элементарная конъюнкция называется полной относительно переменных х 1 …..х n , если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).

Например: из перечисленных в предыдущем примере конъюнкций полной является только 4) относительно переменных x,y,z,t; а относительно переменных x,y,z полной является только 1).

Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных х 1 …..х n называется дизъюнктивная нормальная форма, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны относительно переменных х 1 …..х n

Разложение по переменным

Теорема 1. Всякая логическая функция может быть представлена в СДНФ:

где m, а дизъюнкция берется по всем 2 m наборам значений переменных х 1 ,…х m . Функция f разложена по первым n-переменным. Данное равенство называется разложением по переменным. х 1 ,…х m . Например при n=4, m=2 разложение имеет вид:

теорема доказывается подстановкой в обе части равенства (1) произвольного набора (b 1 ,…,b m , b m+1 ,…,b n) всех n-переменных.

При m = 1 из (1) получаем разложение функции по одной переменной:

Очевидно, что аналогичное разложение справедливо для любой из n- переменных.

Другой важный случай когда n=m. При этом все переменные в правой части (1) получают фиксированные значения и функции в конъюнкции правой части становятся равными 0 или 1, что дает:

где дизъюнкция берется по всем наборам (b 1 …b n), на которых f=1. При f=0 множество конъюнкций в правой части пусто. Такое разложение называется совершенной дизъюнктивной нормальной формой. СДНФ функции f содержит ровно столько конъюнкций, сколько единиц получается в таблице истинности f. Каждому единичному набору (b 1 ,…, b n) соответствует конъюнкция всех переменных, в которой x i взято с отрицанием, если b i =0 b ,и без отрицания, если, b i =1. Таким образом существует взаимно однозначное соответствие между таблицей истинности функции f и ее СДНФ, и,следовательно, СДНФ для всякой логической функции единственна. Единственная функция не имеющая СДНФ - это константа 0.

Теорема 2 . Всякая логическая функция может быть представлена в виде булевой формулы.

Действительно, для всякой функции, кроме константы 0, таким представлением может служит ее СДНФ. Константу 0 можно представить булевой формулой.

Выделим переменную x 1 и рассмотрим функцию f относительно нее.

Все множество наборов таблицы истинности разбивается на два подмножества, в каждом из которых по четыре набора <0, a 2 , a 3 > и <1, a 2 , a 3 >.

Тогда функцию f(x 1 ,x 2 ,x 3) можно представить в виде дизъюнкции двух функций от двух переменных и эта формула будет иметь вид:

Рассмотрим следующие формулы:

Левая часть первой формулы эквивалентна правой, поскольку для x 1 =0 и в соответствии с операцией конъюнкции. Аналогично можно показать справедливость второй формулы. Таким образом, поставив эти формулы в предыдущую дизъюнкцию, получим:

Это выражение называется разложением функции f(x 1 ,x 2 ,x 3) по переменной x 1 .

Теперь аналогично можно разложить функции f(0,x 2 ,x 3) и f(1,x 2 ,x 3) по переменной x 2 . Получим

Подставляя эти формулы в предыдущие получим

Внесем в соответствии с дистрибутивностью операции & переменную x 1 и ее инверсию в скобки, получим

В общем виде для функции f(x 1 ,x 2 ,..,x n) от n переменных разложение по m переменным (m£n) имеет вид

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

Рассмотрим разложение (*4) при крайнем случае, когда m=n. (см. пример (*3)).

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

Проделаем все это для примера (*3).

После удаления из (*3) конъюнкций с нулевыми значениями функции f на заданных наборах, получим:

Так как в соответствии с таблицей истинности

f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1

то из конъюнкций уберем сомножители функций, после чего получим:

Это и есть совершенная дизъюнктивная нормальная форма булевой функции f.

Лемма. Любая булева функция (кроме константы "0") имеет СДНФ, при том только одну.

Аналогично можно ввести конъюнктивную форму,

Построение СДНФ для функции, заданной таблицей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



Загрузка...
Top