previous up next
Go backward to 2.2.3 Conjunctions
Go up to 2.2 Propositional Logic
Go forward to 2.2.5 Implications
RISC-Linz logo

2.2.4 Disjunctions

If A and B are formulas, then
A \/ B
is a formula.

Alternative Forms  A disjunction of A and B may also appear in other syntactic forms, e.g. as

The last form is the input syntax for the Logic Evaluator.

Definition 7 (Semantics of Disjunction) Let A and B be formulas. The meaning of A \/ B is defined by the following truth table:
A B A \/ B
false false false
false true true
true false true
true true true

In other words, A \/ B is false if and only if both A and B are false.

Since A \/ B is also true if both A and B are true, it must not be read as "either A or B" (which would indicate otherwise). Such an "exclusive or" connective needs an extra definition (which is given at the end of this section).

Operational Interpretation  In the Logic Evaluator, a disjunction is represented by an object of the Java type

public final class Or implements Formula
  private Formula formula0;
  private Formula formula1;

  public Or(Formula _formula0, Formula _formula1)
    formula0 = _formula0;
    formula1 = _formula1;

  public boolean eval() throws EvalException
    if (formula0.eval())
      return true;
      if (formula1.eval())
        return true;
        return false;
The Java expression (new Or(A, B)).eval() computes the truth value of A \/ B. As one can see, if A evaluates to true, the result is immediately true, i.e., the truth value of B does not matter any more. Only if A evaluates to false, also B is evaluated; the result is false only if both formulas are false.

From Definition Semantics of Disjunction, we can deduce the following properties of disjunctions.

Proposition 6 (Disjunctive Laws) Disjunction is commutative, i.e., for all formulas A and B, we have
A \/ B iff B \/ A.
Disjunction is also associative, i.e., for all formulas A, B, and C, we have
A \/ (B \/ C) iff (A \/ B) \/ C

We have an important duality between conjunctions and disjunctions expressed by the following law.

Proposition 7 (De Morgan's Laws) For all formulas A and B, the following holds:
~(A /\  B) iff ~A \/ ~B,
~(A \/ B) iff ~A /\  ~B

Consequence  From above laws, we have

A \/ B iff ~(~A /\  ~B).
The disjunction A \/ B is therefore frequently defined just as a syntactic abbreviation of ~(~A /\  ~B).

Convention  Because of associativity, it does not matter in which particular way parentheses are placed in nestings of disjunctive formulas. We will therefore write A \/ B \/ C instead of A \/ (B \/ C) respectively (A \/ B) \/ C and, in general,

A0 \/ A1 \/ ... \/ An-1
for conjunctions of n formulas (for every n). Also the Logic Evaluator allows disjunctions
or(A0, A1, ..., An-1)
of an arbitrary number of formulas.

Exclusive Disjunction  Finally we give the definition of the "exclusive or" connective mentioned above.

Definition 8 (Exclusive Disjunction) If A and B are formulas, then also
(A xor B)
is a formula, the  exclusive disjunction (Ausschließende Oder-Verknüpfung) of A and B, The meaning of this formula is defined by the following truth table:
A B A xor B
false false false
false true true
true false true
true true false
In other words, A xor B is true, if and only if exactly one of A or B is true. 

We then have the following relationship between both kinds of disjunctions.

Proposition 8 (Inclusive and Exclusive Disjunction) For all formulas A and B, we have
(A xor B) iff (A /\  ~B) \/ (~A /\  B). 

Because of this law, the formula (A xor B) is frequently just defined as a syntactic abbreviation for (A /\  ~B) \/ (~A /\  B).

Author: Wolfgang Schreiner
Last Modification: October 4, 1999

previous up next