Логічні операції та їх властивості

Кон'юнкція або логічне множення (в теорії множин - це перетин)

Кон'юнкція є складним логічним виразом, яке істинно в тому і тільки тому випадку, коли обидва простих висловлювання є істинними. Така ситуація можлива лише в єдиному випадку, у всіх інших випадках кон'юнкція помилкова.

позначення: , $ \ Wedge $, $ \ cdot $.

Таблиця істинності для кон'юнкції

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

Диз'юнкція або логічне додавання (в теорії множин це об'єднання)

Диз'юнкція є складним логічним виразом, яке істинно практично завжди, за винятком, коли всі вирази помилкові.

Таблиця істинності для диз'юнкції

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

Заперечення, логічне заперечення або інверсія (в теорії множин це заперечення)

Заперечення - означає, що до вихідного логічного виразу додається частка НЕ або слова НЕВІРНО, ЩО і в результаті отримуємо, що якщо вихідне вираз істинний, то заперечення вихідного - буде хибно і навпаки, якщо вихідне вираз помилково, то його заперечення було це слово.

Позначення: не $ A $, $ \ bar $, $ ¬A $.

Таблиця істинності для інверсії

«Подвійне заперечення» $ ¬¬A $ є наслідком судження $ A $, тобто має місце тавтологія у формальній логіці і дорівнює самому значенню в булевої логіки.

Імплікація або логічне слідування

Імплікація - це складне логічне вираз, яке істинно у всіх випадках, крім як з істини слід брехня. Тобто, дана логічна операція пов'язує два простих логічних вирази, з яких перше є умовою ($ A $), а друге ($ A $) є наслідком умови ($ A $).

Позначення: $ \ to $, $ \ Rightarrow $.

Таблиця істинності для імплікації

$ A \ to B = ¬A \ vee B $.
Імплікація $ A \ to B $ помилкова, якщо $ A = 1 $ і $ B = 0 $.
Якщо $ A = 0 $, то імплікація $ A \ to B $ істинна при будь-якому значенні $ B $, (з брехні може слідувати істинна).

Еквівалентність або логічна рівнозначність

Еквівалентність - це складне логічне вираз, яке істинно на рівних значеннях змінних $ A $ і $ B $.

Позначення: $ \ leftrightarrow $, $ \ Leftrightarrow $, $ \ equiv $.

Таблиця істинності для еквівалентності

Еквівалентність істинна на рівних наборах значень змінних $ A $ і $ B $.
КНФ $ A \ equiv B = (\ bar \ vee B) \ cdot (A \ cdot \ bar) $
ДНФ $ A \ equiv B = \ bar \ cdot \ bar \ vee A \ cdot B $

Сувора диз'юнкція або складання по модулю 2 (в теорії множин це об'єднання двох множин без їх перетину)

Сувора диз'юнкція істинна, якщо значення аргументів не рівні.

Для функції трьох і більше змінних результат виконання операції буде істинним тільки тоді, коли кількість аргументів рівних $ 1 $, складових поточний набір - непарне. Така операція природним чином виникає в кільці відрахувань по модулю 2, звідки і походить назва операції.

Позначення: $ A \ oplus B $ (в мовах програмування), $ A ≠ B $, $ A \ wedge B $ (в мовах програмування).

Таблиця істинності для операції додавання по модулю два

Властивості суворої диз'юнкції:

$ A \ oplus 0 = a $ (ідемпотентність)
$ A \ oplus 1 = \ bar $ (заперечення)
$ A \ oplus a = 0 $ (отримання 0)
$ A \ oplus b = b \ oplus a $ (коммутативность)
$ (A \ oplus b) \ oplus c = a \ oplus (b \ oplus c) $ (асоціативність)
$ (A \ oplus b) \ oplus b = a $ (поглинання)
$ \ Bar \ oplus b = a \ oplus \ bar = (a \ equiv b) $ (порівняння по модулю)

стрілка Пірса

Бінарна логічна операція, булева функція над двома змінними. Названа на честь Чарльза Пірса і введена в алгебру логіки в $ 1880-1881 $ рр.

Позначення: $ \ downarrow $. АБО НЕ

Таблиця істинності для стрілки Пірса

Стрілка Пірса, як і кон'юнкція, диз'юнкція, заперечення, утворює базис для булевих функцій двох змінних. За допомогою стрілки Пірса, можна побудувати всі інші логічні операції, наприклад:

$ X \ downarrow X = ¬X $ - заперечення

$ (X \ downarrow Y) \ downarrow (X \ downarrow Y) \ equiv X \ vee Y $ - диз'юнкція

$ (X \ downarrow X) \ downarrow (Y \ downarrow Y) \ equiv X \ wedge Y $ - кон'юнкція

$ ((X \ downarrow X) \ downarrow Y) \ downarrow ((X \ downarrow X) \ downarrow Y) = X \ to Y $ - імплікація

В електроніці стрілка Пірса представлена у вигляді елемента, який носить назву «операція 2ИЛИ-НЕ» (2-in NОR).

штрих Шеффера

Булева функція двох змінних або бінарна логічна операція. Введена в розгляд Генрі Шеффер в 1913 р

Позначення: $ | $, еквівалентно операції І-НЕ.

Таблицею істинності для функції штрих Шеффера

Штрих Шеффера утворює базис для всіх булевих функцій двох змінних. Застосовуючи штрих Шеффера можна побудувати інші операції, наприклад,

$ X \ mid X = ¬X $ - заперечення

$ (X \ mid Y) \ mid (X \ mid Y) = (X \ wedge Y) $ - кон'юнкція

$ (X \ mid X) \ mid (Y \ mid Y) = X \ vee Y $ - диз'юнкція

$ X \ mid ¬X $ - константа 1

Для електроніки це означає, що реалізація схем можлива з використанням одного типового елемента (правда це найдорожчий елемент).

Порядок виконання логічних операцій в складному логічному вираженні

Інверсія (заперечення);
Кон'юнкція (логічне множення);
Диз'юнкція і сувора диз'юнкція (логічне додавання);
Імплікація (наслідок);
Еквівалентність (тотожність).

Вирішуємо контрольні з усіх предметів. 10 років досвід! Ціна від 100 руб. термін від 1 дня!