Дизъюнктивный одночлен

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Дизъюнкти́вный одночле́н (элементарная дизъюнкция, дизъюнкт, максте́рм, клауза от англ. clause) — дизъюнкция литералов (переменных и их отрицаний):

,

где каждый  — литерал, то есть или .

Может принимать ложное значение только при единственном из всех возможных наборов значений переменных, входящих в него. Если содержит одновременно переменную и её отрицание, то всегда даёт истинное значение.

Примеры:

  • [1]

Всякая булева формула может быть представлена как конъюнкция дизъюнктивных одночленов (конъюнктивная нормальная форма).

Важный класс дизъюниктивных одночленов — хорновские дизъюнкты, состоящие из не более, чем одного положительного литерала.

Примечания[править | править код]

  1. Конъюнкция ассоциативна, поэтому внутри одночленов скобки не пишутся.

Ссылки[править | править код]