Дискретні структури Лекція 4 Елементи математичної логіки 4.1. Висловлювання та операції над ними 4.2. Булева алгебра 4.3. Булеві функції

4.1. Висловлювання та операції над ними Основними обєктами математичної логіки є висловлювання та константи. Висловлювання - будь-яке речення, про яке можна однозначно сказати істинне воно чи хибне. Приклад. Висловлювання A: «Число 9 ділиться націло на число 3» – істинне висловлювання. Висловлювання B: «Земля – друга від Сонця планета Сонячної системи» – хибне висловлювання. Висловлювання позначають великими латинськими буквами: A, B, C, … Константи: логічний нуль – 0, та логічна одиниця – 1. Логічний нуль позначають також F (від слова false – хибно, фальш), а логічну одиницю – T (від слова true – істина, правда). Приклад. В цих позначеннях можна записати: A = 1, B = 0.

Операції над висловлюваннями: 1. Логічна операція константа нуль створює завжди хибне висловлювання.F=0. 2. Логічна операція константа одиниця створює завжди істинне висловлювання. F=1. 3. Логічна операція змінна Х створює висловлювання F=Х, яке дорівнює 0 тоді, коли Х дорівнює 0 і навпаки. Читається: Висловлювання залежить лише від Х. 4. Логічна операція інверсія (логічне заперечення), позначається (не x,), це висловлення, яке істинне, якщо x хибне, і хибне, якщо x істинне.

5. Логічна операція конюнкція (логічне множення) висловлювань а та b (позначається a b (a & b, ab). Це складне висловлення, яке істинне тоді, і лише тоді, коли істинні обидва висловлення a та b. 6. Логічна операція дизюнкція (логічне додавання) висловлень а та b (a b) це складне висловлення, яке хибне тоді, і лише тоді, коли хибні обидва висловлення a та b.

7. Логічна операція імплікація a b (a імплікує b) це висловлювання, яке хибне тоді, коли a істинне, а b хибне. 8. Логічна операція еквівалентність a b (a b) істинна тоді, коли a та b одночасно істинні або одночасно хибні.

Основні закони алгебри логіки

4.2. Булева алгебра

4.3. Булеві функції Булева функція функція, область значень якої 0 та 1, і яка залежить від змінних, що набувають лише цих значень. Три основні способи задання булевих функцій: 1) у вигляді формули, що вказує послідовність логічних операцій над висловленнями; 2) у вигляді таблиці, в якій наведені значення істинності складного висловлення; 3) за допомогою логічної схеми. Областю визначення булевої функції від n змінних є сукупність всіх можливих упорядкованих наборів значень змінних, які називаються двійковими. Такі набори (x1,x2…xn) впорядковують за зростанням відповідного двійкового числа, тобто в i-му розряді (i = 0, 1, …, n – 1) знаходиться змінна xi+1.

Для булевих функцій також можна скласти таблиці значень, що відповідають основним логічним операціям. Правило де Моргана для конюнкції -

Основні класи булевих функцій Функція f називається такою, що зберігає нуль, якщо на наборі з нулів вона набуває значення 0. Наприклад, функції,, 0 зберігають нуль, а,,, |, 1 не зберігають. Функція f називається такою, що зберігає одиницю, якщо на наборі з одиниць вона набуває значення 1. Наприклад, функції,, 1 зберігають одиницю, а,,, |, 0 не зберігають. Функція f називається самодвоїстою, якщо f(x1, x2, …, xn) = = f( x1, x2, …, xn). Наприклад, функція самодвоїста, а несамодвоїсті,,,, |, 0, 1. Функція називається монотонною, якщо для будь-якої пари наборів х = (x1, x2, …, xn) та y = (y1, y2, …, yn), таких що xi yi, i = = 1, …, n, f(x) f(y). Монотонними є функції,, 0, 1, а немонотонними,,, |.