WikiSort.ru - Не сортированное

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

${\displaystyle l_{1}\lor \cdots \lor l_{n}}$ ,

где каждый ${\displaystyle l_{i}}$  — литерал, то есть ${\displaystyle l_{i}=X}$ или ${\displaystyle l_{i}=\neg X}$ .

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

Примеры:

• ${\displaystyle \neg X_{1}\lor X_{2}\lor X_{3}}$
• ${\displaystyle X_{2}\lor X_{2}}$
• ${\displaystyle \neg X_{2}\lor X_{1}\lor \neg X_{4}\lor \neg X_{1}\lor X_{4}\lor \neg X_{2}}$ ^[1]

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

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

Примечания

Ссылки

• Логика высказываний

Для улучшения этой статьи по математике желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).