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

Зв'язок між алгеброю множин і логікою алгебри полягає в тому, що є 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 (SA (f)) - складність схеми.

L A (n) = max L A (f), f . Макс. береться за всіма змінними.

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

Нехай у СДНФ l (Ель) доданків.

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

Позначимо отриману схему S тоді

L(S) = L(Dn)+L(V l)

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

l≤ 2 n

L(V l)=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 (Бі) = 9.

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

КВИТОК 38

Логіка висловлювань.

Логіка висловлювань - це певна сукупність формул, тобто. складних висловлювань, записаних спеціально сконструйованим штучною мовою. Мова логіки висловлювань включає:

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

2. Спеціальні символи для логічних зв'язок: & - "і", v - "або", V - "або, або", ? - "якщо то", ? - "якщо і тільки якщо", ~ - "невірно, що""

3. дужки, що грають розділових знаків звичайної мови. Щоб використовувати меншу кількість дужок, умовимося, що операція заперечення виконується першою, потім йдуть кон'юнкція та диз'юнкція, і лише після цього імплікація та еквівалентність.

Формулам логіки висловлювань, утвореним із змінних та зв'язок, у природній мові відповідають речення. Наприклад, якщо А є вислів «Зараз день», В – висловлювання «Зараз світло» і З – висловлювання «Зараз холодно», то формула:

А? У С, або з усіма дужками: (А? (У С)) ,

представляє вислів «Якщо зараз день, то зараз світло чи холодно». Формула:

У & З? А, або ((В & С) ? А) ,

представляє вислів "Якщо зараз світло і холодно, то зараз день". Формула:

~ В? ~ А, або ((~ В) ? (~ А)) ,

представляє висловлювання «Якщо не так, що зараз світло, то не так, що зараз день» і т.п. Підставляючи замість змінних інші конкретні (істинні чи хибні) висловлювання, отримаємо інші переклади зазначених формул звичайною мовою.

Формула, якій відповідає осмислене речення, побудована неправильно.

Такі, зокрема, формули:

(А?), (& В), (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 і без заперечення, якщо, 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

то з кон'юнкцій приберемо співмножники функцій, після чого отримаємо:

Це і є досконала диз'юнктивна нормальна форма бульової функції.

Лемма.Будь-яка функція булева (крім константи "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