A clause is an OR of literals. Under a truth assignment, it is true if at least one literal is true. For example, (p OR NOT q) is false only when p is false and q is true. A single literal also counts as a clause.

Clause in propositional logic

A truth assignment chooses true or false for every distinct variable in a declared list. For the list p, q, the four assignments are (false, false), (false, true), (true, false), and (true, true). To add a new declared variable r, extend each assignment once with r = false and once with r = true. This gives two extensions for each old assignment, doubling the list from four to eight. A declared variable still gets a value even if it never appears in the formula (logical expression).

Truth assignments over a declared variable set

A literal is a propositional variable, such as p, or its negation, NOT p. A truth assignment gives p either the value true or false; NOT p has the opposite value.

AI Agents

A declarative statement that is either true or false

Propositions (mathematics)

James Gallicchio. Verified CNF Encodings. Carnegie Mellon Computer Science Department PhD Blog, January 9, 2026. The SAT Definitions section supplies the definitions cited here.

https://www.cs.cmu.edu/~csd-phd-blog/2026/verified-cnf-encodings/

Verified CNF Encodings by James Gallicchio

- Two parallel lines on a plane have a point in common : (FALSE)

- Ann Arbor is the capital of America : (FALSE)

- 2 + 3 + 5 = 10 : (TRUE)

Examples of propositions

Propositions and connectives are used to make compound propositions. One can make deductions and proofs drawing from the structure of propositions

Propositional Logic

Built from multiple propositions using logical operators to connect the propositions

Compound proposition

If the proposition is not a contradiction then it is satisfiable, otherwise it is not.

How can we know if a proposition is satisfiable?

If two compound propositions have the same truth table they are logically equivalent (p $$\equiv$$ q).
- ((p $$\rightarrow$$ q) $$\land$$ (q $$\rightarrow$$ p) $$\equiv$$ p $$\leftrightarrow$$ q is a tautology)

Logically Equivalent

A proposition that is always false (e.g. $$\lnot$$ p $$\land$$ p)

Contradiction (propositions)

A proposition that is always true (e.g. $$\lnot$$ p $$\lor$$ p)

Tautology (propositions)

Axioms (propositions)

A chain of logical deductions that leads to a proposition form an original (base) set of axioms.

Formal Proofs (of propositions)

A predicate is an open declarative statement containing one or more variables. It becomes a proposition when every variable is assigned an object or value from its domain or is bound by a quantifier, so that the resulting statement can be true or false.

Learn Before

Related

Learn After

Learn After

Related