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

 

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

Пусть А и В – два множества и < a, b > – упорядоченная пара, где первый элемент , а второй элемент . Декартово произведение  – это множество пар таких что . Бинарным отношением f из множества А в множество В называется подмножество : .

Функция – это такое отношение, что из  и следует, что x = z, то есть функциональность – это однозначность.

ПРИМЕР.

А={1,2,3,4,5}

B ={1,4,9,16,25}

={<1,1>, <1,4>, <1,9>, <1,16>, <1,25>, <2,1>, <2,4>, <2,9>, <2,16>, <2,25>,….<3,9>, ….,<4,16>,…..<5,25>}

f ={<1,1>, <2,4>, <3,9>, <4,16>, <5,25>} – это функция, где b = a ².

Теперь перейдем к определению булевых функций.

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

Если область значений функций содержит k различных элементов, то она называется k -значной функцией. 

Определение. Логическая функция – это функция, в которой переменные принимают только два значения: логическая единица или логический ноль.

Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).

Определение. Функцией алгебры логики (ФАЛ) называется функция, дающая однозначное отображение Х в Y.

Замечание 1. Число различных ФАЛ, зависящих от n аргументов, конечно и равно .

Замечание 2. ФАЛ f(x₁, x₂, …, x_i, x_i+1, …, x_n-1, x_n) существенно зависит от аргумента x_i, если имеет место соотношение

f(x₁, x₂, …, x_i-1,0, x_i+1, …, x_n-1, x_n) ¹ f(x₁, x₂, …, x_i-1,1, x_i+1, …, x_n-1, x_n)

в противном случае говорят, что от x_i функция зависит не существенно и x_i  является ее фиктивным аргументом. ФАЛ не изменяется, если к ее аргументам дописать любое число фиктивных аргументов или зачеркнуть те аргументы, которые являются фиктивными.

Как найти несущественные аргументы? Для этого, если ФАЛ задана таблично, поступают следующим образом.

Разбивают множество наборов аргументов функции на два подмножества:

- подмножество, на котором заданная функция принимает значение 1;

- подмножество, на котором заданная функция принимает 0.

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

ПРИМЕР.

                                                                                           Таблица

x1  x2   x3    x4	f (x1, x2, x3, x4)
0  0  0  0	0
0  0  0  1	0
0  0  1  0	0
0  0  1  1	0
0  1  0  0	1
0  1   0 1	1
0  1   1 0	0
0  1   1 1	0
1  0   0 0	0
1  0   0 1	0
1  0   1 0	0
1  0   1 1	0
1  1   0 0	1
1  1   0 1	1
1  1   1 0	1
1  1   1 1	1

 

Произведем разбиение набора аргументов:

x₁ x₂ x₃   x₄

0 0 0 0                                          

0 0 0 1                                                              x₁ x₂ x₃   x₄

0 0 1 0                                                              0 1 0 0

0 0 1 1               наборы х                         0 1 0 1

0 1 1 0               на которых                     1 1 0 0            f()= 1

0 1 1 1               f()= 0                             1 1 0 1

1 0 0 0                                                              1 1 1 0

1 0 0 1                                                              1 1 1 1

1 0 1 1

 

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