Формули алгебри висловлень

Будемо позначати Р, Q, R, S, X, Y, Z або такими ж буквами з індексами Р₁, Р₂,..., Q₁, Q₂,..., Х₁, Х₂,..., Y₁, Y₂, змінні, замість яких можна підставляти висловлення. Такі змінні називатимемо пропозиційними змінними.

Дамо означення формули алгебри висловлень.

1. Кожна окремо взята пропозиційна змінна є формулою алгебри висловлень.

2. Якщо F₁ і F₂ - формули алгебри висловлень, то вирази , , , , також є формулами алгебри висловлень.

3. Ніяких інших формул алгебри висловлень, окрім тих, що утворюються згідно пунктів 1, 2 не існує.

Наведемо приклади формул. Згідно п. 1 означення формулами є пропозиційні змінні: Р, Q, R, S, X, Y, Z; Р₁, Р₂,..., Q₁, Q₂,..., Х₁, Х₂,..., Y₁, Y₂,.... Згідно п. 2 із цих формул одержуємо наступні формули: , , , , , , , , , . Із одержаних формул також згідно п. 2 утворимо більш складні формули: , , , , , і т. д.

Наведемо приклади виразів, які не є формулами.

, , , , , , .

Якби у виразі стояли зовнішні дужки, тобто, якби мали , то це була б формула й формулою був би вираз .

Для спрощеного запису формул використовуються наступні домовленості.

1. Зовнішні дужки у формулі опускаються.

2. Логічні операції в записі формули без дужок виконуються в наступному прядку: спочатку виконується операція Ø, операція Ù виконується перед операцією Ú, і обидві вони виконуються раніше операцій ® та «.

Наприклад, замість формули будемо писати або , замість будемо писати , або .

Підформулою формули алгебри висловлень називається довільна її частина, яка сама є формулою.

Приклад. Нехай маємо формулу . Підформулами даної формули є: , , , , , .

Рангом r(F) формули F називається число всіх символів логічних операцій, за допомогою яких із системи пропозиційних змінних утворена формула F.

Приклад. F = , r(F) = 6.