Переключательные функции. Булева алгебра.

Рассмотрим множество В={0,1}, где 0 и 1 не несут арифметической нагрузки, т. е. 0 -"нет сигнала"("ложь"), 1- "есть сигнал"("истина"). Такое множество называется булевым.

Алгебра, заданная на булевом носителе, называется булевой алгеброй или алгеброй логики.

Сигнатуру алгебры составляют переключательные функции - функции алгебры логики (логические функции).

Опр: Переключательная функция f(x₁,x₂,…,x_n)- это функция, принимающая значения из множества В, аргументы которой тоже принимают значения 0 или 1.

f: Bⁿ ®B - логическая функция.

Пример:голосование 3 человек.

I
II
III
итог
	Нулевое множество (состоит из нулевых наборов)	Единичное множество (состоит из единичных наборов)

Количество комбинаций значений, которые могут принимать переменные, равно 2ⁿ, значит, количество различных функций от n переменных равно .

От одной переменной: f(x) количество значений - 2¹=2;

Количество функций - 2²=4.

x f₁ f₂ f₃ f₄ f₁ =0 и f₄=1 – константы;

0 0 0 1 1 f₂ =х – тождественная;

1 0 1 0 1 f₃ =х – отрицание;

 

Опр: Переменная x_i в функции f(x₁,… x_i …x_n) называется фиктивной (несущественной), если от нее не зависит значение функции:

f(x₁,… x_i-1,1,x_i+1 …x_n)= f(x₁,… x_i-1,0,x_i+1 …x_n).

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

Остальные переменные называются существенными.

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

Способы задания функций:

1. Таблица истинности

Список переменных | Значения функции

 

 

Используемые функции от двух переменных:

х₁ х₂ х₁~ х₂ х₁Ú х₂ х₁Ùх₂ х₁® х₂ х₁® х₂ х₁¯х₂ х₁|х₂ х₁Å х₂

0 0 1 0 0 1 0 1 1 0

0 1 0 1 0 1 0 0 1 1

1 0 0 1 0 0 1 0 1 1

1 1 1 1 1 1 0 0 0 0

 

2. Формула

Функции описываются с использованием операторов:

х₁~ х₂ - эквивалентность (тождественность)

х₁Ú х₂ - дизъюнкция (или)

х₁Ùх₂ - конъюнкция (и)

х₁® х₂ - импликация (следствие)

х₁¯х₂ - стрелка Пирса (не или)

х₁|х₂- штрих Шеффера (не и)

х₁Å х₂ - неравнозначность (сложение по модулю два, xor).

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

Переменные в формуле имеют глубину 0, сама формула имеет высшую глубину. Разбиение формулы по глубинам облегчает вычисление значения функции.

Пример:F=(у or x) xor (x and (x xor y))

После построения таблицы истинности имеем F=y, при этом х- фиктивная переменная.

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

Для упрощения формул применяются свойства логических функций:

Основные свойства булевых функций:

1) идемпотентность: хÚх=х, хÙх=х,

2) коммутативность: хÙу=уÙх, хÚу=уÚх,

3) ассоциативность: хÚ(yÚz)= (хÚy)Úz, хÙ(yÙz)= (хÙy)Ùz,

4) поглощение: (xÙy)Úx=x, (xÚy)Ùx=x,

5) дистрибутивность: хÙ(yÚz)= (хÙy)Ú (хÙz), хÚ(yÙz)= (хÚy)Ù (хÚz),

6) двойное отрицание: x=x,

7) законы де Моргана: хÙу= хÚy, хÙу= хÚy.

8) склеивание: xyÚxy=x, (xÚy)(xÚy)=x.

9) действия с константами: xÚ0=x xÙ0=0

xÚ1=1 xÙ1=x

xÚx=1 xÙx=0.

Приоритет: инверсия, конъюнкция, дизъюнкция, остальные функции.

Поскольку свойства определены только для И, ИЛИ, НЕ, то запишем некоторые подстановки (равносильные формулы):

х₁® х₂= not (х₁)or х₂

х₁¯х₂ = not (х₁ or х₂)

х₁|х₂= not (х₁¯х₂)= not (х₁ and х₂)

х₁Å х₂ =(not х₁ and х₂) or ( х₁and not х₂)

х₁Û х₂ = not(х₁Å х₂) =(not х₁ or х₂) and ( х₁or not х₂)

х₁Å 1 =not х_1.

Таким образом, любую переключательную функцию можно задать булевой формулой: с применением переменных, их отрицаний и операций Ú и Ù, т.е <Ú,Ù, not>-сигнатура булевой алгебры.