Суббота, 10.12.2016, 06:04
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 6
Гостей: 6
Пользователей: 0
» »
21:05
Булевы функции

Булевы функции

Представление булевой функции формулой логики высказываний

  • Определение. Булевой функцией называется n-местная функция, аргументы которой принимают значения во множестве {0, 1} и сама функция принимает значения в этом же множестве.

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

Пример.

Для n=3 булеву функцию можно задать таблицей .

Таблица

x1

x2

x3

f(x1, x2, x3)

0

0

0

0

f(0, 0, 0)

1

0

0

1

f(0, 0, 1)

2

0

1

0

f(0, 1, 0)

3

0

1

1

f(0, 1, 1)

4

1

0

0

f(1, 0, 0)

5

1

0

1

f(1, 0, 1)

6

1

1

0

f(1, 1, 0)

7

1

1

1

f(1, 1, 1)

 

 

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

Пример.

Пусть задана булева функция от трех переменных (табл.). Тогда число наборов 23=8.

Таблица

№ набора

х1

х2

х3

f

0

0

0

0

0

1

0

0

1

0

2

0

1

0

1

3

0

1

1

0

4

1

0

0

1

5

1

0

1

1

6

1

1

0

0

7

1

1

1

1

 

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

Эту же функцию можно записать f(х1, х2, х3)=00101101.

Существует ровно $2^{2^{n}}$ различных булевых функций от n переменных. Константы 0 и 1 считают нуль-местными булевыми функциями.

Утверждение. Каждой формуле логики высказываний соответствует некоторая булева функция.

Пример. Построить все булевы функции, зависящие от двух  переменных.

Решение. Поскольку n=2, различных булевых функций от двух переменных существует ровно 16 (табл.).

№ функции Значение функции Формула, соответствующая функции Название
0 $f=0000$ $f=0$ Константа ноль
1 $f=0001$ $f=x_1\wedge x_2$ Конъюнкция
2 $f=0010$ $f=\overline{x_1\rightarrow x_2}=x_1\leftarrow x_2$ Инверсия прямой импликации
3 $f=0011$ $f=x_1$ Первый операнд
4 $f=0100$ $f=\overline{x_1}\wedge x_2=x_2\leftarrow x_1$ Инверсия обратнойимпликации
5 $f=0101$ $f= x_2$ Второй операнд
6 $f=0110$ $f=x_1\bigoplus x_2$ Сложение по модулю 2
7 $f=0111$ $f=x_1\vee x_2$ Дизъюнкция
8 $f=1000$ $f=\overline{x_1\wedge  x_2}=x_1↓x_2$ Стрелка Пирса (функция Вебба)
9 Sf=1001$ $f=x_1\sim x_2$ Эквивалентность
10 $f=1010$ $f=\bar{x_2}$ Отрицание второго операнда
11 $f=1011$ $f=x_1\vee \bar{x_2}=x_2\rightarrow x_1$ Обратная импликация
12 $f=1100$ $f=\bar{x_1}$ Отрицание первого операнда
13 $f=1101$ $f=x_1\rightarrow  x_2$ Прямая импликация
14 $f=1110$ $f=\overline{x_1\vee x_2}=x_1|x_2$ Штрих Шеффера
15 $f=1111$ $f=1$ Константа 1

 

Таблица истинности элементарных функций дцух переменных

$x_1$

$x_2$

$f_0$

$f_1$

$f_2$

$f_3$

$f_4$

$f_5$

$f_6$

$f_7$

$f_8$

$f_9$

$f_{10}$

$f_{11}$

$f_{12}$

$f_{13}$

$f_{14}$

$f_{15}$

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

 

$\bar{x_1}$

 

$x_1$

 

Операция

0

$\cdot$

$\leftarrow $

$x_1$

$\cdot$

$x_2$

$\bigoplus $

$+$

$↓$

$\sim $

$\bar{x_2}$

$+$

$\bar{x_1}$

$\rightarrow$

$/$

1

 

$x_2$

 

$\bar{x_2}$

 

 

Теорема 1. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x1, x2, …, xn и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.

Теорема 2. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x1, x2, …, xk и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.

Поскольку каждая булева функция представима в виде формулы логики высказываний, то принцип построения СДНФ и СКНФ сохраняется такой же как и для формул логики высказываний.

ПримерПостроить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00101110.

 

Категория: Дискретная математика | Просмотров: 682 | Добавил: Admin | Теги: булева алгебра | Рейтинг: 0.0/0



Всего комментариев: 0
avatar
  .