визначення: Булева формула є в 3CNF, якщо вона має форму C1 ∧ C2 ∧···∧ Ck, де кожен Ci є ∨ з трьох або менше літералів. Визначення: Булева формула є у формі 3SAT, якщо вона у формі 3CNF, а також SATisfiable. БІЛЛ- Виконайте приклади та контрприклади на дошці.

2.1 Проблема 3-CNF-SAT Булева формула має кон’юнктивну нормальну форму, або CNF, якщо вона виражається як кон’юнкції (за допомогою І) речень, кожне з яких є диз’юнкцією (за допомогою АБО) одного або кількох літералів. Булева формула має 3-кон’юнктивну нормальну форму, або 3-CNF-SAT, якщо кожне речення має рівно три різні літерали.

Нарешті, є формула "3CNF". формула в CNF з додатковим обмеженням, що кожне речення має не більше трьох літералів. Отже, наприклад, наступна формула 3CNF: (a∨¬b∨¬c)∧(¬a∨b∨c)∧(¬a∨¬c)

3SAT, або булева проблема виконуваності, є завдання, яке запитує, який найшвидший алгоритм для визначення заданої формули в булевій алгебрі (з невідомою кількістю змінних), чи є вона задовільною, тобто чи існує деяка комбінація (двійкових) значень змінних, яка дасть 1.

SAT — це NP-повна проблема. CNFSAT — це проблема SAT, але обмежена пропозиційними формулами в CNF. Нагадаємо, що CNF-еквівалент загальної пропозиційної формули може бути набагато довшим, тому складність SAT і CNFSAT не однакова. CNFSAT також є NP-повним.

Що таке 3SAT? визначення: Булева формула є в 3CNF, якщо вона має форму C1 ∧ C2 ∧···∧ Ck, де кожен Ci є ∨ з трьох або менше літералів. Визначення: Булева формула є у формі 3SAT, якщо вона у формі 3CNF, а також SATisfiable. БІЛЛ- Виконайте приклади та контрприклади на дошці.