Сьогодні ми разом навчимося спрощувати логічні вирази, познайомимося з основними законами і вивчимо таблиці істинності функцій логіки.
Почнемо з того, навіщо потрібен цей предмет. Ви ніколи не помічали, як розмовляєте? Зверніть увагу на те, що наша мова і дії завжди підкоряються законам логіки. Для того щоб знати результат якої-небудь події і не потрапити в халепу, вивчіть прості і зрозумілі закони логіки. Вони допоможуть вам не тільки отримати гарну оцінку з інформатики або набрати більше балів на єдиному державному іспиті, але і діяти в життєвих ситуаціях не навмання.
Операції
Для того щоб навчитися спрощувати логічні вирази, необхідно знати:
які функції є в булевої алгебри; закони скорочення і перетворення виразів; порядок виконання операцій. Зараз ми розглянемо ці питання дуже докладно. Почнемо з операцій. Їх досить легко запам'ятати.
Першим ділом ми відзначимо логічне множення, у літературі його називають операцією кон'юнкції. Якщо умова записано у вигляді виразу, то операція позначається перевернутої галочкою, знаком множення або «&». Наступна найбільш часто зустрічається функція – логічне додавання або диз'юнкція. Її відзначають галочкою або знаком плюс. Дуже важлива функція заперечення або інверсії. Згадайте, як у російській мові ви виділяли приставку. Графічно інверсія позначається знаком приставки перед виразом або горизонтальною лінією над ним. Логічний наслідок (чи імплікація) позначається стрілкою від значення до слідства. Якщо розглядати операцію з точки зору російської мови, то вона відповідає таким видом побудови речення: «якщо, то». Далі йде еквіваленція, яка позначається двосторонньою стрілкою. У російській мові операція має вигляд: «тоді». Штрих Шеффера розділяє два вирази вертикальною рискою. Стрілка Пірса, аналогічно штрихові Шеффера, поділяє вираження вертикальною стрілкою, спрямованою вниз. Обов'язково запам'ятайте те, що операції необхідно виконувати в суворій послідовності: заперечення, множення, додавання, слідство, еквівалентність. Для операцій «штрих Шеффера» і «стрілка Пірса» немає правила черговості. Отже, їх потрібно виконувати в тій послідовності, в якій вони стоять у складному вираженні.
Таблиці істинності
Спростити логічний вираз і побудувати таблицю істинності для подальшого його вирішення неможливо без знання таблиць основних операцій. Зараз ми пропонуємо, щоб з ними познайомитися. Зверніть увагу на те, що значення можуть приймати або істинне, або хибне значення. Для кон'юнкції таблиця виглядає наступним чином:
Вираз №1
Вираз №2
Підсумок
Брехня
Брехня
Брехня
Брехня
Істина
Брехня
Істина
Брехня
Брехня
Істина
Істина
Істина
Таблиця для операції диз'юнкція:
Вираз №1
Вираз №2
Підсумок
-
-
-
-
+
+
+
-
+
+
+
+
Заперечення:
Вхідна значення
Підсумок
Справжнє вираження
-
Помилкове висловлення
+
Наслідок:
Вираз №1
Вираз №2
Підсумок
-
-
Істина
-
+
Істина
+
-
Брехня
+
+
Істина
Рівнозначність:
Вираз №1
Вираз №2
Підсумок
Помилкове
Помилкове
+
Помилкове
Справжнє
-
Справжнє
Помилкове
-
Справжнє
Справжнє
+
Штрих Шиффера:
Вираз №1
Вираз №2
Підсумок
0
0
Істина
0
1
Істина
1
0
Істина
1
1
Брехня
Стрілка Пірса:
Вираз №1
Вираз №2
Підсумок
-
-
+
-
+
-
+
-
-
+
+
-
Закони спрощення
На питання про те, як спрощувати логічні вирази в інформатиці, нам допоможуть знайти відповіді прості і зрозумілі закони логіки.
Почнемо з самого простого закону суперечності. Якщо ми множимо протилежні поняття (А і неА), то отримуємо брехня. У разі складання протилежних понять, ми отримуємо істину, цей закон має назву «закон виключеного третього». Часто в булевої алгебри зустрічаються вирази з подвійним запереченням (не неА), в такому разі ми отримуємо відповідь А. Також є два закони де Моргана:
якщо у нас є заперечення логічного додавання, то ми отримуємо множення двох виразів з інверсією (не(А+В)=неА*неВ); аналогічно діє і другий закон, їли ми маємо заперечення операції множення, то отримуємо додавання двох значень з інверсією. Дуже часто зустрічається дублювання, одне і те ж значення (А або В) складається або множиться між собою. У такому випадку діє закон повторення (А*А=А або В+В=В). Мають місце і закони поглинання:
А+(А*В)=А; А*(А+В)=А; А*(неА+В)=А*В. Є два закони склеювання:
(А*В)+(А*В)=А; (А+В)*(А+В)=А. Спрощувати логічні вирази нескладно, якщо знати закони булевої алгебри. Всі перераховані в цьому розділі статті закони можна перевірити дослідним шляхом. Для цього варто відкрити дужки за законами математики.
Приклад 1
Ми вивчили всі особливості спрощення логічних виразів, тепер необхідно закріпити свої нові знання на практиці. Ми пропонуємо вам розібрати разом три приклади зі шкільної програми і квитків єдиного державного іспиту.
У першому прикладі нам потрібно спростити вираз: (С*Е)+(З неї). Насамперед ми звертаємо свою увагу на те, що і в першій, і в другій дужці є одна і та ж змінна, пропонуємо вам винести її за дужки. Після виконаної маніпуляції ми отримуємо вираз: С*(Е+неї). Раніше ми розглянули закон виключення третього, застосуємо його щодо цього виразу. Слідуючи йому, ми можемо стверджувати, що Е+неї=1 отже, наше вираз приймає вигляд:*1. Отриманий вираз ми можемо ще спростити, знаючи, що З*1=С.
Приклад 2
Наступне наше завдання буде звучати так: чому буде дорівнювати спрощене логічне вираження не(С+неї)+(С+Е)+С*Е? Зверніть увагу, в даному прикладі є заперечення складних виразів, від цього варто позбуватися, керуючись законами де Моргана. Застосувавши їх, ми одержимо вираз: ніс*Е+ніс*неї+С*Тобто Ми знову спостерігаємо повторення змінної в двох доданків, виносимо за дужки: ніс*(Е+неї)+С*Е. Знову застосовуємо закон виключення: ніс*1+С*Е. Згадуємо вислів «ніс*1» дорівнює ніс: ніс+С*Е. Далі пропонуємо застосувати розподільний закон: (ніс+С)*(ніс+Е). Застосовуємо закон виключення третього: ніс+Е.
Приклад 3
Ви переконалися в тому, що на насправді дуже просто спростити логічний вираз. Приклад №3 буде розписаний менш докладно, постарайтеся зробити його самостійно. Спростіть вираз: (D+Е)*(D+F).
D*D+D*F+E*D+E*F; D+D*F+E*D+E*F; D*(1+F)+ E*D+E*F; D+ E*D+E*F; D*(1+E)+E*F; D+E*F. Як бачите, якщо знати закони спрощення складних логічних виразів, то дане завдання ніколи не викличе у вас труднощів.