Булеви функции - studopediya

Да предположим, че първоначалната азбука на променливи.

Функционални алгебра logikiot променливи е функция, която приема стойности 1, 0 и аргументи, които да вземат стойностите 1, 0.

Обикновено, булеви функции, наречени булеви функции. Името "булеви функции" е възникнало във връзка с използването на този вид функции на алгебра на логиката, която беше лансирана произведения на ирландски учен на 19 век Джон. Бул. Домейн Булева функция на наш променливи е съвкупност от всички
п триизмерни кортежи. къде.

Трябва да се отбележи, че всяка такава серия може да се разглежда като представителство на неотрицателно число в двоична система. Например, комплектът (0,1,0,1) съответства на брой. и комплект (1,1,1) - номер.

Всички набори от измерение п са номерирани от 0.2 N -1. Затова е лесно да се забележи, че броят на тези масиви е 2 п.

Всеки Булева функция на наш променливи може да се настрои с помощта на таблицата на истината:

Тази таблица се състои от 2 п реда, където всички го задава, подредени във възходящ ред на номерата им.

Очевидно е, булеви функции на наш променливи са еднозначно определени от последната си колона на тази таблица, т.е. 2 п комплекта от нули и единици. Следователно различните булеви функции на наш променливи ще бъдат възможно най-много, тъй като има различни групи дължина 2 п. и броят им е. Така че сме доказали следната теорема:

Теорема 1Imeetsya точно булеви функции на променливи.

В алгебра на логиката, от особено значение са следните булеви функции, които се наричат ​​елементарни булеви функции:

1) - постоянно 0;

2) - постоянно 1;

3) - функцията за идентичност;

4) - отрицание на х;

5) - съюзът на х и у;

6) - х и у дизюнкция;

7) - х и у отражение;

8) - еквивалентност х и у;

9) - добавяне на х и у MOD2;

10) - функцията Schaeffer;

11) - Pierce стрелка.

Последните три функции, определени от следната таблица: истина

Въведено понятието булева функция е несъвършен, тъй като не позволява да се разгледа функцията на по-малък брой аргументи, като функция на все по-голям брой аргументи. За да се преодолее това ограничение, ще се въведе концепцията за фиктивна променлива.

Променлива XI в функция се нарича сляпо. ако = за всички стойности на други променливи. В този случай функцията. по същество независима от (п-1) - променлива, т.е. Това е функция на (п-1) вариабилен. Функцията д се получава от функция F чрез отстраняване на сляпо променлива, функцията F се получава от грам въвеждането на сляпо, тези функции са равни.

С въвеждането на фиктивни променливи всяка булева функция на променливите може да се разглежда като функция на всеки по-голям брой променливи. Следователно, всяко крайно множество от булеви функции може да се приеме, за да зависи от един и същ брой променливи.

Въпроси за самоконтрол

1 Определяне на основните логически операции на булевата алгебра.

2 Определяне на булева функция.

3 Какво е масата за истината на булева функция?

4 Какъв е броят на булеви функции на променливите?

5 Какви са елементарни булеви функции се наричат?