Satisfiability Problem · Problem Statement

Lesson 6

Nikolai Chukhin · Alexander S. Kulikov

Problem. Mark the satisfiable formulas.

5 points

  1. \((x_{1} \lor x_{2} \lor x_{3} \lor x_{4}) \land (x_{1} \lor \overline{x}_{2}) \land (x_{2} \lor \overline{x}_{3}) \land (x_{3} \lor \overline{x_4}) \land (x_{4} \lor \overline{x}_{1}) \land (\overline{x}_{1} \lor \overline{x}_{4})\)

  2. \((x_{1} \lor x_{2} \lor x_{3}) \land (x_{1} \lor \overline{x}_{2}) \land (\overline{x}_{2} \lor x_{3})\)

  3. \((\overline{x}_{1} \lor x_{2}) \land (\overline{x}_{1} \lor \overline{x}_{2}) \land (x_{1} \lor \overline{x}_{2}) \land (x_{1} \lor x_{2})\)

  4. \((x_{1} \lor x_{2} \lor x_{3}) \land (x_{1} \lor \overline{x}_{2}) \land (x_{2} \lor \overline{x}_{3}) \land (x_{3} \lor \overline{x}_{1}) \land (\overline{x}_{1} \lor \overline{x}_{2} \lor \overline{x}_{3})\)

  5. \((x_{1} \lor x_{2} \lor x_{3}) \land (x_{2} \lor \overline{x}_{3}) \land (x_{3} \lor \overline{x}_{1}) \land (\overline{x}_{1} \lor \overline{x}_{2} \lor \overline{x}_{3})\)

  6. \((x_{2} \lor \overline{x}_{3}) \land (x_{3}) \land (\overline{x}_{2} \lor x_{1}) \land (\overline{x}_{1})\)

  7. \((\overline{x}_{2}) \land (x_{1} \lor x_{2} \lor x_{3} \lor x_{4} \lor x_{5} \lor x_{6}) \land (\overline{x}_{5})\)