ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     3.3. БУЛЕВІ ФУНКЦІЇ ДВОХ ЗМІННИХ

      , тобто таких функцій 16. Знайдемо їх за допомогою таблиці 4.

Таблиця 4.

		Змінна	0	0	1	1
		Змінна	0	1	0	1
№	Назва	Позначення					Фіктивні змінні
0	Нуль		0	0	0	0
1	Кон'юнкція		0	0	0	1
2	Заборона		0	0	1	0
3			0	0	1	1
4			0	1	0	0
5			0	1	0	1
6	Додавання за модулем 2		0	1	1	0
7	Диз'юнкція		0	1	1	1
8	Стрілка Пірса		1	0	0	0
9	Еквівалентність		1	0	0	1
10			1	0	1	0
11			1	0	1	1
12			1	1	0	0
13	Імплікація		1	1	0	1
14	Штрих Шеффера		1	1	1	0
1	Одиниця		1	1	1	1

Розглянемо деякі булеві функції з позиції теорії множин. Нехай задано деяку універсальну множину V та множини . Тоді:

З теорії множин відомо, що

.

.

Аналогічні рівності виконують і для логічних функцій:

- тавтологія;

- протиріччя

Тавтологія - це завжди істинний логічний вираз; протиріччя - завжди хибний логічний вираз, які б значення не набував би .

Побудуємо діаграми Венна для операцій та (рис.4) Результат залито синім кольором.

                   

             a)                                        б)

Рис. 4 (Результат залито синім кольором).

На мові логіки цей факт виражається наступним чином::

- для стрілки Пірса:

- для штриха Шефера.

З таблиці істинності для даних функцій видно, що:

;

.

Симетрична різниця двох множин та є об'єднанням різниць, тобто тобто(рис.5.а) Результат залито синім кольором.

Еквівалентність (тотожність) визначається тими елементамита, для яких вони загальні, причому елементи, які не входять ні вні втеж вважаються еквівалентними.

(рис. 5.б). Результат залито синім кольором.

                   

             a)                                        б)

Рис.5.

Для логічних функцій

,

,

або таблиця 5.

Таблиця 5.

Симетрична різниця має декілька назв: строга диз'юнкція, виключна альтернатива, сума за модулем два. Операцію можна передати словами "або , або ".

Логічна зв'язка "або" без включення зв'язку "і".

ЗМІСТ