Math 2.0

definition

Conjunctive normal form

Definition

A formula of propositional logic is in conjunctive normal form if it is a conjunction of one or more disjunctions of one or more literals. Each disjunction is a clause.

Remarks

Example: (p∨¬q)∧(q∨r)∧¬p(p \vee \neg q) \wedge (q \vee r) \wedge \neg p is in conjunctive normal form. Every formula is logically equivalent to a formula in conjunctive normal form. Negate the formula, put the negation in disjunctive normal form, and use the De Morgan laws. The satisfiability problem for formulas in conjunctive normal form with clauses of 33 literals is NP-complete.

Explanations

L1 human

A formula in conjunctive normal form is an and of ors of simple conditions. Each clause is a constraint, and the formula is true when all constraints hold.

What this node needs for W2
  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a node is. They do not measure its truth.

What this needs

To read this node, read these 2 nodes in this order. The foundations come first, and the list ends with this node.

Disjunctive normal form, definition, no evidence levelDisjunctive normal fo…definitionConjunctive normal form, definition, no evidence levelConjunctive normal fo…definition
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Disjunctive normal form definition
  2. Conjunctive normal form definition

Sources

  1. Web https://en.wikipedia.org/wiki/Conjunctive_normal_form, Definition

What links here

No node links to this node yet.