1. Логічні операції та логічні змінні

Нехай множина . Елементи цієї множини називають логічними значеннями, а змінні, які можуть приймати логічні значення – логічними змінними.

Визначимо на множині логічні операції.

• 0-арні (нульмісні) операції:

• константа 0; (0)

• константа 1. (1)

• 1-арні (одномісні) операції:

• повторення

(2)

• заперечення;

(3)

• 2-арні (двомісні) операції:

• кон’юнкція

; (4)

• імплікація

; (5)

• заперечення імплікації

; (6)

• сума за модулем 2

; (7)

• диз’юнкція

; (8)

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

; (9)

• еквівалентність:

; (10)

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

; (11)

Вирази 0, 1, , , , , , , , , називаються логічними виразами (формулами). Вони є найпростішими логічними формулами. Більш складні формули можна одержати суперпозицією, при якій у вихідній формулі замість змінних підставляють інші вирази.

Приклад 1. Якщо в формулі взяти , , то одержимо більш складну формулу , яку також можна використати для одержання ще більш складної формули, наприклад, такої

.

2. Булеві функції

Функція називається булевою, якщо вона разом зі своїми аргументами приймає значення 0 або 1:

і ().

Область визначення логічних функцій

( разів).

Елементи цієї множини – кортежі (n-ки) , які в математичній логіці називають словами і позначають рядком символів

або стовпчиком із символів

.

Кількість слів скінчена і дорівнює .

Приклад 1. При:

– два слова: 0, 1;

– чотири слова: 00, 01, 10, 11;

– вісім слів: 000, 111, 001, 101, 010, 011, 100, 110.

Кожному слову можна поставити у відповідність ціле число (номер слова)

. (1)

Приклад 2. Слову 010101 можна поставити у відповідність ціле число (номер)

.

Співставлення словам їх номерів дозволяє ввести на множині слів ідеальний строгий порядок: слово з меншим номером передує слову із більшим номером. Іншими словами, множину слів можна впорядкувати за зростанням їх номерів.

Приклад 3. При впорядкована множина слів така: 000 (відповідне число 0), 001(1), 010(2), 011(3), 100(4), 101(5), 110(6), 111(7).

Область значень будь-якої булевих функції

.

Кількість булевих функцій скінчена і дорівнює . Вона швидко зростає із збільшенням n. Так, при є 4 булеві функції однієї змінної, при 16 функцій двох змінних, при 256 функцій трьох змінних, а при більше 4-х трильйонів функцій п’яти змінних – всіх не перелічити.

Булевій функції n змінних можна поставити у відповідність число (номер функції)

, (2)

де – значення булевих функції на слові з номером 0, – на слові з номером 1 і т. д.

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

Номери повністю визначають булеві функції і дозволяють будувати таблиці істинності (таблиці істинності є одним із способів подання булевих функцій).

Приклад 4. Випишемо таблицю істинності функції , враховуючи, що .

3. Булеві функції однієї та двох змінних

Булеві функції однієї та двох змінних можна легко полічити.

Функції однієї змінної.

, ,

, . (1)

Функції двох змінних.

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, . (2)

Порівнюючи визначення функцій (1,2) і логічних операцій (0, 1, …, 11, п. 1) можна прийти до висновку, що булеві функції однієї та двох змінних можна подати первинними логічними формулами. З огляду на це булеві функції однієї та двох змінних називають відповідною операцією:

– константа 0;

– повторення аргументу;

– заперечення аргументу,

– константа 1;

– константа 0;

– кон’юнкція;

– заперечення імплікації;

– повторення аргументу ;

– заперечення зворотної імплікації;

– повторення аргументу ;

– сума за модулем 2;

– диз’юнкція;

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

– еквівалентність;

– заперечення другого аргументу ;

– зворотна імплікація;

– заперечення першого аргументу ;

– імплікація;

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

– константа 1.

Булеві функції однієї та двох змінних можна подати і складними логічними виразами.

Приклад 1.

,

.

Будь-яка булева функція багатьох змінних може бути задана логічним виразом (логічною формулою).

Приклад 2.

Логічний вираз визначає одну булеву функцію. Обернене твердження не правильне. Будь-яка логічна функція може бути подана багатьма формулами (теоретично необмеженою кількістю). Формули, які визначають одну і ту саму функцію називаються рівносильними. Рівносильні формули з′єднуються знаком рівності (=).