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

Мета: познайомитися з логічними функціями LibreOffice Calc, навчитися будувати таблиці істинності висловлювань різної складності і з їхньою допомогою за таблицею істинності складати структурну формулу.

Обладнання: ПК з встановленою ОС і LibreOffice, (дана) інструкція.

Структура уроку

1. Організаційний момент.
2. Актуалізація опорних знань.
3. Вивчення нового матеріалу.
4. Інструктаж з ТБ.
5. Закріплення вивченого матеріалу.
6. Підбиття підсумків уроку.
7. Домашнє завдання.

Хід уроку

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

2. Актуалізація опорних знань

1. Які категорії функцій використано у LibreOffice Calc?
2. Які вставити запис функції?
3. Що таке висловлювання?
4. Яку змінну називають логічною (булевою)?
5. У чому різниця між логічними змінною і висловлюванням?
6. Назвіть порядок виконання логічних операцій.

3. Вивчення нового матеріалу

Мотивація Логіка розглядає закони і правила логічного мислення, які є відображенням найбільш загальних форм інформаційних процесів об'єктивної реальності. Математична логіка і теорія множин лежать в основі грандіозної будівлі сучасної математики. Вміння працювати з об'єктами математичної логіки (булевими змінними і булевими функціями) — такий щабель наукового пізнання, який неможливо уникнути. Урок присвячено опрацюванню булевих функцій з використанням LibreOffice Calc. Залежно від конкретної ситуації зручно оперувати або формулою певного вигляду, або таблицею істинності. Тому природний інтерес викликає задача переходу від одного вигляду до інщого.

Елементи математичної логіки
Булева алгебра (алгебра булевих функцій, множина логічних функцій) — це втілення життєвого досвіду в апарат математики, формалізація його із запровадженням жорстких правил отримання однозначного результату.

Існує нескінчена множини булевих функцій. Три з них заслуговують особливої уваги. З їх допомогою можна легко й природно побудувати (описати) всі інші. Ще кажуть, що ці три операції породжують всю множину булевих функцій.

Такими функціями є кон'юнкція (логічне «і», логічне множення), диз'юнкція (логічне «або», логічне додавання) і заперечення. Перші дві функції мають по два булевих аргументи, остання — лише один:

• кон'юнкція справджується тоді й лише тоді, коли справджуються обидва її аргументи;

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

• заперечення справджується тоді й лише тоді, коли не справджується її аргумент.

Крім словесних означень булеву функцію зручно означати (описувати) за допомогою таблиці істинності.

Таблиця істинності — це прямокутна таблиця, що виражає відповідність між усіма наборами величин змінних і величин функції. У такій таблиці, як усталено для двозначної логіки, 1 позначає істинність, 0 позначає хибність. У поданій далі таблиці істинності основних булевих функцій перші два стовпчики відведено аргументам A, B, наступні — кон'юнкції (A ∧ B), диз'юнкції (A ∨ B), імплікації (A ⇒ B), еквівалентності (A ⇔ B), штриху Шеффера (A | B) й стрілці Пірса (A ↓ B).

При використанні електронних таблиць (а інколи й у друкованих працях) використовують зарезервовані слова true та false.

Диз'юнктивна нормальна форма (ДНФ) булевої функції — це подання функції диз'юнкцією кон'юнкцій аргументів або їхніх заперечень.

Досконала диз'юнктивна нормальна форма — це така диз'юнктивнa нормальна форма, в якій у кожну кон'юнкцію входять всі змінні (або самі, або їх заперечення), причому в одному й тому самому порядку.

Наприклад, (¬A ∧ ¬B) ∨ (A ∧ B) — досконала диз'юнктивна нормальна форма еквівалентності A ⇔ B.

Алгоритм побудови досконалої диз'юнктивної нормальної форми за таблицею істинності

1. Виділити ті рядки таблиці істинності, в останніх стовпчмках яких міститься 1 (true) — величина функції.

2. Виписати для кожного такого виділеного рядка кон'юнкцію (логічне «і») таким чином: якщо величина змінної цьому рядку дорівнює 1 (true), то в кон'юнкцію записати позначення цієї змінної, інакше — її заперечення.

3. Всі отримані на попередньому кроці кон'юнкції записати елементами диз'юнкції (логічного «або»).

Логічні функції в електронних таблицях
Однією зі складових сучасних інформаційних офісних технологій є програми опрацювання електронних таблиць — табличні процесори. Табличні процесори дозволяють здійснювати широкий спектр технологічних операцій і містять велику кількість вбудованих функцій. Усі функції поділено на категорії: математичні, статистичні, фінансові, текстові, інформаційні та інші. У тому числі логічні. Таким чином, табличні процесори придатні для розв'язування задач булевої алгебри.

У середовищі LibreOffice Calc логічні функції вставляють таким чином. У попередньо підготовленій таблиці встановити курсор миші у потрібну комірку і звернутися до Помічника з функцій, наприклад, натиснувши клавіші Ctrl + F2. У вікні діалогу Function Wizard на закладці Functions вибрати категорію Логічні функції, а в — ній потрібну функцію. Ввести у поля аргументів потрібні параметри і натиснути кнопку Гаразд.

4. Інструктаж з ТБ

5. Закріплення вивченого матеріалу

Завдання 1. Побудувати таблицю істинності для булевої функції двох змінних:

Розв'язання (бажано демонструвати за допомогою проектора). Запишемо функцію за допомогою зарезервованих у мові Pascal слів.

Маємо:
n = 2 — кількість змінних;
p = 6 — кількість операцій;
m = 2ⁿ + 1 = 5 — кількість рядків таблиці разом із заголовками;
s = n + p = 8 — кількість стовпчиків таблиці.

Будуємо таблицю розміром 5×8 (на поданій далі ілюстрації у діапазоні клітин A3:H7). Встановивши послідовність виконання логічних операцій з урахуванням дужок і пріоритетів, заповнюємо таблицю істинності (зліва направо), виконуючи логічні операції відповідно до встановленої послідовністі.

При цьому вміст клітинок такий:

• C4 =not(A4);
• D4 =not(B4);
• E4 =and(C4;B4);
• F4 =or(A4;D4);
• G4 =not(F4);
• H4 =or(E4;G4).

Вміст перелічених вище комірок рядка 4 скопійовано у клітинки, розташовані нижче у тому самому стовпчику.

Відповідь (подано лише для завдання 1): (¬ X ∧ Y).

Примітка. Описаний спосіб створення таблиці істинності відтворює без змін дії людини. Використовуючи середовище опрацювання електронних таблиць, можна спокуситися створювати таблиці істинності без обчислення проміжних результатів. Тобто обчислювати функцію з посиланням лише на комірки, що містять величини аргументів. Краще утриматися від цього нетехнологічного рішення. Інакше виникнуть великі труднощі пошуку можливих помилок. А стовпчики з проміжними результатами (C, D, E, F, G для розглянутого прикладу) можна сховати.

Завдання 2. У середовищі LibreOffice Calc побудувати таблицю істинності булевої функції трьох змінних.

1 варіант: X ∨ (¬Y) ⇒ (¬Z).
2 варіант: (X ∨ Y) ∧ (X ∨ Z) ⇔ X ∨ Y ∧ Z.

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

Вказівка: використати еквівалентність імплікації (A ⇒ B) і диз'юнкції (¬A ∨ B). Наявність трьох змінних призводить до розгляду восьми наборів величин аргументів: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).

Після виконання завдання перевірити правильність результатів, порівнявши побудовану таблицю істинності зі зразками.

1 варіант



2 варіант

6. Підбиття підсумків уроку
Виставлення оцінок. Демонстрація результату побудови таблиці істинності булевої функції чотирьох змінних.

При цьому вміст клітинок такий:

• E4 =not(A4);
• F4 =not(B4);
• G4 =not(C4);
• H4 =and(E4;F4);
• I4 =and(G4;D4);
• J4 =not(H4);
• K4 =or(J4;I4).

7. Домашнє завдання

Ознайомитися з таким матеріалом.

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

Досконала кон'юнктивна нормальна форма — така кон'юнктивна нормальна форма, в якій у кожну диз'юнкцію входять всі змінні (або самі, або їх заперечення), причому в одному й тому самому порядку.

Наприклад, (¬A ∨ B) — досконала кон'юнктивна нормальна форма імплікації A ⇒ B.

Алгоритм побудови досконалої кон'юнктивної нормальної форми за таблицею істинності

1. Виділити ті рядки таблиці істинності, в останніх стовпцях яких міститься 0 (false) — величина функції.

2. Виписати для кожного такого виділеного рядка диз'юнкцію (логічне «або») таким чином: якщо величина змінної цьому рядку дорівнює 0 (false), то в кон'юнкцію записати позначення цієї змінної, інакше — її заперечення.

3. Всі отримані на попередньому кроці кон'юнкції записуємо елементами кон'юнкції (логічного «і»).

Примітка. (Досконалу) кон'юнктивну нормальну форму отримують запереченням (досконалої) диз'юнктивної нормальної форми заперечення булевої функції з використанням правил де Моргана:

• заперечення кон'юнкції еквівалентна диз'юнкції заперечень;
• заперечення диз'юнкції еквівалентна кон'юнкції заперечень,

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

Текст упорядкувала Тетяна Костянтинівна Семенова, вчитель гімназії № 267 Дарницького району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 29 жовтня по 28 грудня 2012 року.