· Пріоритет логічних операцій;
· Тотожне справжні і тотожно хибні операції;
· Основні закони алгебри логіки;
· Доказ логічних законів;
· Найпростіші перетворювачі інформації;
Якщо складне висловлювання істинно для всіх значень назв змінних, то такий вислів називається тотожно істинною або тавтологією (позначається константою 1).
НАПРИКЛАД вислів: "Демократ - це людина, що сповідує демократичні переконання" - завжди істинно, тобто є тавтологією.
Всі математичні, фізичні та ін. Закони є тавтологія. Наприклад: (а + b) 2 = a 2 + 2ab + b 2
Прогноз погоди на завтра може бути, наприклад, таким: "Дощ буде або дощу не буде". Такий прогноз буде завжди істинним, хоча навряд чи кого влаштує. Його математична запис:
(Згідно із законом виключеного третього завжди має бути істинним або судження, або його заперечення).
Перевірити, чи є складне висловлювання тотожне істинним, можна по таблиці істинності.
Якщо складне висловлення помилкове при всіх значеннях вхідних в нього змінних, то такий вислів називається тотожним помилковий (позначається константою 0).
НАПРИКЛАД, висловлювання: "Сьогодні субота, а це - другий день тижня" є тотожним хибним. Тотожно хибним є і наступний вислів: "Комп'ютер увімкнений і комп'ютер не включений (вимкнений)". Математична запис його така:
(Згідно із законом суперечності: не можуть бути одночасно істинними твердження і його заперечення.)
Якщо значення складних висловлювань збігаються при всіх можливих значеннях вхідних в них змінних, то такі висловлювання називають рівносильними, тотожні, еквівалентну
Спрощення складних висловлювань - це заміна висловлювання на рівносильну їй на основі законів алгебри висловлювань
ОСНОВНІ ЗАКОНИ (рівносильно) АЛГЕБРИ ЛОГІКИ
· Логіка, як наука;
· Пріоритет логічних операцій;
· Тотожне справжні і тотожно хибні операції;
· Основні закони алгебри логіки;
· Доказ логічних законів;
· Найпростіші перетворювачі інформації;
При вирішенні логічних завдань часто доводиться спрощувати формули. Спрощення формул в булевої алгебри проводиться на основі еквівалентних перетворень, що спираються на основні закони.
Закони логіки висловлювань - це такі вирази, яким завжди відповідає істинне висловлювання, які б підстановки значень ми не робили замість змінних. В алгебрі висловлювань логічні закони виражаються у вигляді формул.
1.1. Закон тотожності:
- будь-яка думка тотожна самій собі, тобто "А є А", де А - будь-яке висловлювання.
2. Закон виключеного третього:
- в один і той же момент часу висловлювання може бути або істинним, або хибним, третього не дано. Істинно або А, або не А.
НАПРИКЛАД. "Число 123 або парне, або непарне, третього не дано".
Закон виключеного третього не є законом, який визнається всіма логіками як універсального закону логіки. Цей закон застосовується там, де пізнання має справу з жорсткою ситуацією: або-або, істина-брехня. Там же де зустрічається невизначеність (наприклад, в міркуваннях про майбутнє), закон виключеного третього часто не може бути застосований.
Розглянемо наступний вислів: "Ця пропозиція помилково". Воно не може бути істинним, тому, що воно стверджує, що воно помилкове. Але воно не може бути і помилковим, тому що тоді воно було б неправдою. Це висловлювання неправдиве і не помилково, а тому порушується закон виключеного третього.
Парадокс (грец. Paradoxos - несподіваний, дивний) виникає через те, що пропозиція посилається саме на себе. Іншим відомим парадоксом є завдання про перукаря:
"В одному місті перукар стриже волосся всім жителям, крім тих, хто стриже себе сам. Хто стриже волосся перукаря?"
В нашій формальної системі немає можливості ввести таке посилається саме на себе тлумачення, тому ми не можемо висловити всі можливі думки і доводи.
3. Закон несуперечливий:
- не можуть бути одночасно істинними судження і його заперечення. Тобто, якщо висловлювання А - істинно, то його заперечення А повинно бути помилковим (і навпаки). Тоді їх твір буде завжди помилковим.
Саме ця формула часто використовується при спрощення складних логічних виразів.
Іноді цей закон формулюється так: два суперечать один одному висловлювання не можуть бути одночасно істинними.
ПРИКЛАД. Е = "На Марсі є життя і на Марсі життя немає"
4. Закон подвійного заперечення:
- якщо заперечувати двічі деякий вислів, то в результаті виходить оригінал висловлювання.
НАПРИКЛАД: А = "Невірно. Що Матроскін не кіт"
еквівалентно висловом А = "Матроскін - кіт".
Заперечення одночасної істинності
Мнемонічне правило. У лівій частині тотожності операція заперечення стоїть над усім висловлюванням. У правій частині вона як би розривається і заперечення стоїть над кожним з простих висловлювань, але одночасно змінюється операція диз'юнкція на кон'юнкцію і навпаки.
"Невірно, що я знаю арабська або китайська мова" тотожне тому, що "Я не знаю арабської мови і не знаю китайської мови"
"Невірно, що я вивчив урок і отримав по ньому двійку" тотожне тому, що "або я не вивчив урок, або я не отримав двійку"
Операцій імплікації і еквівалентності іноді немає серед логічних операцій конкретного комп'ютера або транслятора з мови, а при вирішенні завдань вони потрібні. Існують формули заміни даних операцій з використанням тільки операцій заперечення, диз'юнкції і кон'юнкції. Так, замість операції імплікації можна використовувати наступне тотожне вираз:
A → B = A V B
Для заміни операції еквівалентності існує два вирази:
A <=> B = (A ^ B) V (A ^ B)
A <=> B = (A V B) ^ (A V B)
Знання даних формул допомагає, наприклад, правильно побудувати заперечення імплікації.
Розглянемо наступний приклад.
Нехай дано висловлювання:
Е = "Невірно, що якщо я виграю конкурс, то отримаю приз"
Нехай А = "Я виграю конкурс", В = "Я отримаю приз", тоді
Е = (A → B) = (A V B) = A ^ B = A ^ B,
тобто Е = "Можливо, що я виграю конкурс, але приз не отримаю".
Інтерес представляють і такі формули:
А → B = B → A
A <=> B = (A → B) ^ (B → A)
Довести їх справедливість можна також за допомогою таблиць істинності. Цікаво їх вираження в розмовній мові. Наприклад, фраза "Якщо Вінні-Пух з'їв мед, то він ситий" тотожна фразі "Якщо Вінні-Пух ситий, то меду він не їв".
Доказ ЛОГІЧНИХ ЗАКОНІВ
· Логіка, як наука;
· Пріоритет логічних операцій;
· Тотожне справжні і тотожно хибні операції;
· Основні закони алгебри логіки;
· Доказ логічних законів;
· Найпростіші перетворювачі інформації;
Для того, щоб використовувати будь-які закони в практиці, необхідно бути впевненим у їх правильності. Довести закон алгебри висловлювань можна:
побудувавши таблицю істинності для правої і лівої частини закону;
виконавши еквівалентні перетворення над правою і лівою частиною формули для приведення їх до одного виду;
за допомогою діаграм Ейлера-Венна;
шляхом правильних логічних міркувань.
Спрощення складних висловлювань - це заміна їх на рівносильні їм на основі законів алгебри висловлювань.
При спрощення складних висловлювань терміни вживаються в такому прийоми:
по властивості констант
X = Х ^ 1, Х = X V 0
за законом виключеного третього
за законом суперечності
за законом ідемпотентності
В = В V В = B V B V B V B,
C = C ^ C = C ^ C ^ C ^ C
за законом подвійного заперечення
Приклад 1. Спростити: А ^ В V А ^ В
Згідно із законом дистрибутивности винесемо А за дужки:
А ^ В V А ^ В = A ^ (B V B) = А ^ 1 = А
Приклад 2. (перший спосіб)
Спростити: (А V В) ^ (А V В)
Розкриємо дужки згідно із законом дистрибутивности:
(А V В) ^ (А V В) = A V (B ^ B) = A V 0 = А
Приклад 2. (другий спосіб)
Спростити: (А V В) ^ (А V В)
Перемножимо дужки (як в звичайній алгебрі) на підставі того ж закону дистрибутивности:
= A ^ A V A ^ B V B ^ A V B ^ B =
= A V A ^ (B V B) V 0 = = A V A ^ 1 = А
Спростити: X V X ^ Y
На перший погляд, приклад не дозволяє його спростити, так як в цьому виразі нічого не можна винести за дужки. Зауважимо, що "хочеться", щоб у змінної Х "з'явився" Y. Для цього представимо
Х як Х ^ 1. а 1 розпишемо по закону виключеного третього
Далі розкриємо дужки.
= X ^ Y V X ^ Y V X ^ Y =
додамо до отриманого виразу X ^ Y.
= X ^ Y V X ^ Y V X ^ Y V X ^ Y =
= X ^ (Y V Y) V Y ^ (X V X) =
Спростити: A ^ C V B ^ C V A ^ B
Один з можливих варіантів спрощення полягає в тому, щоб додати до останнього доданку змінну С. Це робиться стандартним способом: помножити А ^ B на 1, а 1 розписати як (С V C).
A ^ C V B ^ C V A ^ B ^ 1 =
A ^ C V B ^ C V A ^ B ^ (C V C) =
A ^ C V B ^ C V A ^ B ^ C V B ^ C) =
A ^ C V B ^ C V A ^ B ^ C V A ^ B ^ C =
A ^ C ^ (1 V B) V B ^ C ^ (1 V A) =
A ^ C ^ 1 V B ^ C ^ 1 =
Спростити: (X V Y)