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

     ГЛАВА 3. ЛОГІКА

     ВСТУП

      Будемо розглядати, так звану, формальну логіку, яка ділиться на три частини: логіку Буля, логіку висловлювань та логіку предикатів. Логіка Буля має за основу відношення еквівалентності, в основі двох інших - відношення порядку.

     3.1. БУЛЕВІ ФУНКЦІЇ

      Визначення. Функції , де , називаються функціями логіки або булевими функціями. Всю множину булевих функційзмінних позначимо .

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

   

Таблиця 1.

.

      Якщо число змінних n, то таблиця істинності містить рядків, які відповідають всім можливим комбінаціям змінних. Змінну називають істотною змінною, якщо булева функція істотно залежить від а саме:

.

      У випадку, коли

.
називають неістотною або фіктивною змінною.

      Наприклад, нехай задана таблицею істинності (табл.2):

Таблиця 2.

тут - фіктивна, - істотна змінна.