Логічні змінні. Логічні вирази та їх таблиці істинності. Логічні формули

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

Цікаві факти з історії

Основні положення алгебри логіки були сформульовані англійським математиком та філософом Джорджем Булем (1815-1864) (рис. 2.44). У 1854 році вийшла його основна праця «Дослідження законів думки, на яких засновані математичні теорії логіки й імовірності». Ця книга нині зараховується до математичної класики. У ній досліджується система алгебри, яку сьогодні називають «алгеброю висловлень» або «булевою логікою». Булева логіка стала основним математичним інструментом для створення комп’ютерів.

 

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

 

Запам’ятайте!

Логічна змінна – це змінна, яка може набувати лише значень true або false.

 

Завданням алгебри логіки є визначення істинності логічних виразів – виразів, що складаються з логічних констант, логічних змінних, логічних операцій, дужок, наприклад, `(A \/ B) /\ (A \/ В).

Зрозуміло, що значенням логічного виразу може бути лише true або false.

Для логічних операцій, розглянутих вище, визначений такий пріоритет операцій: заперечення, кон’юнкція, диз’юнкція. Для змінення цього порядку виконання логічних операцій використовують дужки.

Для обчислення значення істинності логічного виразу можна використати таблиці істинності.

Для складання та заповнення таблиці істинності потрібно:

1. Обчислити кількість можливих наборів значень логічних змінних. Якщо формула містить n різнихлогічних змінних, то можливих наборів значень цих змінних буде 2ⁿ . Це число визначає кількість рядків у таблиці істинності.

2. Обчислити кількість логічних операцій у логічному виразі. Ця кількість плюс кількість логічних змінних визначає кількість стовпців таблиці.

3. Заповнити перші n стовпців усіма можливими наборами значень логічних змінних.

4. Заповнити кожний наступний стовпець значеннями, отриманими при виконанні чергової логічної операції. Черговість встановлюється згідно названого пріоритету операцій.

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

Наприклад, вираз `A \/ B /\ A містить дві логічні змінні, тобто n=2. Значить, усього існує 4 набори можливих значень цих змінних (2ⁿ = 2² =4). Вираз містить 3 логічні операції: заперечення, диз’юнкція і кон’юнкція. Таким чином, таблиця істинності буде складатися з 4 рядків та 5 стовпців. Першою згідно пріоритету буде виконуватись операція заперечення, другою – кон’юнкція, останньою – диз’юнкція, в якій потрібно використовувати результати перших двох операцій.

Отримаємо таку таблицю істинності:

А	В
`A	B /\ A	(`A) (B /\ A)

 

Аналізуючи останній стовпець таблиці істинності, робимо висновок, що вираз буде мати значення false лише у випадку, коли логічні змінні мають такі значення: А = true, B = false. У всіх інших випадках значенням логічного виразу буде true.

Запам’ятайте!

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

Рівність двох логічних виразів утворюють логічну формулу.

 

Наведемо кілька цікавих і корисних логічних формул:

1. – формула подвійного заперечення

2. А \/ А = А – формула поглинання

3. = – формула заперечення диз’юнкції (закон де Моргана)

Для доведення цих рівностей можна скласти і порівняти таблиці істинності логічних виразів у правій і лівій частинах. Пропонуємо вам зробити це самостійно.

 

Цікаві факти з історії

Аугустус де Морган (1806 - 1871) (рис. 2.45) – шотландський математик і логік, професор математики Лонднського університетського коледжу, перший президент Лондонського математичного товариства. Результати своїх досліджень з логіки одержав незалежно від Джорджа Буля і виклав у 1847 році.

Перевірте себе

1. º Що вивчає наука логіка? Що вивчає математична логіка?

2. º Що таке висловлення? Наведіть приклади істинних і хибних висловлень

3. * Які речення не є висловленнями?

4. º Що називається логічною константою?

5. ·Як утворюються складені висловлення? Наведіть приклади

6. · Що таке заперечення? Наведіть приклади.

7. º Для чого використовують таблиці істинності?

8. · Наведіть таблицю істинності заперечення

9. · Що таке кон’юнкція? Наведіть приклади.

10. · Наведіть таблицю істинності кон’юнкції.

11. · Що таке диз’юнкція? Наведіть приклади.

12. · Наведіть таблицю істинності диз’юнкції.

13. º Яка змінна називається логічною?

14. *Чим логічна змінна відрізняється від логічного висловлення?

15. · З чого складаються логічні вирази? Які значення вони можуть набувати?

16. º Назвіть пріоритет логічних операцій.

17. · Наведіть алгоритм складання та заповнення таблиці істинності логічного виразу.

18. ·Які логічні вирази називаються рівними? Що таке логічна формула?

Виконайте завдання

1. · Побудуйте заперечення висловлень та з’ясуйте їх істинність:

а) Число 3 є дільником числа 545.

б) Автомобіль не має права їхати на червоне світло

в) Існують паралелограми з прямими кутами

г) Рівняння 2х² – 3х + 1 = 0 має цілий корінь

є) Не існує натурального числа, що поділяється на 2

ж) Існує ціле число, яке ділиться на всі цілі числа

2. · Серед наступних складених висловлень знайдіть кон’юнкції та диз’юнкції та визначте їх істинність:

а) “Число 27 кратне 3 та кратне 9”

б) “17 < 42 < 18”

в) “Число 2 просте або парне”

г) “∆ АВС є гострокутним, прямокутним або тупокутним”

д) “Діагоналі будь-якого паралелограму перпендикулярні та точкою перетину поділяються навпіл”

є) “7² = 49 і (-7)² = 49”

ж) “Якщо трикутник рівнобедрений, то він рівносторонній”

з) “21 ≤ 21”

и) “21 ≤ 18”.

Кон’юнкція
Диз’юнкція
Ні кон’юнкція, ні диз’юнкція

 

3. · Визначте істинність або хибність складених висловлень для наведених значень змінних:

1. «x > 0 і y > 0 або x < 0 і y < 0»

2. «x > 0 і не y < 0 або x < 0 та y > 0»

Значення змінних:

а) х = 5, у = 8

б) х = 5, у = -8

в) х = -5, у = 8

г) х = -5, у = -8.

4. (ДЗ) · Нехай А = "Іванов вивчає англійську мову", В = "Іванов має оцінку 8 з інформатики". Сформулюйте висловлення:

а) А /\`B б)`А \/ B в) A \/ `A /\ B г) `A \/ `B /\ А

5. º Вкажіть порядок виконання операції у логічних виразах:

а) A \/ `A /\ B

б) `A \/ `B /\ А

в) (A \/`B) /\ (`A \/ `B)

г) `A /\`B \/ C /\ D

6. · Побудуйте таблиці істинності логічних виразів:

а) A \/ A /\ B

б) A \/ `A /\ B

в) A /\ B \/`B

г) (ДЗ) (A \/`B) /\ (`A \/ `B)

д) (ДЗ) `A \/ `B

е) (ДЗ) A /\`B \/`A /\ B

7. Доведіть логічні формули:

a. A /\ A = A

b. =

c. A /\ (B \/ C) = (A /\ B) \/ (A /\ C)

d. (ДЗ) A \/ (B /\ C) = (A \/ B) /\ (A \/ C)

e. (ДЗ) A /\ (A \/ B) º A