Формули алгебри логіки та їх спрощення

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

Приклади формул:

Виникає запитання: яку роль відіграють дужки в алгебрі висловлювань?

В алгебрі висловлювань можна не вживати квадратних або фігурних дужок. Правда, іноді їх застосовують, але тільки для наочності.

В алгебрі висловлювань справедливі такі найважливіші правила:

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

Приклади:

У першому прикладі треба спочатку утворити висловлення , потім , далі і, нарешті, Легко побачити, що роль дужок тут виконує знак операції заперечення.

У другому прикладі порядок побудови висловлення такий:

2. Знак кон’юнкції пов’язує висловлення тісніше, ніж знаки логічних операцій:

Приклади:

У наведених прикладах дужок немає. Проте порядок побудови висловлення в кожному прикладі цілком визначений. Так, у першому прикладі висловлення будуємо в такому порядку У третьому прикладі:

3. Знак диз’юнкції пов’язує висловлення тісніше, ніж знаки логічних операцій:

Приклади:

У цих прикладах спочатку виконуємо логічну операцію диз’юнкції.

4. Знак імплікації пов’язує висловлення тісніше, ніж знаки логічних операцій:

Приклади:

У першому прикладі порядок побудови висловлення такий:

У другому прикладі:

Зауважимо, що іноді для наочності у формулах ставлять дужки там, де вони непотрібні.

Приклади:

Замість пишуть

Замість пишуть

Якщо у формулі зустрічається тільки операція імплікації, то можна записати так: і виконувати операції послідовно зліва направо. Проте для наочності вживаємо дужки і писатимемо: ((А→В)→С)→К.

Формула, яка є кон’юнкцією простих висловлень або їх заперечень, називається елементарною кон’юнкцією.

Приклади:

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

Приклади:

Формула, яка є диз’юнкцією простих висловлень або їх заперечень, називається елементарною диз’юнкцією.

Приклади:

Якщо в елементарній диз’юнкції є висловлення і його заперечення, то така елементарна диз’юнкція дорівнює 1.

Приклади:

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

Приклади:

Наведені правила дають можливість спростити складні формули алгебри висловлень.

Якщо формула містить логічні операції: операцію Шеффера, еквівалентність, заперечення еквівалентності і імплікацію, то спочатку треба замінити ці операції на “бульові” операції (заперечення, диз’юнкцію, кон’юнкцію), а потім застосувати закони бульової алгебри.

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

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

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

 

Порядок виконання роботи

 

1. Завантажте табличний процесор Excel. Викличте майстер функцій. Оберіть категорію «Логічні».

2. Повторіть порядок побудови таблиць істинності. Виконуйте завдання поступово, враховуючи правила порядку дій у алгебрі логіки. Продемонструйте викладачу результати побудови таблиць істинності.

3. Прослідкуйте, щоб кожен стовпчик даних мав відповідній до назви операції заголовок, створений у Microsoft Equation.

4. Залежно від варіанту виконайте завдання обов’язкового рівня:

1 варіант. За допомогою таблиць істинності перевірте, чи є здійсненними формули:

2 варіант. За допомогою таблиць істинності перевірте, чи є здійсненними формули:

Продемонструйте викладачу результати виконання роботи.

5. Зверніться до викладача за індивідуальним завданням достатнього чи високого рівня складності.

6. Підготуйте звіт відповідно до встановленого зразка.