Problem Forge
Сделайте каждую переменную истинной или ложной так, чтобы в каждом дизъюнкте был хотя бы один истинный литерал.
(x₁ ∨ x₂ ∨ x₃)
∧ (¬x₁ ∨ ¬x₂)
x₁ = 1, x₂ = 0, x₃ = 0
(x₁ ∨ x₂)
∧ (¬x₁ ∨ x₂)
∧ (x₁ ∨ ¬x₂)
∧ (¬x₁ ∨ ¬x₂)
Испытания этого месяца: Задача выполнимости булевых формул (SAT)
Ступени этого месяца
| ступень | решено, все участники | отправленные ответы, все участники | состояние |
|---|---|---|---|
| 2026-11-SAT-12 | 0 | 0 | не решена |
| 2026-11-SAT-11 | 0 | 0 | не решена |
| 2026-11-SAT-10 | 0 | 0 | не решена |
| 2026-11-SAT-09 | 0 | 0 | не решена |
| 2026-11-SAT-08 | 1 | 1 | решена |
| 2026-11-SAT-07 | 1 | 1 | решена |
| 2026-11-SAT-06 | 1 | 1 | решена |
| 2026-11-SAT-05 | 1 | 1 | решена |
| 2026-11-SAT-04 | 1 | 1 | решена |
| 2026-11-SAT-03 | 1 | 1 | решена |
| 2026-11-SAT-02 | 1 | 1 | решена |
| 2026-11-SAT-01 | 1 | 1 | решена |
| 2026-11-SAT-00 | 1 | 1 | решена |
Войдите, чтобы видеть свой прогресс и открывать ступени.
Образцы
Пять файлов-образцов, к каждому прилагается ответ. Аккаунт не нужен. Чтобы проверить свой ответ, откройте файл на странице «Проверка».
- SAMPLE-SAT-01.cnf · переменных: 35, дизъюнктов: 141 · ответ
- SAMPLE-SAT-02.cnf · переменных: 32, дизъюнктов: 167 · ответ
- SAMPLE-SAT-03.cnf · переменных: 27, дизъюнктов: 137 · ответ
- SAMPLE-SAT-04.cnf · переменных: 28, дизъюнктов: 155 · ответ
- SAMPLE-SAT-05.cnf · переменных: 28, дизъюнктов: 119 · ответ
Что почитать: литература по задаче Задача выполнимости булевых формул (SAT).