3. Реалізація булевих функцій формулами.

Булеві змінні будемо позначати малими буквами латинського алфавіту , а також малими буквами латинського алфавіту з індексами ,.

Нехай – множина булевих змінних, – множина логічних зв’язок.

Означення. Формулою над називається будь-який вираз виду:

1. – будь-яка змінна з множини .

2. Якщо і - формули над , то , , , , , , , – формули.

3. Інших формул, крім визначених в пп. 1, 2 не існує.

Для спрощення запису формул над множиною логічних зв’язок

1) зовнішні дужки опускають;

2) За умовчанням приймається такий пріоритет логічних зв’язок: , , , ∨, .

Будь-яка формула, що виражає функцію , задає спосіб її обчислення. Формулу можна обчислити, тільки якщо вже обчислені значення всіх її підформул.

Приклад. Обчислимо значення формули

на наборі 110 (x1=1, x2=1, x3=0), користуючись таблицями значень елементарних функцій.

A==0 \/ 1=1;

B==1+1=0;

C= =1*0=0;

F=A (+) C=1+0=1.

Таким чином, формула кожному набору значень аргументів ставить у відповідність значення функції і тому може служити поряд з таблицею способом задання і обчислення булевої функції. Зокрема, обчислюючи значення формули на всіх наборах, можна побудувати таблицю істинності. Про формулу, яка задає булеву функцію, кажуть, що вона реалізує або представляє цю функцію.

4. Рівносильність та тотожність формул. Принцип двоїстості.

На відміну від табличного задання реалізація функції формулою не єдина. Наприклад, якщо система утворена функціями то функцію | – "штрих Шеффера" можна у відповідності із законами де Моргана представити як або , а функцію "стрілка Пірса" як або .

Означення. Формули, які представляють одну й ту саму функцію, називаються еквивалентними або рівносильними.

Теорема. Для будь-яких формул справедливі рівносильності:

1. А&В≡В&А –комутативність &	1^*. А∨В≡В∨А – комутативність
2.(АВ)СА(ВС)- асоціативність &	2^*.(АВ)СА(ВС) – асоціативність
3. А(ВС)(АВ)(АС) - дистрибутивність & відносно	3^*. А(ВС)(АВ)(АС) - дистрибутивність відносно &
закони де Моргана
4. (АВ)АВ –	4^*. (АВ)АВ
5.АА- закон подвійного заперечення
закони ідемпотентності
6. ААА-	6^*. ААА
Властивості 0 і 1
7. А00 А1А	7^*. А0А А11
8.АВАВ
Закон контрапозиції
9. АВ В  А
10. АВ(АВ)(ВА)

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

Означення. Рівносильним перетворенням даної формули називається заміна формули іншою формулою, їй рівносильною.

Приклад. Довести рівносильність формул

а) за допомогою таблиць;

б) шляхом рівносильних перетворень.

х(ху)ху

а)

х	у	х	у	(ху)	(ху)	х(ху)	ху
0	0	1	1	0	1	1	1
0	1	1	0	1	0	0	0
1	0	0	1	0	1	1	1
1	1	0	0	0	1	1	1

Оскільки формули в лівій і правій частинах набувають однакових значень при будь-яких значеннях змінних висловлень, які входять в них, то вони рівносильні.

б) х(ху)(х(ху))х(ху)х(ху)(хх)уху.

Означення. Спрощенням формули називається рівносильне перетворення, яке приводить до формули, яка містить лише символи , і  , причому знак  відноситься тільки до змінної.

Означення. Логічні зв’язки і називаються двоїстими.

Означення. Нехай формула містить тільки символи . Формула називається двоїстою до формули , якщо її можна отримати з формули заміною символів ,, на , відповідно.

Приклад.

Теорема (про двоїстість). Якщо формули і , які містять тільки символи , рівносильні, то двоїсті до них формули також рівносильні.

Зауваження. При означенні формули символи 0 і 1 також вважаються формулами. При переході до двоїстої формули 0 замінюється 1, а 1 – 0. Наприклад, , а .

Справедливий принцип двоїстості:

Якщо є деяке означення або твердження, яке містить тільки символи , то можна сформулювати двоїсте означення або твердження, замінюючи один на один символи і , 0 і 1. Якщо початкове твердження справедливе, то і двоїсте справедливе.