   Go backward to 2.2.3 ConjunctionsGo up to 2.2 Propositional LogicGo forward to 2.2.5 Implications ### 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

• A + B, A | B, A `||` B;
• "A or B";
• `or(A, B)`.

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;
else
if (formula1.eval())
return true;
else
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   