Елементи логіки

Означення. Висловлення вигляду "A тоді й тільки тоді, коли B" записується як AB і називається еквівалентністю висловлень A і B. Вона істинна, коли значення висловлень A і B збігаються. Якщо ж вони різні, то еквівалентність хибна. Наприклад, висловлення "Якщо 2*2=5, то Сонце обертається навколо Землі" є істинним. Еквівалентність часто позначають не знаком "", а знаком "".

Зауважимо, що запис AB читається також як "B є необхідною і достатньою умовою для A", а також як "Якщо A, то B, і якщо B, то A". Заперечення еквівалентності (AB) читається як "Або A, або B". Складений сполучник "або …, або …" інколи називається "виключне або". Підкреслимо, що диз'юнкція AB відрізняється від заперечення еквівалентності (AB).

Означення. Висловлення записують у вигляді формул за такими правилами:

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

2) якщо X і Y – формули, то (X), (XY), (XY), (XY), (XY) також є формулами;

3) інших формул немає.

За цими правилами, наприклад, (AB), ((AB)&((AB))) є формулами, ABC – ні. Далі ми розглянемо узгодження, які дозволяють скорочувати запис формул. Зокрема, ці узгодження дозволяють розглядати ABC як формулу. Тут лише зауважимо, що можна не записувати зовнішні дужки формул, наприклад, писати XY.

2. Таблиці істинності формул і закониФормула є словом, тобто послідовністю символів – імен пропозиційних змінних, знаків зв'язок і дужок. Це слово має певну структуру, обмежену правилами побудови формул. Підслово цього слова, яке є формулою, називається підформулою. Наприклад, у формулі ((AB)&((AB))) є підформули A, B, (AB), (AB), ((AB)).

Формула, що позначає висловлення, складене з інших, простіших, має значення, яке залежить від значень цих складових висловлень. Для його обчислення спочатку кожній пропозиційній змінній ставиться у відповідність одне зі значень "хибність" чи "істина" (0 чи 1). Далі за означеннями пропозиційних зв'язок обчислюється значення підформул, починаючи від найпростіших і закінчуючи всією формулою. Значення формул з однією двомісною зв'язкою при всіх можливих наборах значень змінних наведено в таблиці:

A BABABABAB

0 00011

0 10110

1 00100

1 11111

Обчислимо значення формули, наприклад, (AB)&(BA) при всіх можливих наборах значень змінних A і B. Обчислення подамо такою таблицею:

A BABBA(AB)&(BA)

0 0111

0 1100

1 0010

1 1111