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

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

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

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

Розглянемо узгодження, які дозволяють скорочувати запис формул. Пропозиційні зв'язки упорядковуються за "силою тяжіння до формул" подібно до знаків арифметичних операцій. Всі розуміють, що вираз 1+23 позначає суму 1 і 23, а не добуток 1+2 і 3, тобто знак множення "притягується" сильніше за знак додавання. Зв'язка  вважається найсильнішою, тобто AB є скороченням від (A)B, а не від (AB). Далі за спаданням "сили тяжіння" двомісні зв'язки ідуть у такому порядку: &, , , . Отже, формулу ABC можна розглядати, як скорочений запис формули A(BC), а формулу ABCA – як A(B(CA)).