Predicates and quantifiers
Quantifiers on the domain {a, b}
How to enter formulas
| Operation | How to enter |
|---|---|
| negation | ¬p ~p !p -p not p |
| conjunction | p ∧ q p & q p * q p ^ q p and q |
| disjunction | p ∨ q p | q p + q p or q |
| sum modulo 2 | p ⊕ q p xor q |
| implication | p → q p -> q p => q |
| equivalence | p ↔ q p <-> q p <=> q p ~ q p = q |
| constants | 0 1 |
| quantifiers | ∀x Ax forall x · ∃y Ey exists y · (∀x)(∃y) |
| predicates | P(x,y) Q(a,x), domain {a, b} |
Precedence from strongest to weakest: ¬, ∧, ∨, →, ⊕, ↔. For example, p → q ⊕ r reads as (p → q) ⊕ r, and p ∧ q ∨ r as (p ∧ q) ∨ r. Implication is right-associative: p → q → r = p → (q → r). Parentheses work as usual.
The scope of a quantifier is the nearest subformula: ∀x P(x,a) ∨ Q(x,x) means (∀x P(x,a)) ∨ Q(x,x), and x in Q(x,x) stays free. Outer parentheses do not change this: (∀x P(x,a) ∨ Q(x,x)) is the same. For the quantifier to cover the whole disjunction, put the parentheses after the variable: ∀x(P(x,a) ∨ Q(x,x)). Negating a quantifier: ¬∀x P(x,a) or ¬(∃x Q(x,x)).
A formula with free variables is a predicate, not a statement: its value cannot be shown until they are substituted or bound.
Interpretation of the predicates on the domain {a, b}: each cell holds the value of the predicate, 1 or 0. By default: P(x,y) = 1 ⇔ y = b; Q(x,y) = 1 ⇔ x = y.