Попередні 5 таблиць істинності для операцій можна розглядати як приклади двомісних і одномісних функцій особливого виду, у яких і аргумент і значення функції можуть приймати одне з 2-х значень 0 чи 1.
Основні об'єкти, про які надалі будемо вивчати формули алгебри логіки, що складаються з букв, знаків логічних операцій і дужок. Букви позначають логічні змінні, котрі приймають тільки два значення -"неправда" і "істина". Знаки операцій позначають логічні операції (логічні зв'язки). Кожна формула задає логічну функцію - функцію від логічних змінних, котра сама може приймати тільки два логічних значення.
Отже, нехай В = {0, 1} - бінарна множина, елементами якої є формальні символи 1 і 0, що не мають арифметичного значення, а інтерпретуються як {“так”, “ні”}, {“істинно”, “хибне”} і т.д.
Алгебра логіки - алгебра, утворена множиною В ={0, 1} разом із усіма можливими операціями на ній.
Функцією алгебри логіки, булевими або логічними функціями f (x1,x2,…xn) = y називається n- місною функція, якщо в неї x1... xn та y приймають своє значення на множині {0,1}.
Будь-яку логічну функцію f(xv... хп) можна задати таблицею істинності, у лівій частині якої виписані всі можливі набори значень її аргументів х1,..., хп, а права частина являє собою стовпець значень функцій, що відповідають цим наборам. Набір значень перемінних, на якому функція приймає значення f= 1, називається одиничним набором функції f; множина всіх одиничних наборів - одиничною множиною функції f. Аналогічно набір значень, на якому f = 0, називається нульовим набором функції f а множина нульових наборів - нульовою множиною.
Число всіх можливих наборів значень, що різняться, n змінних логічний функції f (x1,x2,…xn) дорівнює 2n (дорівнює числу всіх можливих двоичных векторів довжини п). Число всіх різних функцій п перемінних дорівнює числу можливих розміщень нулів і одиниць у стовпці з 2n рядками, тобто .
Особливу роль в алгебрі логіки грають логічні функції однієї і двох перемінних - унарні та бінарні логічні операції, тому що очевидним чином інтерпретуються природними логічними зв'язками "не", "і", "чи" і т.д., широко використовуваними при описі систем, явищ, формалізації міркувань і ін.
Множина усіх логічних функцій однієї перемінної - унарних логічних операцій - представлена в табл. 4.1 своїми таблицями істинності, :
X
F0(x)
F1(x)
F2(x)
F3(x)
х
З таблиці видно, що F0 і F3 - константи 0 і 1 відповідно. Значення цих функцій не залежать від перемінної х, у таких випадках говорять, що змінна х є несуттєвою (фіктивною) для цих функцій.
Функція F1= x (повторення перемінної), а F2 - заперечення перемінної.
Множина всіх логічних функцій двох змінних бінарних логічних операцій - представлене в таблиці своїми таблицями істинності; функцій. Кожна з булевих функцій представлена у виді таблиці має власні значення і використовується в різних алгебраїчних системах.
P
Q
сonst 0
кон’юнк-ція
Р
Q
виключним “АБО”
диз'юнкція
P
Q
еквівалентність
імплікація
сonst 1
З представлених функцій шість мають фіктивні змінні ( , , , , , ). У двох нижніх додаткових рядках таблиці зазначені найбільше вживані логічних операцій і їхнього позначення, що, однак, не є єдиними. Наприклад, - кон'юнкція - виключним “АБО”, – диз'юнкція, – еквівалентність, –імплікація.
Наприклад, побудувати таблицю істинності для формули:
P
Q
R
Еквівалентні співвідношення . Нормальні форми.
Часто необхідно перетворити формули з одного виду в іншій, щоб визначити їх еквівалентність. Формули G і Н називаються еквівалентними, якщо вони приймають однакові значення при будь-яких інтерпретаціях.
Еквівалентні перетворення - перетворення, що використовують еквівалентні співвідношення і правило заміни. Еквівалентні перетворення (поряд зі стандартним методом) є могутнім засобом доказу еквівалентності формул..
Еквівалентні перетворення виконуються на основі переліку заздалегідь наявних еквівалентів формул:
1)
2)
3) Комутативність
,
4) Асоціативність
,
5) Дистрибутивність
,
6) Ідемпотентність
,
7) Закон подвійного заперечення
8) Закон виключення третього
- загальнозначуща формула
9) Закон протиріччя
– суперечлива формула
10) Властивості констант
, , ,
11) Закони де’ Моргана
;
Закони де’Моргана можна узагальнити на випадок n атомів
,
Основні еквівалентні співвідношення відрізняються тим, що:
а) вони не виведені друг із друга; переконатися в їхній справедливості можна, використовуючи стандартний метод доказу еквівалентності формул;
б) цих співвідношень досить для виконання будь-яких еквівалентних перетворень: для будь-яких еквівалентних формул F1 і F2існує еквівалентне перетворення F1 в F2допомогою співвідношень.
Інші співвідношення, часто застосовувані в перетвореннях булевих формул, виведені за допомогою основних законів. Так, поряд з основними співвідношеннями для спрощення формул часто використовуються наступні еквівалентні співвідношення, виведені з основних за допомогою еквівалентних перетворень:
- поглинання , ;
- склеювання ;
- узагальнене склеювання ;
- .
Доказ еквівалентності формули також можливий за допомогою приведення формули до диз'юнктивної нормальної форми або кон'юнктивної нормальної форми.
Літера – це атом, що взято з запереченням або без нього. Прикладом літери можуть бути , , ,
Елементарною кон’юнкцією називається кон’юнкція літер, у якій кожний атом зустрічається не більш одного разу.
Диз'юнктивною нормальною формою (ДНФ) називається формула, що має вид диз'юнкції елементарних кон’юнкцій. Загальний вигляд ДНФ:
, де - кон’юнкція літер
Прикладами ДНФ є наступні формули:
,
Аналогічним чином визначаються елементарна диз’юнкція, кон'юнктивна нормальна форма (КНФ)
Елементарною диз’юнкцією називається диз’юнкція літер, у якій кожний атом зустрічається не більш одного разу.
Формула F находиться в кон'юнктивній нормальній формі, якщо вона має вигляд
– літери або диз'юнкція літер
Прикладом КНФ є наступна формула:
Однак за своїм змістом як ДНФ, так і КНФ для однієї й тієї ж формули можуть відрізняться як кількістю елементарних диз'юнкцій чи кон’юнкцій, так і їх, змістом. А тому постає задача побудови такої формули, яка могла б однозначно відповісти на питання: чи еквівалентні дві формули?
Однозначну відповідь на це питання дає таблиця істинності – коли значення формули збігаються в однакових наборах значень змінних, то й висловлювання еквівалентні. Однак побудова таблиць істинності для висловлювань із багатьма змінними є досить трудомістким процесом, а тим паче, що інколи висловлювання набуває істинних, або неправдивих значень тільки в не багатьох випадках.
Для порівняння формул висловлювань будують досконалу ДНФ (ДДНФ) та досконалу КНФ (ДКНФ)
Досконала ДНФ (ДДНФ) - це ДНФ, кожна елементарна кон'юнкція якої включає всі літери, що входять до формули. Аналогічно Досконала КНФ (ДКНФ) - це КНФ, кожна елементарна диз'юнкція якої включає всі літери, що входять до формули.
Для кожної функції ДДНФ (ДКНФ) єдина (з точністю до перестановок змінних або кон'юнкцій).
Спосіб переходу від табличного завдання логічної функції до булевої формули у ДДНФ:
– виділяються всі набори значень на яких функція f (x1,x2,…xn) дорівнює 1;
– виписуються всі змінні х1,..., хn в такому порядку: якщо змінна в цьому наборі входить з істинним значенням, той вона так і залишається, якщо з неправдивим, то вона ставиться із запереченням. В кожному наборі змінні з'єднуються в елементарну кон'юнкцію;
– елементарні кон'юнкції поєднуються диз'юнкцією.
Наприклад, побудуємо ДДНФ для формули , таблиця істинності для якої побудована раніше
P
Q
R
Елементарні кон'юнкції
Побудовані елементарні кон'юнкції з'єднуються диз'юнкцією для ДДНФ:
Спосіб переходу від табличного завдання логічної функції до булевої формули у ДКНФ:
– виділяються всі набори значень на яких функція f (x1,x2,…xn) дорівнює 0;
– виписуються всі змінні х1,..., хn в якості значень змінних береться інвертовані значення атомів у відповідних строках. В кожному наборі змінні з'єднуються в елементарну диз'юнкцію;
– елементарні диз'юнкції поєднуються кон'юнкцією.
Наприклад, побудуємо ДКНФ для формули , таблиця істинності для якої побудована раніше
P
Q
R
Елементарні диз'юнкції
Важливо відмітити, що ДДНФ та ДКНФ єдина для відповідної формули, з їх допомогою можна побудувати таблицю істинності без перебору всіх інтерпретацій формули.
Інколи необхідно побудувати ДДНФ та ДКНФ шляхом алгебраїчних перетворень. Процедура приведення до ДДНФ та ДКНФ:
1. Усі заперечення "спустити" до перемінних за допомогою законів де’Моргана.
2. Розкрити дужки за допомогою еквівалентних перетворень – закону асоціативності, дистрибутивності.
3. Видалити зайві кон'юнкції і диз'юнкції, повторення змінних та додати змінних, яких недостатньо у кон'юнкціях та диз'юнкціях за допомогою законів ідемфотентності, протиріччя та виключного третього.
4. Видалити константи за допомогою законів, що властиві операціям з константами.
Логіка висловлювань є одним з найпростіших засобів формалізації висловлювань та встановлення формальних логічних висновків. Множина {0,1} операції заперечення, диз’юнкції та кон’юнкції формує алгебру висловлювань.
Тема 3 Комбінаторний аналіз
Комбінаторика - розділ математики, у якій вивчаються питання різних комбінацій, що підпорядковані тим чи іншим умовам чи правилам можна скласти з заданих об'єктів. У комбінаториці вивчаються вибірки, розподіли, упорядкування, розміщення елементів множин, перетинання чи тих чи інших підмножин.
Комбінаторні методи використовують у рішенні транспортних задач, у тому числі складання розкладу, при складанні планів виробництва та реалізації продукції.
Нехай M - кінцева множина , що містять n – елементів. Будемо називати його n-множиною. Підмножина , складається з k елементів, її будемо називати k–підмножиною. Потужність обох множин буде відповідно та
Нагадаємо, що N-множина називається впорядкованою, якщо кожному її елементу взаємно однозначно зіставляється номер .
Під час рішення комбінаторних задач використовуються два основних правила комбінаторики: правило суми та правило добутку.
.
:
- заперечення перемінної.
функцій. Кожна з булевих функцій представлена у виді таблиці має власні значення і використовується в різних алгебраїчних системах.
, 
, 
,
,
, 
- загальнозначуща формула
– суперечлива формула
, 
, 
, 
; 
,
, 
;
;
;
.
, 
, 
, де 
- кон’юнкція літер
, 
– літери або диз'юнкція літер
, таблиця істинності для якої побудована раніше
, складається з k елементів, її будемо називати k–підмножиною. Потужність обох множин буде відповідно 
та 
.