Бульові функції, Детальна інформація

. Ці вирази читаються як "не x".

Подамо також деякі з 16 двомісних функцій разом із їх позначеннями:

x y x(y x(y x(y x(y x(y x | y x(y

0 0 0 0 1 1 0 1 1

0 1 0 1 1 0 1 1 0

1 0 0 1 0 0 1 1 0

1 1 1 1 1 1 0 0 0

Функція, позначена виразом x(y, називається кон'юнкцією і позначається ще як x&y, x(y або xy. Усі ці вирази читаються як "x і y".

Функція, позначена виразом x(y, називається диз'юнкцією. Вираз читається як "x або y".

Функція, позначена виразом x(y, називається імплікацією і позначається ще як x(y. Ці вирази читаються як "x імплікує y" або "з x випливає y".

Функція, позначена виразом x(y, називається еквівалентністю і позначається ще як x~y або x(y. Ці вирази читаються як "x еквівалентно y", що в даному випадку збігається з "x дорівнює y".

Функція, позначена виразом x(y, називається додаванням за модулем 2 або "виключним або". Зауважимо, що її значення є протилежними до значень еквівалентності.

Функція, позначена виразом x|y, називається штрихом Шеффера і має значення, протилежні значенням кон'юнкції. Її вираз читається як "не x або не y".

Функція, позначена виразом x(y, називається стрілкою Пірса і має значення, протилежні значенням диз'юнкції. Її вираз читається як "не x і не y".

Зауважимо, що інфіксні позначення наведених функцій вигляду x f y, де f – відповідний знак, склалися історично. Їх так само можна позначати й у вигляді f(x, y), наприклад, ((x, y).

З тримісних функцій наведемо лише так звану функцію голосування m(x, y, z), графік якої має такий вигляд:

x y z m(x, y, z)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

Її назва зумовлена тим, що її значення на кожному наборі збігається з більшістю значень змінних у цьому наборі.

Множину всіх n-місних функцій позначимо P(n), а множину всіх функцій, тобто об'єднання P(n) по всіх n – P2.

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

Алгебри бульових функцій, як і всі інші алгебри, визначаються своїми носіями та сигнатурами операцій. Носіями в алгебрах бульових функцій є множини функцій. Сигнатуру складає операція суперпозиції, або підстановки.

) і n функцій g1(y1,1, y1,2, …, y1,m1), g2(y2,1, y2,2, …, y2,m2), …, gn(yn,1, yn,2, …, yn,mn), залежні від змінних з деякої їх множини Y={y1, y2, …, yk}. Суперпозицією, або підстановкою функцій g1, g2, …, gn у функцію f(n) називається функція h(m)(y1, y2, …, ym), кожне значення якої h((1, (2, …, (m) визначається як