3.Формули алгебри висловлень
Кожна буква, що виражає елементарне висловлення, є формулою. З букв за допомогою логічних операцій можна будувати нові формули. Зв’язуючи побудовані формули знаками логічних операцій, одержуватимемо нові, більш складні формули. Формули з двох або більшої кількості букв виражають складні висловлення. При цих побудовах формули з двох або більшої кількості букв потрібно брати в дужки. Приклади:
a
b,
b
c,
a
b,
…
,
,
,
…
,
,…
Можна обчислити значення істинності висловлення для деякого набору значень елементарних висловлень. Наприклад:
|010
=
=
=
,
.
Визначимо
порядок старшинства операцій: ¯
,
,
,
,
.
Домовимось, що
=
.
Будемо використовувати це для спрощення
запису формул. Наприклад:
=
=
.
Побудуємо
таблицю істинності висловлення, що
виражається формулою
.
|
|
|
|
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
0 0 1 1 1 1 1 1 |
0 0 0 1 0 0 0 1 |
1 1 0 1 0 0 0 1 |
Побудована таблиця дає нам значення істинності складного висловлення, що виражається формулою для всіх можливих наборів значень елементарних висловлень , , . З іншого боку, формула і таблиця виражають деяку функцію від трьох змінних , , . Особливість цієї функції полягає в тому, що значення функції та Ії аргументів належать множині {0,1}. Такі функції називають бульовими.
4. Бульові функціхї та їх властивості
Означення.
Функцію
f(x1,x2,…xn),
для якої f,x1,x2,…xn
{0;1}
називають n-місною
бульовою функцією.
Властивість 1. n-місна Бульова функція визначена на 2n наборах.
Доведення. Побудуємо таблицю наборів для довільної n-місної бульової функції. Набори значень аргументів розташовуємо в порядку зростання двійкового числа. У першому рядку
x1 x2 ... xn-1 xn |
|
0 0 … 0 0 0 0 … 0 1 0 0 … 1 0 ……………...... 1 1 … 1 0 1 1 … 1 1 |
|
записано число 0, в другому – число 1, в третьому – число 2 і т.д. В останньому рядку записано двійкове число, що виражає кількість наборів, починаючи з другого. Додаючи число 1 до двійкового числа, що записано в останньому наборі, одержуємо кількість всіх наборів, записану двійковим числом. Залишається перевести число з двійкової системи числення в десяткову. Позначаючи кількість всіх наборів буквою m, маємо:
m = 11…112 + 1 = 100…002 = 1×2n+ 0×2n-1 + 0×2n-2 + … + 0×21 + 0×2 0 = 2n
Запишемо одержаний результат у формі властивості двійкових чисел:
Різних двійкових чисел, розмірність яких не перевищує n, Існує точно 2n.
Властивість
2.
Різних n-місних
бульових функцій існує точно
.
Доведення. Побудуємо таблицю значень всіх можливих n - місних бульових функцій від f1 до f k.
x1 x2 ... xn-1 xn |
|
|
|
……………… |
|
|
0 0 … 0 0 0 0 … 0 1 0 0 … 1 0 …………….. 1 1 … 1 0 1 1 … 1 1 |
0 0 0 … 0 0 |
1 0 0 ... 0 0 |
0 1 0 ... 0 0 |
..................... ......................
......................
...................... |
0 1 1 ... 1 1 |
1 1 1 ... 1 1 |
Стовпчики значень функцій розташовуємо в порядку зростання двійкового числа. В першому стовпчику записано число 0, в другому – число 1, в третьому – число 2 і т.д. В останньому стовпчику записано двійкове число, що виражає кількість стовпчиків, починаючи з другого. За відміченою вище властивістю двійкових чисел одержуємо, що кількість стовпчиків
k = 2m, де m – кількість наборів. Вище доведено, що m = 2n, тому k = .