yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Математическая логика

1.2. Булева алгебра

Будем рассматривать множество переменных, каждая из которых может принимать одно из двух возможных .-точений, 0 или 1.

Определение 1.3. Всякую переменную, которая может принимать одно из двух возможных значений, назовем булевой переменной.

Определение 1.4. Функции, определенные на множестве (0,1), и принимающие значения из этого множества, .называются булевыми функциями.

Утверждение. Множество, состоящее из двух значений 0 и 1, на котором определены унарная операция отрицания (¬) согласно табл. 1, и бинарные операции дизъюнкции (v) и конъюнкции {&) согласно табл. 2, является Булевой алгеброй.

Совокупность значений переменных булевой функции будем называть набором  или интерпретацией булевой функции. Множество значений функции па всех наборах называется таблицей истинности булевой функции. Множество всех наборов будем записывать в лексикографическом порядке, так что каждый набор будет представлять собой код двоичного числа. Соответствующее ему десятичное число будем называть номером набора. Например, номер набора 110 равен 6, номер набора 0101 равен 5.

Теорема. Количество наборов булевой функции от n переменных равно 2" Количеств"булевых функций от n переменных равно 2 в степени 2.

Существует 16 булевых функций от двух переменных. В табл. 1.1 и табл. 1. 2 приведены, помимо основных функций ¬, &, и v, операции импликации ( ?) и эквивалентности ().

 

Таблица1.1

x

¬x

0

1

1

0

 

 

 

 

 

 

 

 

 

Таблица 1.2

X

 

У

х&у

 

хvy

 

x  y

 

ху

 

0

 

0

 

б

 

0

 

1

 

1

 

0

 

1

 

0

 

1

 

1

 

0

 

1

 

0

 

0

 

1

 

0

 

0

 

1

 

1

 

1

 

1

 

1

 

1

 

 

7