Boolean

True

Syntax

true

Semantics

true is true

False

Syntax

false

Semantics

false is false

Variables

Syntax

<NAME>

Semantics

x is a proposition for which we do not know the value: it can be either true or false.

Negation

Syntax

¬ <BOOL>

Semantics

If x is true, ¬x is false.
If x is false, ¬x is true.

x ¬x

false true

true false

Examples

¬true is false.
¬false is true.
¬(¬x) has the same value as x.

Conjunction

Syntax

<BOOL> ∧ <BOOL>

Semantics

If x and y are true, then x∧y is true.
Otherwise x∧y is false.

x y x ∧ y

false false false

false true false

true false false

true true true

Examples

true∧x has the same value as x.
false∧x is false.
x∧x has the same value as x.
x∧¬x is false.
x∧y has the same value as y∧x.

Disjunction

Syntax

<BOOL> ∨ <BOOL>

Semantics

If x is true or if y is true, then x∨y is true.
Otherwise x∨y is false.

x y x ∨ y

false false false

false true true

true false true

true true true

A disjunction does not necessarily indicate an alternative.

Equivalent semantics:

If x and y are both false, then x∨y is false.
Otherwise x∨y is true.

Examples

false∨x has the same value as x.
true∨x is true.
x∨x has the same value as x.
x∨¬x is true.
x∨y has the same value as y∨x.

Implication

Syntax

<BOOL> ⇒ <BOOL>

Semantics

If y is true, x⇒y is true.
If x is false and y is false, x⇒y is true.
If x is true and y is false, x⇒y is false.

x y x ⇒ y

false false true

false true true

true false false

true true true

An implication does not necessarily indicate a causality.

Equivalent Semantics

If x is true and y is false, then x⇒y is false.
Otherwise x⇒y is true.

Examples

false⇒x is true.
true⇒x has the same value as x.
x⇒true is true.
x⇒false has the same value as ¬x.
x⇒x is true.
x⇒¬x has the same value as ¬x.
x⇒y has the same value as (¬y)⇒¬x.

Equivalence

Syntax

<BOOL> ≡ <BOOL>

Semantics

If x has the same value as y, then x≡y is true.
Otherwise x≡y is false.

x y x ≡ y

false false true

false true false

true false false

true true true

Examples

false≡x has the same value as ¬x.
true≡x has the same value as x.
x≡x is true.
x≡¬x is false.
x≡y has the same value as y≡x.

Other operators

Binary Operators

x	y	x ? y
false	false	false
false	true	false
true	false	false
true	true	false

x	y	x ? y
false	false	false
false	true	false
true	false	false
true	true	true

x	y	x ? y
false	false	false
false	true	false
true	false	true
true	true	false

x	y	x ? y
false	false	false
false	true	false
true	false	true
true	true	true

x	y	x ? y
false	false	false
false	true	true
true	false	false
true	true	false

x	y	x ? y
false	false	false
false	true	true
true	false	false
true	true	true

x	y	x ? y
false	false	false
false	true	true
true	false	true
true	true	false

x	y	x ? y
false	false	false
false	true	true
true	false	true
true	true	true

x	y	x ? y
false	false	true
false	true	false
true	false	false
true	true	false

x	y	x ? y
false	false	true
false	true	false
true	false	false
true	true	true

x	y	x ? y
false	false	true
false	true	false
true	false	true
true	true	false

x	y	x ? y
false	false	true
false	true	false
true	false	true
true	true	true

x	y	x ? y
false	false	true
false	true	true
true	false	false
true	true	false

x	y	x ? y
false	false	true
false	true	true
true	false	false
true	true	true

x	y	x ? y
false	false	true
false	true	true
true	false	true
true	true	false

x	y	x ? y
false	false	true
false	true	true
true	false	true
true	true	true

 1: false
 2: x ∧ y
 3: x ∧ ¬y
 4: x
 5: ¬x ∧ y
 6: y
 7: (x ∧ ¬y) ∨ (¬x ∧ y) = x xor y = ¬(x ≡ y)
 8: x ∨ y 
 9: ¬x ∧ ¬y = ¬(x ∨ y)
10: (¬x ∧ ¬ y) ∨ (x ∧ y) = ¬(x xor y) = x ≡ y
11: ¬y
12: x ∨ ¬y = y ⇒ x
13: ¬x
14: ¬x ∨ y = x ⇒ y
15: ¬(x ∧ y) = x ⇒ ¬y = ¬x ⇒ y
16: true

N-ary operators

N.B. This proof has not been presented during the lectures and thus is not part of the programme of the course. However, the student should remember the conclusions at the end of this section.

Let f be an operator that takes n variables x1, x2,...xn. We show by induction that it can be expressed with the operators ¬, ∧, ⇒, true and false.

Base case:: If n=0, in that case f is true o false.

Inductive case:

One can write f(x1,x2,...,xn) as (x1 ⇒ f(true,x2,...,xn)) ∧ (¬x1 ⇒ f(false,x2,...,xn)):

If x1 is true, we have
(true ⇒ f(true,x2,...,xn)) ∧ (¬true ⇒ f(false,x2,...,xn))
this is equivalent to
f(true,x2,...,xn) ∧ true
this is equivalent to
f(true,x2,...,xn))
If x1 is false, we have
(false ⇒ f(true,x2,...,xn)) ∧ (¬false ⇒ f(false,x2,...,xn))
this is equivalent to
true ∧ f(false,x2,...,xn)
this is equivalent to
f(false,x2,...,xn))

f(true,x2,...,xn)) and f(false,x2,...,xn)) are operators that take n-1 variables.
Thus, from the inductive hypothesis, one can write them with ¬, ∧, ⇒, true and false.
Hence, this is also the case for f(x1,x2,...,xn).

Examples:

x1 x2 x3 f(x1,x2,x3)

false false false true

false false true true

false true false false

false true true true

true false false true

true false true false

true true false false

true true true true

We have f(x1,x2,..,xn) equivalent to (x1 ⇒ f1(x2,...,xn)) ∧(¬x1 ⇒ f2(x2,...,xn)) where

x2 x3 f1(x2,x3) f2(x2,x3)

false false true true

false true false true

true false false false

true true true true

We have f(x1,x2,x3) equivalent to (x1 ⇒ ((x2 ⇒ f3(x3)) ∧(¬x2 ⇒ f4(x3)))) ∧(¬x1 ⇒ ((x2 ⇒ f5(x3)) ∧(¬x1 ⇒ f6(x3)))) where

x3 f3(x2,x3) f4(x2,x3) f5(x2,x3) f6(x2,x3)

false false true false true

true true false true true

We have f(x1,x2,x3) equivalent to (x1 ⇒ ((x2 ⇒ x3)) ∧(¬x2 ⇒ ¬x3))) ∧(¬x1 ⇒ ((x2 ⇒ x3) ∧(¬x1 ⇒ true))).

Conclusions

The operators that we have are sufficient.
We can have only ¬, ∧ and ∨.
Also ¬, ∧ are sufficient because a∨b can be written as ¬(¬a∧¬b).
Also ¬, ∨ are sufficient because a∧b can be written as ¬(¬a∨¬b).
Also ¬, ⇒ are sufficient because a∧b can be written as ¬(a⇒¬b) e a∨b can be written as ¬a⇒b.

Evaluation of Formulae

Truth table

Formula f: ((x∧y)∨z)⇒(z⇒(x∧y))
Variables: x, y and z
Sub-formulae:

`f1:`	`x∧y`
`f2:`	`f1∨z`
`f3:`	`z⇒f1`
`f:`	`f2⇒f3`

x	y	z	f1	f2	f3	f
false	false	false	false	false	true	true
false	false	true	false	true	false	false
false	true	false	false	false	true	true
false	true	true	false	true	false	false
true	false	false	false	false	true	true
true	false	true	false	true	false	false
true	true	false	true	true	true	true
true	true	true	true	true	true	true

Satisfiability

Definition

A formula is satisfiable if there exists an evaluation of its variables that makes it true.

Examples

((x∧y)∨z)⇒(z⇒(x∧y)) is satisfiable.
x ∧¬x is not satisfiable.

Tautology

Definition

A formula is a tautology if all the evaluations of its variables make it true.

Tautology and Satisfiability

A formula f is a tautology if and only if ¬f is not satisfiable.

Examples

(x∧y)⇒(y∧x) is a tautology.
((x∧y)∨z)⇒(z⇒(x∧y)) is not a tautology.

Exercises

*A7 Give an evaluation of variables that makes the formula x⇒ (y ⇒ x) true.

*A8 Give an evaluation of variables that makes the formula x⇒ (y ⇒ x) false.

*A9 Give an evaluation of variables that makes the formula ¬y⇒ (x ∧ y) true.

*A10 Give an evaluation of variables that makes the formula ¬y⇒ (x ∧ y) false.

*A11 Give an evaluation of variables that makes the formula ((x⇒ y) ⇒ x) ⇒ x true.

*A12 Give an evaluation of variables that makes the formula ((x⇒ y) ⇒ x) ⇒ x false.

*A13 Give the truth table for the formula (x∨ ¬y) ⇒ (x ∧ y).

Monica Nesi

x	y	x ∧ y
false	false	false
false	true	false
true	false	false
true	true	true

x	y	x ∨ y
false	false	false
false	true	true
true	false	true
true	true	true

x	y	x ⇒ y
false	false	true
false	true	true
true	false	false
true	true	true

x	y	x ≡ y
false	false	true
false	true	false
true	false	false
true	true	true

x1	x2	x3	f(x1,x2,x3)
false	false	false	true
false	false	true	true
false	true	false	false
false	true	true	true
true	false	false	true
true	false	true	false
true	true	false	false
true	true	true	true

x2	x3	f1(x2,x3)	f2(x2,x3)
false	false	true	true
false	true	false	true
true	false	false	false
true	true	true	true

x3	f3(x2,x3)	f4(x2,x3)	f5(x2,x3)	f6(x2,x3)
false	false	true	false	true
true	true	false	true	true