1. Булеві функції від n змінних
2. геометричне уявлення
3. табличне представлення

Анотація: Клас Pn булевих функцій від n змінних. Геометричне уявлення булевих функцій. Завдання булевих функцій за допомогою таблиць. Булеві функції від 1-ої і 2-х змінних. булеві (логічні) формули. Рішення задач логіки висловлювань за допомогою булевих формул і функцій

Булеві функції від n змінних

Булеві функції 1 названі на честь англійського математика ХІХ століття Дж. Буля, який вперше застосував алгебраїчні методи для вирішення логічних завдань. Вони утворюють найпростіший нетривіальний клас дискретних функцій - їхні аргументи і значення можуть приймати всього два значення (якщо потужність множини значень функції дорівнює 1, то це тривіальна функція - константа!). З іншого боку, цей клас досить багатий і його функції мають багато цікавих властивостей. Булеві функції знаходять застосування в логіці, електротехніці, багатьох розділах інформатики.

Позначимо через B двоелементною безліч {0,1}. тоді

це безліч всіх двійкових послідовностей (наборів, векторів) довжини n. Булевой функцією від n змінних (аргументів) називається будь-яка функція f (x1, xn): Bn -> B. Кожен з її аргументів xi, 1 <= i <= n, може приймати одне з двох значень 0 або 1 і значенням функції на будь-якому наборі з Bn також може бути 0 або 1. Позначимо через безліч всіх булевих функцій від n змінних. Неважко підрахувати їх число.

Теорема 3.1. .

Доказ Дійсно, по теоремі 1.1 число функцій з k -елементного безлічі A в m -елементное безліч B одно mk. У нашому випадку B = {0, 1}, а A = Bn. Тоді m = 2 і k = | Bn | = 2n. Звідси випливає твердження теореми.

Є кілька різних способів подання та інтерпретації булевих функцій. У цьому розділі ми розглянемо геометричне і табличне представлення, а також представлення за допомогою логічних формул. В "Еквівалентність формул і нормальні форми" буде показано, як булеві функції можна представляти за допомогою формул спеціального виду - діз'юнктівних і кон'юнктивні нормальних форм і многочленів Жегалкина. Крім того, в лекціях "Попередні відомості" і "Індукція і комбінаторика" (Курс "Введення в схеми, автомати і алгоритми") буде розглянуто ще два способи представлення булевих функцій: логічні схеми і впорядковані бінарні діаграми рішень.

геометричне уявлення

Bn можна розглядати як одиничний n-мірний куб. Кожен набір з нулів і одиниць довжини n задає вершину цього куба. на Мал. 3.1 представлені поодинокі куби Bn при n = 3,4.

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

Наприклад, верхній грані куба B3 (її вершини виділені на малюнку) відповідає функція f: f (0,0,1) = f (0,1,1) = f (1,0,1) = f (1,1, 1) = 1 і f (0,0,0) = f (0,1,0) = f (1,0,0) = f (1,1,0) = 0. Очевидно, що вказане відповідність дійсно взаимнооднозначное: кожна булева функція f від n змінних задає підмножина Af = {(x1, ..., xn) | f (x1, ..., xn) = 1} вершин Bn. Наприклад, функція, тотожно рівна 0, задає порожня множина , А функція, тотожно рівна 1, задає безліч всіх вершин Bn.

табличне представлення

Булеві функції від невеликого числа аргументів зручно представляти за допомогою таблиць. Таблиця для функції f (x1, ..., xn) має n + 1 стовпець. У перших n шпальтах вказуються значення аргументів x1, ..., xn, а в (n + 1) -му стовпці значення функції на цих аргументах - f (x1, ..., xn).

Таблиця 3.1. Табличне представлення функції f (x1, ..., xn) x1. . . xn-1 xn f (x1, ..., xn) 0. . . 0 0 f (0, ..., 0,0) 0. . . 0 1 f (0, ..., 0,1) 0. . . 1 0 f (0, ..., 1,0). . . . . . 1. . . 1 1 f (1, ..., 1,1)

Набори аргументів в рядках зазвичай розташовуються в словниковому порядку:

існує таке , Що при , а .

Якщо ці набори розглядати як записи чисел в двійковій системі числення, то 1-ша рядок представляє число 0, 2-а - 1, 3-тя - 2, а остання - 2n-1.

При великих n табличне представлення стає громіздким, наприклад, для функції від 10 змінних потрібно таблиця з 1024 рядками. Але для малих n воно досить наочно.