Елементи математичної логіки, функції алгебри логіки

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

Наприклад, формула (х у )®z является функцией трех переменных f (х, у. z ). Особливістю цієї функції є та обставина, що її аргументи приймають одне з двох значень: нуль або одиницю, і при цьому функція також приймає одне з двох значень: нуль або одиницю.

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

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

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

Можливі логічні функції однієї змінної

З цієї таблиці випливає, що дві функції однієї змінної будуть постійними: F 1 (x) º 1, F 4 (x) º 0, F 2 (x) º x і.

Будь-яку довільну функцію алгебри логіки можна представити у вигляді формули алгебри логіки.

Нехай, наприклад, F (х 1, x 2. хn) - довільна функція алгебри логіки n змінних. Розглянемо формулу

ÚF (1,1. 0) x 1x 2. Ú (1)

ÚF (1,1. 1,0,1) x 1x 2. xn Ú. Ú

яка складена таким чином: кожний доданок цієї логічної суми являє собою кон'юнкцію, в якій перший член є значенням функції F при деяких певних значеннях змінних х 1, x 2. xn. інші ж члени кон'юнкції є змінними або їх заперечення. При цьому під знаком заперечення знаходяться ті і тільки ті змінні, які в першому члені кон'юнкції мають значення 0. Таким чином, формула (1) містить у вигляді логічних доданків всілякі кон'юнкції зазначеного виду.

Ясно, що формула (1) повністю визначає функцію F (x 1, x 2. xn). Інакше кажучи, значення функції F і формули (1) збігаються на всіх наборах значень змінних x 1, x 2. xn.

Наприклад, якщо х 1 приймає значення 0, а інші змінні приймають значення 1, то функція F приймає значення F (0,1,1. 1). При цьому логічне доданок F (0,1. 1) x 2. xn. що входить в формулу (1), приймає також значення F (0,1. 1), так як x 2. xn º1, а F (x 1, x 2. xn) 1ºF (x 1, x 2. xn). Всі інші логічні складові формули (1) мають значення 0. Дійсно, в них знаки заперечення над змінними розподіляються інакше, ніж в розглянутому слагаемом, але тоді при заміні змінних тими ж значеннями в кон'юнкцію увійде символ 0 без знака заперечення, символ 1 під знаком заперечення . В таком случае один из членов конъюнкции имеет значение 0, а поэтому вся конъюнкция имеет значение 0 и F (x 1, x 2. xn )0º0. У зв'язку з цим на підставі равносильности х Ú 0 º х значенням формули (1) є F (0,1. 1).

Ясно, що вид формули (1) може бути значно спрощений, якщо в ній відкинути ті логічні складові, в яких перший член кон'юнкції тобто F (x 1, x 2. xn) має значення 0 (і, отже, вся кон'юнкція має значення 0). Якщо ж в логічному слагаемом перший член кон'юнкції має значення 1 (тобто F (x 1, x 2. xn) = 1) то, користуючись рівносильно 1х º х. цей член кон'юнкції можна не виписувати.

Таким чином, в результаті виходить формула (1), яка містить тільки елементарні змінні висловлювання і має такі властивості.

1. Кожна логічне доданок формули містить всі змінні, що входять в функцію F (x 1, x 2. xn).

2. Всі логічні складові формули різні.

3. Жодне логічне доданок формули не містить одночасно змінну і її заперечення.

4. Жодне логічне доданок формули не містить одну і ту ж змінну двічі.

Перечисленные свойства называются свойствами совершенства или, коротко, свойствами (С). Таким чином, властивості досконалості - це набір властивостей функції алгебри логіки, при якому вона має максимально простий вигляд.

З наведених міркувань видно, що кожної не тотожне помилковою функції відповідає єдина формула зазначеного виду.

Якщо функція F (x 1, x 2. xn) задана таблицею істинності, то відповідна їй формула алгебри логіки може бути отримана просто. Действительно, для каждого набора значений переменных, на котором функция F (x 1, x 2. xn ) принимает значение 1, запишем конъюнкцию элементарных переменных высказываний, взяв за член конъюнкции хk. если значение хk на указанном наборе значений переменных есть 1 и отрицание хk. якщо значення хk є 0. Диз'юнкція всіх записаних кон'юнкція і буде шуканої формулою.

Нехай, наприклад, функція F (x 1, x 2, x 3) має наступну таблицю істинності (табл. 9).

Таблиця істинності для функції F (x 1, x 2, x 3)

Для наборів значень змінних (1,1,0) і (0,1,0), на яких функція приймає значення 1, запишемо кон'юнкції, а шукана формула, що володіє властивостями (С), має вигляд

Розглянемо так званий закон подвійності, який використовується в перетвореннях формул алгебри логіки.

Нехай формула А містить лише операції кон'юнкції, диз'юнкції і заперечення. Будемо називати операцію кон'юнкції двоїстої операції диз'юнкції, а операцію диз'юнкції двоїстої операції кон'юнкції.

Формули А і А * називаються подвійними якщо формула А * виходить з формули А шляхом заміни в ній кожної операції на двоїсту.

Наприклад, для формули А = (х Úу) z двоїстої формулою буде формула А * º (х у)Úz.

Наведемо без доведення наступні теореми щодо подвійних формул.

Теорема 1. Якщо формули А і В рівносильні, то рівносильні і їм подвійні формули, тобто А * ºВ *.

Теорема 2. Якщо для формули А (x 1, x 2, ..., xn) двоїстої формулою є А * (x 1, x 2, ..., xn), то справедлива равносильность

Таким чином, в результаті заперечення деякої формули виходить подвійна їй формула, в яких замість змінних стоять їх заперечення.