L_3

Мета лекції
Отримання знань щодо алгебри логіки

Питання, що будуть розглянуті
Логічні (булеві) функції.
Алгебра логіки.
Повні набори функцій
Канонічні форми булевих функцій.
Спрощення формул. Утворення скороченої ДНФ методом Квайна

1. Логічні (булеві) функції

Вступ до алгебри логіки
Порівняння основних властивостей множин та логіки висловлювань показало, що ці властивості мають багато спільного.
Як результат з’явилась Булева алгебра, яка є частиною математичної логіки.

Вступ до алгебри логіки
Математична логіка є сучасний вид формальної логіки, науки, що вивчає умовиводи з точки зору їхнього формального створення.
Основи математичної логіки закладено в таких працях англійського математика Джорджа Буля (1815 – 1864) як «Математичний аналіз логіки» (1847) і «Закони мислення» (1854), де він уперше виклав алгебру логіки – алгебру Буля.

Логічні (булеві) змінні
Означення 1.1. Логічними (булевими) змінними в булевій алгебрі називають величини, які незалежно від їхньої конкретної суті можуть набувати лише двох значень.

Логічні (булеві) змінні
Ці значення будемо позначати нулем (0) й одиницею (1), маючи на увазі, що 0 і 1 це формальні символи, що не мають арифметичного змісту, а зображують будь-які змінні, що набувають лише двох значень, наприклад „ТАК” і „НІ”, „ІСТИННО” (І) – „ХИБНО” (Х) і т.д.
Якщо змінна має одиничне значення, то записуємо x=1, а якщо нульове, то x=0.

Булева функція

Сфери застосування булевих функцій
В обчислювальній техніці булеві функції застосовуються для:
опису алгоритмів,
засобів цієї техніки – дискретних пристроїв, які призначаються для перетворення дискретної інформації, що розкладається на елементарні одиниці – біти, які в пристроях реалізуються сигналами, що описуються двійковими змінними – булевими.
Для вирішення деяких економічних задач
Для вирішення задач цілочисельного програмування

Кортеж

Терм

Терм.Приклад

Терм. Додаткова інформація

Терм. Додаткова інформація

Терм. Додаткова інформація

Основні способи подання булевих функцій

Аналітичний спосіб. Приклад

Табличний спосіб. Приклад

Набір функції

Булеві функції однієї змінної

Булеві функції однієї змінної

Область визначення логічної функції

Область визначення логічної функції. Приклад

Кількість булевих функцій.

Елементарні функції алгебри логіки

Елементарні функції алгебри логіки

Функції двох змінних

Функції двох змінних

Функції двох змінних

Функції двох змінних

Функція Шеффера (штрих Шеффера)

Функція (стрілка) Пірса-Вебба

2. Алгебра логіки

Поняття формули в алгебрі логіки

Поняття формули в алгебрі логіки

Приклади формул в алгебрі логіки

Приклади формул в алгебрі логіки

Зв’язок між функцією та формулою в алгебрі логіки

Зв’язок між функцією та формулою в алгебрі логіки

Зв’язок між функцією та формулою в алгебрі логіки. Приклад

Рівносильні формули

Еквівалентність формул

Закони булевої алгебри

Універсальність функції Шефера

Універсальність функції Шефера

Універсальність функції Шефера

Універсальність функції стрілки
Пірса-Вебба

Універсальність функції стрілки
Пірса-Вебба

Універсальність функції стрілки
Пірса-Вебба

3. Повні набори функцій

Повні набори функцій

Повні набори функцій

Повні набори функцій

Повні набори функцій

Повні набори функцій

4. Канонічні форми булевих функцій

Тотожно істинна формула

Тотожно хибна та здійсненна формули

Проблема розв’язуваності

Проблема розв’язуваності

Проблема розв’язуваності

ДДНФ і ДКНФ

Елементарна кон’юнкція

Диз’юнктивна нормальна форма

Диз’юнктивна нормальна форма

Диз’юнктивна нормальна форма. Приклад

Диз’юнктивна нормальна форма. Приклад

Диз’юнктивна нормальна форма

Досконала диз’юнктивна нормальна форма

Досконала диз’юнктивна нормальна форма

Досконала диз’юнктивна нормальна форма. Приклад

Спосіб «розгортання» ДНФ до вигляду ДДНФ деякої функції, що залежить від n змінних

Ще один спосіб «розгортання», виходячи з табличного представлення

Спосіб «розгортання», виходячи з табличного представлення. Приклад

Спосіб «розгортання», виходячи з табличного представлення. Приклад

Спосіб «розгортання», виходячи з табличного представлення. Приклад

Спосіб «розгортання», виходячи з табличного представлення. Приклад

Спосіб «розгортання», виходячи з табличного представлення. Приклад

Елементарна диз’юнкція

Кон’юктивна нормальна форма

Довершена кон’юктивна нормальна форма

Довершена кон’юктивна нормальна форма

Спосіб «розгортання» КНФ деякої функції до вигляду ДКНФ

Спосіб «розгортання» КНФ деякої функції до вигляду ДКНФ. Приклад

Спосіб «розгортання» за табличним поданням функції

Спосіб «розгортання» за табличним поданням функції. Приклад

Спосіб «розгортання» за табличним поданням функції. Приклад

Спосіб «розгортання» за табличним поданням функції. Приклад

5. Спрощення формул

Спрощення формул

Утворення скороченої ДНФ методом Квайна

Операції повного склеювання та поглинання

Теорема Квайна

Метод Квайна. 1 етап. Початкове скорочення формули.

Метод Квайна. 1 етап. Початкове скорочення формули.Приклад

Метод Квайна. 1 етап. Початкове скорочення формули.Приклад

Метод Квайна. 1 етап. Початкове скорочення формули.Приклад

Метод Квайна. 1 етап. Початкове скорочення формули.Приклад

Метод Квайна. 1 етап. Початкове скорочення формули.Приклад

Метод Квайна. 1 етап. Початкове скорочення формули.Приклад

Метод Квайна. 2 етап. Розставляння міток.

Метод Квайна. 2 етап. Розставляння міток. Приклад

Метод Квайна. 3 етап. Знаходження суттєвих доданків.

Метод Квайна. 3 етап. Знаходження суттєвих доданків.

Метод Квайна. 3 етап. Розставляння міток. Приклад

Метод Квайна. 4 етап. Викреслювання зайвих стовпців.

Метод Квайна. 5 етап. Викреслювання зайвих кон’юнкцій скороченої ДНФ.

Метод Квайна. 6 етап. Вибір мінімального покриття.

Метод Квайна. 6 етап. Вибір мінімального покриття. Приклад

Питання, що були розглянуті
Логічні (булеві) функції.
Алгебра логіки.
Повні набори функцій
Канонічні форми булевих функцій.
Спрощення формул. Утворення скороченої ДНФ методом Квайна