Учебное пособие: Математические и логические основы информатики

Областью определения такой булевской функции будет n-тая декартова степень множества {0,1}, то есть всевозможные двоичные наборы длины n вида <a1a2…an>, где aiÎ{0,1}. Число таких всевозможных наборов (n-ок) составляет 2n.

Область значений булевской функции от n переменных - это множество {0,1}.

В дальнейшем мы будем рассматривать только всюду определенные булевские функции, то есть область определения таких функций совпадает с n-той декартовой степенью множества {0,1}.

Булевские функции от большего числа переменных могут быть так же заданы таблично, или с помощью формул логики высказываний , или в виде суперпозиции (взаимной подстановки ) булевских функций одной и/или двух переменных.

Например, булевская функция y=f(x,y,z), задаваемая формулой логики высказываний x&yÚØx&ØyÚz может быть задана в виде следующей суперпозиции функций от одной и двух переменных: y=f8(f8(f2(x,y),f9(x,y)),φ2(z)).

Учитывая принципиальную возможность выразить булевскую функцию от любого числа переменных в виде суперпозиции (взаимной подстановки) булевских функций от одной и двух переменных, мы чаще будем использовать либо табличный способ задания таких функций, либо с помощью формул логики высказываний.

Табличный способ задания булевских функций от одной и двух переменных (см. приведенные выше таблицы, определяющие эти функции) наводит нас на некоторые соображения:

- число наборов истинностных значений, на которых определена булевская функция от n переменных, составляет 2n (при n=1 это число составляет 2, при n=2 - 4);

- значение каждой булевской функции от n переменных представляет собой двоичный набор длины 2n;

- каждая булевская функция отличается от любой другой булевской функции с тем же числом переменных своим значением хотя бы на одном из таких наборов

А отсюда можно сделать предположение о том, число N различных булевских функций от n переменных равно числу различных двоичных наборов длины 2n, то есть:

При n=1 это число равно 4, при n=2 - 16, n=3 - 256, n=4 - 65536 и т.д.

Полные системы булевских функций

В предыдущем пункте было отмечено, что можно выразить любую булевскую функцию от n переменных в виде суперпозиции (взаимной подстановки) булевских функций от одной и двух переменных. В свою очередь эти функции задаются формулами, содержащими логические операции: отрицание(Ø), конъюнкцию (&),строгую дизъюнкцию (Å), дизъюнкцию(Ú), импликацию(É), эквиваленцию (~).

Но как известно из логики высказываний, операции логики высказываний строгая дизъюнкция (Å), импликация (É), эквиваленция (~) могут быть выражены через дизъюнкцию (Ú), конъюнкцию (&) и отрицание (Ø).

В свою очередь, дизъюнкция (Ú) может быть выражена через конъюнкцию (&) и отрицание (Ø), а конъюнкция (&) - через дизъюнкцию (Ú) и отрицание (Ø).

Таким образом, конъюнкция и отрицание, а также дизъюнкция и отрицание, образуют полную систему логических связок , то есть через эти операции могут быть выражены все остальные.

Более того, можно определить логическую операцию, через которую выражаются все шесть операций: отрицание (Ø), конъюнкция (&), дизъюнкция (Ú), строгая дизъюнкция (Å), импликация (É), эквиваленция (~). Таковой, например, является операция, соответствующая сложному союзу "не А или не В" ("или" соединительное). Эта операция обозначается символом ô(например, АôВ) и получила название штрих Шеффера . Штрих Шеффера определяется с помощью следующей таблицы:

X	Y	XôY
Л	Л	И
Л	И	И
И	Л	И
И	И	Л

Как легко видеть, штрих Шеффера представляет собой отрицание конъюнкции: XôYºØXÚØYºØ(X&Y).

Можно убедиться, что ØXºXôX.

А отсюда: X&YºØ( XôY) º (XôY) ô( XôY).

Таким образом, через штрих Шеффера могут быть выражены конъюнкция и отрицание, а значит и все остальные операции логики высказываний. То есть система логических связок, содержащая единственную операцию - штрих Шеффера, является полной.

Есть еще одна логическая операция, аналогичная штриху Шеффера и называемая стрелкой Пирса . Она обозначается символом ­ и представляет собой отрицание дизъюнкции (или конъюнкцию отрицаний): X­YºØ(XÚY) ºØX&ØY.

Можно убедиться, что ØXºX­X.

А отсюда: XÚYºØ( X­Y) º (X­Y) ­ ( X­Y).

Таким образом, через стрелку Пирса могут быть выражены дизъюнкция и отрицание, а значит и все остальные операции логики высказываний. То есть система логических связок, содержащая единственную операцию - стрелку Пирса, является полной.

Систему булевских функций будем называть функционально полной , если любую булевскую функцию можно выразить в виде суперпозиции (взаимной подстановки) функций из этой системы.

В соответствии с высказанными выше соображениями о полноте системы логических связок и задании булевских функций формулами логики высказываний, можно сделать вывод о функциональной полноте следующих систем булевских функций:

S0 = {φ3(x), f2(x,y), f8(x,y)} - отрицание, конъюнкция, дизъюнкция.

S1 = {φ3(x), f2(x,y)} - отрицание, конъюнкция.