Упражнение. Какой номер у набора значений переменных булевой функции (11101)?

Какой номер у набора значений переменных булевой функции (11101)? Номером какого набора значений переменных булевой функции от пяти переменных является число 18?

Ответ: 1) 57, 2) (10010).

Единый способ записи наборов значений переменных дает возможность записывать функции лишь в виде столбца ее значений. Например, = (0001), = (0111), h = (00010111). Нульместные функции 0 и 1 называются соответственно тождественным нулем и тождественной единицей. Функция называется тождественной функцией. Функция называется отрицанием . Все одноместные функции можно свести в таблицу:

Таблица 3.2

x	0()	1()	f () = Ø

Выпишем все двуместные булевы функции

Таблица 3.3

Конъюнкция и y обозначается также y, min и читается « и y». Дизъюнкция читается « или y». Функция называется суммой по модулю 2 или альтернативной дизъюнкцией и читается “ плюс y по модулю 2”. Эквивалентность часто обозначается также «y, ~ y, º y. Импликация в некоторых книгах обозначается также y, и часто читается «x имплицирует y». Функция ½ y называется штрихом Шеффера. Функция ¯ у называется стрелкой Пирса, функцией Пирса. Все эти функции называют элементарными. Символы Ø, &, Ú, Å, Þ, Û, ½, ¯ называют логическими связками.

Две функции называются равными, если они принимают одинаковые значения на одних и тех же наборах значений переменных. Говорят, что f(x ₁ ,…, x_n) существенно зависит от переменной x ₁, если существует такой набор значений переменных = a ₂,…, = a_n, что f( 0, a ₂ ,…, a_n) ¹ f( 1, a ₂ ,…, a_n). Переменные, от которых функция зависит существенно, называются существенными, остальные – фиктивными. Отождествляем функции, из которых добавлением фиктивных переменных можно получить одну и ту же функцию.

ТЕОРЕМА. Число всех различных n- местных булевых функций равно

Доказательство. Число наборов значений n переменных равно В случае стандартной нумерации наборов значений переменных n- местной булевой функции ставится во взаимооднозначное соответствие двоичный вектор длины . Таких векторов . Так как соответствие взаимооднозначное, то и всех булевых функций тоже столько.■

Приведем пример, в котором появляются булевы функции.

1. Составным элементом нервной системы является нейрон. Это устройство предназначено для того, чтобы не пропускать слабые возбуждения и передавать достаточно регулярные и сильные.

Одна из моделей нейрона. Нейрон имеет n входов, по которым в некоторый момент времени t могут поступать или не поступать возбуждения. Если в момент t более h входов возбуждены, на выход нейрона поступает возбуждение, в противном случае оно не поступает. Обозначим входы нейрона , …, Будем говорить, что вход принимает значение 0 в момент t, если он не возбужден в этот момент, и значение 1, если возбужден в момент t. Состояние выхода однозначно определяется соотношением входов и числом h. Будем считать если среди значений более h равняется 1; если среди значений не более h равняется 1.

Пример. Для ( ) имеем таблицу истинности 3.4.

Упражнения

1. Найдите число всех различных n- местных булевых функций, принимающих одинаковые значения на противоположных наборах значений переменных.

2. Найдите число всех различных n- местных функций k -значной логики (k ³ 2).

3.3. Формулы алгебры логики

Алфавитом называется любое непустое множество. Элементы этого множества называются символами алфавита. Словом в алфавите G называется произвольная конечная (возможно пустая) последовательность символов из G. Фиксируем некоторый конечный или счетный алфавит переменных X ={ x₁, x₂, …}.

Формула алгебры логики определяется следующим образом (индуктивное определение):

1) Переменная есть формула.

2) Если и – формулы, то (), ( Ú ), ( & ), ( Þ ), ( Å ), ( Û ), ( ½ ), ( ¯ ) – тоже формулы.

3) Других формул нет.

Подформулой формулы называется любое подслово слова , которое само является формулой. Для сокращения записи формул обычно принимаются следующие соглашения:

а) внешние скобки у формул опускаются;

б) формула Ø записывается в виде

в) формула & записывается в виде

г) связка Ø считается сильнее любой двуместной связки;

д) связка & считается сильнее любой другой двуместной связки.

В соответствии с этим договоримся, что логические операции выполняются в следующем порядке:

1) конъюнкция,

2) дизъюнкция,

3) импликация и эквиваленция в порядке их записи,

4) если часть формулы заключена в скобки, то сначала производится действие в скобках,

5) если над частью формулы стоит знак отрицания, то он заменяет собой скобки, в которые заключена эта часть формулы.

Функция , реализуемая формулой , вводится следующим образом:

1) формуле = сопоставляется тождественная функция

2) если = Ø , то = Ø ; если = то = где = &, Ú, Þ, Û, Å, ½, ¯.

Пусть Ф = { f ₁^(m), f ₂^(m), …} – множество функциональных символов, где верхние символы указывают местность (арность) символов. Если арности из контекста известны, то верхние индексы будем опускать.

Формулы над множеством Ф – это выражения вида и только они:

1) f_к, где f_к – нульместный символ;

где – n -местный функциональный символ, – переменные из множества Х.

2) где – s -местный функциональный символ, – либо формула над Ф, либо переменная из Х, 1 £ i £ s.

Пусть Ф – множество функциональных символов, Р – множество соответствующих им функций. Суперпозицией над множеством Р называется всякая функция F, которую можно реализовать формулой над множеством Ф.

Формула алгебры логики называется выполнимой, если существует набор значений переменных, на которых реализуемая ею функция принимает значение 1, и опровержимой, если 0. Формула называется тождественно истинной или тавтологией, если она реализует функцию «тождественная единица», и тождественно ложной, если 0. Проблема разрешимости заключается в задаче: указать алгоритм, позволяющий для каждой формулы выяснять, является ли она тождественно истинной. Ответ на этот вопрос можно дать после изучения нормальных форм.

Пример. Докажите, что формула тождественно истинна