Розкладання по змінним дозволяє замінювати в функції змінні на константи, виносячи відповідні змінні вліво від функцій. У наведеному прикладі розкладання вдалося функцію 4-х змінних розкласти в вираз, в якому функція залежить лише від двох змінних.
1.2.3. Властивості розкладання по змінним. При m = 1 отримуємо розкладання функції по одній змінної:
Інший важливий випадок: m = n. При цьому всі змінні в правій частині (1.1) отримують фіксовані значення. Функції в правій частині перетворюються в константи 0 або 1 і вступають в кон'юнкцію з усіма змінними. Наприклад, при m = 2 маємо:
Обчисливши истинностное значення функції у всіх чотирьох різних інтерпретаціях, необхідно підставити ці значення в формулу. Нехай, наприклад, f (0, 1) = 0, f (0, 0) = 1, f (1, 0) = 1, f (1, 1) = 0, тоді f (x1, x2) = x1 0 × x2 0 + x1 1 × x2 0. Або компактно:. Легко помітити, що отриманий вираз для функції лежить в області булевої алгебри, так як містить лише булеві операції.
У загальному вигляді властивість розкладання по всім змінним має вигляд:
тобто кожна диз'юнкція відповідає набору змінних, звертає вихідну функцію в 1.
Праву частину (1.3) називають досконалої диз'юнктивній нормальною формою (СДНФ). Будь-ФАЛ ставиться у відповідність єдина СДНФ. Це дозволяє говорити про СДНФ як про стандартній формі запису ФАЛ у вигляді функції БА спеціального виду.
Надалі буде показано, як робити переклад будь-якої функції в СДНФ.
Для отримання СДНФ згідно (1.3) потрібно інформація про наборах, в яких функція звертається в 1. Така інформація є в таблиці істинності. Але відомо також, що ФАЛ має два способи представлення: у вигляді таблиці істинності і у вигляді формули, полінома двійковій алгебри логіки. Якщо є трохи таблиця істинності, а поліном, то можна отримати СДНФ, використовуючи тільки його. Для цього формулу поетапно видозмінюють, не змінюючи її змісту, і поступово приводять в форму СДНФ.
1.2.4. Повнота булевої алгебри. (1.3) приводить до важливого висновку.
Теорема 1.2. БА, що використовує 3 операції: кон'юнкцію, диз'юнкцію і заперечення - є повною.
Таким чином, 3-х операцій досить для вираження через них будь-ФАЛ і формалізації будь-якого словесного висловлювання.
Для доказу досить поглянути на (1.3), тут видно, що будь-яка функція (зліва) може бути представлена комбінацією 3-х операцій (праворуч). (1.3) не описує лише одну функцію: в цій функції немає жодного набору, звертає її в 1. Ця функція - константа 0. Але неважко показати, що. Теорема доведена.
1.2.5. Перехід в булеву алгебру. Щоб отримати СДНФ з ППФ, спочатку необхідно здійснити перехід в БА. Адже в СДНФ присутні лише три операції. Складні висловлювання реальної мови не обмежені спілками «І», «АБО» і часткою «НЕ». Складові висловлювання формуються з використанням всіх операцій з табл. 2.
З'ясувавши повноту БА, ми можемо бути впевнені, що будь-яка логічна функція, в тому числі будь-яка бінарна логічна операція, виражається через «І», «АБО» і «НЕ». Наступні два співвідношення інтерпретують операції еквівалентності і імплікації. Використовуючи табл. 2, читач легко доведе їх перевіркою на всіх можливих інтерпретаціях атомів.
Читачеві рекомендується завести таблицю рівності, що виконують переклад будь-якої операції з табл. 2 в операції БА.
1.2.6. Властивості булевих операцій. Булеві операції мають деякі властивості, перевірити які можна, будуючи таблиці істинності для виразів, що стоять в равенствах зліва і справа, або логічними міркуваннями, виходячи з ідентичності сенсу виразів справа і зліва:
Друге застосування закону де Моргана дає:
що збігається з результатом, отриманим по таблиці істинності.
1.2.13. Доведення еквівалентності формул. Отже, СДНФ і СКНФ - це стандартні форми запису ФАЛ. Більш того, взаімооднозначном функції з її СДНФ використовується при доведенні еквівалентності двох функцій (формул). Послідовно привівши дві формули до СДНФ, роблять висновок про їх еквівалентності, якщо СДНФ обох збігаються.
1.2.14. Створення еквівалентних формул шляхом приведення до СДНФ.
Теорема 1.3. Для будь-яких двох еквівалентних формул F 1 і F 2 існує еквівалентну перетворення F 1 в F 2 за допомогою співвідношень (1.4) - (1.17).
Доведення. Так як F 1 і F 2 еквівалентні, то їх СДНФ збігаються. Читаючи співвідношення (1.4) - (1.17) у зворотний бік, можна від СДНФ F 2 перейти до самої F 2. Тоді з F 1 перейдемо до СДНФ, а від СДНФ перейдемо до F 2. Отримана таким чином ланцюжок перетворень показує еквівалентність формул F 1 і F 2. Теорема доведена.
1.2.15. Двоїстість. Як показала практика, еквівалентності важливі в роботі з ФАЛ, тому не зайвим буде описати ще один спосіб отримання еквівалентностей. Це апарат двоїстих функцій.
1.2.16. Принцип подвійності. Використовуючи визначення подвійності, неважко прямий викладкою довести принцип подвійності. якщо у формулі, що представляє функцію, все знаки функцій замінити подвійними функціями, то отримана формула буде описувати функцію, двоїсту вихідної функції.
В БА кон'юнкція двоїста диз'юнкції, одиниця - нулю, заперечення самодвоїстих. Використовуючи це, в БА отримують нові еквівалентні співвідношення. Замінивши в лівій частині + на , на +, 1 на 0 і 0 на 1, отримують подвійну до лівої частини формулу, потім роблять те ж з правою частиною і отримані формули прирівнюють. Два співвідношення поглинання отримані саме так.
1.3.Методіка рішення типових задач
1.3.1. Формалізація висловлювань. Завдання формалізації висловлювання - поставити у відповідність висловом формулу, яка відображатиме його внутрішню структуру.
Для вирішення завдання формалізації висловлювання необхідно виділити у висловленні «атоми» - неподільні частини, елементарні висловлювання. Цим висловлюванням найбільш просто зіставити логічний зміст: «істина» або «брехня». У записі формули, еквівалентній лінгвістичного твердженням, елементарні висловлювання відповідають атомам (іменах змінних).
Розглянемо приклад: «Якщо вогонь горить і дрова сухі, то зараз темно або холодно. Якщо ж дрова не сухі, то невірно, що зараз темно або холодно, крім того, якщо вогонь не горить, то холодно. З усього вищесказаного випливає, що або холодно і дрова сухі, або зараз темно і вогонь горить ». Виділимо атоми: x - «вогонь горить», y - «дрова сухі», z - «зараз темно», h - «зараз холодно».
Після визначення атомів необхідно відновити структуру вихідного висловлювання за допомогою логічних зв'язок. Основні конструкції мови, що задають структуру висловлювання, представлені в табл. 3. Якщо в висловлюванні структура задається мовними зворотами, що не представленими в табл. 3, необхідно спробувати звести їх до табличних. Для цього сумнівний оборот замінюють відомим (з табл. 3) і, якщо структура і зміст висловлювання зберігаються, то застосовується заміна обороту табличним.
Зведені дані про логічних операціях
Висловлювання з прикладу складається з 3-х пропозицій. Формалізуємо кожне з них окремо з урахуванням зафіксованих атомів:
1. «Якщо вогонь горить і дрова сухі, то зараз темно або холодно»: Так як імплікація відноситься до обох атомів, z і h. їх необхідно відокремити роздільниками.
2. «Якщо ж дрова не сухі, то невірно, що зараз темно або холодно, крім того, якщо вогонь не горить, то холодно»: Завдання ускладнилася появою зв'язки «крім того», заміна цієї зв'язки кон'юнкція «і» не змінює сенсу сказаного . Зв'язка «і» є однією з найбільш «сильних», тому потрібні роздільники, щоб в кон'юнкцію вступали потрібні частини пропозиції. Крім того, фраза «невірно, що зараз темно або холодно» може бути записана двома еквівалентними способами:
З через великий обсяг цей матеріал розміщений на декількох сторінках:
1 2 3 4 5 6 7
Підпишіться на розсилку:
Цікаві новини
важливі теми
Огляди сервісів Pandia.ru
Росія
могутня держава!
обчислення
це отримання з вхідних даних нового знання
Проекти по темі:
Математика
логіка