Алгебра висловлень

З пропозиційних змінних і елементарних висловлень за допомогою операцій і дужок будуються пропозиційні формули або просто формули алгебри висловлень за такими індуктивними правилами:

1) всі пропозиційні змінні та елементарні висловлення є формулами;

2) якщо A і B - формули, то вирази (AB), (AB), (A), (AB) також є формулами;

3) інших формул, ніж побудовані за правилами 1) і 2), немає.

Традиційно формули алгебри висловлень позначають великими готичними літерами, але для зручності позначатимемо їх великими латинськими літерами.Кожна формула A зображує форму або схему складеного висловлення: вона перетворюється у висловлення якщо замість її пропозиційних змінних підставити будь-які висловлення. Оскільки кожне з підставлених висловлень має значення 0 або 1, то послідовно обчислюючи значення всіх підформул формули A, одержимо значення формули A на цьому наборі висловлень, яке дорівнюватиме 0 або 1. Підставляючи у формулу A замість її пропозиційних змінних інший набір висловлень, аналогічним чином обчислимо нове значення формули A і т.д. Оскільки кожне з висловлень набору повністю характеризується своїм значенням (істинно або хибно, тобто 1 або 0), то замість пропозиційних змінних у формулу можна підставляти не самі висловлення, а їхні значення - 1 або 0.

Нехай p1,p2,...,pn - це всі пропозиційні змінні, що входять у формулу A; будемо позначати цей факт A(p1,p2,...,pn). Формулі A(p1,p2,...,pn) поставимо у відповідність функцію f (p1,p2,...,pn), що означена на множині Bn (B={0,1}) і приймає значення у множині B, тобто функцію типу BnB. Значення функції f на наборі значень a1,a2,...,an її змінних p1,p2,...,pn дорівнює значенню формули A(p1,p2,...,pn) при підстановці в неї замість пропозиційних змінних p1,p2,...,pn значень a1,a2,...,an відповідно.

Зауважимо, що кількість елементів в області визначення функції f дорівнює 2n, тобто |Pr1f |=2n.

Функцію f називають функцією істинності для формули A або відповідного складеного висловлення. Для функції істинності може бути побудована так звана таблиця істинності цієї функції (див.таблицю 3).

Таблиця 3

p1 p2 ...... pn-1 pnf (p1,p2,...,pn-1,pn)

0 0 ... 0 0

0 0 ... 0 1

0 0 ... 1 0

0 0 ... 1 1

.........................

1 1 ... 1 0

1 1 ... 1 1 f (0,0,...,0,0)

f (0,0,...,0,1)

f (0,0,...,1,0)

f (0,0,...,1,1)