загрузка...
загрузка...
На головну

Побудова формул алгебри логіки по заданій таблиці істинності

  1. Divide; Побудова характеристик насосів
  2. I. Рішення логічних задач засобами алгебри логіки
  3. III. ФОРМУЛИ ПОВНОГО ІМОВІРНОСТІ І Байєса.
  4. IV.4.1) Походження і зміст формулярного процесу.
  5. IV.4.3) Загальний хід формулярного процесу.
  6. А. К. Замбржіцкая Пілотування формулювання анкетного питання
  7. алгебра логіки

нехай F - Двійкова функція від n змінних. Припустимо, що F не дорівнює тотожно нулю. нехай T1, T2,..., Tk - Всі крапки її визначення, в яких F= 1. Можна довести, що справедлива наступна формула:

,

де  , J = 1,2, ..., k,

побудувати функцію F можна і по-іншому. якщо функція F не дорівнює тотожно одиниці і S1, S2, ..., Sm - Всі крапки області її визначення, в яких F= 0, то справедлива формула:

,

де , j = 1,2, ..., m.

З наведених формул видно, що будь-яку двійкову функцію можна записати, використовуючи лише операції, , .

Основна кон'юнкція - це кон'юнкція основних висловлювань змінних або їх заперечень. наприклад, .

Основна диз'юнкція - це диз'юнкція основних висловлювань змінних або їх заперечень. наприклад, .

Кон'юнктівной нормальною формою (КНФ) даної формули називається формула, рівносильна даній і представлена ??у вигляді кон'юнкції основних диз'юнкцій. наприклад, (A + B) (A + C + B) (D + A).

Диз'юнктивній нормальною формою (ДНФ) даної формули називається формула, рівносильна даній і представлена ??у вигляді диз'юнкції основних кон'юнкція. наприклад, AB + C + AC.

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

Теорема 2. Для того щоб формула алгебри висловлювань була тотожно хибною, необхідно і достатньо, щоб її ДНФ містила в кожної елементарної кон'юнкції деякий висловлювання і його заперечення.

Вчинені диз'юнктивні, кон'юнктівние і поліноміальні нормальні форми подання переключательних (логічних) функцій. Різноманіття формул, за допомогою яких може бути виражена будь-яка логічна функція, визначає різноманіття форм логічних функцій, т. Е. Способів їх запису шляхом застосування до змінних і їх групам елементарних логічних операцій. Найбільш зручними для практичного використання виявляються вчинені нормальні форми представлення складних логічних функцій. В алгебрі логіки доводять, що будь-яка логічна функція F (A, B, C, ..., N) може бути представлена ??тільки однією досконалої диз'юнктивній нормальною формою (крім константи нуль) або тільки однієї досконалої кон'юнктівной нормальною формою (крім константи одиниця).

нехай функція X = F (A, B, C) задана таблицею 4. Запис функції Х у вигляді логічної суми (диз'юнкції) логічних творів (кон'юнкція) змінних, для яких значення функції Х дорівнює 1, і є досконалою диз'юнктивній нормальною формою (СДНФ) уявлення логічної функції.

Таблиця 4

A B C X

СДНФ логічної функції слід знаходити в такій послідовності:

1) скласти твори змінних для рядків таблиці істинності, в яких Х дорівнює 1. Якщо значення змінної (А, В або С) В рядку дорівнює 0, то в творі записується заперечення цієї змінної;

2) написати суму творів, для яких функція Х дорівнює 1. Отримана сума і є СДНФ. У загальному вигляді

 , (1)

Це правило називають правилом записи перемикальної функції по одиницям. Згідно з цим правилом, дані табл. 4 описуються аналітичним виразом, що зв'язує всі набори змінних, для яких Х= 1, у вигляді:

 . (2)


запис функції Х у вигляді логічного твори (кон'юнкції) логічних сум (диз'юнкцій) змінних, для яких функція Х дорівнює 0, є досконалою кон'юнктівной нормальною формою (СКНФ) уявлення логічної функції.

Для табл. 4 аналітичний вираз в СДНФ, що зв'язує всі набори змінних, для яких Х= 0, має вигляд:

 . (3)

Для подання логічної функції Х в СКНФ зробимо операцію заперечення лівої і правої частин рівності (3)

і на підставі законів подвійного заперечення і інверсії

 . (4)

СКНФ логічної функції, згідно (4), слід знаходити в такій послідовності:

1) скласти логічні суми змінних для рядків таблиці істинності, в яких функція Х дорівнює 0. Якщо значення змінної (А, В або С) В рядку дорівнює 1, то в сумі записується заперечення цієї змінної;

2) написати логічне твір складених логічних сум. Отримане твір і є СКНФ. У загальному вигляді:


 , (5)

де Fi - Складні диз'юнкції.

Це правило також називають правилом побудови перемикача функції по нулях.

Окрім представлення функцій у вигляді СДНФ і СКНФ використовують і досконалу поліноміальних нормальну форму СПНФ. Замість диз'юнкції може бути записана функція додавання за модулем два (сума Жегалкина):

 , (6)

де Fi - Складні кон'юнкції.

Існує спеціальна таблиця, в якій всі елементарні логічні операції від двох аргументів представлені в двох досконалих нормальних формах.

Нормальні форми подання перемикальної функції іноді називають стандартними (Табл. 5).

Таблиця 5

f  A B  Назва функції  позначення функції  СДНФ  СКНФ
f0  Константа нуль  Не має
f1  Логічне твір, кон'юнкція
f2  Заборона по В
f3  змінна А
f4  Заборона по А
f5  Мінлива В
f6  Сума по мо дулю 2, логічна нерівнозначність
f7  Роз'єднання, диз'юнкція
f8  Операція (стрілка) Пірса, операція Вебба
f9  Еквівалентність, логічна рівнозначність
f10  інверсія В
f11  Імплікація від В до А
f12  інверсія А
f13  Імплікація від А до В
f14  Операція (штрих) Шеффера
f15  Константа одиниця  Не має

Многочленом Жегалкина називається многочлен, який є сумою константи 0 або 1 і різних одночленним, в які всі змінні входять не вище, ніж в першого ступеня.

Теорема. Будь-яка функція булевої алгебри може бути представлена, і до того ж єдиним чином, за допомогою полінома Жегалкина виду

J = .

Уявімо, наприклад, у вигляді полінома вираз виду X1 X2. Для цього проведемо наступні міркування.

нехай

X1 X2 = aX1X2+ bX1+ cX2+ K,

де а, b, с, k - Невизначені коефіцієнти.

при X1 = X2 = 0 маємо k = 0. При Х1 = 1, X2= 0 маємо b= 1. При Х1= 0, Х2= 1 маємо с= 1. При X1= Х2= 1 маємо а + b + с = 1, т. Е. а = -1. Таким чином, отримуємо:

X1 X2 = - X1X2+ X1+ X2.

СПНФ утворюється шляхом заміни в СДНФ:  на + і  на

1  х.

,

,

В останньому випадку вираз для  легко можна спростити, якщо розкрити дужки і взаємно скоротити всі однакові складові, що входять в формулу парне число раз:

.

Подібне спрощення, яке називається мінімізацією логічної функції, можна здійснити і по відношенню до СДНФ і СКНФ.

Таблиця 6

y

Застосування законів алгебри логіки дозволяє знайти більш компактні аналітичні вирази для заданої функції у, Т. Е. Мінімальну діз'юнктівную нормальну форму  . Наведемо відповідні форми представлення функції у, Заданої табл. 6:

,

і для СКНФ, т. е. мінімальну КНФ:

.

Після того, як знайдені мінімальні нормальні форми (МНФ), їх рекомендується перевірити на всіх наборах аргументів  . змінні  або  часто називають термами. Саме повний набір з n термів утворює конституенту. У процесі ж мінімізації деякі терми з констітуєнт пропадуть. Тоді решту диз'юнкт або Кон'юнктів називають импликантой.

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

Контрольні питання і вправи

1. Дайте визначення логічної функції багатьох змінних.

2. Що таке вектор значень булевої функції? Наведіть приклад побудови таблиці істинності логічної функції багатьох змінних.

3. Скільки існує булевих функцій від n змінних?

4. Що таке ДНФ і КНФ?

5. Який алгоритм побудови СДНФ? Наведіть приклад побудови СДНФ.

6. Який алгоритм побудови СКНФ? Наведіть приклад побудови СКНФ.

7. Складіть СКНФ і СДНФ для функції .

8. Наведіть приклад побудови СПНФ.

 



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   Наступна

Дискретна математика | Введення в алгебру логіки | Основні функції алгебри логіки | Формули алгебри логіки | Закони алгебри логіки і наслідки з них | Алгебра Жегалкина і лінійні функції | Методи мінімізації логічних функцій | Неповністю певні логічні функції | Бінарні діаграми рішень (БДР) | Побудова логічних схем |

загрузка...
© um.co.ua - учбові матеріали та реферати