1.    Логіка висловлювань. Елементарні логічні функції.
2.    Рівносильні формули для логічних функції.
3.    Принципи двоїстості.
4.    Схеми реалізації елементарних логічних операцій. Типові логічні вузли.

I. При записі тих чи інших логічних виразів використовується спеціальна мова, яка є прийнятою в математичній логіці. Основоположником математичної логіки є німецький математик Лейбніц. Він зробив першу спробу побудувати універсальну мову, з допомогою якої можна було б вирішувати суперечки між людьми через обчислення. На закладеній Лейбніцем  основі ірландський математик Джордж Буль побудував нову науку, яка могла оперувати не числами, а висловленнями. На честь Д. Буля логічні функції прийнято називати Булевими.
Висловлення – це будь-яке твердження, відносно яких можна сказати хибне воно чи істинне.
В математичній логіці та теорії інформатики прийняті такі позначення:
хибне                     0           false          [’fo:ls]
істинне                  1            true           [’tru:]
Логічні функції можуть бути унарними та бінарними. До унарних операцій належать:

Назва        Значення змінної   
0    1   
нуль, хибність    0    0    0    константа
тотожність    x    0    1   
заперечення    ¬х, , ,Not
1    0    не
одиниця, істинність    1    1    1    константа


Характерною рисою мат. логіки є сучасний формальний аксіоматичний метод, розроблений Гілбертом.
Полягає у:
1) повне абстрагування від змісту;
2) точне формулювання всіх вихідних тверджень;
3) явне формулювання логічних засобів.
Приклад:
1)    Піаніно – це музичний інструмент: у нас є піаніно. Отже, у нас є музичний інструмент.
2)    Час – це гроші; у нас є час. Отже, у нас є гроші.
3)    Всі дикуни розмальовують своє обличчя. Деякі жінки теж розмальовують свої обличчя. Отже, деякі сучасні жінки – теж дикуни.
Хибність висновку в 2 та 3 пояснюється неоднозначністю термінів природної мови. Тому і виникла потреба в створені штучної однозначної мови символів.
Парадокс – це два несумісних твердження, для кожного з яких наводяться аргументи, які здаються переконливими.
Парадокс Епіменіда: “Те, що я кажу, -  не правда.”

Булеві функції від двох змінних
1
1    0    0
0    1    0    1
Назва    Позначення   
Кон’юнція     
0    1    0    0
Диз’юнція    +,   або, OR
1    1    0    1
Еквівалентність     
0    1    1    0
Імплікація     
0    1    1    1
Виключене
або    XOR    1    0    0    1
і – не    NOT( x AND y)    1    0    1    1

II. Рівносильні формули:
1.                                                        
2.                                                  
3.                                   
4.                                                
5.                           
6.                                                           
7.                                                        
8.     
9.                                       
10.                                                      

Ш. Принцип двоїстості.
Нехай f(x,y) або f(x) – деякі булеві функції, тоді функція f*(x,y) або f*(x), яка визначена таким чином:


називається двоїстою до функції f.
Властивість двоїстості інволютивна:
f**=f.
Двоїсті функції:
Кон’юнція і диз’юнція

x    y     


0    0    0    0
0    1    1    1
1    0    1    1
1    1    1    1

Функція називається самодвоїстою, якщо
f*(x,y) = f(x,y)
f*(x) = f(x).
Приклад: заперечення.
Принцип двоїстості:
Нехай маємо F = {f1,…, fm} – множина булевих функцій. Тоді, якщо в множині F справедлива деяка формула К, то в множині F* буде справедливою формула К*, отримана з К заміною функцій f  на f*.
Наприклад:
Із формули   за принципом двоїстості маємо формулу:


IV. З мат. логіки відомо, що будь- яку логічну функцію можна подати у вигляді комбінацій простих базових операцій. Спочатку в ЕОМ і реалізовувався цей принцип і випускалися мікросхеми, які відповідали основним логічним діям. Але з розвитком техніки виникла потреба в випуску більш складних типових вузлів: тріггерів, суматорів, дешифраторів, регістрів.
Обробка інформації в ЕОМ відбувається шляхом послідовного виконання елементарних операцій. До елементарних операцій відносяться: запис в регістр елемента двійкового кода, перезапис кода з одного елемента в інший, зсув – зміна положення кода відносно вихідного, перекодування, додавання.
На практиці всі базові елементи мають свої позначення:        











Продемонструємо схему тріггера та суматора
Тріггер – елемент пристрою оперативного збереження інформації.
Логічна схема тріггера: (4 елем. і – не )














Суматор – елемент для додавання чисел.
Логічна схема напівсуматора: