Классификация
формул

[предыдущая глава]  [оглавление]  [следующая глава]

Существует общепринятая классификация булевых формул в зависимости от вида таблицы истинности. Во-первых, как само собой разумеющееся, можно сказать о количестве перменных в формуле. Как минимум ноль переменных для формул вроде (true false), как максимум - сколько угодно. Во-вторых, имеет значение, что написано в последнем столбце. Если там одни только true, то такая формула называется "общезначимой" или "тавтологией". Иначе это будет "необщезначимая" формула. Если там одни только false, то такая формула называется "невыполнимой", иначе это будет "выполнимая" формула. "Нейтральные" формулы содержат как true, так и false.

[тавтология]:

[общезначимая формула]: Тавтологией или общезначимой формулой называется булева формула, таблица истинности которой содержит только true в правом столбце.

Пример: true false

[выполнимая формула]: Выполнимой формулой называется булева формула, таблица истинности которой содержит хотя бы одно true в правом столбце.

Пример: ~A

[невыполнимая формула]: Выполнимой формулой называется булева формула, таблица истинности которой содержит только false в правом столбце.

Пример: A & ~A

[необщезначимая формула]: Необщезначимой формулой называется булева формула, таблица истинности которой содержит хотя бы одно false в правом столбце.

Пример: A B C

[нейтральная формула]: Нейтральной формулой называется булева формула, таблица истинности которой содержит хотя бы одно false и хотя бы одно true в правом столбце.

Пример: (A B) C

Слово "тавтология" имеет несколько другой смысл вне математики. Это - утверждения, которые используют разного рода примитивные повторения. Например "масло масляное", "свет светлый", "сон - это сон", "не может быть потому, что не может быть никогда". Тавтология в математике не обязательно содержит столь примитивные повторения. Например, формула (A ~A B C D) - тавтология. Вскоре вы увидите, что математические тавтологии бывают весьма полезны.

Итак, все булевы формулы делятся на три изолированных класса - общезначимые (тавтологии), нейтральные и невыполнимые. Общезначимые и нейтральные вместе дают класс выполнимых формул. Невыполнимые и нейтральные вместе дают класс необщезначимых. Вот наглядная таблица для этой классификации:

общезначимая (тавтология)	нейтральная	невыполнимая
выполнимая
	необщезначимая
... ... ... true true ... true true	... ... ... true false ... false true	... ... ... false false ... false false

Вопросы и задания для самостоятельной работы

1. В правом столбце таблицы истинности некоторой формулы содержатся только true. Является ли эта формула выполнимой?
   Посмотреть ответ

   Да.

2. В правом столбце таблицы истинности некоторой формулы содержатся только true. Является ли эта формула необщезначимой?
   Посмотреть ответ

   Нет.

3. В правом столбце таблицы истинности некоторой формулы содержится следующая серия значений истинности: true, true, false, true, true, true, true. true. Является ли эта формула нейтральной?
   Посмотреть ответ

   Да.

4. В правом столбце таблицы истинности некоторой формулы содержится следующая серия значений истинности: false, false, false, false, false, false, false. false. Является ли эта формула нейтральной?
   Посмотреть ответ

   Нет.

5. Чем отличаются нейтральные формулы от необщезначимых?
   Посмотреть ответ

   В нейтральной в правом столбце должно быть хотя бы одно true. Для необщезначимых это необязательно.

6. Докажите, что (x ~x) & (~y y) - тавтология.
   Посмотреть ответ

   Составим таблицу истинности для этой формулы:

   x	y	(x ~x) & (~y y)
   false	false	true
   false	true	true
   true	false	true
   true	true	true

   Поскольку все ячейки в правом столбце (кроме верхней) содержат true - это по определению тавтология.