Ноу Інти, лекція, булеві функції та їх подання

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

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

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

Позначимо через B двоелементною безліч. тоді

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

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

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

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

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

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

Наприклад, верхній грані куба B 3 (її вершини виділені на малюнку) відповідає функція 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 = 1. xn) | f (x1. xn) = 1> вершин B n. Наприклад, функція, тотожно рівна 0, задає порожня множина, а функція, тотожно рівна 1, задає безліч всіх вершин B n.

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

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

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